While answering this question, I stumbled upon the fact that the only proof I knew of the optimality of Grover's algorithm (that is, Zalka's one) uses a phase oracle. I know that a phase oracle can be built from a standard oracle, but we would need the converse to use this proof in the case of a standard oracle.

The converse is almost true, in that it is possible to build it using a controlled version of the phase oracle, which is not in the problem's statement. Has there been a proof of the optimality of Grover's algorithm in the Standard oracle case? Or is there a reduction from the phase oracle to the standard one without using a controlled version?


1 Answer 1


I don't know how to reduce a standard oracle to a phase oracle, but the proof can actually be generalized to the standard oracle model, with a little more work. You can check out the proof on my blog for better math typesetting.

Notations and definitions

Let $S=\{0,1\}^n$ be the search space, and $R\subset S$ be the solutions, we define $N=|S|,M=|R|$. Let $f_R:S\to\{0,1\}$ be a function that checks whether a given solution is valid, i.e. $f_R(x)=1\iff x\in R$. To find a solution, we are allowed to query $f_R$ as an oracle in our algorithm design. For a quantum algorithm, we are given an "oracle operation" $O_R$ such that $O_R|x\rangle|b\rangle=|x\rangle|b\oplus f_R(x)\rangle$

First, we introduce a lemma to bound the sum of vector norms:

Lemma 1

Let $\{\alpha_i\}$ and $\{\beta_i\}$ be some finite sequence of vectors in a inner product space. Then we have $$\begin{align} \sum_i\|\alpha_i+\beta_i\|^2&\le\left(\sqrt{\sum_i\|\alpha_i\|^2}+\sqrt{\sum_i\|\beta_i\|^2}\right)^2\\ \sum_i\|\alpha_i+\beta_i\|^2&\ge\left(\sqrt{\sum_i\|\alpha_i\|^2}-\sqrt{\sum_i\|\beta_i\|^2}\right)^2 \end{align}$$

Proof of Lemma 1

By the triangle inequality, we have

$$\begin{align} \sum_i\|\alpha_i+\beta_i\|^2 &\le\sum_i(\|\alpha_i\|+\|\beta_i\|)^2\\ &=\sum_i\|\alpha_i\|^2+\sum_i\|\beta_i\|^2+2\sum_i\|\alpha_i\|\|\beta_i\| \end{align}$$

Then we apply Cauchy-Schwarz inequality on the third term:

$$\begin{align} \sum_i\|\alpha_i+\beta_i\|^2 &\le\sum_i\|\alpha_i\|^2+\sum_i\|\beta_i\|^2+2\sqrt{\sum_i\|\alpha_i\|^2}\sqrt{\sum_i\|\beta_i\|^2}\\ &=\left(\sqrt{\sum_i\|\alpha_i\|^2}+\sqrt{\sum_i\|\beta_i\|^2}\right)^2 \end{align}$$

The other side is similar:

$$\begin{align} \sum_i\|\alpha_i+\beta_i\|^2 &\ge\sum_i(\|\alpha_i\|-\|\beta_i\|)^2\\ &=\sum_i\|\alpha_i\|^2+\sum_i\|\beta_i\|^2-2\sum_i\|\alpha_i\|\|\beta_i\|\\ &\ge\sum_i\|\alpha_i\|^2+\sum_i\|\beta_i\|^2-2\sqrt{\sum_i\|\alpha_i\|^2}\sqrt{\sum_i\|\beta_i\|^2}\\ &=\left(\sqrt{\sum_i\|\alpha_i\|^2}-\sqrt{\sum_i\|\beta_i\|^2}\right)^2 \end{align}$$

Now we are going to prove the main result:

Theorem 1

All quantum algorithms that find a solution with $O(1)$ probability requires $\Omega\left(\sqrt{\frac NM}\right)$ oracle queries.

Proof of Theorem 1

Without loss of generality, we may assume that the quantum algorithm uses $m$ qubits for some $m>n$. It applies $W$ unitary operations, interleaved with $W$ oracle operations. More specifically, let $|\psi\rangle$ be the initial state of the register, we compute $|\psi_W^R\rangle:=U_WO_RU_{W-1}O_R\cdots U_1O_R|\psi\rangle$, and then measure the first $n$ qubits of $|\psi_W^R\rangle$ as an answer. We may assume that the oracle queries are done on the first $n$ qubits, and the result is XORed with the $(n+1)$'th qubit. (Otherwise we can "swap" the queried qubits with the first $(n+1)$ qubits, and then swap them back after the query, as there is no limit on the unitary operations we apply.)

We define $$\begin{align} |\psi_k^R\rangle&:=U_kO_RU_{k-1}O_R\cdots U_1O_R|\psi\rangle\\ |\psi_k\rangle&:=U_kU_{k-1}\cdots U_1|\psi\rangle\\ D_k&:=\sum_{R\subset S}\left\|\psi_k^R-\psi_k\right\|^2 \end{align}$$

Upperbound of $D_W$

For the first half of the proof, we upperbound $D_k$ by $4k^2\binom{N-1}{M-1}$ using induction:

$$\begin{align} D_{k+1} &=\sum_{R\subset S}\left\|U_{k+1}O_R\psi_k^R-U_{k+1}\psi_k\right\|^2\\ &=\sum_{R\subset S}\left\|O_R\psi_k^R-\psi_k\right\|^2\\ &=\sum_{R\subset S}\left\|O_R(\psi_k^R-\psi_k)+(O_R-I)\psi_k\right\|^2\\ \end{align}$$

