TRADING TGATES FOR QUBITS IN ARBITRARY STATE AND UNITARY SYNTHESIS

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A method, comprising:
 inputting a quantum algorithm description;
synthesizing the quantum algorithm description into a synthesized quantum circuit representation, wherein the quantum circuit representation is implementable on a quantum computing device, and wherein the synthesizing comprises assigning one or more ancilla qubits to be used for at least one nonClifford operation; and
outputting the quantum circuit representation.
0 Assignments
0 Petitions
Accused Products
Abstract
Efficient synthesis of arbitrary quantum states and unitaries from a universal fault tolerant gateset (e.g., Clifford+T) is a goal in quantum computation. As physical quanturn computers are fixed in size, all available qubits should be used if it minimizes overall gate counts, especially that of the expensive Tgates. In this application, a quantum algorithm is described for preparing any dimensionN quantum state specified by a list of N classical numbers, that realizes a tradeoff between space and Tgates. Example embodiments exploit (λ) ancilla qubits, to reduce the Tgate cost to
Notably, this it proven to be optimal up to logarithmic factors for any λ=o(√{square root over (N)}) through an unconditional gate counting argument. Though (N) Clifford gates are always required, only (√{square root over (N)}) Tgates are needed in the best case, which is a quadratic improvement over prior art. Similar statements are provien for unitary synthesis by reduction to state preparation.
0 Citations
No References
No References
20 Claims
 1. A method, comprising:
inputting a quantum algorithm description; synthesizing the quantum algorithm description into a synthesized quantum circuit representation, wherein the quantum circuit representation is implementable on a quantum computing device, and wherein the synthesizing comprises assigning one or more ancilla qubits to be used for at least one nonClifford operation; and outputting the quantum circuit representation.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 10)
 9. The method of chant 1, wherein the method is performed to synthesize arbitrary unitaries.
 11. One or more computerreadable media storing computerexecutable instructions, which when executed by a classical computer cause the classical computer to perform a method of controlling a quantum computing device, the method comprising:
inputting a quantum algorithm description; synthesizing the quantum algorithm description into a synthesized quantum circuit representation, wherein the quantum circuit representation is implementable on a quantum computing device, and wherein the synthesizing comprises assigning one or more ancilla qubits to be used for at least one nonClifford operation; and outputting the quantum circuit representation.  View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
 20. A quantum circuit comprising a combination of Clifford and nonClifford gates, wherein the number of nonClifford gates is controlled by a tunable factor, wherein the tunable factor achieves a desired spacedepth tradeoff for the quantum circuit.
