[Note] Quantum Computation and Quantum Information - Chapter 6: Quantum search algorithms

上課筆記，原文書:

Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang

6.1 The quantum search algorithm

• Search marked items out of $N$ items
  • Classical: $\Theta(N)$ operations
  • Quantum: $O(\sqrt N)$ operations, $\Omega(\sqrt N)$ matching lower bound

6.1.1 The oracle

• Use a blackbox $\tilde{O_f}$ to store information about a function $f: \{0, 1\}^k\to\{0,1\}$.
  • $\tilde{O_f}\vert x\rangle\vert q\rangle = \vert x\rangle\vert f(x)\oplus q\rangle$
  • In the search problem, we think $f(x)=1$ as an marked item, i.e. we want to find an $x$ s.t. $f(x)=1$
• Quantum query complexity: number of $\tilde{O_f}$ you need to put in your circuit to solve the problem.
• Assume $N$ items (indexed $\{0, 1,\dots, N-1\}$), exactly $M$ marked items (i.e. solutions) $1\le M \le N$.
  • find any marked item: $O(\sqrt{\frac{N}{M}})$
  • find all marked item: $\Theta(\sqrt{MN})$
  • find first marked item: $O(\sqrt{N})$

Phase version of quantum oracle

$$\begin{align*} \tilde{O_f}\vert x\rangle\vert -\rangle &= \tilde{O_f}\vert x\rangle \frac{1}{\sqrt 2}(\vert 0\rangle-\vert 1\rangle)\\ &= \begin{cases} \vert x\rangle\vert -\rangle, &f(x)=0\\ -\vert x\rangle\vert -\rangle, & f(x)=1 \end{cases}\\ &= (-1)^{f(x)}\vert x\rangle\vert -\rangle \end{align*}$$

• Using one $\tilde{O_f}$, we can simulate one $O_f$ s.t. $$O_f\vert x\rangle=(-1)^{f(x)}\vert x\rangle$$
• We can also simulate $\tilde{O_f}$ with one controlled-$O_f$: $$CO_f\vert x\rangle\vert y\rangle=(-1)^{f(x)}\vert x\rangle\vert y\rangle$$
  • $y$ is the control qubit
  • $\tilde{O_f}$ and $CO_f$ is equivalant

6.1.2 The procedure

• $G$ is the grover iteration, which composed of 4 steps:

  1. Apply Oracle $O_f$
  2. Apply $H^{\otimes n}$
  3. Apply an conditioned phase shift $(2\vert 0\rangle\langle 0\vert -I)$ (only $\vert 0\rangle$ get an extra phase of $-1$) $$\vert x\rangle \to -(-1)^{\delta_{x0}}\vert x\rangle$$
  4. Apply $H^{\otimes n}$
     

• Step 3 is a reflection about $\vert 0\rangle$:

  $$\vert x\rangle \to (2\vert 0\rangle\langle 0\vert-I)\vert x \rangle$$
• Step 2 3 4 together is a reflection around $\vert \psi\rangle$ $$\begin{align*} \vert \psi \rangle \equiv \frac{1}{\sqrt N}\sum^{N-1}_{x=0}\vert x\rangle&=H^{\otimes n}\vert 0\rangle\\ H^{\otimes n}(2\vert 0\rangle\langle 0\vert - I)H^{\otimes n} &= 2\vert \psi\rangle\langle\psi\vert - (H^{\otimes n})^2\\ &= 2\vert \psi\rangle\langle \psi\vert -I \end{align*}$$
• Step 2 3 4 no oracle calls, can be implemented efficiently $O(n)$ gates
• $G=(2\vert \psi\rangle\langle\psi\vert -I)O_f$

6.1.3 Geometric visualization

Suppose there are $M$ marked items (solutions), let $\vert \beta\rangle$ be the superposition of all marked items, $\vert \alpha\rangle$ be the superposition of non-marked items

$$\begin{align*} \vert \beta\rangle &\equiv \frac{1}{\sqrt M} \sum_{x:f(x)=1} \vert x\rangle\\ \vert \alpha\rangle &\equiv \frac{1}{\sqrt {N-M}}\sum{x:f(x)=0} \vert x\rangle \end{align*}$$ $$\Rightarrow \vert \psi\rangle = \sqrt{\frac{N-M}{N}}\vert \alpha\rangle + \sqrt{\frac{M}{N}}\vert \beta\rangle$$