Notice that $O_R$ and $I$ can be written as $$\begin{align} O_R&=\sum_{x\notin R}|x\rangle\langle x|\otimes I\otimes I+\sum_{x\in R}|x\rangle\langle x|\otimes X\otimes I\\ I&=\sum_{x\notin R}|x\rangle\langle x|\otimes I\otimes I+\sum_{x\in R}|x\rangle\langle x|\otimes I\otimes I \end{align}$$

Therefore we have $$\begin{align} D_{k+1} &=\sum_{R\subset S}\left\|O_R(\psi_k^R-\psi_k)+\left(\sum_{x\in R}|x\rangle\langle x|\otimes(X-I)\otimes I\right)\psi_k\right\|^2 \end{align}$$

To apply Lemma 1, we upper bound the first term:

$$\begin{align} \sum_{R\subset S}\left\|O_R(\psi_k^R-\psi_k)\right\|^2 &=\sum_{R\subset S}\left\|(\psi_k^R-\psi_k)\right\|^2\\ &=D_k\\ \end{align}$$

and the second term:

$$\begin{align} &\sum_{R\subset S}\left\|\left(\sum_{x\in R}|x\rangle\langle x|\otimes(X-I)\otimes I\right)\psi_k\right\|^2\\ &=\sum_{R\subset S}\sum_{x\in R}\langle\psi_k|(|x\rangle\langle x|\otimes(2I-2X)\otimes I)|\psi_k\rangle\\ &=2\binom{N-1}{M-1}\sum_{x\in S}\langle\psi_k|(|x\rangle\langle x|\otimes(I-X))|\psi_k\rangle\\ &=2\binom{N-1}{M-1}(\langle\psi_k|\psi_k\rangle-\langle\psi_k|I\otimes X\otimes I|\psi_k\rangle)\\ &\le4\binom{N-1}{M-1} \end{align}$$

By induction, $D_k\le4k^2\binom{N-1}{M-1}$, and with Lemma 1 we conclude that $$\begin{align} D_{k+1} &\le\left(2k\sqrt{\binom{N-1}{M-1}}+2\sqrt{\binom{N-1}{M-1}}\right)^2\\ &=4(k+1)^2\binom{N-1}{M-1} \end{align}$$

Lowerbound of $D_W$

For the second half of the proof, we lowerbound $D_k$ by $\Omega(1)\binom NM$. First, we define the projection matrix onto the subspace spanned by the solutions $R$:

$$\begin{align} P_R:=\sum_{x\in R}|x\rangle\langle x|\otimes I \end{align}$$

Then again, we split $D_W$ into two parts, and try to apply Lemma 1:

$$\begin{align} D_W &=\sum_{R\subset S}\left\|(I-P_R)\psi_W^R+(P_R\psi_W^R-\psi_W)\right\|^2\\ \end{align}$$

For the first term, we have $\langle\psi_W^R|(I-P_R)|\psi_W^R\rangle\le\frac12$, as we may assume that the probability of success is no less than $\frac12$ for this quantum algorithm. Thus we write down

$$\begin{align} \sum_{R\subset S}\left\|(I-P_R)\psi_W^R\right\|^2\le\frac12\binom NM \end{align}$$

For the second term, we have

$$\begin{align} \left\|P_R\psi_W^R-\psi_W\right\|^2 &=1+\langle\psi_W^R|P_R|\psi_W^R\rangle-2\Re\langle\psi_W|P_R|\psi_W^R\rangle\\ &\ge\frac32-2\|P_R\psi_W\|^2\\ &=\frac32-2\langle\psi_W|P_R|\psi_W\rangle\\ \end{align}$$

Summing over $R$,

$$\begin{align} \sum_{R\subset S}\left\|P_R\psi_W^R-\psi_W\right\|^2 &\ge\frac32\binom NM-2\sum_{R\subset S}\sum_{x\in R}\langle\psi_W|(|x\rangle\langle x|\otimes I)|\psi_W\rangle\\ &=\frac32\binom NM-2\binom{N-1}{M-1}\sum_{x\in S}\langle\psi_W|(|x\rangle\langle x|\otimes I)|\psi_W\rangle\\ &=\frac32\binom NM-2\binom{N-1}{M-1}\\ &=\left(\frac32-2\frac MN\right)\binom NM \end{align}$$

We may assume that $\frac MN\le\frac14$. (In fact, for $\frac MN>\frac 14$, the problem is trivial as one only needs less than 4 trials on average using a naive algorithm.) We then apply Lemma 1:

$$\begin{align} D_W &\ge\left(\sqrt{\frac32-2\frac MN}-\sqrt{\frac12}\right)^2\binom NM\\ &\ge\left(\frac32-\sqrt2\right)\binom NM \end{align}$$

Combining the lowerbound and upperbound of $D_W$, we have

$$\begin{align} &\left(\frac32-\sqrt2\right)\binom NM\le D_W\le4W^2\binom{N-1}{M-1}\\ &\implies W\ge\frac{2-\sqrt2}4\sqrt{\frac NM}\\ &\implies W\ge\Omega\left(\sqrt{\frac NM}\right) \end{align}$$

Which completes our proof.


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.