1 Specification
This application claims the benefit of U.S. Provisional Application No. 62/752,887 entitled “TRADING TGATES FOR QUBITS IN ARBITRARY STATE AND UNITARY SYNTHESIS” and filed on Oct. 30, 2018, which is hereby incorporated herein by reference in its entirety.
This application relates to quantum computing. In particular, this application relates to tools and techniques for trading Tgates for qubits in an arbitrary state and unitary synthesis.
Efficient synthesis of arbitrary quantum states and unitaries from a universal faulttolerant gateset (e.g., Clifford+T) is a goal in quantum computation. As physical quantum computers are fixed in size, all available qubits should be used if it minimizes overall gate counts, especially that of the expensive Tgates. In this application, a quantum algorithm is described for preparing any dimensionN quantum state specified by a list of N classical numbers, that realizes a tradeoff between space and Tgates. Example embodiments exploit (λ) ancilla qubits, to reduce the Tgate cost to
Notably, this is proven to be optimal up to logarithmic factors for any λ=o(√{square root over (N)}) through an unconditional gate counting argument. Though (N) Clifford gates are always required, only (√{square root over (N)}) Tgates are needed in the best case, which is a quadratic improvement over prior art. Similar statements are provien for unitary synthesis by reduction to state preparation.
In certain embodiments, a quantum algorithm description is input (e.g., into a classical computer). The quantum algorithm description is synthesized into a synthesized quantum circuit representation (e.g., using the classical computer and using an appropriate compilation/synthesis tool for quantum computing). In the illustrated embodiment, the quantum circuit representation is implementable on a quantum computing device, and the synthesizing comprises assigning one or more ancilla qubits to be used for at least one nonClifford operation. The synthesized quantum circuit representation is output (e.g., the synthesized quantum circuit representation is a set of lowlevel machine instructions for .implementation on a quantum device).
Any of the disclosed embodiments can be implemented by one or more computerreadable media storing computerexecutable instructions, which when executed by a computer cause the computer to perform any of the disclosed methods. Also disclosed herein are systems for performing embodiments of the disclosed embodiments comprising a classical computer configured to program, control, and/or measure a quantum computing device. The foregoing and other objects, features, and advantages of the disclosed technology will become more apparent from the following detailed description, which proceeds with reference to the accompanying figures.
As used in this application, 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. Further, as used herein, the term “and/or” means any one item or combination of any items in the phrase.
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 highlevel 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 the art.
Many realworld applications of quantum algorithms rely on the input of classical data into a quantum system. It is often the case where achieving quantum speedups uses the ability to coherently access classical data in superposition. Examples where this is a useful step include machine learning, simulation of physical systems, solving systems of linear equations, data regression, and sampling.
The central challenge is synthesizing some arbitrary unitary A∈^{N×N }specified by a list of N^{2 }complex coefficients. In any scalable approach to quantum computation, unitaries are desirably expressed in terms of a universal faulttolerant quantum gate set, such as Clifford gates {H, S, C_{NOT}} and T gates. Also of interest is synthesizing any unitary that prepares an arbitrary quantum state A0=ψ of dimension: N—a special case also of interest. This state is similarly specified by N coefficients {right arrow over (a)}∈^{N }that are completely arbitrary.
Solovay and Kitaev were the first to recognize that any singlequbit unitary could be ϵapproximated using (log^{c}(1/ϵ)) (for c=3.97) faulttolerant gates. See M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 1st ed. (Cambridge University Press, 2004). Through a series of work, this has since been improved to an optimal c=1. See, e.g., V. Kliuchnikov, D. Maslov, and M. Mosca, Phys. Rev. Lett. 110, 190502 (2013); N. J. Ross, Quantum Info. Comput. 15, 932 (2015). By bootstrapping these results, it is known that without any ancilla qubits, (N^{{1,2}) }log (N/ϵ) gates suffice to synthesize any {quantum state, unitary}. Though early approaches exploit ancilla qubits for the N=2 case, these only achieve constant factor improvements. See V. Kliuchnikov, B. Maslov, and M. Mosca, Phys. Rev. Lett. 110, 190502 (2013). Through gatecounting arguments (see, e.g., A. W. Harrow, B. Recht, and I. L. Chuang, Journal of Mathematical Physics 43, 4445 (2002), https://doi.org/10.1063/1.1495899), the dimension scaling and log (1/ϵ) factor appears optimal. Thus it appears there is nothing new to discover. All that remains is more and more precise constant factors.
However, not all faulttolerant quantum gates are equal. It is now understood that faulttolerant Clifford gates {H, S, C
In this disclosure, an approach is disclosed that focuses on minimizing the T count. Notably, it was found that exploiting a variable number (λ) of ancilla qubits enables a (λ) improvement in the T count for λ∈[1, √{square root over (N)}] seen in Table 1, while keeping the Clifford count roughly unchanged. This leads to a T count of (√{square root over (N)}), representing a quadratic speedup, for the case of preparing arbitrary pure states
or density matrices
through their purification
Of some practical interest is circuit depth, Which also decreases by a factor (λ) for any λ∈[1, N]. Moreover, all unconditional gate complexity lower bound is proven, independent of any complexitytheoretic assumptions, that demonstrates that an embodiment of the disclosed approach realizes an optimal ancillaqubit and T count tradeoff, up to logarithmic factors. A similar statement for synthesizing arbitrary unitaries is also proven.
Of course, the full quadratic speedup may not always be achievable, or practical. Space constraints of the physical machine limit ancilla usage, and T gates are only finitely expensive. Nevertheless, the ability to tradeoff space for a T gate advantage will be very useful to optimizing physical qubit resources in quantum computers.
It is also useful to relate the disclosed approach to those that decompose additionally into black box datalookup oracles O that allow coherent access to arbitrary classical data {right arrow over (a)} like
Ox00=xa_{x}garbage_{x}. (3)
For instance, Grover search allows for arbitrary state preparation using (√{square root over (N)}N) queries. See L. K. Grover, Proceedings of the Twentyeight Annual ACM Symposium on Theory of Computing, STOC '"'"'96, 212 (1996). In fact, there exists classical data such that preparing any ψ requires only (polylog(N)) queries and additional primitive quantum gates. This, of course, hides the fact that implementing these oracles cost at least Ω(N) primitive gates in the worst cases.
The improved T gate scaling disclosed herein stems from an improved implementation of the datalockup oracle of Equation 3. This improvement is referred to herein as a ‘S
The description begins by describing this network. Subsequently, the ‘S
The unitary datalookup oracle of Equation 3 accepts an input number state x∈^{N }where x∈[N], and returns a bbit number a_{x}∈{0, 1}^{b}, where the N values of a_{x }are unstructured but known. The attached garbage state may always be uncomputed by applying O in reverse. An embodiment of the disclosed approach interpolates between standard implementations of O. These are S
The S
Thus O is realized by choosing
to either be identity or the PauliX gate depending on the bit string a_{x}. As illustrated in block diagram 100 of
The S
The disclosed S
is determined only by the dimension of the S
Preparation of an arbitrary dimension N=2^{n }quantum state
using the S
For any bitstring y∈{0, 1}^{w }of length w≤n, let the probability that the first w qubits of ψ are in state
Thus a singlequbit rotation e^{−iYθ}0 by angle θ=cos^{−1 }√{square root over (p_{0})} prepares the state ψ_{1}=√{square root over (p_{0})}0+√{square root over (p_{1})}1, where p_{0 }is the probability that the first qubit of ψ is in state 0. One can recursively apply single qubit rotations on the w+1^{th }qubit conditioned on the first w qubits being in state y. The rotation angles θ_{y}=cos^{−1 }√{square root over (p_{y0}/p_{y})} are chosen so that the state produced ψ_{w+1} reproduces the correct probabilities on the first w+1 qubits. For instance when w=1, one can map
These conditional rotations are implemented using a sequence of datalookup oracles O_{1}, . . . , O_{n−1}, where O_{w }stores a bbit approximation of all θ_{y }where y∈{0, 1}^{w}. At the w^{th }iteration,
Note that any garbage registers are omitted as they are always uncomputed. Also, the second line is implemented using b singlequbit rotations each controlled by a bit of θ_{y}. The complex phases of the target state ψ are applied to ψ_{n} by a final step with a datalookup oracle storing ϕ_{x}=arg[a_{x}/√{square root over (p_{x})}]. Thus (b log N) singlequbit rotations are applied in total.
These oracles are implemented with the S
which is then added to the total T count of
for synthesizing all singlequbit rotations each to error δ using the phase gradient technique (see, e.g., C. Gidney, Quantum 2, 74 (2018)). The error of the resulting state ψ′ produced is determined by the number of bits b used to represent the rotation angles, in addition to rotation synthesis error δs. Adding these errors leads to
which is bounded by ϵ with the choice
and δ=Θ(ϵ). As a function of ϵ, the total T gate complexity is then
A similar calculation for the total depth leads to the complexity in Table 1.
In some applications, it suffices to prepare the density matrix
through a quantum state
of Eq. (2) where the number state x is entangled with some garbage that depends only on x. By allowing garbage, it was shown by R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, arXiv preprint arXiv:1805.03662 (2018) that strictly linear T gate complexity in N is achievable, using a S
The original approach is based on an observation, By comparing a bbit number state a together with a uniform superposition state
over 2^{b }elements, a may be mapped to
where we denote a uniform superposition after the first a elements by
This may be implemented using quantum addition (see S. A. Cuccaro, T. C. Draper, S. A. Kutin, and D. P. Moulton, arXiv preprint quantph/0410184 (2004)), which costs (b) Clifford+T gates with depth (b).
This observation is converted to statepreparation in four steps. First, the normalized coefficients
are rounded to nearest integer values such that ∥{right arrow over (a)}′∥_{1}=N2^{b}. Second, the datalookup oracle that writes two numbers a″_{x}∈[2^{b}] and f(x)∈[N] such that a′_{x}=a″_{x}+Σ_{y∈{f}_{−1}_{(x)}}(2^{b}−a″_{y}). Thus
Ox00=xa″_{x}f(x), (6)
where the irrelevant garbage state has been omitted. Third, the oracle O is applied to a uniform superposition over x, and the comparator trick of Eq. (5) is applied. This produces the state
Finally, f(x) is swapped with x, controlled on the 1 state. This leads to a state
After tracing out the garbage register, the resulting density matrix ρ′ approximates the desired state ρ with trace distance
∥ρ′−ρ∥_{1}=(2^{−b})≤ϵ. (7)
The T gate complexity is then the cost of the datalookup oracle of Eq. (6) plus (b) for the comparator of Eq. (5), plus (log N) for the controlled swap with f(x). By implementing this datalookup oracle with the S
where b=(log (1/ϵ)) is chosen.
In this section, the optimality of the abovedescribed construction is proven through a circuit counting argument. The most general circuit on q qubits that uses Γ Tgates has the canonical form C·Π_{j=1}^{Γ}e^{−iπP}^{j}^{/8}, where each P_{j }is one of 4^{q }possible Pauli operators, and C is one of 2^{(q}^{2}^{) }possible Clifford operators. Thus the number of unique quantum circuits is at most
Unique quantum circuits=(4^{qΓ+}^{(q}^{2}^{)} (8)
A lower bound on the cubit and Tgate complexity of the datalookup oracle of Equation 3 is obtained by counting the number of unique Boolean functions f:[N]→{0, 1}^{b}. As there are 2^{bN }such functions, one can compare with Eq. (8). This leads to a lower bound on the spaceTgate product
qΓ=Ω(bN−q^{2}). (9)
As the S
A similar lower bound on state preparation is obtained by counting the number of dimensionN quantum states that a distinguishable with error ϵ. Without loss of generality, one can only count quantum states ψ∈^{N }with real coefficients. These states live on the surface a unitball _{N }of dimension N, with area
Let one now fix a state ψ. Then the states χ that satisfy ∥ψ−χ∥≤ϵ live inside a ϵball _{N−1 }with volume
Thus there are at least
quantum states. Once again by comparing with Eq. (8), one can obtain a Tgate lower bound of
qΓ=Ω(N log(1/ϵ)−q^{2}). (10)
This also matches the cost of the disclosed approach in Eq. (8) up to logarithmic factors, so long as λ=o(√{square root over (N/log(1/ϵ)))}. An analogous argument can be made for density matrix preparation by considering the unit simplex instead of the unit ball.
The approach by Shende, Bullock, and Markov synthesizes a unitary A that prepares a pure state
with arbitrary coefficients in N=2^{n }dimensions. A key element of the circuit are j∈{0, 1, . . . n−1} multiplexors U_{j }where
for some set of rotation angles θ_{j, x}. Each multiplexor is applied twice—once to create a pure state with the right probabilities a_{x}^{2}, and once to apply the correct phase e^{i arg[a}^{x }^{]}. In the following, these multiplexors U_{j }are approximated by a unitary U′_{j }to error δ like ∥U′_{j}−U_{j}∥≤δ. Using a triangle inequality, this leads to an approximate A′ such that
∥A′−A∥≤2nδ. (12)
Hence the state ψ′=A′0 approximates ψ with error
∥ψ′−ψ∥≤∥A′−A∥≤2nδ. (13)
In embodiments of the disclosed approach, these multiplexors are implemented using the datalookup oracles O_{j }that encode a bbit approximation θ′_{j, x }of these angles, that is θ′_{j, x}−θ_{j, x}≤2^{−b}. In other words,
O_{j}x0=xθ′_{x,k}. (14)
Using the controlled phase gradient operation
this implements the multiplexor U_{j}^{(1) }where
This approximates U_{j }with error
∥U′_{j}−U_{j}∥≤∥I−e^{iπ2}^{−b}∥≤π2^{−b}. (17)
One also needs to account for he cost of approximating the phase gradient operation. A naive approach implements G
The resulting unitary A″ prepares the state ψ″=A″0 that approximates ψ with error
∥ψ″−ψ∥≤∥A″−A∥≤πn2^{−b+1}+nγ≤ϵ,
which is controlled by choosing
A better approach (see C. Gidney, Quantum 2, 14 (2018)) implements the phase gradient G
A
The T cost: of each adder is (b). As the Fourier state is not consumed, an approximation ′ of it to error γ has a onetime T cost of (b log (1/γ) The resulting unitary A″′ prepares the state ψ″′=A″′0′. This approximates ψ with error
∥ψ″′−ψ∥≤πn2^{−b+1}+γ≤ϵ,
which is controlled by choosing
Consider N×N unitary matrix U and let integer K be between 1 and N. Isometry synthesis problem for U is to find a quantum circuit that implements unitary V, such that its first K columns equal to first K columns of V. To define approximate unitary isometry problem, one can use the notion of weak semitwo norm ∥A∥_{2, k}=max_{b<K}∥Ab∥. Weak semitwonorm with parameter K of matrix A is the biggest norm of vectors ∥Ax∥ where x goes over the first K standard basis vectors. Note that ∥V−U∥_{2, K}=0 if and only if first K columns of V and U coincide. This is why map A∥A∥_{2, K }is called seminorm: ∥A∥_{2, K}=0 does not imply that A=0. The approximate isometry synthesis problem for target unitary U and precision ε is to find a circuit that implements unitary V such that ∥V−U∥_{2, K}≤ε.
It has been shown in E. Knill, “Approximation by Quantum Circuits,” arXiv:quantph/9508006 (1995) [quantph] that isometry synthesis problem can be reduced to K state synthesis problems and synthesis of K operators exp(e^{iϕ}e_{1}e_{1}) where e_{1} is the first standard basis vector. The idea, is illustrated here for K=N. Using eigenbasis u_{k} unitary matrix U can be written as exp (Σ_{k=1}^{N}iϕ_{k}u_{k}u_{k}). Introducing operations R_{k}=exp(e^{iϕ}^{k}u_{k}u_{k}) one can express U as product Π_{k=1}^{N}R_{k}. Let V_{k }be a unitary operator that prepares state u_{k }starting from e_{1} then R_{k}=V_{k}exp(e^{iϕ}^{k}e_{1}e_{1})V_{k}^{†}. The case K<N follows from the Lemma 3.10 on Page 10. The lemma shows that any unitary matrix U can be replaced by a unitary matrix U′ such that first K columns of U and U′ coincide and U′ has at least N−K eigenvalues equal to 1. This implies that at least N−K operators R_{k }in the decomposition of U′ are identity operators. Using outline scheme the cost of isometry synthesis is twice the cost of state synthesis of each eigenvector u_{k} plus the cost of synthesis of each of exp(e^{iϕ}^{k}e_{1}_{1}).
Alternatively, one can use Householder reflections decomposition (see, e.g., A. S. Householder, Journal of the ACM 5, 339 (1958) to find another U″ that is a product of K reflections exp(e^{iπ}v_{j}v_{j})=−2v_{j}v_{j} and diagonal matrix diag(e^{iϕ′}^{1}, . . . , e^{iϕ′}^{K}, 1, . . . , 1) such that first K columns of U and U″ coincide. Note that the representation of a unitary as a product of N operators exp(e^{iϕ}^{j}v_{j}v_{j}) is not unique, another method for finding such decomposition closely related to A. S. Householder, Journal of the ACM 5, 339 (1958) can be found in P. A. Ivanov, E. S. Kyoseva, and N. V. Vitanov, (2007), 10.1103/PhysRevA.74.022323, arXiv:0708.2811. It has a slight advantage in that it does not require finding eigenbasis of U.
It is possible to get rid of the need for implementing diag(e^{iϕ′}^{1}, . . . , e^{iϕ′}^{K}, 1, . . . , 1) or exp(e^{iϕ}e_{1}e_{1}) by using one ancillary qubit as discussed in V. Kliuchnikov, ArXiv eprints, 1 (2013), arXiv:1306.3200 [quantph]. To implement unitary U it is sufficient to implement unitary W=01⊗U+10⊗U^{†} by using reflection decomposition. Let u_{1}, . . . , u_{N }be columns of U. According to Lemma 1 on Page 1, operator W is equal to the product of reflections −2ψψ where ψ goes over vectors w_{j}=(1⊗j−0⊗u_{j})/√{square root over (2)} for j from 1 to N. It is sufficient to take product of reflections around w_{j} for j from 1 to K if one is interested in implementing first K columns of U. Finally, note that given unitary V′_{j }that prepares u_{j} starting from e_{1}, one can prepare state w_{j} starting from 0⊗e_{1}. First apply Hadamard gate to the first qubit, then the sequence of CNOT gates to prepare state 1⊗j+0⊗e_{1} and finally apply ControlledV′_{j }negatively controlled on the first qubit. When this method is applied to the synthesis of sparse isometries, the states being synthesized are again sparse. The number of nonclifford gates used to synthesize an isometry is twice the number of nonclifford gates needed to synthesize each of K columns controlled on a qubit.
Approximate isometry synthesis reduces to approximate state synthesis by using discussed decompositions and properties of seminorms ∥A∥_{2, K }discussed in E. Knill, 1 (1995), arXiv:quantph/9508006 [quantph].
The total number of isometries within at least distance ϵ from each other can be estimated using Lemma 4.3 on Page 14. Roughly, the number of isometries Ω((1/ϵ)^{KN}). i
At 610, various input parameters are input. In the illustrated embodiment, the input parameters are: (1) Length N=^{n }list of bbit numbers L=a_{0}a_{1}, a_{N−1}; (2) A number Between 1 and N; (3) nqubit index register X; (4) bqubit ancilla registers R=R_{0}, R_{1}, R_{−1}; and (5) quantum state x>.
At 612, the Select quantum algorithm is applied to load elements of list L in parallel to register R.
At 614, the Swap quantum algorithm is applied to move one of the registers R to a standard output.
At 616, a quantum state quantum state x>a_{x}>garbage _{x}> is output.
At 710, a quantum algorithm description is input (e.g. into a classical computer). The quantum algorithm description can be, for example, a description in a highlevel functional language (e.g., F #).
At 712, the quantum algorithm description is synthesized into a synthesized quantum circuit representation (e.g., using the classical computer and using an appropriate compilation/synthesis tool for quantum computing, such as LIQUi>). In the illustrated embodiment, the quantum circuit representation is implementable on a quantum computing device, and the synthesizing comprises assigning one or more ancilla qubits to be used for at least one nonClifford operation.
At 714, the synthesized quantum circuit representation is output. The synthesized quantum circuit representation is a set of lowlevel machine instructions for implementation on a quanturn device.
At 716, a quantum computing device is controlled to implement the quantum circuit representations (e.g., by a classical computer in communication with a quantum computing device, such as in a configuration as shown in
In some embodiments, the ancilla qubits to be used for at least one nonClifford operation replace at least one Toffoligate. In further embodiments, the synthesized quantum circuit representation includes a combination of both Toffili gates and ancilla qubits to perform nonClifford operations, the combination being determined at least in part by a userselectable variable. In certain embodiments, the synthesizing comprises using a selectswap operation. In particular implementations, the selectswap operation enables sublinear Tgate complexity. In further implementations, the selectswap operation results from a combination of a select operation and a swap network. In some embodiments, the method reduces nonClifford gates at a cost of greater overall ancilla qubits. In further embodiments, the synthesizing implements a datalookup oracle using a selectswap operation. In certain embodiments, the method is performed to synthesize arbitrary unitaries.
Any of the disclosed embodiments can be implemented by one or more computerreadable media storing computerexecutable instructions, which when executed by a computer cause the computer to perform any of the disclosed methods. Also disclosed herein are systems for performing embodiments of the disclosed embodiments comprising a classical computer configured to program, control, and/or measure a quantum computing device.
Further embodiments include a quantum circuit comprising a combination of Clifford and nonClifford gates, wherein the number of nonClifford gates is controlled by a tunable factor, wherein the tunable factor achieves a desired spacedepth tradeoff for the quantum circuit.
With reference to
The computing environment can have additional features. For example, the computing environment 200 includes storage 240, one or more input devices 250, one or more output devices 260, and one or more communication connections 270. An interconnection mechanism (not shown), such as a bus, controller, or network, interconnects the components of the computing environment 200. Typically, operating system software (not shown) provides an operating environment for other software executing in the computing environment 200, and coordinates activities of the components of the computing environment 200.
The storage 240 can be removable or nonremovable, and includes one or more magnetic disks (e.g., hard drives), solid state drives (e.g., flash drives), magnetic tapes or cassettes, CDROMs, DVDs, or any other tangible nonvolatile storage medium which can be used to store information and which can be accessed within the computing environment 200. The storage 240 can also store instructions for the software 280 implementing any of the disclosed quantumcircuit design techniques. The storage 240 can also store instructions for the software 280 for generating and/or synthesizing any of the described techniques, systems, or reversible circuits.
The input device(s) 250 can be a touch input device such as a keyboard, touchscreen, mouse, pen, trackball, a voice input device, a scanning device, or another device that provides input to the computing environment 200. The output device(s) 260 can be a display device (e.g., a computer monitor, laptop display, smartphone display, tablet display, netbook display, or touchscreen), printer, speaker, or another device that provides output from the computing environment 200.
The communication connection(s) 270 enable communication over a communication medium to another computing entity. The communication medium conveys information such as computerexecutable instructions or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media include wired or wireless techniques implemented with an electrical, optical, RF, infrared, acoustic, or other carrier.
As noted, the various methods, circuit design techniques, or compilation/synthesis techniques can be described in the general context of computerreadable instructions stored on one or more computerreadable media. Computer readable media are any available media (e.g., memory or storage device) that call be accessed within or by a computing environment. Computerreadable media include tangible computerreadable memory or storage devices, such as memory 220 and/or storage 240, and do not include propagating carrier waves or signals per se (tangible computerreadable memory or storage devices do not include propagating carrier waves or signals per se).
Various embodiments of the methods disclosed herein can also be described in the general context of computerexecutable instructions (such as those included in program modules) being executed in a computing environment by a processor. Generally, program modules include routines, programs, libraries, objects, classes, components, data structures, and so on, that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or split between program modules as desired in various embodiments. Computerexecutable instructions for program modules may be executed within a local or distributed computing environment.
An example of a possible network topology 300 (e.g., a clientserver network) for implementing a system according to the disclosed technology is depicted in
Another example of a possible network topology 400 (e.g., a distributed computing environment) for implementing a system according to the disclosed technology is depicted in
With reference to
The environment 500 includes one or more quantum processing units 502 and one or more readout device(s) 508. The quantum processing unit(s) execute quantum circuits that e precompiled and described by the quantum computer circuit description. The quantum processing unit(s) can be one or more of, but are not limited to: of a superconducting quantum computer; (b) an ion trap quantum computer; (c) a faulttolerant architecture for quantum computing; and/or (d) a topological quantum architecture (e.g., a topological quantum computing device using Majorana zero modes). The precompiled quantum circuits, including any of the disclosed circuits, can be sent into (or otherwise applied to) the quantum processing unit(s) via control lines 506 at the control of quantum processor controller 520. The quantum processor controller (QP controller) 520 can operate in conjunction with a classical processor 510 (e.g., having an architecture as described above with respect to
With reference to
In other embodiments, compilation and/or verification can be performed remotely by a remote computer 560 (e.g., a computer having a computing environment as described above with respect to
In particular embodiments, the environment 500 can be a cloud computing environment, which provides the quantum processing resources of the environment 500 to one or more remote computers (such as remote computer 560) over a suitable network (which can include the internet).
We have shown that arbitrary quantum states with N coefficients specified by classical data may be prepared using a T gate complexity (√{square root over (N)}) that is an optimal squareroot improvement over prior art. As the Clifford group is efficiently simulable, the ‘quantumness’ of a quantum algorithm is captured in part by its T gate cost. Our results show that reading classical data into a quantum algorithm is a ‘classical’ task that costs (N) Clifford gates and should be separated from the harder part of creating a superposition captured by the T gate complexity.
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 viceversa. 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.