Efficient synthesis of repeat-until-success circuits in clifford + T basis

Repeat-Until-Success (RUS) circuits are compiled in a Clifford+T basis by selecting a suitable cyclotomic integer approximation of a target rotation so that the rotation is approximated within a predetermined precision. The cyclotomic integer approximation is randomly modified until a modified value can be expanded into a single-qubit unitary matrix by solving one or more norm equations. The matrix is then expanded into a two-qubit unitary matrix of special form, which is then decomposed into an optimal two-qubit Clifford+T circuit. A two-qubit RUS circuit using a primary qubit and an ancillary qubit is then obtained based on the latter decomposition. An alternate embodiment is disclosed that keeps the total T-depth of the derived circuit small using at most 3 additional ancilla qubits. Arbitrary unitary matrices defined over the cyclotomic field of 8th roots of unity are implemented with RUS circuits.

FIELD

The disclosure pertains to decomposition of quantum circuits in a Clifford+T basis.

BACKGROUND

One objective of compilation systems for quantum computing is the decomposition of any required single-qubit unitary operation into sets of gates that can implement arbitrary single-qubit unitary operations. Typically, gate sets that provide fault tolerance are preferred. One gate set that has been identified is referred to as the {H,T} gate set that includes the Hadamard gate and the T-gate. This gate set is universal for single-qubit unitaries (can realize arbitrary single-qubit unitary operations to required precision) and is fault tolerant.

The {H,T} gate set has been used to implement circuits, but historically resulting circuits had excessive cost. Significant progress has been made in the last two years in reducing the cost, but there is ample room for improvement. It has been shown that adding ancillary qubit(s), a two-qubit gate (for example, CNOT or CZ), and measurement operations to the gate set can result in lower cost computation. One approach is based on so-called Repeat-Until-Success (RUS) circuits in which an intended output state can be identified using a measurement of an ancillary qubit and a sequence of Clifford+T gates, where the Clifford+T gate set includes the two-qubit CNOT gate (or CZ gate), the Hadamard gate, and the T-gate. Paetznick and Svore, “Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries,” available at http://arxiv.org/abs/1311.1074, describe methods for implementing rotations using the Clifford+T gates in combination with measurements and classical feedback. The RUS method achieves superior computation cost. However, these methods are based on an exhaustive search and require exponential runtime. Thus, these methods are limited in achievable precision and hence in applicability.

SUMMARY

Methods and apparatus are disclosed that permit decomposition of quantum computational circuits such as rotation gates into series of Clifford+T gates using one or more ancillary qubits. Typically, a single-qubit unitary is obtained by finding a cyclotomic integer z such that z*/z is rational and corresponds to the selected rotation within a desired precision. The cyclotomic integer z is then modified so as to solve a norm equation, and the modified or scaled value of z is used to define the single-qubit unitary in the Clifford+T basis. This intermediate single-qubit unitary is then expanded into a larger two-qubit unitary which serves as the basis of the circuit design. A Clifford+T decomposition of this two-qubit unitary is arranged as a Repeat-Until-Success (RUS) circuit in which a state associated with an ancillary qubit is measured to determine if the intended circuit operation has been realized on a primary qubit. If not, the primary qubit is restored to an initial state, and RUS circuit operations are repeated.

The foregoing and other features, and advantages of the invention will become more apparent from the following detailed description, which proceeds with reference to the accompanying figures.

DETAILED DESCRIPTION

In some examples, the terms “unitary” or “unitary matrix” are used to refer to functions performed by quantum circuits that can be implemented in a variety of ways. In the following description, such matrices are also referred to as circuits for convenient description. Some commonly used quantum gates corresponding to single-qubit operators S, X, Y, and Z can be represented as:

Compilation of high-level quantum algorithms into lower-level fault-tolerant circuits is a critical component of quantum computation. One fault-tolerant universal quantum basis, referred to as the Clifford+T basis, consists of the two-qubit Controlled-NOT gate (CNOT), and two single-qubit gates, the Hadamard gate (H) and the T-gate T. The operation of these gates can be written as:

CNOT=(1000010000010010)H=12⁡[111-1],andT=[100eⅈ⁢π4].
These circuits can be combined to implement an arbitrary unitary operation. A one-qubit unitary operator can be expressed as a unitary 2×2 matrix with complex elements:

[ab-b*a*],
wherein a and b are complex numbers and the notation “x*” indicates a complex conjugate of x. Such a unitary 2×2 matrix U has the following property:

U†⁢U=UU†=I=[1001],⁢whereinU†=[a*-bb*a].
The adjoint U′ of a unitary matrix U is the complex-conjugate transpose of the unitary U and is the inverse of U, denoted U−1.

While circuits can be compiled using the Clifford+T basis, compilation using conventional techniques as in Paetznick and Svore can require exhaustive searches and exponential classical runtimes. Alternative compilation methods, apparatus, and associated circuits based on the Clifford+T basis are disclosed herein. In typical examples described below, a few ancillary qubits and a few measurement operations are used along with purely unitary circuits.

