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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.