# Has the optimality of Grover's algorithm be proven in the standard oracle case?

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?

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.