# Expressing a quantum state as a polynomial

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.

• What do you mean by "size of a polynomial"? Do you meant the degree? Apr 22 at 2:46
• 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. Apr 22 at 7:38

## 1 Answer

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.

• 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. Apr 22 at 9:35
• 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. Apr 22 at 12:41
• @DorianoBrogioli please read the link I provided in my answer. The polynomial above always gives the lowest degree. Apr 22 at 15:37