Part I Quantum circuits
Part I Quantum circuits
Chapter 2 Efficient universality of quantum circuits Are some universal gate sets better than others?Classically,this is not an issue:the set of possible operations is discrete,so any gate acting on a constant number of bits can be simulated exactly using a constant number of gates from any given universal gate set.But we might imagine that some quantum gates are much more powerful than others.For example,given two rotations about strange axes by strange angles,it may not be obvious how to implement a Hadamard gate,and we might worry that implementing such a gate to high precision could take a very large number of elementary operations,scaling badly with the required precision. Fortunately,this is not the case:a unitary operator that can be realized efficiently with one set of 1-and 2-qubit gates can also be realized efficiently with another such set.In particular,we have the following(see [81,Appendix 3],[38],and [64,Chapter 8]). Theorem 2.1(Solovay-Kitaev).Fir two universal gate sets that are closed under inverses.Then any t-gate circuit using one gate set can be implemented to precision e using a circuit of t.poly(log)gates from other set (indeed,there is a classical algorithm for finding this circuit in time t.poly(log). Thus,not only are the two gate sets equivalent under polynomial-time reduction,but the running time of an algorithm using one gate set is the same as that using the other gate set up to logarithmic factors. This means that even polynomial quantum speedups are robust with respect to the choice of gate set. 2.1 Subadditivity of errors We begin with the basic fact that errors in the approximation of one quantum circuit by another accumulate at most linearly. Lemma2.2.LetU,Vi be unitary matrices satisfying i-Vl≤e for all i∈{1,2，.，t}.Then IU..U2U1-.2Ml≤te. (2.1) Proof.We use induction on t.For t=1 the lemma is trivial.Now suppose the lemma holds for a particular value of t.Then by the triangle inequality and the fact that the norm is unitarily invariant (AV=All for any unitary matrices U,V), lUU:...U-Vitv:...Vll =lU+1Ut..U1-U+1..+U+1..-+1V. (2.2) ≤lU+1Ut.U1-U+1..‖+lU+1E.-V+1e.l (2.3) =lU+1(Ut..U1-..)川+I(Ut+1-V+1)V..l (2.4) =IUe..U-..l+IU+1-+1l (2.5) ≤(t+1)e, (2.6) so the lemma follows by induction ◇
Chapter 2 Efficient universality of quantum circuits Are some universal gate sets better than others? Classically, this is not an issue: the set of possible operations is discrete, so any gate acting on a constant number of bits can be simulated exactly using a constant number of gates from any given universal gate set. But we might imagine that some quantum gates are much more powerful than others. For example, given two rotations about strange axes by strange angles, it may not be obvious how to implement a Hadamard gate, and we might worry that implementing such a gate to high precision could take a very large number of elementary operations, scaling badly with the required precision. Fortunately, this is not the case: a unitary operator that can be realized efficiently with one set of 1- and 2-qubit gates can also be realized efficiently with another such set. In particular, we have the following (see [81, Appendix 3], [38], and [64, Chapter 8]). Theorem 2.1 (Solovay-Kitaev). Fix two universal gate sets that are closed under inverses. Then any t-gate circuit using one gate set can be implemented to precision using a circuit of t· poly(log t ) gates from other set (indeed, there is a classical algorithm for finding this circuit in time t · poly(log t )). Thus, not only are the two gate sets equivalent under polynomial-time reduction, but the running time of an algorithm using one gate set is the same as that using the other gate set up to logarithmic factors. This means that even polynomial quantum speedups are robust with respect to the choice of gate set. 2.1 Subadditivity of errors We begin with the basic fact that errors in the approximation of one quantum circuit by another accumulate at most linearly. Lemma 2.2. Let Ui , Vi be unitary matrices satisfying kUi − Vik ≤ for all i ∈ {1, 2, . . . , t}. Then kUt . . . U2U1 − Vt . . . V2V1k ≤ t. (2.1) Proof. We use induction on t. For t = 1 the lemma is trivial. Now suppose the lemma holds for a particular value of t. Then by the triangle inequality and the fact that the norm is unitarily invariant (kUAV k = kAk for any unitary matrices U, V ), kUt+1Ut . . . U1 − Vt+1Vt . . . V1k = kUt+1Ut . . . U1 − Ut+1Vt . . . V1 + Ut+1Vt . . . V1 − Vt+1Vt . . . V1k (2.2) ≤ kUt+1Ut . . . U1 − Ut+1Vt . . . V1k + kUt+1Vt . . . V1 − Vt+1Vt . . . V1k (2.3) = kUt+1(Ut . . . U1 − Vt . . . V1)k + k(Ut+1 − Vt+1)Vt . . . V1k (2.4) = kUt . . . U1 − Vt . . . V1k + kUt+1 − Vt+1k (2.5) ≤ (t + 1), (2.6) so the lemma follows by induction
Chapter 2.Efficient universality of quantum circuits Thus,in order to simulate a t-gate quantum circuit with total error at most e,it suffices to simulate each individual gate with error at most e/t. 2.2 The group commutator and a net around the identity To simulate an arbitrary individual gate,the strategy is to first construct a very fine net covering a very small ball around the identity using the group commutator, IU,V]:=UVU-1V-1. (2.7) To approximate general unitaries,we will effectively translate them close to the identity. Note that it suffices to consider unitary gates with determinant 1 (i.e.,elements of SU(2))since a global phase is irrelevant.Let Se={U∈SU(2):II-UI‖≤e} (2.8) denote the e-ball around the identity.Given sets I,S SU(2),we say that I is an e-net for S if for any A∈S,there is a U∈T such that‖A-U‖≤e.The following result(to be proved later on)indicates how the group commutator helps us to make a fine net around the identity. Lemma 2.3.If I is an e2-net for Se,then I,Il:={IU,V]:U,VEI}is an O(e)-net for S2. To make an arbitrarily fine net,we apply this idea recursively.But first it is helpful to derive a consequence of the lemma that is more suitable for recursion.We would like to maintain the quadratic relationship between the size of the ball and the quality of the net.If we aim for a k2e3-net (for some constant k), we would like it to apply to arbitrary points in Ske,whereas the lemma only lets us approximate points in Se2.To handle an arbitrary A E Skea/2,we first let W be the closest gate in I to A.For sufficiently small e we have ke3/2 <e,so Skea/C Se,and therefore A E Se.Since I is an e2-net for Se,we have ∥A-Wl≤e2,i.e,lAWt-Il≤2，so AWt∈Se2.Then we can apply the lemma to find U,V∈T such that llAWt-IU,VI =IA-IU,V]WIl s k2e3.In other words,if I is an e2-net for Se,then r,I]r : IU,V]W:U,V,W EI}is a k2e3-net for Skesv2. Now suppose that To is an eo-net for Seo,and let Ii=-1,T-]-1 for all positive integers i.Then T:is an e-net for Swhere ke Solving this recursion gives()() 2.3 Proof of the Solovay-Kitaev Theorem With these tools in hand,we are prepared to establish the main result. Proof of Theorem 2.1.It suffices to consider how to approximate an arbitrary U E SU(2)to precision e by a sequence of gates from a given universal gate set I. First we take products of elements of I to form a new universal gate set To that is an e-net for SU(2), for some sufficiently small constant co.We know this can be done since I is universal.Since co is a constant, the overhead in constructing To is constant. Now we can find Vo∈To such that-Vol‖≤.SinceU-Voll=IUvg-Il,we have UVo∈Se&.If 6 o is sufficiently smal,then6<keg/2-∈1，so UVd∈Se: Since To is an eo-net for SU(2),in particular it is an eo-net for Seo.Thus by the above argument,I1 is an ei-net for S,so we can find Vir such that lVd-vill s<ke/2=e2,i.e.UVoVES. In general,suppose we are given Vo,Vi,...,V-1 such that UVoV...VS Since Ti is an e-net for Se,we can find∈T such that哈yf..Vt1-ll≤.ntum,this implies that UVoV..V∈ Repeating this process t times gives a very good approximation of U by Vi...ViVo:in particular,we have U-Vi...ViVoll<e.Suppose we consider a gate from To to be elementary.(These gates can be implemented using only a constant number of gates from I,so there is a constant factor overhead if we only count gates in I as elementary.)The number of elementary gates needed to implement a gate from Ii is 5
8 Chapter 2. Efficient universality of quantum circuits Thus, in order to simulate a t-gate quantum circuit with total error at most , it suffices to simulate each individual gate with error at most /t. 2.2 The group commutator and a net around the identity To simulate an arbitrary individual gate, the strategy is to first construct a very fine net covering a very small ball around the identity using the group commutator, JU, V K := UV U −1V −1 . (2.7) To approximate general unitaries, we will effectively translate them close to the identity. Note that it suffices to consider unitary gates with determinant 1 (i.e., elements of SU(2)) since a global phase is irrelevant. Let S := {U ∈ SU(2): kI − Uk ≤ } (2.8) denote the -ball around the identity. Given sets Γ, S ⊆ SU(2), we say that Γ is an -net for S if for any A ∈ S, there is a U ∈ Γ such that kA − Uk ≤ . The following result (to be proved later on) indicates how the group commutator helps us to make a fine net around the identity. Lemma 2.3. If Γ is an 2 -net for S, then JΓ, ΓK := {JU, V K : U, V ∈ Γ} is an O( 3 )-net for S 2 . To make an arbitrarily fine net, we apply this idea recursively. But first it is helpful to derive a consequence of the lemma that is more suitable for recursion. We would like to maintain the quadratic relationship between the size of the ball and the quality of the net. If we aim for a k 2 3 -net (for some constant k), we would like it to apply to arbitrary points in Sk3/2 , whereas the lemma only lets us approximate points in S 2 . To handle an arbitrary A ∈ Sk3/2 , we first let W be the closest gate in Γ to A. For sufficiently small we have k3/2 < , so Sk3/2 ⊂ S, and therefore A ∈ S. Since Γ is an 2 -net for S, we have kA − Wk ≤ 2 , i.e., kAW† − Ik ≤ 2 , so AW† ∈ S 2 . Then we can apply the lemma to find U, V ∈ Γ such that kAW† − JU, V Kk = kA − JU, V KWk ≤ k 2 3 . In other words, if Γ is an 2 -net for S, then JΓ, ΓKΓ := {JU, V KW : U, V, W ∈ Γ} is a k 2 3 -net for Sk3/2 . Now suppose that Γ0 is an 2 0 -net for S0 , and let Γi := JΓi−1, Γi−1KΓi−1 for all positive integers i. Then Γi is an 2 i -net for Si , where i = k3/2 i−1 . Solving this recursion gives i = (k 2 0) (3/2)i /k2 . 2.3 Proof of the Solovay-Kitaev Theorem With these tools in hand, we are prepared to establish the main result. Proof of Theorem 2.1. It suffices to consider how to approximate an arbitrary U ∈ SU(2) to precision by a sequence of gates from a given universal gate set Γ. First we take products of elements of Γ to form a new universal gate set Γ0 that is an 2 0 -net for SU(2), for some sufficiently small constant 0. We know this can be done since Γ is universal. Since 0 is a constant, the overhead in constructing Γ0 is constant. Now we can find V0 ∈ Γ0 such that kU − V0k ≤ 2 0 . Since kU − V0k = kUV † 0 − Ik, we have UV † 0 ∈ S 2 0 . If 0 is sufficiently small, then 2 0 < k3/2 0 = 1, so UV † 0 ∈ S1 . Since Γ0 is an 2 0 -net for SU(2), in particular it is an 2 0 -net for S0 . Thus by the above argument, Γ1 is an 2 1 -net for S1 , so we can find V1 ∈ Γ1 such that kUV † 0 − V1k ≤ 2 1 < k3/2 1 = 2, i.e., UV † 0 V † 1 ∈ S2 . In general, suppose we are given V0, V1, . . . , Vi−1 such that UV † 0 V † 1 . . . V † i−1 ∈ Si . Since Γi is an 2 i -net for Si , we can find Vi ∈ Γi such that kUV † 0 V † 1 . . . V † i−1 − Vik ≤ 2 i . In turn, this implies that UV † 0 V † 1 . . . V † i ∈ Si+1 . Repeating this process t times gives a very good approximation of U by Vt . . . V1V0: in particular, we have kU − Vt . . . V1V0k ≤ 2 t . Suppose we consider a gate from Γ0 to be elementary. (These gates can be implemented using only a constant number of gates from Γ, so there is a constant factor overhead if we only count gates in Γ as elementary.) The number of elementary gates needed to implement a gate from Γi is 5i
2.4.Proof of Lemma 2.3 9 so the total number of gates in the approximation is-(5+1-1)/4-0(5).To achieve an overall error at most e,we need =((k2e)(3/2)/k2)2ei.e., t 号log(k4e) (2.9) 2 log(k2co) Thus the number of gates used is O(log"1)where v=log5/log At this point,it may not be clear that the approximation can be found quickly,since I;contains a large number of points,so we need to be careful about how we find a good approximation Vi E Ti of UVoVi...V1.However,by constructing the approximation recursively,it can be shown that the running time of this procedure is poly(log).It will be clearer how to do this after we prove the lemma,but we leave the details as an exercise. 口 2.4 Proof of Lemma 2.3 It remains to prove the lemma.A key idea is to move between the Lie group SU(2)and its Lie algebra,i.e., the Hamiltonians generating these unitaries.In particular,we can represent any ASU(2)as A where aER3 and =(o,u:)is a vector of Pauli matrices.Note that we can choose llall without loss of generality. In the proof,the following basic facts about SU(2)will be useful. (i)IlI-eit-ll 2sin Iig=llall +o(llall3) ()if,a≤e then e6d-e运=I6-a+O(e) (i)[6.,c.=2i(6×· (iv)Ille4-,ese]-e-5-=O(1I(+Ill)) Here the big-O notation is with respect to llall0 in (i)and with respect to oll,llcll0 in (iv). Proof of Lemma 2.3.Let A S2.Our goal is to find U,V EI such that lA-IU,V]l =O(e3). Choose aR3 such that A=eia-5.Since A S2,by (i)we can choose d so that llall =O(e2) Then choose b,c R3 such that -2b x c=a.We can choose these vectors to be orthogonal and of equal length,so that=llel=vlall/2=O(e).Let B=ei-and C=e.Then the only difference between A and [B,C]is the difference between the commutator and the group commutator,which is O(e3)by (iv). However,we need to choose points from the net I.So let U=ei be the closest element of I to B. and let V=ei be the closest element of I to C.Since I is an e2-net for Se,we have U-Bll<e2 and Iv -Clls e2,so in particular (by (ii)),llbll =O(e2)and lli-cll =o(e2). Now by the triangle inequality,we have ‖A-U,VIl≤‖A-e2a(ax0d‖+le2(a×0d-[U,VI. (2.10) For the first term,using (ii),we have IA-e2i(x=lle2i(6xa)0-e2i(x (2.11) ≤2l6×c-立×训 (2.12) =2l(6-立+动）×(-i+)-i× (2.13) =2l(6-)×(c-动+(6-)×元+t×(c-川 (2.14) =O(3). (2.15) For the second term,using (iii)and (iv)gives lle2i(x)--IU,V]ll lle-l-.--U,v]ll =o(e3). (2.16) The lemma follows. ◇ Note that it is possible to improve the construction somewhat over the version described above.Further- more,it can be generalized to SU(N)for arbitrary N.In general,the cost is exponential in N2,but for any fixed N this is just a constant
2.4. Proof of Lemma 2.3 9 so the total number of gates in the approximation is Pt i=0 5 i = (5t+1 − 1)/4 = O(5t ). To achieve an overall error at most , we need 2 t = ((k 2 0) (3/2)t /k2 ) 2 ≤ , i.e., 3 2 t > 1 2 log(k 4 ) log(k 20) . (2.9) Thus the number of gates used is O(logν 1 ) where ν = log 5/ log 3 2 . At this point, it may not be clear that the approximation can be found quickly, since Γi contains a large number of points, so we need to be careful about how we find a good approximation Vi ∈ Γi of UV † 0 V † 1 . . . V † i−1 . However, by constructing the approximation recursively, it can be shown that the running time of this procedure is poly(log 1 ). It will be clearer how to do this after we prove the lemma, but we leave the details as an exercise. 2.4 Proof of Lemma 2.3 It remains to prove the lemma. A key idea is to move between the Lie group SU(2) and its Lie algebra, i.e., the Hamiltonians generating these unitaries. In particular, we can represent any A ∈ SU(2) as A = e i~a·~σ , where ~a ∈ R 3 and ~σ = (σx, σy, σz) is a vector of Pauli matrices. Note that we can choose k~ak ≤ π without loss of generality. In the proof, the following basic facts about SU(2) will be useful. (i) kI − e i~a·~σk = 2 sin k~ak 2 = k~ak + O(k~ak 3 ) (ii) if k ~bk, k~ck ≤ then ke i~b·~σ − e i~c·~σk = k ~b − ~ck + O( 3 ) (iii) [ ~b · ~σ, ~c · ~σ] = 2i( ~b × ~c) · ~σ (iv) kJe i~b·~σ, ei~c·~σK − e −[~b·~σ,~c·~σ]k = O(k ~bkk~ck(k ~bk + k~ck)) Here the big-O notation is with respect to k~ak → 0 in (i) and with respect to k ~bk, k~ck → 0 in (iv). Proof of Lemma 2.3. Let A ∈ S 2 . Our goal is to find U, V ∈ Γ such that kA − JU, V Kk = O( 3 ). Choose ~a ∈ R 3 such that A = e i~a·~σ. Since A ∈ S 2 , by (i) we can choose ~a so that k~ak = O( 2 ). Then choose ~b, ~c ∈ R 3 such that −2 ~b ×~c = ~a. We can choose these vectors to be orthogonal and of equal length, so that k ~bk = k~ck = p k~ak/2 = O(). Let B = e i~b·~σ and C = e i~c·~σ. Then the only difference between A and JB, CK is the difference between the commutator and the group commutator, which is O( 3 ) by (iv). However, we need to choose points from the net Γ. So let U = e i~u·~σ be the closest element of Γ to B, and let V = e i~v·~σ be the closest element of Γ to C. Since Γ is an 2 -net for S, we have kU − Bk ≤ 2 and kV − Ck ≤ 2 , so in particular (by (ii)), k~u −~bk = O( 2 ) and k~v − ~ck = O( 2 ). Now by the triangle inequality, we have kA − JU, V Kk ≤ kA − e 2i(~u×~v)·~σk + ke 2i(~u×~v)·~σ − JU, V Kk. (2.10) For the first term, using (ii), we have kA − e 2i(~u×~v)·~σk = ke 2i(~b×~c)·~σ − e 2i(~u×~v)·~σk (2.11) ≤ 2k ~b × ~c − ~u × ~vk (2.12) = 2k( ~b − ~u + ~u) × (~c − ~v + ~v) − ~u × ~vk (2.13) = 2k( ~b − ~u) × (~c − ~v) + (~b − ~u) × ~v + ~u × (~c − ~v)k (2.14) = O( 3 ). (2.15) For the second term, using (iii) and (iv) gives ke 2i(~u×~v)·~σ − JU, V Kk = ke −[~u·~σ,~v·~σ] − JU, V Kk = O( 3 ). (2.16) The lemma follows. Note that it is possible to improve the construction somewhat over the version described above. Furthermore, it can be generalized to SU(N) for arbitrary N. In general, the cost is exponential in N2 , but for any fixed N this is just a constant
10 Chapter 2.Efficient universality of quantum circuits
10 Chapter 2. Efficient universality of quantum circuits