The hybrid argument for the optimality of quantum search compares

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Grover search, amplitude amplification and counting

Problem

The hybrid argument for the optimality of quantum search compares, for each possible marked item

x\in\{0,\dots,N-1\}

, the state

|\psi_k^x\rangle

of a fixed quantum search circuit after

k

calls to the oracle

O_x

that marks only

x

, with the state

|\psi_k\rangle

after

k

calls to the oracle

O_{\varnothing}

that marks no item at all. Both start from the same initial state and the circuit applies the same fixed unitaries between queries regardless of

x

. Define

D_k=\sum_{x=0}^{N-1}\big\||\psi_k^x\rangle-|\psi_k\rangle\big\|^2.

You are given: (i)

D_0=0

; (ii) for any normalised state

|\phi\rangle

\|O_x|\phi\rangle-|\phi\rangle\|=2|\langle x|\phi\rangle|

, and hence, for the no-oracle state,

\sum_x\|O_x|\psi_k\rangle-|\psi_k\rangle\|^2=4

; (iii) every unitary applied between queries preserves the norm of a state and of a difference of states. ((a)) Using the triangle inequality on

\big\||\psi_{k+1}^x\rangle-|\psi_{k+1}\rangle\big\|

and then the Cauchy-Schwarz inequality on the resulting cross term, show that

D_{k+1}\le\left(\sqrt{D_k}+2\right)^2

. ((b)) Prove by induction on

k

that

D_k\le4k^2

for every integer

k\ge0

. ((c)) A search circuit that can reliably say which of the

N

oracles it was given must, once it succeeds with good probability, have driven the state far enough from the untouched one that

D_k\ge N/2

. Using part (b), find the least

k

(an integer) for which this is possible when

N=10^6

, and compare it with the

R=785

Grover iterations that actually solve this case with one marked item.

Browse the problem library