A unitary operation is representable by a Clifford+T circuit if and only if the unitary operation is represented by a unitary matrix of the form 1/√{square root over (2)}kU where U is a matrix with elements from □[ω] and k is a non-negative integer. □[ω] is a ring of cyclotomic integers of order 8, and consists of all numbers of the form aω3+bω2+cω+d wherein a, b, c, d are arbitrary integers and ω=eiπ/4. One choice for a basis of □[ω] is {ω3ω2,ω,1}. To be unitary, UU†=2kId, where Id is an identity matrix. A matrix of such form can be represented as an asymptotically optimal Clifford+T circuit using at most two ancillary qubits. In other representations, no ancillary qubits are required for a single-qubit subject unitary or when Det(1/√{square root over (2)}kU)=1. Any single-qubit circuit in the {H,T} basis can be expressed as a sequence of syllables of the form T−kHTk, k∈□ and at most one additional single-qubit Clifford gate. Any single-qubit unitary operation U can be decomposed into a sequence of axial rotations U=Rz(α) Rx(β) Rz(γ) in accordance with the Euler angle decomposition of U. Thus any single-qubit unitary operation can be decomposed using the techniques presented herein.

T-gates are much harder to perform in a fault-tolerant manner than any of the Clifford gates. In most architectures, a T-gate requires a so-called fault-tolerant “magic state” which is more than an order of magnitude harder to distill for typical quantum error correcting codes than a fault-tolerant Hadamard gate H. The T-gate can be up to two orders of magnitude harder to perform than a CNOT gate or any of the Pauli gates. Accordingly, a cost measure for a Clifford+T circuit (a T-count) is a number of T-gates in a circuit and this cost measure in used in the following description.

With reference toFIG. 1, a compilation method100is provided that synthesizes a repeat-until-success (RUS) circuit over a Clifford+T basis for implementing an axial rotation Rz(θ) to a precision ε>0. At102, a rotation angle and a precision are selected. At104, a phase factor eiθis approximated with a unimodal cyclotomic rational, i.e., with an algebraic number of the form z*/z wherein z∈□[ω]. A suitable approximation procedure based on solving an integer relation problem is discussed below. The value of z is defined up to an arbitrary real-valued factor. In general, a selected z-value may not be includable in a unitary matrix of the form

12L⁢(zy-y*z*)
that is exactly representable in the Clifford+T basis.

At106, several rounds of random modification z(rz), r∈□[√{square root over (2)}] are performed in search of r such that (a) the norm equation |y|22L−|rz|2is solvable for y∈□[ω],L∈□ and (b) the one-round success probability |rz|2/2Lis sufficiently close to 1. Suitable procedures are described below. At108, the value of z is modified and at110, a corresponding one-qubit circuit is defined. At112, a two-qubit RUS matrix based on the one-qubit circuit is defined. At114, a desired two-qubit RUS circuit in the Clifford+T basis is synthesized that implements the Rz(θ) rotation on success and an easily correctable Clifford gate on failure. While a Clifford gate based circuit is convenient for implementation of a correction operation, a correction circuit can include T-gates as well. At116, a circuit specification for the rotation Rz(θ) is output. Example implementations of these steps are described in further detail below.

Cyclotomic Rational Approximation

As shown inFIG. 1, at104, an initial approximation of eiθis obtained such that z*/z□eiθ, wherein z is a cyclotomic integer. For a selected real θ and a cyclotomic integer z=aω3+bω2+cω+d, a,b,c,d∈□, |z*/z−eiθ|≤ε if and only if: |a(cos(θ/2)−sin(θ/2))+b√{square root over (2)} cos(θ/2)+c(cos(θ/2)+sin(θ/2))+d√{square root over (2)} sin(θ/2)|<ε|z|. Thus eiθis representable exactly only if ε|z|=0. If ε|z| is small, then |z*/z−eiθ| is small as well. An integer relation algorithm can be used to find a relation between a set of real numbers and a candidate vector defined by a set of integers a1, . . . , an, not all zero, such that:
aix1+ . . . +anxn=0.
Most commonly an integer relation algorithm makes iterative attempts to find an integer relation until the size of the candidate vector a1, . . . , anexceeds a certain pre-set bound or a1x1+ . . . +anxnfalls below a selected resolution level. Such an algorithm can be used to reduce the size of a1x1+ . . . +anxnto an arbitrarily small value.

