Chapter 3 Quantum circuit synthesis over Clifford +T As we discussed in Chapter 2,the Solovay-Kitaev Theorem tells us that we can convert between gate sets with overhead that is only poly(log(1/e)).However,the overhead may not be that small in practice (we upper bounded the power of the log by log5/log3.97),and it is natural to ask if we can do better.A counting argument shows that the best possible exponent is 1(see [66]and [81,Section 4.5.4]).Can we get close to this lower bound-ideally while retaining a fast algorithm? In general,no such result is known (even if we do not require a fast algorithm).However,there are strong circuit synthesis results for particular gate sets with nice structure.In particular,one can perform fast,nearly-optimal synthesis for the set of single-qubit Clifford+T circuits.Not only does it admit fast synthesis,but this gate set is also the most common choice for fault-tolerant quantum computation,so it is likely to be relevant in practice. To understand the synthesis of Clifford+T circuits,we focus here on the problem of exactly expressing a given unitary operation over that gate set,assuming such a representation is possible.This result can be extended to give an algorithm for approximately synthesizing arbitrary single-qubit gates,although the details are beyond the scope of this lecture.(Note that some of these ideas can also be applied to the synthesis of multi-qubit circuits,but that is also beyond our scope.) 3.1 Converting to Matsumoto-Amano normal form An algorithm for exact synthesis of Clifford+T circuits was first presented in [65].However,our presentation here is based on a simpler analysis [48]that uses a normal form for such circuits introduced by Matsumoto and Amano [77]. The single-qubit Clifford group C=(H,S,w)is generated by the Hadamard gate H,the phase gate S, and the phase w:=eix/4,where =G) =(6) s==(（69) (3.1) By adding the T gate,we get a universal gate set-in other words,the set (H,T,w)is dense in U(2).We call any unitary operation that can be represented exactly over this gate set a Clifford+T operation. Clearly,any single-qubit Clifford+T operation M can be written in the form M=CnTCn-1T…CTCo (3.2） where Co,...,CnEC.Our goal is to rewrite such an expression into a simpler form
Chapter 3 Quantum circuit synthesis over Clifford+T As we discussed in Chapter 2, the Solovay-Kitaev Theorem tells us that we can convert between gate sets with overhead that is only poly(log(1/)). However, the overhead may not be that small in practice (we upper bounded the power of the log by log 5/ log 3 2 ≈ 3.97), and it is natural to ask if we can do better. A counting argument shows that the best possible exponent is 1 (see [66] and [81, Section 4.5.4]). Can we get close to this lower bound—ideally while retaining a fast algorithm? In general, no such result is known (even if we do not require a fast algorithm). However, there are strong circuit synthesis results for particular gate sets with nice structure. In particular, one can perform fast, nearly-optimal synthesis for the set of single-qubit Clifford+T circuits. Not only does it admit fast synthesis, but this gate set is also the most common choice for fault-tolerant quantum computation, so it is likely to be relevant in practice. To understand the synthesis of Clifford+T circuits, we focus here on the problem of exactly expressing a given unitary operation over that gate set, assuming such a representation is possible. This result can be extended to give an algorithm for approximately synthesizing arbitrary single-qubit gates, although the details are beyond the scope of this lecture. (Note that some of these ideas can also be applied to the synthesis of multi-qubit circuits, but that is also beyond our scope.) 3.1 Converting to Matsumoto-Amano normal form An algorithm for exact synthesis of Clifford+T circuits was first presented in [65]. However, our presentation here is based on a simpler analysis [48] that uses a normal form for such circuits introduced by Matsumoto and Amano [77]. The single-qubit Clifford group C = hH, S, ωi is generated by the Hadamard gate H, the phase gate S, and the phase ω := e iπ/4 , where H := 1 √ 2 1 1 1 −1 T := 1 0 0 ω S := T 2 = 1 0 0 i . (3.1) By adding the T gate, we get a universal gate set—in other words, the set hH, T, ωi is dense in U(2). We call any unitary operation that can be represented exactly over this gate set a Clifford+T operation. Clearly, any single-qubit Clifford+T operation M can be written in the form M = CnT Cn−1T · · · C1T C0 (3.2) where C0, . . . , Cn ∈ C. Our goal is to rewrite such an expression into a simpler form
12 Chapter 3.Quantum circuit synthesis over Clifford+T Let S:=(S,X,w)<C.Any element of S can be pushed through T(say,to the right),since we have ST=TS (3.3) XT=w-ITXS (3.4) WT=Tw. (3.5) Thus we can assume C1,...,Cn-1 S.(In some cases,pushing elements of S to the right might cause two T gates to merge into SEC;we take n to be the number of Clifford gates after any such cancellations.) An explicit calculation shows that S=64,whereas C=192.Since I,H,and SH are in different left cosets of S in C,they can be chosen as the three coset representatives,and we can write every element of the Clifford group in the form HS,where HE{I,H,SH}and SE S.Similarly,every element of C\S can be written in the same form,where HE[H,SH.Thus we can write M in the form M HnSnTHn-1Sn-1T...HiSTCo (3.6) where Co∈C,Hi,.,Hn-1∈{H,SH},Hn∈{I,H,SH}andS1,,Sn∈S. Now we can further simplify this expression by again pushing elements of S to the right.We have already seen that such operators can be pushed through T gates,giving new elements of S.But furthermore,they can also be pushed through elements of H.SA,since SH∈{H,SH} SSH=HX (3.7） XH=HZ=HS2 XSH=SHY =SH(w2XS2) (3.8) WH=Hw WSH SHw. (3.9) After applying these rules,we are left with an expression of the form M=HkTHk.-1T…H1TC0 (3.10) where H1,...,Hk-1E[H,H)and Hk E[I,H,SH).(Note that we can have k<n,since again we could find cancellations as we push gates to the right.)This expression is now in Matsumoto-Amano (MA)normal form.In terms of regular expressions,we can write this form as (s|T)(HT SHT)*C,where s denotes the empty string. Since the above argument is constructive,it also gives an algorithm for converting circuits to MA normal form.A naive implementation would take time O(n2),since we might make a pass through O(n)gates to find a simplification,and we might have to repeat this O(n)times before reaching MA normal form.However, we can reduce to MA normal form in linear time by simplifying the given circuit gate-by-gate,maintaining MA normal form along the way.If N is in MA normal form and CEC,then NC can be reduced to MA normal form in constant time(we simply combine the rightmost two Clifford operators).On the other hand, case analysis shows that reducing NT to MA normal form only requires updating the rightmost 5 gates,so it can also be reduced in constant time.Overall,this approach takes O(n)steps,each taking time O(1),for a total running time of O(n). An important parameter of a Clifford+T circuit is its T-count,which is simply the number of T gates it contains.Clearly there is a way of writing any Clifford+T circuit in MA normal form such that the T-count is minimal,simply because the reduction procedure described above never increases the T-count. 3.2 Uniqueness of Matsumoto-Amano normal form In fact,the MA normal form is unique,so the procedure described above always produces a circuit with minimal T-count.Furthermore,the proof of this helps to develop an algebraic characterization of Clifford+T unitaries that facilitates approximate synthesis. Given a single-qubit unitary U,let U denote its Bloch sphere representation.If U(xX+yY+zZ)Ut= rX+yy+z,them0(但）)=(），nd thisreionptodee0 by linearity.We have 0 0 0-10 -10 00 i= 0 √2 (3.11) 00/ 0 01 02
12 Chapter 3. Quantum circuit synthesis over Clifford+T Let S := hS, X, ωi ≤ C. Any element of S can be pushed through T (say, to the right), since we have ST = T S (3.3) XT = ω −1T XS (3.4) ωT = T ω. (3.5) Thus we can assume C1, . . . , Cn−1 ∈ S / . (In some cases, pushing elements of S to the right might cause two T gates to merge into S ∈ C; we take n to be the number of Clifford gates after any such cancellations.) An explicit calculation shows that |S| = 64, whereas |C| = 192. Since I, H, and SH are in different left cosets of S in C, they can be chosen as the three coset representatives, and we can write every element of the Clifford group in the form H˜S˜, where H˜ ∈ {I, H, SH} and S˜ ∈ S. Similarly, every element of C \ S can be written in the same form, where H˜ ∈ {H, SH}. Thus we can write M in the form M = HnSnT Hn−1Sn−1T · · · H1S1T C0 (3.6) where C0 ∈ C, H1, . . . , Hn−1 ∈ {H, SH}, Hn ∈ {I, H, SH} and S1, . . . , Sn ∈ S. Now we can further simplify this expression by again pushing elements of S to the right. We have already seen that such operators can be pushed through T gates, giving new elements of S. But furthermore, they can also be pushed through elements of {H, SH}, since SH ∈ {H, SH} SSH = HX (3.7) XH = HZ = HS2 XSH = SHY = SH(ω 2XS2 ) (3.8) ωH = Hω ωSH = SHω. (3.9) After applying these rules, we are left with an expression of the form M = HkT Hk−1T · · · H1T C0 (3.10) where H1, . . . , Hk−1 ∈ {H, SH} and Hk ∈ {I, H, SH}. (Note that we can have k < n, since again we could find cancellations as we push gates to the right.) This expression is now in Matsumoto-Amano (MA) normal form. In terms of regular expressions, we can write this form as (ε | T) (HT | SHT) ∗ C, where ε denotes the empty string. Since the above argument is constructive, it also gives an algorithm for converting circuits to MA normal form. A naive implementation would take time O(n 2 ), since we might make a pass through O(n) gates to find a simplification, and we might have to repeat this O(n) times before reaching MA normal form. However, we can reduce to MA normal form in linear time by simplifying the given circuit gate-by-gate, maintaining MA normal form along the way. If N is in MA normal form and C ∈ C, then NC can be reduced to MA normal form in constant time (we simply combine the rightmost two Clifford operators). On the other hand, case analysis shows that reducing NT to MA normal form only requires updating the rightmost 5 gates, so it can also be reduced in constant time. Overall, this approach takes O(n) steps, each taking time O(1), for a total running time of O(n). An important parameter of a Clifford+T circuit is its T-count, which is simply the number of T gates it contains. Clearly there is a way of writing any Clifford+T circuit in MA normal form such that the T-count is minimal, simply because the reduction procedure described above never increases the T-count. 3.2 Uniqueness of Matsumoto-Amano normal form In fact, the MA normal form is unique, so the procedure described above always produces a circuit with minimal T-count. Furthermore, the proof of this helps to develop an algebraic characterization of Clifford+T unitaries that facilitates approximate synthesis. Given a single-qubit unitary U, let Uˆ denote its Bloch sphere representation. If U(xX + yY + zZ)U † = x 0X + y 0Y + z 0Z, then Uˆ x y z = x 0 y 0 z 0 , and this relationship serves to define Uˆ by linearity. We have Hˆ = 0 0 1 0 −1 0 1 0 0 Sˆ = 0 −1 0 1 0 0 0 0 1 Tˆ = 1 √ 2 1 −1 0 1 1 0 0 0 √ 2 . (3.11)
3.3.Algebraic characterization of Clifford+T unitaries 13 These generators belong to the ringa,ZN),so clearly the Bloch sphere representation of any Clifford+T operator has entries in this ring. We say that k∈Nis a denominator exponent of x∈Z☑lifV2x∈Zv-{a+bv2:a,b∈z}.We call the smallest such k the least denominator exponent of x. Define the parity ofx∈Z√②，denoted p(z),such that p(a+bV②)is the parity of a(i.e,0 if a is even and 1 if a is odd).If k is a denominator exponent for define the k-parity of as p():-p(). Observe that the Bloch sphere representation of a Clifford operator is a signed permutation matrix,so it has denominator exponent 0,and its parity (applied to the matrix elementwise)is a permutation. We can define an equivalence relation on(k-)parity matrices of Bloch sphere representations of Clifford+T operators such that they are equivalent if they differ by right-multiplication by the parity matrix of a Clifford operator (in other words,by permutation of the columns).Now consider what happens to the k-parity matrix of the operator as we proceed through the MA normal form,where we increase k by one every time we multiply by a T gate.A simple calculation shows that transitions between the resulting equivalence classes are as follows: T C 0 0 (3.12) 0 0 0 0 1 1 0 H Here the matrices are representatives of equivalence classes of k-parity matrices and the labels on the arrows show what gates induce the transitions.We have k=0 at the leftmost(starting)matrix,and the value of k is increased by 1 along each thick arrow.For example,for the transitions under a T gate,we have a11+b11V2a12+b12V2 a13+b13V2 0 a11+b11V2a12+b12V2 a13+b13V② a21+b21V2 a22+b22V2a23+b23V2 0 21+b21vV2a22+i2V5 a23+b23V2 a31+b31V2 a32+b32V2 a33+b33V2 0 v② \a31+bg1V2a32+b32V2 a33+b33V2 (a11-a21）+(b11-b21)V2(a12-a22)+(b12-b22)V2 (a13-a23）+(b13-b23)V② V2 (a11+a21)+(b11+b21)V2(a12+a22）+(b12+b22)v2 (a13+a23)+(b13+b23)V2 (3.13) 2bg1+a31V2 2b32+ag2V2 2b33+ag3V2 At the leftmost matrix,we have a11,a22,a33 odd and aij even for ij.Clearly the resulting 1-parity matrix is of the indicated form.Similar calculations verify the other transitions. From this transition diagram,we can easily see that the MA normal form is unique.If we remain at the leftmost matrix,the operation is Clifford.On the other hand,if we end at one of the next three matrices to the right,the leftmost syllable of M is T,HT,or SHT,respectively.Given a matrix M,let k be its least denominator exponent.By computing p(M)and determining which equivalence class it belongs to,we can determine the final syllable of its MA normal form.By induction,the entire MA normal form is determined. Note that this also shows that the least denominator exponent of M is its minimal T-count. This argument also implies an algorithm for exact synthesis given the matrix of a Clifford+T operation (instead of some initial Clifford+T circuit).We simply convert to the Bloch matrix representation,compute the least denominator exponent k,use pk(M)to determine the leftmost syllable of the MA normal form,and recurse until we are left with a Clifford operation.In this algorithm,the number of arithmetic operations performed is O(k). 3.3 Algebraic characterization of Clifford+T unitaries We can use the ideas of the previous section to give an algebraic characterization of Clifford+T operations. Specifically,a matrix UE SO(3)is the Bloch sphere representation of a Clifford+T unitary if and only if its
3.3. Algebraic characterization of Clifford+T unitaries 13 These generators belong to the ring Z[ √ 1 2 ] = { a+b √ 2 √ 2 k : a, b ∈ Z, k ∈ N}, so clearly the Bloch sphere representation of any Clifford+T operator has entries in this ring. We say that k ∈ N is a denominator exponent of x ∈ Z[ √ 1 2 ] if √ 2 k x ∈ Z[ √ 2] = {a + b √ 2 : a, b ∈ Z}. We call the smallest such k the least denominator exponent of x. Define the parity of x ∈ Z[ √ 2], denoted p(x), such that p(a+b √ 2) is the parity of a (i.e., 0 if a is even and 1 if a is odd). If k is a denominator exponent for x, define the k-parity of x ∈ Z[ √ 1 2 ] as pk(x) := p( √ 2 k x). Observe that the Bloch sphere representation of a Clifford operator is a signed permutation matrix, so it has denominator exponent 0, and its parity (applied to the matrix elementwise) is a permutation. We can define an equivalence relation on (k-)parity matrices of Bloch sphere representations of Clifford+T operators such that they are equivalent if they differ by right-multiplication by the parity matrix of a Clifford operator (in other words, by permutation of the columns). Now consider what happens to the k-parity matrix of the operator as we proceed through the MA normal form, where we increase k by one every time we multiply by a T gate. A simple calculation shows that transitions between the resulting equivalence classes are as follows: 1 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 C T H T S T (3.12) Here the matrices are representatives of equivalence classes of k-parity matrices and the labels on the arrows show what gates induce the transitions. We have k = 0 at the leftmost (starting) matrix, and the value of k is increased by 1 along each thick arrow. For example, for the transitions under a T gate, we have a11 + b11 √ 2 a12 + b12 √ 2 a13 + b13 √ 2 a21 + b21 √ 2 a22 + b22 √ 2 a23 + b23 √ 2 a31 + b31 √ 2 a32 + b32 √ 2 a33 + b33 √ 2 7→ 1 √ 2 1 −1 0 1 1 0 0 0 √ 2 a11 + b11√ 2 a12 + b12√ 2 a13 + b13√ 2 a21 + b21√ 2 a22 + b22√ 2 a23 + b23√ 2 a31 + b31√ 2 a32 + b32√ 2 a33 + b33√ 2 = 1 √ 2 (a11 − a21) + (b11 − b21) √ 2 (a12 − a22) + (b12 − b22) √ 2 (a13 − a23) + (b13 − b23) √ 2 (a11 + a21) + (b11 + b21) √ 2 (a12 + a22) + (b12 + b22) √ 2 (a13 + a23) + (b13 + b23) √ 2 2b31 + a31√ 2 2b32 + a32√ 2 2b33 + a33√ 2 . (3.13) At the leftmost matrix, we have a11, a22, a33 odd and aij even for i 6= j. Clearly the resulting 1-parity matrix is of the indicated form. Similar calculations verify the other transitions. From this transition diagram, we can easily see that the MA normal form is unique. If we remain at the leftmost matrix, the operation is Clifford. On the other hand, if we end at one of the next three matrices to the right, the leftmost syllable of M is T, HT, or SHT, respectively. Given a matrix M, let k be its least denominator exponent. By computing pk(M) and determining which equivalence class it belongs to, we can determine the final syllable of its MA normal form. By induction, the entire MA normal form is determined. Note that this also shows that the least denominator exponent of M is its minimal T-count. This argument also implies an algorithm for exact synthesis given the matrix of a Clifford+T operation (instead of some initial Clifford+T circuit). We simply convert to the Bloch matrix representation, compute the least denominator exponent k, use pk(M) to determine the leftmost syllable of the MA normal form, and recurse until we are left with a Clifford operation. In this algorithm, the number of arithmetic operations performed is O(k). 3.3 Algebraic characterization of Clifford+T unitaries We can use the ideas of the previous section to give an algebraic characterization of Clifford+T operations. Specifically, a matrix Uˆ ∈ SO(3) is the Bloch sphere representation of a Clifford+T unitary if and only if its
14 Chapter 3.Quantum circuit synthesis over Clifford+T entries are in Z[As noted above,the "only if"part is trivial;it remains to show that any such matrix corresponds to a Clifford+T operation. The proof of this statement uses the orthogonality condition on U to characterize the possible values of p&(U)(specifically,to show it is one of the forms in the above transition diagram,up to permutation of the columns),and then shows that the least denominator can always be reduced by multiplying from the left by the inverse of a matrix from [T,HT,SHT.The proofs of these statements are straightforward,but involve some explicit calculation and case analysis;see 48 for details. As a simple corollary,we can establish that U is a Clifford+T unitary if and only if its entries are in Again the"onlyif"direction is trivial.For the other direction,simply observe that if the entries of U are in],then the entries of are in Z and we can apply the characterization of Bloch matrices of Clifford+T unitaries.Note that this only determines the actual matrix up to a phase,but this phase must be a power of w,so indeed the original U must be a Clifford+T unitary. In summary,we have seen that any Clifford+T unitary can be synthesized into a Clifford+T circuit,with the minimal number of T gates (equal to the least denominator exponent of its Bloch sphere representation), in time linear in the T-count. 3.4 From exact to approximate synthesis The methods described above can only be directly applied if the unitary operation in question can be performed exactly using Clifford+T gates.However,the methods can be adapted to perform approximate synthesis of arbitrary gates.The basic idea is to"round"a given unitary to a nearby element of i]and then to synthesize that operation over Clifford+T.This is far from straightforward since a naive rounding procedure(say,rounding the matrix elementwise)will generally yield an operation that is not unitary,and thus not amenable to synthesis.However,by a careful rounding procedure,we can produce a nearby unitary matrix over,and thus produce an e-approximation of length O(log(1/e))
14 Chapter 3. Quantum circuit synthesis over Clifford+T entries are in Z[ √ 1 2 ]. As noted above, the “only if” part is trivial; it remains to show that any such matrix corresponds to a Clifford+T operation. The proof of this statement uses the orthogonality condition on Uˆ to characterize the possible values of pk(Uˆ) (specifically, to show it is one of the forms in the above transition diagram, up to permutation of the columns), and then shows that the least denominator can always be reduced by multiplying from the left by the inverse of a matrix from {T, HT, SHT}. The proofs of these statements are straightforward, but involve some explicit calculation and case analysis; see [48] for details. As a simple corollary, we can establish that U is a Clifford+T unitary if and only if its entries are in Z[ √ 1 2 , i] Again the “only if” direction is trivial. For the other direction, simply observe that if the entries of U are in Z[ √ 1 2 , i], then the entries of Uˆ are in Z[ √ 1 2 ], and we can apply the characterization of Bloch matrices of Clifford+T unitaries. Note that this only determines the actual matrix up to a phase, but this phase must be a power of ω, so indeed the original U must be a Clifford+T unitary. In summary, we have seen that any Clifford+T unitary can be synthesized into a Clifford+T circuit, with the minimal number of T gates (equal to the least denominator exponent of its Bloch sphere representation), in time linear in the T-count. 3.4 From exact to approximate synthesis The methods described above can only be directly applied if the unitary operation in question can be performed exactly using Clifford+T gates. However, the methods can be adapted to perform approximate synthesis of arbitrary gates. The basic idea is to “round” a given unitary to a nearby element of Z[ √ 1 2 , i] and then to synthesize that operation over Clifford+T. This is far from straightforward since a naive rounding procedure (say, rounding the matrix elementwise) will generally yield an operation that is not unitary, and thus not amenable to synthesis. However, by a careful rounding procedure, we can produce a nearby unitary matrix over Z[ √ 1 2 , i], and thus produce an -approximation of length O(log(1/))
Part II Quantum algorithms for algebraic problems
Part II Quantum algorithms for algebraic problems