EFFICIENT SYNTHESIS OF PROBABILISTIC QUANTUM CIRCUITS WITH FALLBACK

Abstract

A Probabilistic Quantum Circuit with Fallback (PQFs) is composed as a series of circuit stages that are selected to implement a target unitary. A final stage is conditioned on unsuccessful results of all the preceding stages as indicated by measurement of one or more ancillary qubits. This final stage executes a fallback circuit that enforces deterministic execution of the target unitary at a relatively high cost (mitigated by very low probability of the fallback). Specific instances of general PQF synthesis method and are disclosed with reference to the specific Clifford+T, Clifford+V and Clifford+π/12 bases. The resulting circuits have expected cost in log.sub.b(1/ε(log(log(1/ε)))+const wherein b is specific to each basis. The three specific instances of the synthesis have polynomial compilation time guarantees.

Claims

1. -15.(canceled)

16. A computer-implemented method of defining a quantum circuit, comprising: establishing a first approximation of a target unitary to a requested precision; expanding the first approximation into a first multi-qubit unitary that implements the target single-qubit unitary in a selected basis upon successful measurement; defining a fallback circuit in the selected basis, wherein the fallback circuit implements the target unitary based upon an unsuccessful measurement; and outputting a circuit definition that includes a definition of the multi-qubit unitary and a definition of the fallback circuit; and based on the circuit definition, constructing the quantum circuit.

17. The computer-implemented method of claim 16, wherein the target unitary is a multi-qubit unitary, and further comprising: establishing a second approximation of the target multi-qubit unitary to a requested precision based on an unsuccessful output of the first multi-qubit unitary; and expanding the second approximation into a second multi-qubit unitary that implements the target single-qubit unitary in the selected basis upon successful measurement, wherein the fallback circuit implements the target unitary based upon an unsuccessful measurement associated with the second multi-qubit unitary.

18. The computer-implemented method of claim 16, further comprising: establishing a series of approximations of the target unitary to a requested precision based on an unsuccessful measurement of a multi-qubit unitary associated with a prior approximation in the series; and expanding the series of approximations into a corresponding series of multi-qubit unitaries that implement the target qubit unitary in the selected basis upon successful measurement, wherein the fallback circuit implements the target unitary based upon an unsuccessful measurement associated with a final multi-qubit unitary in the series.

19. The computer-implemented method of claim 16, wherein the approximation of the target qubit unitary is based on a rational cyclotomic approximation of the target qubit unitary.

20. The computer-implemented method of claim 16, further comprising establishing the rational cyclotomic approximation of the target qubit unitary by solving a norm equation.

21. The computer-implemented method of claim 16, wherein the target unitary is an axial rotation and is approximated by z*/z wherein z is a cyclotomic integer; and

22. The computer-implemented method of claim 16, wherein the multi-qubit unitary is defined with respect to at least one ancillary qubit and at least one primary qubit.

23. The computer-implemented method of claim 17, wherein the target single-qubit unitary is of the form $\frac{1}{{\sqrt{2}}^L}.Math.\left(\begin{array}{cc}\mathrm{rz}& y\\ -y^{*}& r^{*}.Math.z^{*}\end{array}\right),$ wherein z is a cyclotomic rational, r is a probability enhancement factor, and L is the minimal positive integer such that 2.sup.L>|r z|.sup.2.

24. The computer-implemented method of claim 23, further comprising selecting a value of r ∈[√{square root over (2)}] such that a norm equation is solvable for z replaced by rz.

25. The method of claim 16, wherein the first multi-qubit unitary is coupled to at least one ancillary qubit having a predetermined state.

26. The method of claim 25, wherein the at least one ancillary qubit is used in each of a plurality of probabilistic quantum circuit with fallback (PQF) stages associated with different multi-qubit unitaries and measurements associated with at least one of the PQF stages.

27. A quantum circuit, comprising: a series of multi-qubit sub-circuits based on a plurality of gates selected from a basis set so as to implement an axial rotation R based on respective ratios z*/z for each multi-qubit circuit of the series, wherein z is a cyclotomic integer, the series including at least an initial multi-qubit sub-circuit and a final multi-qubit sub-circuit, the final multi-qubit sub-circuit arranged to implement the rotation R based on an unsuccessful output of at least one sub-circuit of the series; and at least one ancillary qubit and at least one primary qubit coupled to at least the initial multi-qubit sub-circuit such that production of a first output state of the at least one ancillary qubits is associated with an output state of the primary qubit that is associated with the rotation R and a second output state is associated with an output state of the primary qubit that is not the rotation R.

28. The quantum circuit of claim 27, further comprising a fallback sub-circuit coupled to the final multi-qubit sub-circuit that implements the rotation R if an output state of the at least one ancillary qubit produced by the final multi-qubit sub-circuit is associated with an output state of the final multi-qubit sub-circuit that does not correspond to the rotation R.

29. The quantum circuit of claim 27, further comprising a switch that couples an output state of the initial multi-qubit sub-circuit to the final multi-qubit sub-circuit based on the output state of the initial qubit.

30. The quantum circuit of claim 27, further comprising a series of intermediate multi-qubit sub-circuits coupled between the initial and final multi-qubit sub-circuits, each of the intermediate multi-qubit sub-circuits coupled to respective switches that direct output states of the least one primary qubit by each intermediate multi-qubit sub-circuit to a subsequent intermediate multi-qubit circuit or the final multi-qubit sub-circuit based on the output state of the intermediate multi-qubit sub-circuits.

31. The quantum circuit of claim 30, wherein the output states of the intermediate multi-qubit sub-circuits is associated with a result other than the rotation R.

32. The quantum circuit of claim 31, wherein each of the intermediate multi-qubit sub-circuits implements the rotation R if successful based on the output state of the immediately prior multi-qubit sub-circuit.

33. The quantum circuit of claim 32, wherein the output state of the immediately prior multi-qubit sub-circuit corresponds to a state other than an input state at the initial multi-qubit sub-circuit.

34. The quantum circuit of claim 27, wherein the basis is the Clifford+T basis, the Clifford+π/12 basis, or the Clifford+V basis.

35. A compiler for defining a quantum circuit, comprising: a processor; and at least one computer-readable storage medium having computer-executable instructions for a method comprising: receiving a target rotation, a number of stages k, and a precision; selecting cyclotomic integers z such that z*/z is associated with a stage rotation angle within the selected precision for each stage; performing search to find values of r such that a norm equation or a two squares equation is solvable for z=rz for each stage; defining a one-qubit unitary for each stage based on r,z and the solution of the norm equation; defining a multi-qubit circuit having k stages based on the one qubit unitary and a plurality of gates selected from the Clifford+T basis, the Clifford+π/12 basis, or the Clifford+V basis, the multiple-qubit circuit including at least one ancillary qubit having an output state that is associated with realization of an output state associated with the target rotation; and a fallback circuit coupled to a final stage of the multi-qubit circuit and that implements the target rotation if the at least one ancillary qubit indicates failure of each of the k stages.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0007] FIG. 1 illustrates a representative PQF circuit.