In one example, a so-called PSLQ relation algorithm is used to find an integer relation between (cos(θ/2)−sin(θ/2), √{square root over (2)} cos (θ/2), (cos(θ/2)+sin(θ/2)), √{square root over (2)} sin(θ/2) and terminates if and only if |z*/z−eiθ|<ε. (The PSLQ algorithm is described in, for example, Helaman R. P. Ferguson and David H. Bailey, “A Polynomial Time, Numerically Stable Integer Relation Algorithm,” RNR Technical Report RNR-91-032 (Jul. 14, 1992), which is incorporated herein by reference.) Upon termination, the algorithm also provides the integer relation candidate vector {a, b,c,d} for which the integer relation is satisfied. Then, z=aω3+bω2+cω+d is the desired cyclotomic integer.

Lifting Phase Approximation to a Unitary: Randomized Search

Upon finding a cyclotomic integer z, the value of z is to be included in a unitary matrix of the form:

wherein y∈□[ω],L∈□. In addition, reasonably large values of |z|2/2Lare associated with one-round success probability of an eventual RUS circuit and are thus preferred. It is not clear that a particular value of z can be included in a unitary matrix such as shown above. A value of y∈□[ω] is needed that satisfies a norm equation (|y|2+|z|2)/2L=1, or, alternatively |y|2=2L−|z|2.

To solve the above norm equation, it is convenient to note that the cyclotomic integer z obtained from a cyclotomic rational approximation of eiθis not unique, but is defined up to an arbitrary real-valued factor r∈□[√{square root over (2)}]. For any such r, (rz)*/(rz) is identical to z*/z but the norm equation |y|2=2L−|rz|2can change dramatically. Thus, if suitable values of r are reasonably dense in □[√{square root over (2)}], random values of r can be selected until the norm equation |y|2=2L−|rz|2is solvable. Selection of a particular value of y (and a particular unitary matrix) can be based on a ratio of circuit complexity (for example, T-count) and a probability of circuit success, wherein the probability of circuit success can be expressed as p(r)=|rz|2/2L. Thus, a suitable value of r can be found and the value of z modified so that (rz)*/(rz)□eiθ. With this modification of z, a y value can be obtained by solving the norm equation, and a single-qubit unitary defined.

Referring toFIG. 2, a method200of defining a unitary includes receiving a cyclotomic integer z=aω3+bω2+cω+d such that z*/z□eiθand receiving a number sz of samples of r to be evaluated at202. At204, a sample space SMfrom which r-values are to be randomly selected is defined as SM←{a+b√{square root over (2)},a,b∈□|0<a2+b2<M2}, wherein M is a sampling radius. Sample spaces of other shapes can be used, but a sampling radius M is convenient. At206, a value of r is randomly selected without replacement from the sample space SM, and at208an associated value of L is determined as Lr←j log2(|rz|2)k, wherein j f k is a ceiling function having a value equal to the smallest integer that is greater than f. At210, the norm equation |y|2=2L′−|rz|2is evaluated to determine if it is easily solvable for the selected value of r. If the norm equation is not easily solvable, the method200determines if additional samples are to be evaluated at220. If easily solvable, a value of y is obtained at212and a merit function is evaluated at214to determine if this value of y is preferable to previously obtained values. A representative merit function tc is a ratio of circuit T-count to probability of success p, i.e.,

Upon computation of the merit function tc at214, the computed value is compared with a value associated with a previous estimate of y at216. If the value of the merit function is less than that associated with the previous estimate, stored values of r and y and the associated merit function value are updated at218. It is then determined if additional samples of r are to be tried at220. If the merit function found to have not been decreased at216, then it is determined if additional samples of r are to be tried at220as well. If so additional samples are to be evaluated, an additional random value of r is obtained at206and the processing steps are repeated with this value of r. Otherwise, values of r and y are output at222. In some instances, no suitable values of r are found, and the lack of suitable values is output instead at222. Generally, if no values are found (i.e., Y=none), the procedure is repeated by reducing the value of precision by, for example, reducing the value by a factor of 2.

A particular merit function is used in the example ofFIG. 2and is based on a function:

Tcount=Tcount⁡[12Lr⁢(zy-y*z*)].
Methods of determination and/or estimation of a number of T-gates (i.e., circuit T-count) for a unitary as shown above are well known. However, other types of merit functions can be used based on one or more of T-count, success probability, or other factors. The T-count function is described in, for example, Bocharov and Svore, “A Depth-Optimal Canonical Form for Single-Qubit Quantum Circuits,” available at http://arxiv.org/abs/1206.3223, and Gossett et al., “An algorithm for the T-count,” available at http://arxiv.org/abs/1308.4134. Methods similar to the method ofFIG. 2are shown in greater detail in the pseudo-code for the procedures RAND-NORMALIZATION of Tables 1-2 below.

FIG. 3illustrates a method300of defining a single-qubit circuit based on a selected rotation angle θ, a precision ε, a number of iterations sz, and a sampling radius M that are input at302. At304, a value of the precision is re-assigned, and at306a procedure for finding parameters for the corresponding unitary matrix is initiated. At308, a suitable cyclotomic integer is found, and at310a random search/norm equation solution procedure such as those of Tables 1-2 is implemented. If a suitable value of Y={r,y} is found, a value of L is computed at314, and the required unitary matrix is defined at316. Pseudocode for such a method is shown in Table 3 below.

Repeat-Until-Success Unitary Circuit Synthesis

With the above methods, a single-qubit unitary matrix for the rotation R(θ) in the Clifford+T basis is found of the form:

V=12L⁢(zy-y*z*),
wherein y, z∈□(ω),L∈□. The unitary matrix V can be represented as an ancilla-free circuit in the single-qubit Clifford+T basis using a procedure described by Kliuchnikov et al., “Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates,” arXiv:12065236v4 (Feb. 27, 2013), which is incorporated herein by reference. The unitary matrix V can be decomposed by other methods as well. To find a two-qubit (RUS) circuit (i.e., with an ancilla), define a two-qubit unitary

U=(V00V†).
This two-qubit unitary can be incorporated into a RUS circuit with one ancilla so as to perform the rotation

(100z*/z)
on a primary qubit on success and the Pauli Z operation on failure. The unitary matrix V that is included in U can be incorporated into a two-qubit Repeat-Until-Success (RUS) circuit with one ancillary qubit, such that the circuit performs the rotation

(100z*/z)
upon success and a Pauli Z operator on failure, wherein

Z=(100-1).
For example, for a two-qubit design where qubit 1 is a primary qubit and qubit 2 is an ancillary qubit initialized with |0, if |Ψ=a|0+b|1is the input state on the primary qubit then U(|Ψ⊗|0) is proportional to za|00−y*a|01+z*b|10+y*b|11. Therefore upon measuring the ancillary qubit, if the measurement result is 0, then the output state is equivalent to a|0+(z*/z)b|1(i.e., success) and if the measurement result is 1 then the output state is equivalent to a|0−b|1(i.e., failure).

A representative RUS circuit400with an ancillary qubit402is illustrated inFIG. 4. The ancillary qubit402is initialized in a state |0and is coupled to an RUS circuit406along with a primary qubit404in a state |Ψ=a|0+b|1. At408, an output state of the ancillary qubit408is measured. If the measurement of the ancillary qubit402is 0, the output state of the primary qubit corresponds to a|0+(z*/z)b|1which is associated with the selected rotation (referred to as “success”). If the output state of the ancillary qubit is 1, then the output state of the primary qubit404is a|0−b|1, which does not correspond to the intended rotation operator (referred to as “failure”). In this case, the primary qubit404is coupled to a subsequent two-qubit circuit414having an ancillary qubit409that is initialized to state |0. The primary qubit404is coupled to a Z gate412that produces a state |ω=a|0+b|1which is the same as the original input state to the RUS circuit406so that the Z gate412reverses the operation of the RUS circuit406. The processing operations of the two-qubit circuit414can be repeated until success is achieved. The second RUS circuit416provides similar results at the RUS circuit406upon measurement at418. Additional similar stages such as circuit420can be provided to increase the likelihood of success.

The two-qubit unitary U can be implemented as a series of Clifford+T gates but implementations in which circuit T-count is the same or only slightly greater than that of the corresponding optimal single qubit circuit are preferred. If V and W are single-qubit unitaries both representable by single-qubit ancilla-free Clifford+T circuits of the same minimal T-count t, then it can be shown that the two-qubit unitary

U=(V00W)
is exactly and constructively representable by a Clifford+T circuit of T-count at most t+9. Generally, given two single-qubit Clifford+T circuits of the same T-count, either can be manufactured from the other by insertion and deletion of Pauli gates, along with the addition of at most two non-Pauli Clifford gates. The latter two gates are responsible for all potential T-count increases while lifting the V,W pair to the desired two-qubit circuit.

For convenience, a T code is defined as a circuit generated by TH and T†H syllables. If c is a T code then Hc−1H is a T code. A decorated T code is a circuit generated by syllables of the form PT±1QH wherein P,Q∈{Id,X,Y,Z}, and Id is an identity operator. A decorated T code c2is referred to as a decoration of a T code c1if c1can be obtained from c2by removing all explicit occurrences of Pauli gates. A single-qubit, ancilla-free Clifford+T circuit can be constructively rewritten in the form g1cg2where c is a T code and g1, g2are single-qubit Clifford gates.

The following identities can also be useful:

CanonicalT, Hcircuits are defined as circuits representable as arbitrary compositions of TH and HTH syllables, and starting with a TH syllable. For any T code c1any single-qubit ancilla-free Clifford+T circuit c2of the same T-count can be constructively rewritten as g3c′1g4where c′1is a decoration of c1and g3, g4are Clifford gates. If c1and c2are single-qubit Clifford+T circuits of the same T-count t, a T code c3, one of its decorations c4, and Clifford gates g1, g2, g3, g4can be found such that c1=g1c3g2and c2=g3c4g4.

A lift procedure is defined that converts a decorated T-code into a two qubit circuit. For any Pauli gate P, Lift(P)=Λ(P), where Λ(P) indicates a controlled-P gate. For any other gate g, Lift(g)=Id⊗g. Given a single-qubit Clifford+T circuit c=g1. . . g4wherein gi∈{X,Y,Z,H,T,T†} i=1, . . . , r, Lift(c)=Lift(g1) . . . Lift(gr). Informally, up to Clifford gate wrappers, any two single-qubit Clifford+T circuits are related via T code decoration.

If a single-qubit unitary U is represented as Hc1where c1is a T code of T-count t, then the two-qubit unitary

(U00U†)
is constructively represented by a two-qubit Clifford+T circuit of T-count of either t or t+1. The unitary matrix U†can be decomposed into Hc2ωk, k∈□ wherein c2is a decoration of the circuit c1. Since (Hc1)−1=(c1)−1H is H followed by a T code, the desired decomposition is Lift(Hc2)(Tk⊗Id). The T-count of Lift(Hc2) is t and the T-count of (TkId) is either 0 or 1.

More generally, if V,W are single-qubit unitaries both representable by single-qubit ancilla-free Clifford+T circuits of the same minimal T-count t, then a two-qubit unitary

U=(V00W)
is exactly and constructively representable by a Clifford+T circuit of T-count of at most t+9.
The unitary W can be constructively represented as g3g1c′g2g4wherein c′ is a decoration of c, and g3, g4are Clifford gates. Defining c″=Lift (c′), U can be represented as Λ(g3)(Id⊗g1)c″(Id⊗g2)Λ(g4). Each occurrence of a controlled Clifford gate increases the T-count by at most 5. By applying a suitable global phase the T-count of Λ(g3) is at most 4. For any Clifford gate g, the controlled gate Λ(g) can be can be represented as a product of Clifford gates and exactly one gate of the form Λ(h) wherein h∈{Id,ω−1S,H,ω−1SH,ω−1HS}.

A representative method of obtaining a two-qubit unitary based on a single input unitary Vis shown inFIG. 5. At502, a single qubit unitary V is input. At504, V is represented as a product g1cg2and at506, V†is represented as a product g3c′g4, wherein g1, g2, g3, g4are Clifford gates, c is a T-code, and c′ is a decoration of c. At508, additional Clifford gates are obtained based on the Clifford gates used in the product representations of V and V†. At510, a suitable two qubit unitary is returned as Λ(g5)(Id⊗g1)Lift(c′)(Id⊗g2)Λ(g6). Pseudocode for this method is found in Table 3 below.

Example

Determination of a Clifford+T basis RUS circuit for a representative rotation is described below for a target rotation Rz(π/64) and a precision of 10−11. A ratio z*/z is found that approximates eiπ/64. In this example, z=1167ω3=218ω2−798ω−359 and an associated precision is about 3×10−12, better than the target precision of 10−11. Next, the value of z is modified using a randomized search to find a solvable norm equation so that z=18390ω3−4226ω2−11614ω−1814 and a one round success probability is 0.9885. Circuit synthesis then generates the RUS circuit design Λ(ω−1SH)coreΛ(ω−1SH), whereincore=id{circle around (/)}(T−1H T−1H) CNOT Id ⊗(T−1H T H) CNOT Id⊗(T H T H T31H) CNOT Id ⊗(T−1H) CNOT Id⊗(T−1H) CNOT Id⊗(T−3H) CNOT Id⊗(T−1H) CNOT Id⊗(T H) CNOT Id{circle around (/)}(T−3H T3H) CNOT Id⊗(T−1H T−1H T−1H) CNOT Id⊗(T H T H) CNOT Id⊗(T H T−3H) CNOT Id{circle around (/)}(T3H) CNOT Id⊗(T−3H) CNOT Id⊗(T H T H) CNOT Id⊗(T−1H) CNOT Id⊗(T H T−1H) CNOT Id⊗(T−1H) CNOT Id⊗(T3H) CNOT Id⊗(T−1H T−1H) CNOT Id⊗(T H T H) CNOT Id⊗(T−3H T3H T−1H) CNOT Id⊗(T H T−1H) CNOT Id⊗(T H) CNOT Id⊗(T−1H) CNOT Id⊗(T H) CNOT Id⊗(T−3H) CNOT Id⊗(T H) CNOT T G T−1H T H CNOT Id⊗(T−1H T−1H) CNOT Id⊗(T−3H S†)
The S-gate above corresponds to a square of the T-gate. The Λ(ω−1SH) operation has a T-count of 4 and the overall cost of the RUS circuit measured in T gates is 58. The expected T-cost is 58/0.9885<58.7. This circuit implements a z-rotation on success and Pauli Z gate operation on failure, which is Pauli-correctable. A final trace distance between Rz(π/64) and the rotation implemented by the RUS is 1.056×10−12which is better than the requested precision. Another version of this circuit is Λ(ω−2H)core(Id⊗S)Λ(H), which has an expected T-cost of 54.6, performs the same z-rotation on success and the phase gate Son failure. Application of the phase gate S is Clifford-correctable.

FIGS. 6-7show mean and standard deviation across a set of expected T-count values of the RUS circuits generated algorithmically for each target rotation in the second test set for each precision.FIG. 6shows T-count statistics for 1000 target rotation angles randomly selected from the interval (0,π/2). This set of target axial rotations was evaluated at 25 levels of target precision ε∈{10−11, . . . , 10−35}. A regression formula for T-count is 3.817 log10(1/ε)+9.2=1.149 log2(1/ε)+9.2.FIG. 7shows T-count statistics for 40 rotation angles of the form π/2k, k=2, . . . , 41. This set of target rotation angles (referred to as Fourier angles) was evaluated at 30 levels of target precision ε∈{10−11, . . . , 10−40}. A regression formula for T-count is 3.59 log10(1/ε)+17.5=1.08 log2(1/ε)+17.5.

Consider an n-qubit unitary of the form

1z⁢V
where z∈Z[√{square root over (i)}] and V is a 2n×2nmatrix over Z[√{square root over (i)}]. This unitary can be implemented by a Clifford+T RUS with at most n+2 qubits. A method800for finding such a unitary is shown inFIG. 8. At802, an integer L and an r∈Z[√{square root over (2)}] are selected such that a norm equation |y|2=2L−|rz|2is solvable for y∈Z[√{square root over (t)}]. At804, a 2n+1×2nmatrix

W=12L⁡[rVyI⁢⁢d]
is defined which is to be completed to a 2n+1×2n+1unitary matrix following a procedure described in Kliuchnikov et al., “Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates,” arXiv:12065236v4 (Feb. 27, 2013). At806the 2ncolumns of the matrix W are reduced to a half-basis by a Clifford+T circuit c that is synthesized using a procedure described in Brett Giles and Peter Selinger, “Exact synthesis of multi-qubit Clifford+T circuits,” Phys. Rev. A (2012), such that:

cW=(Id2″02″)
It follows that c−1evaluates to a 2n+1×2n+1unitary matrix that complements the half-square matrix W. The circuit c−1can intermittently use an ancillary qubit to perform the two-level primitive unitaries of the T-type. In any case, c−1is the desired RUS circuit and is output at810. Indeed,

c-1(0〉⊗⁢ψ〉)=(0)⊗(r(2)L⁢V)❘ψ〉)+(1〉⊗(y(2)L⁢Id)⁢ψ〉).
The target operator

