Quantum Computing (Fall2013) Instructor:Shengyu Zhang. Lecture 6 Quantum query complexity:Upper bound. In this lecture,we'll first finish the proof for the quantum adversary method as a lower bound of quantum query complexity.Then we show a matching upper bound,by which we prove the result that the quantum adversary method is in the same order of the quantum query complexity. 1.Lower bound:Quantum adversary method Recall that the quantum query complexity Q(f)is defined as the minimum number of queries needed for an e-error quantum query algorithm to solve a computational problem on the worst case input.The best lower bound by the quantum adversary method is Adv(f)utan mDil where Diy)=1We'll first finish the proof ofthe following theorem. Q.≥(G-Vea-可)Adw(0 2.Upper bound: It turns out that the above lower bound is tight.In this section,we'll show an even strong result,a quantum query algorithm solving a more general computational task of quantum state conversion [LMR+11].Suppose we have a set of pure quantum states [p):x E {0,1)"}and we'd like to convert them to another set of pure quantum states {lo,):x E (0,1)).(Usually the Greek letters p and o are for mixed states,but somehow they are used in [LMR+11]to denote pure states,and we just respect their notation here.)The conversion need to be correct for every x E{0,1)",namely we need to use one universal algorithm to convert lp)to l for all xE(0,1)simultaneously.In general this is not doable without the knowledge of x,as shown by the following basic result. Exercise.There is a unitary operation U that converts the states {lu):i =1,...n}to v):i=1,..,n}if and only if (uilu)=vv)for all i,je [n]
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 6 Quantum query complexity: Upper bound. In this lecture, we’ll first finish the proof for the quantum adversary method as a lower bound of quantum query complexity. Then we show a matching upper bound, by which we prove the result that the quantum adversary method is in the same order of the quantum query complexity. 1. Lower bound: Quantum adversary method Recall that the quantum query complexity 𝑄𝜖 (𝑓) is defined as the minimum number of queries needed for an 𝜖-error quantum query algorithm to solve a computational problem on the worst case input. The best lower bound by the quantum adversary method is 𝐴𝑑𝑣(𝑓) = max 𝛤≠0:𝐻𝑒𝑟𝑚𝑖𝑡𝑖𝑎𝑛 ‖𝛤‖ max 𝑖 ‖𝛤 ∘ 𝐷𝑖 ‖ where 𝐷𝑖 (𝑥, 𝑦) = 1[𝑥𝑖≠𝑦𝑖 ] . We’ll first finish the proof of the following theorem. 𝑄𝜖 (𝑓) ≥ ( 1 2 − √𝜖(1 − 𝜖))𝐴𝑑𝑣(𝑓) 2. Upper bound: It turns out that the above lower bound is tight. In this section, we’ll show an even strong result, a quantum query algorithm solving a more general computational task of quantum state conversion [LMR+11]. Suppose we have a set of pure quantum states {|𝜌𝑥 〉: 𝑥 ∈ {0,1} 𝑛 } and we’d like to convert them to another set of pure quantum states {|𝜎𝑥 〉: 𝑥 ∈ {0,1} 𝑛 }. (Usually the Greek letters 𝜌 and 𝜎 are for mixed states, but somehow they are used in [LMR+11] to denote pure states, and we just respect their notation here.) The conversion need to be correct for every 𝑥 ∈ {0,1} 𝑛 , namely we need to use one universal algorithm to convert |𝜌𝑥 〉 to |𝜎𝑥 〉 for all 𝑥 ∈ {0,1} 𝑛 simultaneously. In general this is not doable without the knowledge of 𝑥, as shown by the following basic result. Exercise. There is a unitary operation 𝑈 that converts the states {|𝑢𝑖 〉:𝑖 = 1, …, 𝑛} to {|𝑣𝑖 〉:𝑖 = 1, …, 𝑛} if and only if 〈𝑢𝑖 |𝑢𝑗 〉 = 〈𝑣𝑖 |𝑣𝑗 〉 for all 𝑖,𝑗 ∈ [𝑛]
Since this condition doesn't hold for general e):xE(0,1)"}and lox):x0,1)").So we need to get some knowledge of the index x.(In the extreme case,consider that we have the full knowledge of x.Then we don't even need the given state lpx)---we can generate lox)by ourselves.)We access x by queries as usual.The question is what the minimum number of queries to x is needed.We of course allow the algorithm to take ancilla,so the algorithm takes as input lp)10)and generates a state close to lo,)Is)for some Is).This generalizes the function evaluation setting,where all lp)=10),and target states is lo,)Is)=If(x))Is,)for some ancilla Is,). The result is the following: Theorem.The query complexity of the above state conversion problem is at most 0(y2(M。-MlD)log(1/e)/e2） where ·M。=【oxlp,lyM,=【laxo小xy .D={D..,Dn}with Di=[xy ·(az)=min{max max{llux,ll川}：Ag=ulo,(Z)} For Boolean functionevaluation,note that all lp)=10)and lox)=If(x)),thus M=J and MF=Ittums out that Adv(f)=Y2 (-FID) by SDP duality.Thus the above theorem does implies the tightness of Adv(f)as a lower bound of the quantum query complexity Let W=Y2(M-MD).An optimum solution lu)in the definition of YM-MD)has the following properties by definition llux≤W,llv2≤W,x (1) ∑jyuxjlvyj〉=(pxlp,）-(oxoy〉(=1rw+for Boolean f) (2)
Since this condition doesn’t hold for general {|𝜌𝑥 〉:𝑥 ∈ {0,1} 𝑛} and {|𝜎𝑥 〉: 𝑥 ∈ {0,1} 𝑛}. So we need to get some knowledge of the index 𝑥. (In the extreme case, consider that we have the full knowledge of 𝑥. Then we don’t even need the given state |𝜌𝑥 〉---we can generate |𝜎𝑥 〉 by ourselves.) We access 𝑥 by queries as usual. The question is what the minimum number of queries to 𝑥 is needed. We of course allow the algorithm to take ancilla, so the algorithm takes as input |𝜌𝑥 〉|0〉 and generates a state close to |𝜎𝑥 〉|𝑠𝑥 〉 for some |𝑠𝑥 〉. This generalizes the function evaluation setting, where all |𝜌𝑥 〉 = |0〉, and target states is |𝜎𝑥 〉|𝑠𝑥 〉 = |𝑓(𝑥)〉|𝑠𝑥 〉 for some ancilla |𝑠𝑥 〉. The result is the following: Theorem. The query complexity of the above state conversion problem is at most 𝑂((𝛾2 (𝑀𝜌 − 𝑀𝜎 |𝐷) log(1/𝜖))/𝜖 2 ) where • 𝑀𝜌 = [〈𝜌𝑥 |𝜌𝑦 〉] 𝑥,𝑦 , 𝑀𝜎 = [〈𝜎𝑥 |𝜎𝑦 〉] 𝑥,𝑦 , • 𝐷 = {𝐷1 , …,𝐷𝑛 } with 𝐷𝑖 = [1[𝑥𝑖≠𝑦𝑖 ] ] 𝑥,𝑦 , • 𝛾2 (𝐴|𝑍) = min {max 𝑥 max {∑ ‖|𝑢𝑥𝑗〉‖ 2 𝑗 , ∑ ‖|𝑣𝑥𝑗〉‖ 2 𝑗 } : 𝐴𝑥𝑦 = ∑ 〈𝑢𝑥𝑗|𝑣𝑦𝑗〉(𝑍𝑗 ) 𝑥𝑦 𝑗 } For Boolean function evaluation, note that all |𝜌𝑥 〉 = |0〉 and |𝜎𝑥 〉 = |𝑓(𝑥)〉, thus 𝑀𝜌 = 𝐽 and 𝑀𝜎 = 𝐹 = [1[𝑓(𝑥)=𝑓(𝑦)] ] 𝑥,𝑦 . It turns out that 𝐴𝑑𝑣(𝑓) = 𝛾2 (𝐽 − 𝐹|𝐷) by SDP duality. Thus the above theorem does implies the tightness of 𝐴𝑑𝑣(𝑓) as a lower bound of the quantum query complexity. Let 𝑊 = 𝛾2 (𝑀𝜌 − 𝑀𝜎 |𝐷). An optimum solution |𝑢𝑥𝑗 〉, |𝑣𝑥𝑗 〉 in the definition of 𝛾2 (𝑀𝜌 − 𝑀𝜎 |𝐷) has the following properties by definition ∑ ‖|𝑢𝑥𝑗〉‖ 2 𝑗 ≤ 𝑊, ∑ ‖|𝑣𝑥𝑗〉‖ 2 𝑗 ≤ 𝑊, ∀𝑥 (1) ∑ 〈𝑢𝑥𝑗|𝑣𝑦𝑗〉 𝑗:𝑥𝑗≠𝑦𝑗 = 〈𝜌𝑥 |𝜌𝑦 〉 − 〈𝜎𝑥 |𝜎𝑦 〉 (= 1[𝑓(𝑥)≠𝑓(𝑦)] for Boolean 𝑓) (2)
Instead of repeating the proof in the usual way,let me try to extract the line of main ideas We actually only need to deal with the case (pxlox)=0,since otherwise we can first attacha 10)to lp),and then transfer it to 11)lo),and then discard the 11). To transfer 10)le,)to |1)lo),it suffices to keep lt unchanged and flipping ltx-〉to-ltx-）,where ltx+)=()lpz)+11)lox)).and It-)=(10)lpz)-11)loz)). (Indeed,10)lpx)=+)+ltx-))(x+)-ltx-))=11)lox).)So it's enough to find a U s.t.t is close to the 1-eigenspace andt is close tothe (-1)-eigenspace. .Actually Itx_)doesn't need to be close to (-1)-eigenspace.As long as It,_) doesn't have a large support on eigenspace of U corresponding to eigenvalue with small phases,a tool called Phase Detection can move It_)to close to -ltx_). (Namely,as long as U moves most of It)'s components,with respect to U's eigenvectors,away in phase,not necessarily to the same far,the Phase Detection works.)More specifically,VU,ve*,there is a circuit R(U)which,on any eia-eigenvector |B〉of U where0≥8*，has IR(U)川B)I0〉+lBI0)I<6. (3) Here the number of extra qubits needed is b =0(log(1/6)log(1/0*)),and number of queries of controlled-U and controlled-Ut is o(log(1/6)/0). The paper finds such a U,which consists of repeated applications of two reflections. In what follows,we only consider the Boolean-function evaluation case for simplicity Algorithm:Run Phase Detection on unitary Ux =(2I7-1)(24-1)and state 10)lpx)10),with precision 0*=e2/W and error E. .Suppose that W=Y2(-FID),and ux),ECm:x,}is an optimal solution in the definition of y2
Instead of repeating the proof in the usual way, let me try to extract the line of main ideas. • We actually only need to deal with the case 〈𝜌𝑥 |𝜎𝑥 〉 = 0, since otherwise we can first attach a |0〉 to |𝜌𝑥 〉, and then transfer it to |1〉|𝜎𝑥 〉, and then discard the |1〉. • To transfer |0〉|𝜌𝑥 〉 to |1〉|𝜎𝑥 〉, it suffices to keep |𝑡𝑥+ 〉 unchanged and flipping |𝑡𝑥−〉 to −|𝑡𝑥− 〉, where |𝑡𝑥+ 〉 = 1 √2 (|0〉|𝜌𝑥 〉 + |1〉|𝜎𝑥 〉), and |𝑡𝑥− 〉 = 1 √2 (|0〉|𝜌𝑥 〉 − |1〉|𝜎𝑥 〉). (Indeed, |0〉|𝜌𝑥 〉 = 1 √2 (|𝑡𝑥+ 〉 + |𝑡𝑥− 〉) → 1 √2 (|𝑡𝑥+ 〉 − |𝑡𝑥− 〉) = |1〉|𝜎𝑥 〉.) So it’s enough to find a 𝑈 s.t. |𝑡𝑥+ 〉 is close to the 1-eigenspace and |𝑡𝑥− 〉 is close to the (−1)-eigenspace. • Actually |𝑡𝑥− 〉 doesn’t need to be close to (−1)-eigenspace. As long as |𝑡𝑥− 〉 doesn’t have a large support on eigenspace of 𝑈 corresponding to eigenvalue with small phases, a tool called Phase Detection can move |𝑡𝑥− 〉 to close to −|𝑡𝑥− 〉. (Namely, as long as 𝑈 moves most of |𝑡𝑥− 〉’s components, with respect to 𝑈’s eigenvectors, away in phase, not necessarily to the same far, the Phase Detection works.) More specifically, ∀𝑈, ∀𝜃 ∗ , there is a circuit 𝑅(𝑈) which, on any 𝑒 𝑖𝜃 -eigenvector |𝛽〉 of 𝑈 where 𝜃 ≥ 𝜃 ∗ , has ‖𝑅(𝑈)|𝛽〉|0 𝑏 〉 + |𝛽〉|0 𝑏 〉‖ < 𝛿. (3) Here the number of extra qubits needed is 𝑏 = 𝑂(log(1/𝛿) log(1/𝜃 ∗ )), and number of queries of controlled-𝑈 and controlled-𝑈 † is 𝑂(log(1/𝛿) /𝜃 ∗ ). • The paper finds such a 𝑈, which consists of repeated applications of two reflections. In what follows, we only consider the Boolean-function evaluation case for simplicity. Algorithm: Run Phase Detection on unitary 𝑈𝑥 = (2𝛱𝑥 − 𝟏)(2𝛥 − 𝟏) and state |0〉|𝜌𝑥 〉|0 𝑏 〉, with precision 𝜃 ∗ = 𝜖 2 /𝑊 and error 𝜖. • Suppose that 𝑊 = 𝛾2 (𝐽 − 𝐹|𝐷), and {|𝑢𝑥𝑗〉, |𝑣𝑥𝑗 〉 ∈ ℂ 𝑚: 𝑥,𝑗} is an optimal solution in the definition of 𝛾2
·△is the projection onto spanΨx:x',where I地x〉=(e/WW)Itx-〉-jU1-xhu. Note that here we attached another space H'=Cn+2+m to H(where 0) originally is),s.t.lp)in the specification of the algorithm lives in the H part of H⊕H'.So are states tx±).ButlΨx)is in the whole space H⊕H',with the first term in H and second in H'.Note that HH'is the direct sum,not product .I requires that whenthe first register of H'is j,the second register of H'be xj Query complexity:(W/82).Each 2-1 takes one query,and 24-1 doesn't need any query. Correctness: (Notation:Pe is the projection onto the eigenspace of U with eigenphase 6,and similarly for Pse.That is,if U=ei)is the spectral decomposition of U,then Po=1:0=0eie and Pso=1:0set0) .Itx+is close toa 1-eigenvector of U.More precisely,lPolt21-e2. Fact 1..‖Pltx+)l2≥1-e2. [Proof]Actually ltx)is in the subspace Ix and almost in the subspace 4.For the former,note that)is in H,while I only has requirement on H'.For the latter, directly bounding lA-ltxll=llspant):ytxll is not that obvious: x)=(t-tx+)=but there are many y's with f(y)= f(x).Fortunately,one can add a little bit to tx)to cancel out the annoying factor: Definet)=ltx++x),then)=( =0 by Eq.(2).And note that the extra term in is of (e/ 2)-small norm because of Eq.(1).(Also note that t)is still in the subspace I because the extra term exactly satisfies the requirement of I,.)
• 𝛥 is the projection onto span{|𝛹𝑥 〉:𝑥} ⊥ , where |𝜓𝑥 〉 = (𝜖/√𝑊)|tx− 〉 − ∑ |𝑗〉|1 − 𝑥𝑗 〉|𝑢𝑥𝑗〉 𝑗 . Note that here we attached another space 𝐻′ = ℂ 𝑛+2+𝑚 to 𝐻 (where |0〉|𝜌𝑥 〉 originally is), s.t. |𝜌𝑥 〉 in the specification of the algorithm lives in the 𝐻 part of 𝐻 ⊕ 𝐻′ . So are states |tx± 〉. But |𝛹𝑥 〉 is in the whole space 𝐻 ⊕ 𝐻′, with the first term in 𝐻 and second in 𝐻′. Note that 𝐻 ⊕ 𝐻′ is the direct sum, not product. • 𝛱𝑥 requires that when the first register of 𝐻′ is 𝑗, the second register of 𝐻′ be 𝑥𝑗 . Query complexity: 𝑂̃(W/ε 2 ). Each 2𝛱𝑥 − 𝟏 takes one query, and 2𝛥 − 𝟏 doesn’t need any query. Correctness: (Notation: 𝑃𝜃 is the projection onto the eigenspace of 𝑈 with eigenphase 𝜃, and similarly for 𝑃≤𝜃 . That is, if 𝑈 = ∑ 𝑒 𝑖𝜃𝑗 |𝜃𝑗 〉〈𝜃𝑗 | 𝑗 is the spectral decomposition of 𝑈, then 𝑃𝜃 = ∑ 𝑒 𝑖𝜃𝑗 |𝜃𝑗 〉〈𝜃𝑗 | 𝑗:𝜃𝑗=𝜃 and 𝑃≤𝜃 = ∑ 𝑒 𝑖𝜃𝑗 |𝜃𝑗 〉〈𝜃𝑗 | 𝑗:𝜃𝑗≤𝜃 . ) • |𝑡𝑥+ 〉 is close to a 1-eigenvector of 𝑈. More precisely, ‖𝑃0 |𝑡𝑥+ 〉‖ 2 ≥ 1 − 𝜖 2 . Fact 1. ‖𝑃0 |𝑡𝑥+ 〉‖ 2 ≥ 1 − 𝜖 2 . [Proof] Actually |𝑡𝑥+ 〉 is in the subspace 𝛱𝑥 and almost in the subspace 𝛥. For the former, note that |𝑡𝑥+ 〉 is in 𝐻, while 𝛱𝑥 only has requirement on 𝐻 ′ . For the latter, directly bounding ‖Δ ⊥|𝑡𝑥+ 〉‖ = ‖𝑠𝑝𝑎𝑛{|𝛹𝑥 〉: 𝑦}|𝑡𝑥+ 〉‖ is not that obvious: 〈𝜓𝑦 |𝑡𝑥+ 〉 = 𝜖 √𝑊 〈𝑡𝑦− |𝑡𝑥+ 〉 = 𝜖 2√𝑊 1[𝑓(𝑥)≠𝑓(𝑦)] , but there are many 𝑦’s with 𝑓(𝑦) = 𝑓(𝑥). Fortunately, one can add a little bit to |𝑡𝑥+ 〉 to cancel out the annoying factor: Define |𝑡𝑥+ ′ 〉 = |𝑡𝑥+ 〉 + 𝜖 2√𝑊 ∑ |𝑗〉|𝑥𝑗 〉|𝑣𝑥𝑗〉 𝑗 , then 〈𝜓𝑦 |𝑡𝑥+ ′ 〉 = 𝜖 2√𝑊 (1[𝑓(𝑥)≠𝑓(𝑦)] − ∑ 〈𝑢𝑥𝑗|𝑣𝑦𝑗〉 𝑗:𝑥𝑗≠𝑦𝑗 ) = 0 by Eq.(2). And note that the extra term in |𝑡𝑥+ ′ 〉 is of (𝜖/ 2)-small norm because of Eq.(1). (Also note that |𝑡𝑥+ ′ 〉 is still in the subspace 𝛱𝑥 because the extra term exactly satisfies the requirement of 𝛱𝑥 .) □
It_)has a small support on small-eigenvectors of U. Fact 2.lIPseltx)12<02W2/4E2,Ve. [Proof]We'll use a spectral gap lemma that is frequently used in one form or another. Lemma.Suppose I7 and 4 are two projections,and U =(2I7-1)(24-1). Suppose that e)}is a complete orthonormal set ofeigenvectors of U,with the respective eigenvalues.For any vector w）,if△lw〉=0，then for any日*≥0， IP≤e川ω)I川≤？Ilωl We'll skip the proof of the lemma,and state how to use it to prove Fact 2.The application is very straightforward by setting).Note that0 and Itx-.）=lxlo〉by definition of 4 andI,respectively.▣ Now putting the above two together,we can show the correctness of the algorithm. IlR(Ux)I0lpx〉-I1川oxI=‖R(Ux)I0lpI0)-I1IoxI0l川 =(R(U)-1)ltx+)10)-(R(U)+1)ltx-)10)ll ≤2l(R(Ux)-1tx+I0)‖川+2I(R(Ux)+1)Itx-0H川 We use Fact 1 to bound the item 1,and use Eq.(3)and Fact 2 to bound item 2. Reference [LMR+11]Troy Lee,Rajat Mittal,Ben Reichardt,Robert Spalek,Mario Szegedy,Quantum query complexity of state conversion,FOCS'11
• |𝑡𝑥− 〉 has a small support on small-eigenvectors of 𝑈. Fact 2. ‖𝑃≤𝜃 |𝑡𝑥− 〉‖ 2 ≤ 𝜃 2𝑊2 /4𝜖 2 , ∀θ. [Proof] We’ll use a spectral gap lemma that is frequently used in one form or another. Lemma. Suppose 𝛱 and 𝛥 are two projections, and 𝑈 = (2𝛱 − 𝟏)(2𝛥− 𝟏). Suppose that {|𝜙𝜃 〉} is a complete orthonormal set of eigenvectors of 𝑈, with the respective eigenvalues 𝑒 𝑖𝜃. For any vector |𝜔〉, if Δ|ω〉 = 0, then for any 𝜃 ∗ ≥ 0, ‖𝑃≤𝜃 ∗𝛱|𝜔〉‖ ≤ 𝜃 ∗ 2 ‖|𝜔〉‖. We’ll skip the proof of the lemma, and state how to use it to prove Fact 2. The application is very straightforward by setting |𝜔〉 = √𝑊 𝜖 |𝜓𝑥 〉. Note that 𝛥|𝜔〉 = 0 and |𝑡𝑥− 〉 = 𝛱𝑥 |𝜔〉 by definition of 𝛥 and 𝛱𝑥 , respectively. □ Now putting the above two together, we can show the correctness of the algorithm. ‖𝑅(𝑈𝑥 )|0〉|𝜌𝑥 〉 − |1〉|𝜎𝑥 〉‖ = ‖𝑅(𝑈𝑥 )|0〉|𝜌𝑥 〉|0 𝑏 〉 − |1〉|𝜎𝑥 〉|0 𝑏 〉‖ = 1 √2 ‖(𝑅(𝑈𝑥 ) − 1)|𝑡𝑥+ 〉|0 𝑏 〉− (𝑅(𝑈𝑥 ) + 1)|𝑡𝑥− 〉|0 𝑏 〉‖ ≤ 1 √2 ‖(𝑅(𝑈𝑥 ) − 1)|𝑡𝑥+ 〉|0 𝑏 〉‖ + 1 √2 ‖(𝑅(𝑈𝑥 ) + 1)|𝑡𝑥− 〉|0 𝑏 〉‖ We use Fact 1 to bound the item 1, and use Eq.(3) and Fact 2 to bound item 2. Reference [LMR+11] Troy Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, Mario Szegedy, Quantum query complexity of state conversion, FOCS’11