[0008] FIG. 2 illustrates a representative method of defining a PQF circuit.

[0009] FIG. 3 illustrates a method of defining a PQF circuit in the Clifford+T, Clifford+π/12, and Clifford+V bases.

[0010] FIG. 4 illustrates a Markov chain of finite length derived from a PQF.

[0011] FIG. 5 is a block diagram of a representative computing environment in which the disclosed methods can be implemented.

[0012] FIG. 6 is a block diagram of a representative computing environment that includes classical and quantum processing.

DETAILED DESCRIPTION

[0013] As used in this application and in the claims, the singular forms “a,” “an,” and “the” include the plural forms unless the context clearly dictates otherwise. Additionally, the term “includes” means “comprises.” Further, the term “coupled” does not exclude the presence of intermediate elements between the coupled items.

[0014] The systems, apparatus, and methods described herein should not be construed as limiting in any way. Instead, the present disclosure is directed toward all novel and non-obvious features and aspects of the various disclosed embodiments, alone and in various combinations and sub-combinations with one another. The disclosed systems, methods, and apparatus are not limited to any specific aspect or feature or combinations thereof, nor do the disclosed systems, methods, and apparatus require that any one or more specific advantages be present or problems be solved. Any theories of operation are to facilitate explanation, but the disclosed systems, methods, and apparatus are not limited to such theories of operation.

[0015] Although the operations of some of the disclosed methods are described in a particular, sequential order for convenient presentation, it should be understood that this manner of description encompasses rearrangement, unless a particular ordering is required by specific language set forth below. For example, operations described sequentially may in some cases be rearranged or performed concurrently. Moreover, for the sake of simplicity, the attached figures may not show the various ways in which the disclosed systems, methods, and apparatus can be used in conjunction with other systems, methods, and apparatus. Additionally, the description sometimes uses terms like “produce” and “provide” to describe the disclosed methods. These terms are high-level abstractions of the actual operations that are performed. The actual operations that correspond to these terms will vary depending on the particular implementation and are readily discernible by one of ordinary skill in the art.