1z⁢V
is the unitarization of

r(2)L⁢V
and the unitarization of

y(2)L
Id is Id.
Thus, when the top qubit is measured,

1z⁢V
is returned for a 0 measurement and Id is returned for a 1 measurement. A one-round success rate for this circuit is |rz|2/2L, therefore, values of L close to ┌log2(|rz|2)┐ are preferred.

Reducing the Number of Entanglers in RUS Designs

RUS circuits synthesized as disclosed herein may include a large number of controlled-Pauli gates. In some cases, an RUS circuit design could contain 2t controlled-Pauli Pauli gates wherein t is the circuit T-count. Although a controlled-Pauli gate has zero T-count, in some examples, it is preferred to reduce the number of controlled-Pauli gates. Up to one half of the Pauli gates in a circuit can be constructively eliminated from a T-oddT, H, Paulicircuit using a set of signature-preserving rewrite rules. For a single-qubit Clifford+T circuit of the form g0Tk1g1, . . . , Tkrgrwhere g0, g4are Clifford gates and for i=1, . . . , r 1 wherein gi∈{Id,X,Y,Z,H,XH,YH, ZH,HX,HY,HZ}, the series of integers {k1, . . . , kr} is referred to as a signature of the circuit. A unitary V†can be represented as a Pauli decoration c′ of a circuit c representing V is so that the signatures of c and c′ are the same. Only the signature of the Pauli decoration circuit is of concern, and any equivalent transformations can be applied to such a decoration as long as those transformations preserve the signature. If the T-count of a decorated T code c is t, then the circuit can be rewritten in a form c′im, m∈□, wherein c′ is an equivalent decorated T code with no more than t+1 Pauli gates and the same signature as c. In some cases, one or more of the following rewrite rules is used:

Based on the commutation rules XH=HZ; YH=−YH; and ZH=XH, any term of the form PQH, wherein P,Q are Pauli gates can be reduced to H P′imm∈□, wherein P′ is a Pauli gate.

Computing Environments

FIG. 9and the following discussion are intended to provide a brief, general description of an exemplary computing environment in which the disclosed technology may be implemented. Although not required, the disclosed technology is described in the general context of computer executable instructions, such as program modules, being executed by a personal computer (PC). Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. Moreover, the disclosed technology may be implemented with other computer system configurations, including hand held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. The disclosed technology may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

With reference toFIG. 9, an exemplary system for implementing the disclosed technology includes a general purpose computing device in the form of an exemplary conventional PC900, including one or more processing units902, a system memory904, and a system bus906that couples various system components including the system memory904to the one or more processing units902. The system bus906may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The exemplary system memory904includes read only memory (ROM)908and random access memory (RAM)910. A basic input/output system (BIOS)912, containing the basic routines that help with the transfer of information between elements within the PC900, is stored in ROM908.

As shown inFIG. 9, computer-executable instructions for RUS synthesis are stored in a memory portion916and includes instructions for, for example, solving integer equations, evaluating and solving norm equations, and random sampling for determination of r values. In addition, a memory portion918stores RUS circuit definitions obtained using the disclosed methods. Computer-executable instructions are also stored for receiving rotation angles and precisions as well as communicating circuit definitions.

