Let us consider the state $\left|\psi\right>$ obtained by applying $m$ 1- and 2-qubit gates to $n$ qubits, starting from the state $\left|0,0,\dots\right>$. Let us express it as: $$ \left|\psi\right> = \sum_{b_1, b_2, \dots} f(b_1, b_2, \dots) \left| b_1, b_2, \dots \right>$$ where the $b_i$ take the values 0 or 1.

It is trivial to see that there is a polynomial $p(b_1, b_2, \dots)$ (something like $b_2 b_4 + 3 b_3^2 b_6 +\dots$) that takes the same values of $f(b_1, b_2, \dots)$ when $b_i$ take the values 0 or 1. This is actually true for whatever $f$, it depends on the discrete values of the $b_i$. Please let me know if I am wrong.

The polynomial obtained with the trivial method is very large but there could be smaller representations. Here, I am asking if there is a know scaling between the the size of the polynomial $p$ (with whatever representation) and the numbers $n$ and $m$. For example, a lower limit, or some method to get a small $p$.

ADDED: the size of the polynomial can be defined in various ways. For example, as the length of the string encoding the polynomial (with a reasonable encoding). Another example: the sum of the degrees of the monomials. The number of monomials or the degree could also be considered.

The question is not about the time needed to calculate $p$, but only about its size.

  • $\begingroup$ What do you mean by "size of a polynomial"? Do you meant the degree? $\endgroup$
    – MonteNero
    Apr 22 at 2:46
  • $\begingroup$ We can characterize the size of a polynomial in various ways. For example, give an encoding as a string and use the length of the string as size. Or the sum of the degrees of all the monomials. I would be happy to see any kind of characterization. The number of monomials, or the degree, could be interesting as well. $\endgroup$ Apr 22 at 7:38

1 Answer 1


I assume $f$ is real because, in your example, the polynomial you gave appears to be real.

The dependence on the number of qubits $n$ is pretty straightforward to see. Once you see that, you realize that $m$ doesn't contribute meaningfully to a polynomial degree.

Briefly, given any function $f:\{0,1\}^n \rightarrow \mathbb{R}$, there exists a polynomial $p(x_1, \ldots, x_n)$ of a degree at most $n$ such that $f(x_1, \ldots, x_n)=p(x_1, \ldots, x_n)$ for all $x_i \in \{0,1\}$. This result follows directly from Lagrange interpolation polynomials. So, the scaling of the degree of a polynomial is linear in the number of qubits, i.e. $\deg{p} = O(n)$.

We can even find a very compact expression of the polynomial by following the Lagrange polynomials' construction in the link above. The polynomial is: $$p(x_1, x_2,\ldots, x_n) = \sum_{b \in \{0,1\}^n}f(b)L_b(x_1, \ldots, x_n), \tag{1}$$ where $L_b(x_1, \ldots, x_n)$ is a multivariate Lagrange polynomial of degree at most $n$ such that for $b \in \{0,1\}^n$ we have: $$L_b(x_1, \ldots, x_n)=\begin{cases} 1, \textrm{ if } x_i = b_i, \textrm{ for all } i, \\ 0, \textrm{ otherwise}. \end{cases} $$ The basis polynomial $L_b(x_1, \ldots, x_n)$ is a product of $n$ univariate linear polynomials: $$L_b(x_1, \ldots, x_n)=\prod^n_{i=1}( b_i x_i +(1-b_i)(1-x_i)).$$ If it is unclear how this is derived, I suggest following the construction of Lagrange polynomials in the link above and considering a special case where $x$ is a binary variable. I hope that, on the intuitive level, (1) makes sense. Basically, we have a sum over exponentially many $n$-degree polynomials $L_b$ where each polynomial acts similarly to the indicator or Kronecker delta function.

Note that we have the explicit equation of a polynomial, which only requires the knowledge of the values of $f(b)$ for $b \in \{0,1\}^n$, but it doesn't require knowledge of $m$. So, you can have as many gates as you want, but the scaling of the degree will still be linear in $n$, i.e. $O(n)$.

Analyzing (1), you can always find the lowest degree. For example, assume $|\psi\rangle$ is a uniform superposition of all states. Then (1) simplifies to: $$p(x_1, \ldots, x_n) = \frac{1}{\sqrt{2^n}}\sum_{b \in \{0,1\}^n} L_b(x_1, \ldots, x_n) = \frac{1}{\sqrt{2^n}}.$$ Recall that $L_b$ add up to 1 because only one term evaluates to 1, and the rest are 0. We conclude that the lowest degree we can get is 0 for the choice of $|\psi\rangle$ above.

  • 1
    $\begingroup$ The answer is for sure correct, but I still have a question: is there a proof that the method gives the lowest degree? The example with uniform superposition works, but, is it a general fact? More in general, rather than the degree, I was asking about the "size" of the polynomial, see the changes to the question for a clarification about the definition of size. $\endgroup$ Apr 22 at 9:35
  • $\begingroup$ Looks like the classical computation problem of minimization of Boolean functions. Also a circuit design optimization problem in electronics, of course. You have algorithms to approach the optimum (simple ones like en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm and more complicated ones). But in that case there is no easy way to find the guaranteed optimum solution, as far as I know. $\endgroup$ Apr 22 at 12:41
  • $\begingroup$ @DorianoBrogioli please read the link I provided in my answer. The polynomial above always gives the lowest degree. $\endgroup$
    – MonteNero
    Apr 22 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.