[0016] In some examples, values, procedures, or apparatus' are referred to as “lowest”, “best”, “minimum,” or the like. It will be appreciated that such descriptions are intended to indicate that a selection among many used functional alternatives can be made, and such selections need not be better, smaller, or otherwise preferable to other selections.

[0017] 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 unitary quantum gates corresponding to single-qubit operators S, X Y, and Z can be represented as:

[00001]$S=\left[\begin{array}{cc}1& 0\\ 0& i\end{array}\right]$$X=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right],.Math.Y=\left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right],.Math.Z=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right].$

[0018] 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:

[00002]$\mathrm{CNOT}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$$H=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right],\mathrm{and}$$T=\left[\begin{array}{cc}1& 0\\ 0& e^{i.Math.\frac{\pi }{4}}\end{array}\right].$

Other bases can be used as well, including the Clifford+π/12 and Clifford+V bases.

[0019] For the Clifford+π/12 basis we augment the set of Clifford gates by the gate

[00003]$\left[\begin{array}{cc}1& 0\\ 0& e^{i.Math..Math.\pi /6}\end{array}\right].$

[0020] For the Clifford+V basis we augment the set of Clifford gates by the 6 gates V.sub.1, V.sub.2, V.sub.3, V.sub.1.sup.−1, V.sub.2.sup.−1, V.sub.3.sup.−1 that are defined as follows:

[00004]$V_1=\frac{1}{\sqrt{5}}.Math.\left(I+2.Math.\mathrm{iX}\right),.Math.V_1^{-1}=\frac{1}{\sqrt{5}}.Math.\left(I-2.Math.\mathrm{iX}\right),.Math.V_2=\frac{1}{\sqrt{5}}.Math.\left(I+2.Math.\mathrm{iY}\right),.Math.V_2^{-1}=\frac{1}{\sqrt{5}}.Math.\left(I-2.Math.\mathrm{iY}\right),.Math.V_3=\frac{1}{\sqrt{5}}.Math.\left(I+2.Math.\mathrm{iZ}\right),.Math.V_3^{-1}=\frac{1}{\sqrt{5}}.Math.\left(I-2.Math.\mathrm{iZ}\right).$

[0021] Basis 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:

[00005]$\left[\begin{array}{cc}a& b\\ -b^{*}& a^{*}\end{array}\right],$

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:

[00006]$U^{†}.Math.U={\mathrm{UU}}^{†}=I=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],$

wherein

[00007]$U^{†}=\left[\begin{array}{cc}{a}^{*}& -b\\ b^{*}& a\end{array}\right].$

The adjoint U.sup.554 of a unitary matrix U is the complex-conjugate transpose of the unitary U and is the inverse of U, denoted U.sup.−1.

[0022] In the following, multi-qubit circuits are disclosed that have one or more qubits that are used to obtain computed values associated with one or more unitaries and one or more qubits that are used to determine success or failure of a circuit or sub-circuit. These qubits are referred to as primary qubits and ancillary qubits (or ancilla), respectively. In most examples, ancillary qubits are initialized to the zero state for convenience, but other initial states can be used. PQF circuits typically include a series of stages, and the circuits for these stages are referred to in some examples as sub-circuits. A PQF circuit generally includes a number of sub-circuits and a fallback circuit that is associated with a final sub-circuit. As noted above, each intermediate stage in the series is followed by measurement of at least one ancillary qubit, and if the measurement indicates that the stage was unsuccessful, then the next stage is executed, and so on. If measurement of a particular stage indicates success, the additional stages and the fallback circuit are not needed. If measurements of all intermediate stages indicate that all intermediate stages are unsuccessful, the fallback circuit is applied.

[0023] For convenient illustration, the examples below pertain to PQF implementation of single-qubit gates. Multi-qubit gates can be implemented as PQF circuits in the same manner. In addition, while implementation examples are shown in particular bases, other bases can be used. Generally, any basis in which a deterministic fallback circuit can be defined is suitable for PQF circuit implementation. In addition to the PQF circuits and methods, the following describes generation of deterministic fallback circuits in the Clifford+π/12 basis.