The exemplary PC900further includes one or more storage devices930such as a hard disk drive for reading from and writing to a hard disk, a magnetic disk drive for reading from or writing to a removable magnetic disk, and an optical disk drive for reading from or writing to a removable optical disk (such as a CD-ROM or other optical media). Such storage devices can be connected to the system bus906by a hard disk drive interface, a magnetic disk drive interface, and an optical drive interface, respectively. The drives and their associated computer readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules, and other data for the PC900. Other types of computer-readable media which can store data that is accessible by a PC, such as magnetic cassettes, flash memory cards, digital video disks, CDs, DVDs, RAMs, ROMs, and the like, may also be used in the exemplary operating environment.

A number of program modules may be stored in the storage devices930including an operating system, one or more application programs, other program modules, and program data. Storage of quantum syntheses and instructions for obtaining such syntheses can be stored in the storage devices930as well as or in addition to the memory904. A user may enter commands and information into the PC900through one or more input devices940such as a keyboard and a pointing device such as a mouse. Other input devices may include a digital camera, microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the one or more processing units902through a serial port interface that is coupled to the system bus906, but may be connected by other interfaces such as a parallel port, game port, or universal serial bus (USB). A monitor946or other type of display device is also connected to the system bus906via an interface, such as a video adapter. Other peripheral output devices, such as speakers and printers (not shown), may be included. In some cases, a user interface is display so that a user can input a circuit for synthesis, and verify successful synthesis.

