Consider a quantum query algorithm that takes as input $x \in \{0,1\}^n$. Denote by $X_i$ the variable that evaluates to $1$ on input $x$ if the $i$-th bit of $x$ is 1, and $-1$ otherwise. Let $X_{\vec{i}}$ be the product of the variables whose indexes are in $\vec{i}$ (for instance : $X_{\overrightarrow{4,1,3}} = X_4X_1X_3$).

The polynomial method relies on the fact that the state $|\phi_t(x)\rangle$ of the algorithm on input $x$ at time $t$ can be written as $|\phi_t(x)\rangle = \sum_u P_u(x) |u\rangle$, where $u$ ranges over all the basis states and the $P_u$'s are multilinear polynomials of degree at most $t$ in the $n$ variables $X_1, \dots, X_n$. In other words, there exist complex numbers $(a_{u,\vec{i}})$ such that for all $x$:

$$|\phi_t(x)\rangle = \sum_{u,\vec{i}} a_{u,\vec{i}} \cdot X_{\vec{i}} \ |u\rangle$$

where $P_u(X) = \sum_{\vec{i}} a_{u,\vec{i}} \cdot X_{\vec{i}}$ (for the sake of simplicity, assume from now on that the $a_{u,\vec{i}}$'s are just real numbers).

Finally, define the L2-norm $||P||_2$ of a polynomial to be the sum of the squares of its coefficients, i.e. $||P_u||_2 = \sum_{\vec{i}} a_{u,\vec{i}}^2$.

My question relies on the following observation:

$$\mathbb{E}_x (\phi_t(x)^2) = 1 = \sum_{u,\vec{i}} a_{u,\vec{i}}^2 = \sum_u ||P_u||_2$$

Indeed, $\phi_t(x)^2 = 1$ for all $x$ (recall that we took real numbers instead of complex ones, so this expresses the fact that $|\phi_t(x)\rangle$ must have norm one). And $\mathbb{E}_x (X_{\vec{i}}) = 0$ whenever $X_{\vec{i}}$ is not the constant 1.

Thus the $a_{u,\vec{i}}$'s must sum to one! In fact, I derived this equality from this paper: https://arxiv.org/pdf/1411.5729v1.pdf (p32), but I did not find any other result in quantum computing that uses it. For instance, is there a connection with the acceptance probability of the algorithm (if $u_a$ is the accepting state, can we relate the acceptance probability with $||P_{u_a}||_2$?



Your Answer

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

Browse other questions tagged or ask your own question.