[0024] 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)}.sup.kU wherein 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ω.sup.3+bω.sup.2+cω+d wherein a,b,c,d are arbitrary integers and ω=e.sup.iπ/4. One choice for a basis of [ω] is {ω.sup.3, ω.sup.2, ω,1}. To be unitary, UU.sup.†=2.sup.kId, 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)}.sup.kU)=1. Any single-qubit circuit in the {H,T} basis can be expressed as a sequence of syllables of the form T.sup.−kHT.sup.k,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=R.sub.z(α) R.sub.x(β) R.sub.z(γ) in accordance with the Euler angle decomposition of U. Thus any single-qubit unitary operation can be decomposed into Clifford+T circuits using the techniques presented herein. Similar single-qubit circuit decompositions can be Clifford+V circuits or Clifford|π/12 circuits.

[0025] Disclosed herein are quantum circuits and methods based on probabilistic circuits with fallback (PQFs) that allow a finite (typically, small) number of trials and only one final correction step that is purely unitary and may have a considerable cost. The expected cost for a PQF circuit is lower than other decomposition techniques due to the probability boosting that decreases the probability of having to perform the costly fallback sub-circuit extremely low. The synthesis of a PQF circuit approximating a given target can be simpler than in the RUS case as in the synthesis of the RUS circuits, considerable effort is directed to maintaining essentially cost-free corrections, for example corrections that are composed of Pauli gates or Clifford gates.

[0026] In the following, it is assumed that a so-called “fallback” circuit synthesis method is available that, for a given unitary target gate G and a desired precision .sub.ε generates a deterministic .sub.ε-approximation circuit F (G,ε) with a known execution cost C.sub.F(G,ε). In addition, it is assumed that there is a “primary” circuit synthesis method that given G and .sub.ε generates a probabilistic circuit P (G, ε) with probability p>0 and performs some other unitary gate G.sub.1 with probability 1−p. A measurement of one or more ancilla qubits is used to determine whether the primary circuit is successful, i.e., provides an output corresponding to the target gate (e.g., G), or unsuccessful, i.e., provides an output corresponding to the other unitary gate (e.g., G.sub.1). A number of stages can be selected based on a cost estimate in view of costs associated with implementation of one or more gates from a basis set. In addition, the number of stages can be selected based on cost so as to avoid including stages that provide little cost benefit and so as to minimize the expected cost of the complete PQF circuit.

[0027] In addition to the Clifford+T basis, some examples are based on the Clifford+V basis and the Clifford+7π/12 basis. The Clifford+V basis provides for shortest known unitary circuits resulting from the classically efficient approximate synthesis. The Clifford+π/12 basis is useful for architectures based on metaplectic anyons. PQF syntheses are disclosed for these bases using the fact that all the exactly representable unitaries over a respective basis are representable as unitarizations of matrices over rings of cyclotomic integers of order 4m,m ∈1,2,3, wherein m=1 for the Clifford+V basis, m=2 for the Clifford+T basis, and m=3 for the Clifford+π/12 basis. As noted above, Clifford+T circuits are based on cyclotomic integers of order 8, i.e., 4m, wherein m=2.

[0028] For a multi-round PQF design with k rounds, sub-circuits are sequentially generated for each round. Each subsequent round of the design is conditional on the failure of all the previous rounds, and accounts for cumulative undesired outcomes of the previous rounds. In what follows a PQF circuit is designed for a target z-rotation such that the undesired outcomes are also z-rotations. With this, each round of the PQF design will have the same logic and only the target rotation angles between the rounds may be different.

[0029] A representative PQF circuit 100 is shown in FIG. 1. One or more ancillary qubits 102 and one or more input (or primary) qubits 104 are coupled to a first stage circuit 106 that implements a unitary U(G.sub.k,ε). As shown in FIG. 1,111 ancillary qubits and n input qubits are provided. A measurement circuit 108 evaluates an output state associated with the ancillary qubits. A first state classical switch circuit S 110 is coupled to the first stage circuit 106 so as to output qubit values corresponding to processing of the input qubits 104. The first stage classically controlled switch 110 selectively couples the processed input qubits to a second stage circuit 116 if the measured result is unfavorable. If the first stage circuit 106 is successful, a desired output V|ψ is provided, and any additional stages such as the second stage circuit 116 are not required.