The PC900may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer960. In some examples, one or more network or communication connections950are included. The remote computer960may be another PC, a server, a router, a network PC, or a peer device or other common network node, and typically includes many or all of the elements described above relative to the PC900, although only a memory storage device962has been illustrated inFIG. 9. The personal computer900and/or the remote computer960can be connected to a logical a local area network (LAN) and a wide area network (WAN). Such networking environments are commonplace in offices, enterprise wide computer networks, intranets, and the Internet.

When used in a LAN networking environment, the PC900is connected to the LAN through a network interface. When used in a WAN networking environment, the PC900typically includes a modem or other means for establishing communications over the WAN, such as the Internet. In a networked environment, program modules depicted relative to the personal computer900, or portions thereof, may be stored in the remote memory storage device or other locations on the LAN or WAN. The network connections shown are exemplary, and other means of establishing a communications link between the computers may be used.

With reference toFIG. 10, an exemplary system for implementing the disclosed technology includes computing environment1000, where compilation into braid pattern circuits is separated from the quantum processing that consumes the compiled circuits. The environment includes a quantum processing unit1002and one or more monitoring/measuring device(s)1046. The quantum processor executes quantum circuits that are precompiled by classical compiler unit1020utilizing one or more classical processor(s)1010. The precompiled quantum circuits such as RUS circuits1003are downloaded into the quantum processing unit via quantum bus1006.

With reference toFIG. 10, the compilation is the process of translation of a high-level description of a quantum algorithm into a sequence of quantum circuits. Such high-level description may be stored, as the case may be, on one or more external computer(s)1060outside the computing environment1000utilizing one or more memory and/or storage device(s)1062, then downloaded as necessary into the computing environment1000via one or more communication connection(s)1050. Alternatively, the classical compiler unit1020is coupled to a classical processor1010and an RUS compiler procedure library1021that contains some or all procedures necessary to implement the methods described above as well as an RUS circuit library1003that stores compiled circuits.

Having described and illustrated the principles of our invention with reference to the illustrated embodiments, it will be recognized that the illustrated embodiments can be modified in arrangement and detail without departing from such principles. For instance, elements of the illustrated embodiment shown in software may be implemented in hardware and vice-versa. Also, the technologies from any example can be combined with the technologies described in any one or more of the other examples. Alternatives specifically addressed in these sections are merely exemplary and do not constitute all possible

FIG. 11illustrates an alternative circuit1100that implements a two-qubit unitary transformation of the form

(U00U†)
wherein U is a single qubit unitary1130, Depending on a value of a flag bit b (established by a qubit1121), the circuit1100implements a transformation of an input state of a qubit1122that is given by either U or U\. The resulting state is obtained at the output1155, wherein the output state is unentangled with all other qubits. The single-qubit unitary U1130is of the form Rz(θ)Rx(β)Rz(−θ), wherein θ and β are real numbers. The circuit1100uses two ancilla qubits1123,1124initialized in 0 states.