• Consider the 2D space spanned by $\vert \psi\rangle$ and $\vert \beta\rangle$
  • Oracle operation $O_f$ performs a reflection about the vector $\vert \alpha\rangle$ in the plane defined by $\vert \alpha\rangle$ and $\vert \beta\rangle$ $$O_f(a\vert \alpha\rangle+b\vert \beta\rangle)=a\vert\alpha\rangle-b\vert \beta\rangle$$
  • $(2\vert \psi\rangle\langle\psi\vert -I)$ performs a reflection about $\vert \psi\rangle$
  • $G$ perfoms a rotation. Both $O_f$ and $(2\vert \psi\rangle\langle\psi\vert -I)$ doesn’t bring vectors outside of this 2D plane. $$G^k\vert \psi\rangle = \cos\left(\frac{2k+1}{2}\theta\right)\vert \alpha\rangle + \sin\left(\frac{2k+1}{2}\theta\right)\vert \beta\rangle$$
  • The Grover iteration can be written as $$G=\left(\begin{matrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{matrix}\right)$$
• After that, get $\vert \beta\rangle=\frac{1}{\sqrt M}\sum_{x:f(x)=1}\vert x\rangle \Rightarrow$ measure to get random $x$

6.1.4 Performance

• How many iterations does Grover’s search need?
  • $\displaystyle\langle \beta \vert \psi\rangle = \sqrt{\frac{M}{N}} = \sin\frac{\theta}{2}$
  • Assume $\displaystyle M\ll N~\Rightarrow \sin\frac{\theta}{2}\approx \frac{\theta}{2}~\Rightarrow~\theta \approx 2\sqrt{\frac{M}{N}} =\Omega(\sqrt{\frac{M}{N}})$
  • We want $\displaystyle\frac{2k+1}{2}\theta=\frac{\pi}{2}~\Rightarrow~ k=\frac{\pi}{2\theta}-\frac{1}{2}\approx \frac{\pi}{2\theta}\approx \frac{\pi}{4}\sqrt{\frac{M}{N}}\approx O(\sqrt{\frac{N}{M}})$

• The probability of getting a solution: $$Pr(\text{success}) = \displaystyle\sin^2\left((k+\frac{1}{2})\theta\right)$$
• The probability of falure: $$\begin{align*} 1-Pr(\text{success}) &=\displaystyle\cos^2\left((k+\frac{1}{2})\theta\right)\\ &= \sin^2\left(\frac{\pi}{2}-(k+\frac{1}{2})\theta\right)\\ &= \sin^2\vert\delta\vert\le \sin^2\frac{\theta}{2}=\frac{M}{N} \end{align*}$$
• This algorith requires you to know $M$. Otherwise, you might overshoot.
• If you know $M$, it is possible to make success probability $100\%$. The idea is to make $\theta$ a little smaller so $k=\frac{\pi}{2\theta}-\frac{1}{2}$ is an integer
• If we don’t know $M$, we can do quantum counting to estimate $M$ first.

6.2 Quantum search as a quantum simulation

待補

6.3 Quantum Counting

• Estimate the number of solutions $M$ from $N$ items with a probability of success at least $1-\varepsilon$
  • Classical: $\Omega(\frac{1}{\varepsilon^2}\frac{N}{M})$
  • Quantum: $O(\frac{1}{\varepsilon}\sqrt{\frac{N}{M}})$ queries, for some $\varepsilon$ multiplicative error.
• Idea: apply phase estimation to Grover iteration $G$ $$G=\left(\begin{matrix}\cos\theta & -\sin\theta\\\sin\theta & \cos\theta\end{matrix}\right)$$
  • Have eigenvalues $e^{i\theta}$ and $e^{i(2\pi-\theta)}$.
  • Estimate $\theta$ to $m$ bits of accuracy ($\vert\Delta\theta\vert\le2^{-m}$) with a probability of success at least $1-\varepsilon$.

Preparation:

• Assume the search space is augmented $N\to2N$ for convenient, $\sin^2(\theta/2)=M/2N$.
• Use $t=m+\lceil\log(2+\frac{1}{2\varepsilon})\rceil$ bits.
• $\vert \psi\rangle=\sum_x\vert x\rangle$ as input to oracle (superposition of all possible states)
  

Proof

Recall that $\sin^2\frac{\theta}{2}=\frac{M}{2N}$, we estimate $M$ by estimating $\theta$ (assume $\theta<\frac{\pi}{2}$)

$$\begin{align*}\frac{\vert \Delta M\vert}{2N} &= \left\vert \sin^2\frac{(\theta+\Delta\theta)}{2}-\sin^2\frac{\theta}{2} \right\vert\\ &= \left(\sin\frac{(\theta+\Delta\theta)}{2}+\sin\frac{\theta}{2}\right)\left\vert \sin\frac{(\theta+\Delta\theta)}{2}-\sin\frac{\theta}{2} \right\vert\end{align*}$$

Two parts:

$$\begin{align*}\left\vert \sin\frac{(\theta+\Delta\theta)}{2}-\sin\frac{\theta}{2} \right\vert &= \left\vert \cos\left(\frac{\theta}{2}+\frac{\Delta\theta}{4}\sin\frac{\Delta\theta}{4}\right) \right\vert \\ &\le \frac{\vert \Delta\theta\vert}{4}\le\frac{\vert \Delta\theta\vert}{2}\\\left\vert \sin\left(\frac{\theta+\Delta\theta}{2}\right)\right\vert &= \left\vert \sin\frac{\theta}{2}\cos\frac{\Delta\theta}{2}+\sin\frac{\Delta\theta}{2}\cos\frac{\theta}{2} \right\vert\\ &\le \sin\frac{\theta}{2}+\frac{\vert\Delta\theta\vert}{2}\end{align*}$$

Implies:

$$\begin{align*}\Rightarrow &&\frac{\vert\Delta M\vert}{2N} &\le (2\sin\frac{\theta}{2}+\frac{\vert\Delta\theta\vert}{2})\frac{\vert\Delta\theta\vert}{2}\\ &&&\le \left(\sqrt{\frac{2M}{N}}+2^{-(m+1)}\right)\frac{2^{-m}}{2}\\\Rightarrow && \vert \Delta M\vert &\le (\sqrt{2MN}+\frac{N}{2^{m+1}})2^{-m}\end{align*}$$

• Pick $\vert \Delta M\vert=\varepsilon M~\Rightarrow~ \varepsilon M\approx 2^{-m}\sqrt{MN}~\Rightarrow~2^m\approx\frac{1}{\varepsilon}\sqrt{\frac{N}{M}}$.
• Use $t=m+\lceil\log(2+\frac{1}{2\delta})\rceil$ bits, need $2^0+2^1+…+2^{t-1}=2^t-1$ Grover iterations for phase estimation $\Rightarrow$ number of quries (oracle calls) $\sim 2^t$ $$2^t=2^m\cdot 2^{\lceil\log(2+\frac{1}{2\delta})\rceil}\approx \frac{1}{\varepsilon}\sqrt{\frac{N}{M}}\left(2+\frac{1}{2\delta}\right)=O(\frac{1}{\varepsilon}\sqrt\frac{N}{M})$$

6.4 Speeding up the solution of NP-complete problems

待補

6.5 Quantum search of an unstructured database

待補

6.6 Optimality of the search algorithm

• No quantum algorithm can perform oracle search using fewer than $\Omega(\sqrt N)$ quries.
• Idea: adversary method
  • Quantum query algorithms can be viewed as
    
  • Consider the distance between $\vert \psi^f_k\rangle$ and $\vert \psi^{f’}_k\rangle$ for some function $f$ and $f’$ $$\left\Vert \vert \psi^f_k\rangle-\vert \psi^{f'}_k\rangle \right\Vert^2$$
  • Start with zer odistance $\vert \psi^f_0\rangle=U_0\vert 0\rangle, ~\forall~f$
  • For some $(f, f’)$ pairs, $\vert \psi^f_k\rangle$ and $\vert \psi^{f’}_k\rangle$ are distinguishable $\Rightarrow$ const distance.
    • for example, $f(x)=0~\forall x$ and $\exists x$ s.t. $f’(x)=1$
  • In the middle, note that $U_t$ does not change the distance $$\begin{align*} \left\Vert U\vert a\rangle - U\vert b\rangle \right\Vert &= \left\Vert U(\vert a\rangle-\vert b\rangle) \right\Vert^2\\ &= (\langle a\vert -\langle b\vert)U^\dagger U(\vert a\rangle-\vert b\rangle)\\ &= \left\Vert \vert a\rangle - \vert b\rangle \right\Vert^2 \end{align*}$$
  • For a specific pair of $(f, f’)$, $O_f$ and $O_{f’}$ might change the distance between $\vert \psi^f_t\rangle$ and $\vert \psi^{f’}_{t}\rangle$ a lot. Eg. $\vert \psi^f_t\rangle=\vert \psi^{f’}_t=\vert x\rangle$ for some $x$ s.t. $f(x)=0$ and $f’(x)=1$ $\Rightarrow$ distance changed by const.
  • So we sum over different pairs of $(f, f’)$, such that the sum of distance cannot increase a lot.
  • Sum of distance start with zero, end with something big, cannot change too much each step $\Rightarrow$ need many steps.

Way to proof:

• Consider $$\begin{align*} f_0 &= \text{all zeros}&\\ f_x &= \begin{cases}f(x)=1\\f(y)=0, &\forall y\ne x\end{cases} \end{align*}$$ we pair between $(f_0, f_x)~~\forall x\in\{1,2,\dots, N\}$
• Use the phase version of the oracle (ignore control, ignore ancilla) $$O_{f_0}=I, \quad O_{f_x}\vert y\rangle=(-1)^{\delta_{xy}}\vert y\rangle = (I-2\vert x\rangle\langle x\vert)\vert y\rangle$$
  • Define $O_x\equiv O_{f_x}=I-2\vert x\rangle\langle x\vert$
• Define $$\begin{align*} \vert \psi^x_k\rangle &\equiv\vert \psi^{f_x}_k\rangle=U_kO_xU_{k-1}O_x\cdots U_1O_xU_0\vert 0\rangle\\ \vert \psi_k\rangle &\equiv\vert \psi^{f_0}_k\rangle=U_kU_{k-1}\cdots U_0\vert 0\rangle \end{align*}$$
• Define “Progress function” $D_k$, the deviation after $k$ steps (simplified notations) $$\begin{align*} D_k\equiv \sum^N_{x=1}\left\Vert\psi^x_k-\psi_k\right\Vert^2 \end{align*}$$
• Need to prove two parts
  1. $D_k \le O(k^2)$ (Induction)
  2. $D_k=\Omega(N)$ to success
• Finally $\Rightarrow~k=\Omega(\sqrt N)$

Proof $D_k\le4k^2$

By induction

Hypothesis: $D_k\le4k^2$

Base case: $k=0$, $D_k=0$

Induction step:

$$\begin{align*}D_{k+1} &= \sum_x \left\Vert U_{k+1}O_x\psi^x_k-U_{k+1}\psi_k \right\Vert^2\\ &= \sum_x\left\Vert O_x\psi^x_k-\psi_k \right\Vert^2\\ &= \sum_x\big\Vert \underbrace{O_x(\psi^x_k-\psi_k)}_{b}+\underbrace{(O_x-I)\psi_k}_{c} \big\Vert^2\end{align*}$$

Applying $\left\Vert b+c\right\Vert^2\le \left\Vert b\right\Vert^2 + 2\left\Vert b\right\Vert \left\Vert c\right\Vert+\left\Vert c\right\Vert^2$ with $b\equiv O_x(\psi^x_k-\psi_k)$ and $c\equiv (O_x-I)\psi_k=-2\vert x\rangle\langle x\vert\psi_k\rangle=-2\langle x\vert \psi_k\rangle\vert x\rangle$

$$D_{k+1}\le \sum_x\left(\underbrace{\left\Vert \psi^x_k-\psi_k\right\Vert^2}_{D_k} +4\underbrace{\left\Vert \psi^x_k-\psi_k \right\Vert\langle x\vert \psi_k\rangle}_{\text{Cauchy}}+4\underbrace{\left\vert \langle \psi_k\vert x\rangle \right\vert^2}_{1} \right)$$

Because $\sum_x\left\vert \langle\psi_k\vert x\rangle \right\vert^2=\sum_x\langle\psi_k\vert x\rangle\langle x\vert \psi_k\rangle=\langle \psi_k\vert \underbrace{\left(\sum_x\vert x\rangle\langle x\vert\right)}_{I}\vert\psi_k\rangle=1$. By Cauchy’s inequality $\sum_x a_xb_x\le \sqrt{\sum_x a^2_x}\sqrt{\sum_x b^2_x}$.

$$\begin{align*}D_{k+1} &\le D_k +4{\textstyle\sqrt{\sum_x\left\Vert \psi^x_k-\psi_k \right\Vert^2}\sqrt{\sum_x\left\vert \langle \psi_k\vert x\rangle \right\vert^2} }+4\\ &\le D_k + 4\sqrt{D_k} + 4\end{align*}$$

By induction hypothesis $D_k\le 4k^2$

$$D_{k+1}\le 4k^2 +4\cdot 2k + 4 = 4(k+1)^2$$

Hence, $D_k\le 4k^2$.

Proof $D_k=\Omega(N)$

Assume $\exists$ projector $P$ s.t. $\left\Vert P\vert\psi_k\rangle \right\Vert^2\le \frac{1}{9}, ~\left\Vert P\vert\psi^x_k\rangle \right\Vert^2\le \frac{8}{9}, ~\forall x$. (some magic number: distinguish prob. $\approx 1/3$)

Claim: if there $\exists~p$ s.t. $\left\Vert P\vert a\rangle \right\Vert^2\le \frac{1}{9}, ~\left\Vert P\vert b\rangle \right\Vert^2\le \frac{8}{9}~\Rightarrow~\left\Vert\vert a\rangle-\vert b\rangle\right\Vert^2\ge\frac{2}{3}$

Proof: Note that $\left\Vert(I-P)\vert b\rangle\right\Vert^2\le \frac{1}{9}$.

Consider $\vert \langle a\vert b\rangle\vert$

$$\begin{align*}\vert \langle a\vert b\rangle\vert &= \left\vert \langle a\vert (I-P)+p \vert b\rangle \right\vert\\ &\le \vert \langle a \vert (I-P)\vert b\rangle \vert + \vert \langle a\vert P\vert b\rangle\vert\\ &\le \left\Vert a \right\Vert \left\Vert (I-P)b \right\Vert + \left\Vert a(P) \right\Vert \left\Vert b \right\Vert\\ &\le 1\cdot \frac{1}{3}+1\cdot \frac{1}{3} =\frac{2}{3}\end{align*}$$

Thus

$$\begin{align*}\left\Vert \vert a\rangle-\vert b\rangle \right\Vert^2 &= \left\Vert a\right\Vert^2+\left\Vert b\right\Vert^2 -\langle a\vert b\rangle -\langle b\vert a\rangle\\ &= 2 - 2\vert \langle a\vert b\rangle\vert\ge 2(1-\frac{2}{3})=\frac{2}{3}\end{align*}$$

Let $\vert a\rangle = \vert \psi_k\rangle$ and $\vert b\rangle=\vert \psi^x_k\rangle$

$$\begin{align*}D_k&=\sum_x\left\Vert \vert \psi_k\rangle-\vert \psi^x_k\rangle\right\Vert^2 \ge \sum_x\frac{2}{3} = \frac{2N}{3}\\\Rightarrow D_k&=\Omega(N)\end{align*}$$

Proof $k=\Omega(\sqrt N)$

By $D_k\le 4k^2$ and $D_k\ge\frac{2N}{3}$

$$\frac{2N}{3}\le D_k\le 4k^2~\Rightarrow~k\ge\sqrt{\frac{N}{6}}=\Omega(\sqrt N)$$

• This can be generalized to adversary method
  • Weight on different pairs
  • Can put negative weight on some pairs. negative weight adversary bound is optimal.
• State distinguishment (Ch. 9)
  • Trace distance: $D_\text{tr}(\rho, \sigma)=\frac{1}{2}\text{tr}\vert\rho-\sigma\vert$, maximum distinguish prob.
  • Fidelity: $F(\psi, \phi)=\vert\langle\psi\vert\phi\rangle\vert$
  • For pure state: $D_\text{tr}(\psi, \phi)^2+F(\psi, \phi)^2=1$

6.7 Black box algorithm limits

待補

Bonus

待補

Better bounds on distinguish quantum states

Suppose we have two quantum states $\vert a\rangle$, $\vert b\rangle$, projective measurements $\{P, I-P\}$ s.t. $\left\Vert P\vert a\rangle \right\Vert^2 \le \varepsilon$, $\left\Vert P\vert b\rangle \right\Vert^2\ge 1-\varepsilon$, $~\varepsilon\in [0, \frac{1}{2}]$.

Claim: $\vert\langle a\vert b\rangle\vert\le 2\sqrt{\varepsilon(1-\varepsilon)}$

Proof $\vert\langle a\vert b\rangle\vert\le 2\sqrt{\varepsilon(1-\varepsilon)}$

Proof 1

$$\begin{align*}\vert \langle a \vert b \rangle \vert &= \vert \langle a \vert P+(I-P)\vert b\rangle\vert\\ &= \vert \langle a\vert P^2+(I-P)^2\vert b\rangle\vert\\ &\le \vert \langle a \vert PP\vert b\rangle \vert + \vert \langle a\vert (I-P)(I-P)\vert b\rangle\vert\\ &\le\big\Vert \underbrace{P\vert a\rangle}_{x_1}\big\Vert \big\Vert \underbrace{P\vert b\rangle}_{x_2}\big\Vert + \big\Vert\underbrace{(I-P)\vert b\rangle}_{y_1}\big\Vert \big\Vert\underbrace{(I-P)\vert a\rangle}_{y_2}\big\Vert\\\end{align*}$$

By Cauchy theory $x_1x_2+y_1y_2\le \sqrt{x_1^2+x_2^2}+\sqrt{y_1^2+y_2^2}$

$$\begin{align*} \vert \langle a \vert b \rangle \vert &\le \sqrt{x_1^2+x_2^2} + \sqrt{y_1^2+y_2^2}\\\end{align*}$$

By

$$\begin{cases}x_1^2+y_2^2=1,&x_1^2\le \varepsilon\\x_2^2+y_1^2=1,&y_1^2\le \varepsilon\end{cases}$$ $$\vert \langle a \vert b \rangle \vert \le \sqrt{(x_1^2+y_1^2)(2-(x_1^2+y_1^2))}$$

By $x\le2\varepsilon$

$$\vert \langle a \vert b \rangle \vert \le \sqrt{2\varepsilon(2-2\varepsilon)}=2\sqrt{\varepsilon(1-\varepsilon)}$$

Proof 2

The best way to distingish $\vert a\rangle$ and $\vert b\rangle$: $\vert b\rangle \sim \vert 0\rangle$ and $\vert a\rangle \sim \vert 1\rangle$

$$\begin{align*}\text{error} = \sin^2\delta \le \varepsilon\end{align*}$$ $$\begin{align*}\Rightarrow~\vert \langle a\vert b\rangle &= \vert \cos(\frac{\pi}{2} - 2\delta)\vert\\ &= \vert \sin(2\delta)\vert \\ &= 2\vert \sin\delta \vert \vert\cos\delta\vert = 2\sqrt{\varepsilon(1-\varepsilon)}\end{align*}$$

Proof 3
Let $T$ be the trace distance between $\vert a\rangle, \vert b\rangle$, $F$ be the Fidelity between $\vert a\rangle$, $\vert b\rangle$.

• Fact 1: $T\ge$ bias betweem measurement probability $\ge(1-\varepsilon)-\varepsilon=1-2\epsilon$
  • $|P\vert b\rangle|^2\ge 1-\varepsilon$
  • $|P\vert a\rangle|^2 \le \varepsilon$
• Fact 2: For $\vert a\rangle$ and $\vert b\rangle$ pur states
  • $T^2+F^2=1$
  • $F=|\langle a\vert b\rangle|=\sqrt{1-T^2}\le \sqrt{1-(1-2\varepsilon)^2}=2\sqrt{\varepsilon(1-\varepsilon)}$

Applications of Grover’s algorithm

Speed up for $NP$-complete problems

• Satisfiability: given boolean formula $\phi(i_1,i_2,\dots,i_n)$, determine whether there exist $i=i_1i_2\dots i_n$ s.t. $\phi(i)=1$ ($\phi(i)$ is easy to compute, but there are $N=2^n$ possible assignment of $i$)
  • Quantum alg: construct $q$ circuit $Q_\phi$ s.t. $\vert i\rangle\to(-1)^{\phi(i)}\vert i\rangle$ ($\vert i,b\rangle\to\vert i,b\oplus \phi(i)\rangle$)
  • $O_\phi$ is easy to construct because $\phi(i)$ is easy to compute
    • $\Rightarrow$ use $O_\phi$ as the oracle in Grover’s search
    • $\Rightarrow$ determine whether $\exists~i,$ s.t. $\phi(i)=1$ in $O(\sqrt{2^n}~\text{cost of}~O_\phi)\sim 2^{m/2}$ time
• However, not always getting quadratic speedup to $NP$ complete problem. Because $\sqrt{\text{num of assignment}}$ might be slower than known classical alg.
  • e.g. Travelling Salesmans Problem (TSP) on $n$
    • number of assignment $=n!\sim n^n$
    • Classical alg $\sim O(2^n)$
    • Best quantum algorithm $\sim O(1.728^n)$ non-trivial application of Grover’s search

$OR$ of $AND$

• A boolean matrix $$\left[\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ \end{matrix}\right]\xrightarrow{\text{row-wise}~AND} \left[\begin{matrix} 0\\0\\0\\1\\0\\0\\ \end{matrix}\right]\xrightarrow{OR}1$$
• Question: is there a row with all $1$’s?
  • Classical: easy to see need $\Omega(N)$ queries
  • Quantum alg 1: Grover search each row for an $0$
    • time for each row $\sqrt{\sqrt{N}}\sim N^{1/4}$ (times $\log N$ because we want $1/N$ error)
    • total time
      $=\text{num of rows}\times\text{time for each row}=\sqrt{N}\cdot N^{1/4}\cdot \log N=N^{3/4}\cdot\log N$
  • Quantum alg 2: run Grover’s search recursively, have an outer Grover that search through rows, and a row is “marked” iff the inner Grover cannot find zero in it
    • total running time $\sqrt{\sqrt{N}}\cdot\sqrt{\sqrt{N}}\cdot\log N=\sqrt{N}\log N$ (quadratic speedup)
    • $\Omega(\sqrt{N})$ lower bound

$AND$-$OR$ tree

• Game tree for chess or Go etc.
  • $1$: win, $0$: lose (ignore tie)
  • $OR$: Is there a move that makes me win?
  • $AND$: Is there a move that makes me lose?
• Recursive Grover? Don’t actually work because error builds up through recursion
• Still has $O(\sqrt N)$ quantum alg. through quantum walk

Collision problem

• Given blackbox access to the function $f:\{1,2,\dots,N\}\to\{1,2,\dots,N\}$
• Promise: $f$ is either one-to-one or two-to-one (has lots of collision)
  • e.g. one-to-one $f:1\to1,~2\to2,~3\to4,~4\to3$
  • e.g. two-to-one $f:1\to1,~2\to4,~3\to1,~4\to4$
• Problom: decide whether $f$ is one-to-one or two-to-one
  • Classical $\Theta(\sqrt N)$
    • Birthday attach: random pair $O(1/N)$ probability to be a collision.
    • If we pick $O(\sqrt N)$ items, there are $O(N)$ pairs $\Rightarrow$ const probability finding a collision in those pairs.
  • Quantum alg 1: $O(\sqrt N)$ queries (no speedup)
    • query $f(1)$, Grover search for an $x\ne1$ s.t. $f(x)=f(1)$
  • Quantum alg 2: $\Omega(N^{1/3})$ lowerbound
    • pick $N^{1/3}$ random elements $S_1$ query them classically and write down the answers
    • pick another $N^{2/3}$ elements $S_2$ (don’t query them yet). Grover search through $y\in S_2$, an item $y\in S_2$ is marked iff $\exists~x\in S_1$ s.t. $f(x)=f(y)$
    • Since we already reordered everything in $S_1$ only need one query $f(y)$ to determined whether $y$ is marked.
    • Total number of queries: $N^{1/3}+\sqrt{N^{2/3}}=O(N^{1/3})$
    • Number of pirs searched: $N^{1/3}\cdot N^{2/3}\sim O(N)\Rightarrow$ const success probability
    • with smart data structure can also do $\tilde{O}(N^{1/3})$ time.

Element distinctness

• also $f:\{1,2,\dots,N\}\to\{1,2,\dots,N\}$, no promise
• Problem: determine whether $f$ is one-to-one (ie. whether $f$ have collision)
  • Classical: $\Theta(N)$
  • Quantum alg 1: $O(N^{3/4})$
    • Divide the inputs into $\sqrt{N}$ blocks of size $\sqrt{N}$
    • Outer Grover search through each block $s$ and query all elements in it (check collision inside)
    • Inner Grover search between pair ($x\in s, y\in s$)
    • If $s$ contain an element of the collision, we find it $\Rightarrow$ prob $\frac{1}{\sqrt N}$
    • Total queries: $\sqrt{\sqrt N}\cdot \sqrt{N}=O(N^{3/4})$
  • Quantum alg 2: $O(N^{2/3})$ by quantum walk
    • $\Omega(N^{2/3})$ lower bound by reduction from collision (pick $\sqrt{N}$ elements)

Exact Grover search

• Promised that an unique marked item, find alg. that find the marked item with prob $1$, in $O(\sqrt N)$ steps. $$f:\{1,2,\dots,N\}\to\{0,1\},\quad \exists~x^* ~\text{s.t.}~ f(x)\begin{cases} 1, &x=x^*\\ 0, &\text{otherwise} \end{cases}$$
• Define $f’:\{1,\dots,2N\}\to\{0,1\}$ $$f'(x)=\begin{cases} f'(x)=f(x), &\text{if}~1\le x\le N\\ f'(x)=0, &\text{if}~N+1\le x\le 2N \end{cases}$$
• can simulate $O_{f’}$ with one $\tilde{O_f}$ $$\tilde{O}_f\vert x,b\rangle = \vert x,f(x)\oplus b\rangle$$
  • define $$U_\gamma=\left(\begin{matrix}\cos\gamma & -\sin\gamma \\ \sin\gamma & \cos\gamma\end{matrix}\right),\quad A=H^{\otimes n}\otimes U_\gamma$$
  • We have $$A\vert 0\rangle^{\otimes n+1}=\frac{1}{\sqrt N}\sum^N_{x=1}\vert x\rangle \otimes (\cos\gamma\vert 0\rangle+\sin\gamma\vert 1\rangle)$$
  • The probability that $A\vert 0\rangle^{\oplus n+1}$ is marked $$\begin{align*} \text{Prob}(A\vert 0\rangle^{\oplus n+1}~\text{marked}) &= \left|\langle x^*,0|A|0\rangle\right|^2\\ &= \frac{1}{N} \cos^2\gamma \end{align*}$$ $$\sin\theta_\gamma=\frac{\cos\theta_\gamma}{\sqrt N},\quad \text{write}~\lceil\tilde k\rceil=k$$ $$\begin{align*} (2k+1)\theta_\gamma=\frac{\pi}{2} &\Rightarrow \theta_\gamma =\frac{\pi}{2(2k+1)}\\ &\Rightarrow \frac{\cos\gamma}{\sqrt N}=\sin\frac{\pi}{2(2k+1)}\quad(\text{let}~\theta_\gamma\approx\gamma)\\ &\Rightarrow \gamma=\cos^{-1}\left(\sqrt N\cdot \sin\frac{\pi}{2(2\lceil \tilde k\rceil+1)}\right) \end{align*}$$

$\Omega(\sqrt{\frac{N}{M}})$ query lower bound for $M$ marked items

• easy solution
  $Q($search $M$ marked items from $N$ items $)$
  $\ge Q($search $M$ marked items from $N$ items promised that marked items are blocks$)$
  $\ge Q($search one marked item in $\frac{N}{M}$ items$)$
  $=\Omega(\sqrt{\frac{N}{M}})$
• harder solution
  • consider all $C^N_M$ ways to mark $M$ items
  • Let $S\subset\{1,2,\dots,N\}$ with size $M$. $C^N_M$ possible $S$ $$D_k=\sum_{\substack{S:S\le[N]\\\vert S\vert=M}} \vert\psi^S_k-\psi\vert^2,\quad D_T=\Omega(C^N_M)$$
  • By induction $$\begin{align*} D_{k+1}&=\sum_S\vert O_S\psi^S_k-\psi_k\vert^2\\ &=\sum_S\big\vert \underbrace{O_S(\psi^S_k-\psi)}_{\equiv~ b_S}+\underbrace{(O_S-I)\psi_k)}_{\equiv ~c_S}\big\vert^2\\ &\le \sum_S\vert b_S\vert^2+2\vert b_S\vert\vert c_S\vert+\vert c_S\vert^2 \end{align*}$$ $$(O_S-I)=-2\sum_{x\in S}\vert x\rangle\langle x\vert, \quad (O_S-I)\vert \psi_k\rangle=-2\sum_{x\in S}\vert x\rangle\langle x\vert \psi_k\rangle$$ $$\begin{align*} \sum_S\vert c_S\vert^2 &= 4\sum_S\left\|\sum_{x\in S}\vert x\rangle\langle x\vert \psi_k\rangle\right\|^2\\ &=4\sum_S\sum_{x\in S}\left\vert \langle x\vert \psi_k\rangle\right\vert^2 \quad (\text{recall}~\sum^N_{x=1}\vert\langle x\vert \psi_s\rangle\vert^2=1)\\ &=4 C^{N-1}_{M-1}\\ \sum_S\vert b_S\vert\vert c_S\vert &\le \sqrt{\sum_S\vert b_S\vert^2}\sqrt{\sum_S\vert c_S\vert^2},\quad \sum_S\vert b_s\vert^2 =D_k\\ \end{align*}$$ $$\begin{align*} \Rightarrow &&D_{k+1}&\le D_k+2\sqrt{D_k}\sqrt{4C^{N-1}_{M-1}}+4C^{N-1}_{M-1}\\ \Rightarrow &&D_{k+1} -D_k &\le 4\sqrt{D_k}\sqrt{C^{N-1}_{M-1}}+4C^{N-1}_{M-1}\\ &&&\le O(\sqrt{C^N_M}\sqrt{C^{N-1}_{M-1}}) \end{align*}$$ $$\begin{align*} T\ge \frac{D_T-D_0}{\Delta D} &=\Omega\left(\frac{C^N_M}{\sqrt{C^N_M}\sqrt{C^{N-1}_{M-1}}}\right) = \Omega\left(\sqrt{\frac{C^N_M}{C^{N-1}_{M-1}}}\right)\\ &= \Omega\left(\sqrt{\frac{N!}{M!(N-M)!}\frac{(M-1)!(N-M)!}{(N-1)!}}\right)\\ &= \Omega\left(\sqrt{\frac{N}{M}}\right) \end{align*}$$

Minimum finding

• Given quantum access to input of $N$ numbers, $x_1,x_2,\dots,x_N$, find the $\min$ of them in $O(\sqrt N\log N)$ steps.
• start with random $s\in\{1,\dots,N\}$ query $x_s$.
• Grover search among the items to find some $r$ s.t. $x_r\le x_s$
  • $O(\sqrt N)$ times find a random one
  • keep doing this until you cannot find a smaller one
  • every iteration expect number of smaller items $\Rightarrow~\log N$ iterations