[0030] The second stage circuit 116 implements a unitary U(G k−1, ε) and is coupled to a measurement circuit 118 and a second stage classically controlled switch 120. As with the first stage circuit 106, the second stage classically controlled switch 120 allows the PQF circuit 100 to continue in additional stages if and only if a measurement result obtained by the measurement circuit 118 is unfavorable. If the result is favorable, the second stage classically controlled switch 120 couples the processed input qubits to provide the desired output V|ψ. Additional stages can be provided, but are not shown in FIG. 1.

[0031] A fallback circuit 136 is coupled to the input qubits as processed by circuit stages 106, 116 (and other stages) and to ancilla qubits 134. The fallback circuit 136 implements the unitary U(G.sub.0, ε) and produces the output V|ψ.

[0032] Let F.sub.j|input be an undesired result of a j-th round of processing as would be signaled by an unfavorable measurement result during execution. Then G.sub.j−1=G.sub.jF.sub.j.sup.† and all G.sub.j, j=0, . . . , k−1 are computed at compile time.

[0033] While additional circuits such as circuits 106, 116 can be provided, in most cases the number k of rounds that need to be applied until the target gate G is implemented is quite small, i.e., only a few such circuits are necessary to achieve nearly optimal performance, typically between 2 and 5 circuits. In both PQF and RUS circuit designs, a unitary operation(s) U is synthesized to act on n+m qubits, of which n are target qubits and in are ancillary qubits. A key difference is that in PQF designs, the unitary may vary from round to round, while it stays the same in RUS designs.

PQF Design Method Overview

[0034] Referring to FIG. 2, a representative circuit design method 200 includes obtaining an input rotation, circuit precision, and a number of stages k at 201. At 202, an implementation of a target unitary is obtained such that the implementation has a probability of success and failure. At 204, it is determined if additional stages are needed. If not, at 206, a fallback circuit is defined based on the kth stage failure. If additional stages are selected, at 208, a counter is decremented, and at 210, an input to a next (k-1) stage is obtained based on the failure of the kth stage. Additional stages are then determined in the same manner.

[0035] Determination of a kth stage is described in detail below. In general, a phase factor e.sup.iθ is expressed as a unimodal cyclotomic rational (z/z*), wherein z∈ω] by finding an approximate solution of an integer relation problem. In a next step, several rounds of modification z(rz) wherein r †[92 ] so that a unitary can be expressed using a set of cyclotomic integers based on a basis in which the PQF circuit is to be implemented. In general, this modification is carried out so that (a) a norm equation |y|.sup.2=2.sup.L−|rz|.sup.2 is solvable for y∈[ω],L∈ and (b) the one-round success probability |rz|.sup.2/2.sup.L is sufficiently close to 1. In a next step, the two-qubit matrix corresponding to the unitary part of the PQF sub-circuit is assembled and during a final step, a two-qubit PQF sub-circuit is synthesized.

Phase Factor Approximation by Cyclotomic Rationals

[0036] For any basis, the elements of a unitary U to be synthesized are selected from a suitable set of cyclotomic integers. Let ζ=e.sup.2πi/m be the m-th primitive root of unity and consider the corresponding ring of cyclotomic integers [ζ]. An arbitrary phase factor can be represented by a unimodal cyclotomic rational z*/z wherein z ∈[ζ] as discussed below.

[0037] Let θ be a real angle, so that |z*/z−e.sup.iθ|=2|Im(ze.sup.iθ/2)|/|z|. The phase factor e.sup.iθ is representable exactly as z*/z if and only if Im(ze.sup.iθ/2)=0. This factor is approximately so representable at absolute precision .sub.ε if and only if |2Im(ze.sup.iθ/2)|<ε|z|.

[0038] Consider the standard integer basis {1,ζ, . . . , ζ.sup.d−1} in [ζ]. Represent z in this basis, as z=a.sub.0+a.sub.1ζ+. . . +aζ.sub.d−1ζ.sup.d−1 wherein {a.sub.0,a.sub.1, . . . , a.sub.d−1} are ordinary integers. By direct complex expansion, Im(ze.sup.iθ/2) is a linear form with real coefficients in {a.sub.0,a.sub.1, . . . , a.sub.d−1}. This form can be expanded as F(a, x(θ))=a.sub.0x.sub.0(θ)+a.sub.1x.sub.1(θ)+. . . +a.sub.d−1x.sub.d−1(θ), wherein x.sub.j(θ)=sin(θ/2+2πj/m), j=0, . . . , d−1 is the corresponding real vector. For θ in general, this vector does not have zero components. It is also helpful to observe that for |θ|<π/2 at least one of x.sub.j is well separated from zero (e.g. at least one x.sub.j(θ) is greater than sin(2π/m)).