The circuit1100consists of an initial preparation circuit1110that produces an Einstein-Podolsky-Rosen (EPR) state |00>+|11> which is then subjected to quantum routing circuits1115and1140that permute part of the EPR state and the input state of the qubit1122depending on the value of bit b. In a “b=0” branch, the input state of the qubit1122undergoes evolution by U and the remaining state |00>+|11> is an eigenstate of eigenvalue 1 of the tensor product operator U\with U. In a “b=1” branch, the input state of the qubit1122undergoes evolution by U\and the remaining state |00>−|11> is an eigenstate of eigenvalue 1 of the tensor product operator U with U.

The overall effect of the circuit1100is to achieve at the output1155a transformation of the input that corresponds to U in case b=0 and U\in case b=1. In either case, the 2 ancilla qubits1123,1124are again returned in the 0 state. As a core circuit1130can be executed in parallel, the circuit1100has the feature that its overall circuit depth is no larger than the circuit depth of U, except for a constant additive overhead due to the EPR preparation1110and computation thereof as well as the routing operations of quantum routing circuits1115,1140.

With reference toFIG. 12, a circuit decomposition method1200for arbitrary unitary transformations over the cyclotomic field Q(ω) is disclosed that uses at most 2 additional ancilla qubits. At1202, a unitary is input that can act on one, two, three, or more qubits, and is not limited to acting on a single qubit. At1206, a selected unitary U is embedded into a unitary W of larger size of the form:

One convenient method of determine integer coefficients α, β, γ, δ at1204is a method based on a Four Square Decomposition of integers which is applicable for arbitrary matrices U over the cyclotomic field. Alternatively, methods solving norm equations over cyclotomic number fields and subfields can be used, and in some examples, suitable methods are based on particular properties of a selected U. Once the embedding matrix W is obtained at1206, a Clifford+T factorization is obtained using methods for decomposition of unitary matrices over the ring of integers in Q(ω) at1208.

In other examples, quantum circuits are defined by obtaining a four tuple of integers so that a given rotation matrix U over the cyclotomic field can be embedded into a unitary W over the ring of cyclotomic integers. The rotation matrix U is embedded into the unitary W, and W is decomposed using a suitable gate set, such as Clifford+T gates. In some examples, an initial RUS circuit is defined based on a plurality of ancilla qubits, and subsequently re-synthesized so as to be implementable with only 2 ancilla qubits.

In other examples, quantum circuits are defined to include two ancilla qubits and a control qubit so as to implement a RUS matrix for axial rotations with circuit depth equal to the circuit depth of the defining block U, wherein a transformation associated with the RUS matrix is associated with U or U\based on a value of a control qubit. A controlled routing operation is arranged to couple an input state to a unitary operation implementing either U or U\and a controlled preparation operation creates one of two available EPR states depending on whether an eigenstate of a tensor product of U with itself or a tensor product of U with its inverse is required. The circuit decomposition of U is lifted to provide a circuit for parallel execution of U and U\and having the same T-depth as a single application of U.

In some examples, quantum circuits such as two-qubit circuits are based on a plurality of gates selected from the group of Hadamard gates, CNOT gates, and T-gates selected in association with an arbitrary single qubit rotation matrix U, wherein entries of the matrix U are real or complex numbers, and U corresponds to a sequence of axial rotations such that U=Rz(α)Rx(β)Rz(γ), wherein Rzdenotes a rotation about a z-axis and Rxdenotes a rotation about an x-axis, wherein α, β, γ are Euler angles. Ancillary qubits and a primary qubit are coupled to the plurality of gates such that production of a first output state of the first ancillary qubit is associated with an output state of the primary qubit that is associated with the rotation Rz(α), a second output state of the second ancillary qubit associated with an output state of the primary qubit that is associated with the rotation Rx(β and a third output state of the third ancillary qubit associated with an output state of the primary qubit that is associated with the rotation Rz(γ). In some examples, the first ancillary qubit and the primary qubit are reused for production of the rotation Rx(β) and at least one of the second and third ancillary qubits and the primary qubit is reused for production of the rotation Rz(γ). In other examples, the decomposition of U into a sequence of axial rotations is based on Givens rotations.

Having described and illustrated the principles of the disclosed technology with reference to the illustrated embodiments, it will be recognized that the illustrated embodiments can be modified in arrangement and detail without departing from such principles. For instance, elements of the illustrated embodiments shown in software may be implemented in hardware and vice-versa. Also, the technologies from any example can be combined with the technologies described in any one or more of the other examples. It will be appreciated that procedures and functions such as those described with reference to the illustrated examples can be implemented in a single hardware or software module, or separate modules can be provided. The particular arrangements above are provided for convenient illustration, and other arrangements can be used.