[0039] Representing the phase factor e.sup.iθ exactly as cyclotomic rational is equivalent to solving an integer relation with real coefficients F (a, x(θ))=0 for a. Furthermore, when this relation is not solvable, an approximate integer relation is solved, i.e., {a.sub.0,a.sub.1, . . . , a.sub.d−1} is found such that F (a, x(θ))|<δ. Such approximate relations can be found for arbitrarily small positive δ.

[0040] In order to find these solutions, the PSLQ integer relation algorithm can be used. An initial approximation of e.sup.iθis obtained such that z*/z˜e.sup.iθ, wherein z is a cyclotomic integer. For a selected real θ and a cyclotomic integer z=aw.sup.3+bω.sup.2+cω+d,a,b,c,d ∈,|z*/z−e.sup.iθ|<ε 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|.

[0041] Thus e.sup.iθ is representable exactly only if ε|z|=0 . If ε|z| is small, then |z*/z−e.sup.iθ is small as well. An integer relation algorithm can be used to find a relation between a set of real numbers x.sub.1, . . . , x.sub.n and a candidate vector defined by a set of integers a.sub.1, . . . , a.sub.n, not all zero, such that:

a.sub.1x.sub.1+. . . +a.sub.nx.sub.n=0.

[0042] Most commonly an integer relation algorithm makes iterative attempts to find an integer relation until the size of the candidate vector a.sub.1, . . . , a.sub.n exceeds a certain pre-set bound or a.sub.1x.sub.1+. . . +a.sub.nx.sub.n falls below a selected resolution level. Such an algorithm can be used to reduce the size of a.sub.1x.sub.1+. . . +a.sub.nx.sub.n to an arbitrarily small value.

[0043] 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. As noted above, upon termination, the algorithm provides the integer relation candidate vector a.sub.1, . . . , a.sub.n for the integer relation a.x=a.sub.1x.sub.1+. . . +a.sub.dx.sub.d such that |a,x| can be made arbitrarily small after a large enough number of iterations. In the examples disclosed herein, iterations terminate when the equivalent of the |z*/z−e.sup.iθ|<εinequality is satisfied.

[0044] In the disclosed examples, the cases m=4,8,12 are considered, which correspond to the Clifford+V, Clifford+T, and Clifford+π/12 bases respectively.

Probability Modifier

[0045] Let ζ=e.sup.2πi/m and limit the analysis to m that is a multiple of 4 (so that the ring [ζ] contains i=√{square root over (−1)}). Define a unitarization base v:v=√{square root over (5)} for m>4 and v=√{square root over (5)} for m=4 (the latter for the Clifford+V basis). Let θ be the target angle of rotation and z*/z,z ∈[ζ] be an .sub.ε-approximation of the phase factor e.sup.iθ. The synthesis of both purely unitary and measurement-assisted circuits around z*/z hinges on the existence of a unitary matrix of the form

[00008]$\frac{1}{v^L}\left[\begin{array}{cc}z& y\\ -y^{*}& z^{*}\end{array}\right],$

wherein y ∈[ζ], L∈.

[0046] The corresponding matrix

[00009]$\frac{1}{v^{L_r}}\left[\begin{array}{cc}\mathrm{rz}& y\\ -y^{*}& {\mathrm{rz}}^{*}\end{array}\right]$

can be determined by solving the norm equation |y|.sup.2=V.sup.2L.sup.r−|rz |.sup.2 for y ∈[ζ]. This equation is referred to as a norm equation over the cyclotomic integers, and its solutions are well known. In some cases, this norm equation can be referred to as easily solvable when an integer N(v.sup.2L.sup.r−|rz|.sup.2) is easy to factor and the norm equation has a solution. The exact form of the norm equation depends on the selected basis. For the case of ζ=i (which corresponds to m=4), any phase factor e.sup.i6 can be approximated with a Gaussian rational z*/z,z ∈[i] wherein |z| is in Or(ε.sup.−1/2).

PQF Circuit Design

[0047] As a result of the previous stages, a unitary matrix such as

[00010]$V=\frac{1}{{\sqrt{5}}^{L_r}}\left[\begin{array}{cc}\mathrm{rz}& y\\ -y^{*}& {\mathrm{rz}}^{*}\end{array}\right]$

is available, wherein L.sub.r=j log.sub.5(r.sup.2|z|.sup.2)k≦log.sub.5(|z|.sup.2)+O(log(log.sub.5(|z|.sup.2))) and r.sup.2|z|.sup.2/5.sup.L.sup.r>1−1/log.sub.5(|z|.sup.2). V is exactly represented by a unitary Clifford+V circuit with V-count of at most L.sub.r. The two-qubit PQF matrix U=CNOT(1V)CNOT is exactly represented by a circuit with the same V-count.

[0048] By direct computation, when U is applied to |ψ0 and the second qubit is measured, then:

[0049] (0) on measurement result 0, the Λ(z*/z)˜Λ(e.sup.iθ) rotation gate is effectively applied to the primary qubit wherein Λ(*) is a rotation about the z-axis by an angle *; and

[0050] (1) on measurement result 1, the Λ(−y/y*) rotation gate is applied to the primary qubit, wherein Λ(*) is a rotation about the z-axis by an angle *. Thus the level one fallback circuit must be a unitary .sub.ε-approximation of the rotation gate Λ(−y*/ye.sup.iθ). Fallback circuits at subsequent levels have similar structure.

[0051] Given a unitary matrix V that is determined as described above, a two-qubit unitary

[00011]$U=\mathrm{CNOT}\left(I.Math.V\right).Math.\mathrm{CNOT}=\left[\begin{array}{cc}V& 0\\ 0& \mathrm{XVX}\end{array}\right]$

is constructed. Denote the primary input state for the round as |ψ. The subcircuit for the round uses the first qubit as primary and the second qubit, which is initialized to |0> as ancillary. The unitary U is then applied to the initial state |ψ|0 and the (ancillary) second qubit is measured in the computational basis. When the measurement result is 0, then the primary output is reduced to

[00012]$\left[\begin{array}{cc}1& 0\\ 0& z^{*}/z\end{array}\right].Math..Math.\psi 〉$

which is the desired ε-approximation of R.sub.z(θ). When the measurement result is 1, then the primary output is reduced to

[00013]$\left[\begin{array}{cc}1& 0\\ 0& -y/y^{*}\end{array}\right].Math..Math.\psi 〉.$

[0052] Unless −y/y* is ε-close to e.sup.iθ the tail end of the PQF protocol now has to implement the rotation R.sub.z(θ′) so that θ′=θ−arg(−y/y*) is the target rotation for the next round of the PQF protocol. If more than one round is desired, this procedure is repeated for the angle θ′.

[0053] A representative compilation method 300 illustrating the above procedure is provided in FIG. 3. At 302, a rotation angle, a precision, and a number of rounds are provided. At 304, if k=0 (the last stage), a fallback circuit is established. Otherwise, at 306, an initial approximation of e.sup.iθ is obtained. At 308, a value of z is obtained such that z*/z˜e.sup.iθ, wherein z∈ω]. At 310, a modifier r is found with a solvable norm equation and high success probability. If the gate set is Clifford+T or Clifford+π/12 then r ∈Z[√{square root over (2)}]. If the gate set is Clifford+V then r ∈Z. In the case of Clifford+V, the initial approximation of e.sup.iθ at 306 can be based on determination of a Gaussian rational number in this basis. The Gaussian rational can be modified to provide for a solvable two squares equation at 310.

[0054] At 312, the modifier is used so that (rz)*/(rz)˜e.sup.iθ. At 312, a PQF circuit is obtained for the current round based on r, z and at 316, a two-qubit PQF matrix is found for the current round. At 318, the PQF is synthesized for the current round. At 320, an undesired angle is determined based on stage failure and at 322, steps 306-320 are repeated for additional rounds (i.e., until k=0). At step 324 a unitary to compensate for the failure in the previous step is computed so that in step 326 another attempt of implementing the overall target gate can be made. At run-time, in case the binary classical control BC in step 326 indicates success, the protocol is terminated at this point as the target unitary G has been correctly implemented. In case the binary classical control indicates failure, the protocol continues with the application of the compensation unitary F.sub.k-1 which has been precomputed recursively at compile time.

[0055] In PQF circuit compilations, a number of stages k is selected so that a sequence of probabilistic sub-circuits is obtained, along with a deterministic fallback circuit. At PQF compile-time, the number of stages k can be determined as a function of the difficulty, or cost, of implementing the stages and the fallback circuit. The method or function used to determine k can be for example minimizing the expected non-Clifford gate count. Alternatively, the number of rounds can be set to the smallest k value for which q.sup.kC.sub.F<1, where C.sub.F is the cost of the fallback circuit and q is the probability of failure. When a PQF circuit is executed with a particular input value, the number of stages that is needed typically depends on the input value. Thus, PQF circuit run-time is a function of the input value and the measurement outcomes. If a given round succeeds, then the remainder of rounds and the fallback circuit will not be executed.

[0056] Referring to FIG. 4, a Markov chain 400 is derived from the PQF synthesized by the PQF design method. The nodes of the graph specify the unitary transformations 410-430 F.sub.k, F.sub.k−1, . . . , F.sub.1 that are applied to the input state at each respective round in case the outcome of the measurement was unsuccessful. The overall maximum number k of attempts to implement a target unitary transformation G 440 is fixed before compilation of the circuit using the PQF design method. At execution of the PQF circuit, each transition is probabilistic and is induced by applying a multi-qubit unitary to the primary qubit and at least one ancilla qubit. The probability of success of the jth round is denoted by p .sub.j, implying a probability of 1−p.sub.j for the unsuccess in the jth round. A unitary G.sub.j=G.sub.j−1F.sub.j.sup.+ is computed recursively that is used to compensate for the error being made in the jth step.

[0057] FIG. 5 and 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.

[0058] With reference to FIG. 5, an exemplary system for implementing the disclosed technology includes a general purpose computing device in the form of an exemplary conventional PC 500, including one or more processing units 502, a system memory 504, and a system bus 506 that couples various system components including the system memory 504 to the one or more processing units 502. The system bus 506 may 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 memory 504 includes read only memory (ROM) 508 and random access memory (RAM) 510. A basic input/output system (BIOS) 512, containing the basic routines that help with the transfer of information between elements within the PC 500, is stored in ROM 508.

[0059] As shown in FIG. 5, computer-executable instructions for PQF circuit synthesis are stored in a memory portion 516 and includes instructions for, for example, solving integer equations, evaluating and solving norm equations, and deterministic search for determination of r values. In addition, a memory portion 518 stores circuit definitions for circuits that, upon success, implement an approximation to a desired unitary or procedures associated with the disclosed methods. Fallback circuit definition and procedures are stored in a memory portion 519. Computer-executable instructions are also stored for receiving rotation angles and precisions as well as communicating circuit definitions.

[0060] The exemplary PC 500 further includes one or more storage devices 530 such 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 bus 506 by 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 PC 500. 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.

[0061] A number of program modules may be stored in the storage devices 530 including 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 devices 530 as well as or in addition to the memory 504. A user may enter commands and information into the PC 500 through one or more input devices 540 such 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 units 502 through a serial port interface that is coupled to the system bus 506, but may be connected by other interfaces such as a parallel port, game port, or universal serial bus (USB). A monitor 546 or other type of display device is also connected to the system bus 506 via 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.

[0062] The PC 500 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 560. In some examples, one or more network or communication connections 550 are included. The remote computer 560 may 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 PC 500, although only a memory storage device 562 has been illustrated in FIG. 5.

[0063] The personal computer 500 and/or the remote computer 560 can 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.

[0064] When used in a LAN networking environment, the PC 500 is connected to the LAN through a network interface. When used in a WAN networking environment, the PC 500 typically 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 computer 500, 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.

[0065] With reference to FIG. 6, an exemplary system for implementing the disclosed technology includes computing environment 600, where compilation into braid pattern circuits is separated from the quantum processing that consumes the compiled circuits. The environment includes a quantum processing unit 602 and one or more monitoring/measuring device(s) 646. The quantum processor executes quantum circuits that are precompiled by classical compiler unit 620 utilizing one or more classical processor(s) 610. The precompiled quantum circuits such as PQF circuits 603 are downloaded and the instruction set is communicated to the qubits via a bus 606.

[0066] With reference to FIG. 6, 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) 660 outside the computing environment 600 utilizing one or more memory and/or storage device(s) 662, then downloaded as necessary into the computing environment 600 via one or more communication connection(s) 650. Alternatively, the classical compiler unit 620 is coupled to a classical processor 610 and a PQF compiler procedure library 621 that contains some or all procedures necessary to implement the methods described above as well as a PQF circuit library 623 that stores compiled circuits.

[0067] 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 embodiments.