CROSS-REFERENCE TO RELATED APPLICATIONS:

[001] The present application claims priority to U.S. Patent Application No. 62/287,183, titled "Decoding-Based System and Method for Quantum Circuit Optimization", and filed on January 26, 2016, the entire contents of which are hereby incorporated by reference.

FIELD OF INVENTION

[002] The present invention relates to quantum computing and, in particular, to optimizing quantum circuits over a standard set of gates with respect to gate counts.

BACKGROUND

[003] Traditional digital computers use arrays of transistors to perform operations over binary data -- that is, series of bits which have two possible values: "on" and "off, "high" and "low", 0 and 1, etc. Massive advancements in this technology have been made over the past century, to the point where a computer that fits in one's pocket can outperform computers that previously spanned multiple rooms. This is due in large part to the shrinking of the transistor and the continuously compressing more transistors onto smaller chips. However, certain physical laws restrict this process from repeating indefinitely and as such the speed of digital computers will eventually reach a plateau. Hence researchers have been looking to other types of computation as ways of progressing beyond this bound.

[004] Quantum computers, first devised in 1982 by Richard Feynman, use the principles of quantum mechanics to perform computations. These computational devices can exploit, for example, phenomena such as "quantum parallelism" whereby computations are, in effect, performed on an exponential number of input states simultaneously. In fact, algorithms have been devised exploiting such effects to theoretically out-perform best known classical algorithms - for example, Shor's algorithm provides an exponential speed-up over the best known classical algorithm for factoring numbers. [005] These theoretical benefits are subject to certain "crossover points," the instance size after which a quantum algorithm begins to outperform a classical one. The crossover points are influenced by a variety of factors, including the cost of the implementation of the algorithm in the form of a quantum circuit. To reduce the crossover points, at which point the overhead of performing quantum computation is less than the theoretical speedup, it is therefore an object of research to develop methods by which the cost of quantum circuits may be reduced, a process which is referred to as circuit optimization.

SUMMARY

[006] The invention accordingly comprises methods and systems for synthesizing quantum circuits over a particular set of gates, and for the reduction, or optimization, of the number of gates in a quantum circuit already expressed over the aforementioned set of gates. The methods and systems utilize decoders for a specific family of linear codes to minimize the circuit cost of an integer- valued vector which represents in a precise fashion the quantum operation being synthesized. An equivalent circuit is then synthesized using the cost- minimized vector. Moreover, the vector has cost lesser or equal to the cost of the input circuit.

[007] Neither this section nor the sections which follow are intended to either limit the scope of the claims which follow or define the scope of those claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[008] The details and features of the invention will become more apparent in the following description which references the appended drawings.

[009] FIG. 1 is an example of a quantum circuit over gates;

[010] FIG. 2 is a method of quantum circuit optimization based on decoding integer tuples;

[011] FIG. 3 is an exemplary decoding method which minimizes the rotation gates with the smallest angle; [012] FIG. 4 shows an example quantum circuit before and after applying an embodiment of the present invention; and

[013] FIG. 5 is an example system for generating and executing a new quantum circuit;

[014] The details and features of the invention will become more apparent in the following description which references the appended drawings.

DETAILED DESCRIPTION

[015] The description of the present invention is divided into two sections. The first of which comprises a brief description of the quantum circuit model in which we describe our invention. A reader who is familiar with quantum circuits may wish to proceed directly to the latter section.

Overview of Quantum Circuits

[016] A basic unit of information in a quantum computer is called a quantum bit (qubit), the quantum analog of a bit. Qubits may be described mathematically as having a state given by a vector in the 2 dimensional complex vector space The two vectors of the standard basis are denoted by and represent the classical binary values 0 and 1 respectively. The state of a qubit is then effectively a complex-valued combination (sum) of the 0 and 1 states where and β are complex numbers. This is the principle of superposition which allows quantum computers to perform operations on many different inputs, in a sense, simultaneously.

[017] When multiple qubits are used within a quantum computation their states may become entangled, meaning it may not be possible to describe the state of each qubit independendy from the entire system. Generally, the state of a system of n-qubits is given as a vector in the 2 ⁿ -dimensional complex vector space with the standard basis vectors denoted

of a system of

n qubits may be effectively viewed as a complex-valued combination of n-bit strings:

[018] Basic quantum operations are unitary operators on the state space of a system of qubits. Specifically, a unitary operator on n qubits is a complex-valued matrix U which has inverse equal to its conjugate-transpose, denoted The conjugate transpose of U is obtained by a transposition of its rows and columns, and then replacing each entry with its complex conjugate. Applying an n-qubit unitary U to an n-qubit quantum state vector \Ψ) results in the state given by the regular matrix-vector multiplication . Unitaries acting on different qubits in a system are combined into a unitary on the entire system by taking their tensor product denoted by For instance,

Other quantum operations, such as measurement of a qubit with respect to a basis, are also possible.

[019] Quantum circuits are an analog of classical circuits which are used to describe quantum computations in terms of smaller quantum operations. In a quantum circuit, wires carry qubits to gates, which transform their state according to some unitary matrix. Quantum circuits are typically displayed as a graph with horizontal lines representing qubits and labeled boxes representing the application of gates to sets of qubits. As a convention quantum circuits are run from left to right. FIG. 1 gives one such example of a graphical representation of a quantum circuit. 100, 102, 104, 106 and 108 are all quantum gates, while the boxed area 110 is a subcircuit of the entire circuit. 106 represents the two-qubit controlled-NOT gate, also called a CNOT gate, defined as

The other gates shown are defined below. [020] Given a particular, possibly infinite, set of gates a circuit over is a quantum circuit in which only the gates found in Q are used. Such a set of gates is referred to as a gate set or basis.

[021] Quantum circuits may also include other features such as measurements or classical control; such features are irrelevant to this application and are not described, but it is appreciated that the present invention applies to quantum circuits which may make use of such features. Additionally, while quantum circuits and computation are described here in the language of mathematics, it is understood that these function as a formalism for physical computations that are performed on a quantum computer, and that the object of invention applies to these physical computations. For example, a quantum circuit represented in some format, either as a drawing or in a suitable binary format may be mapped, by hand or by an automated tool, into a sequence of individual instructions for a quantum computer. In this way, the object of invention applies to the efficient operation of physical quantum computing hardware.

Methods and Systems Disclosed in the Current Application

[022] The present invention is directed to methods and systems of optimization circuits over the two qubit CNOT gate and the infinite family of one qubit gates for integers k,

defined as

It is understood that by gates" or "phase gates" we mean for any integer value of k greater than 0.

[023] Due to the linearity of quantum mechanics, it is known that these quantum gates may be alternately expressed as injections from the vectors of the standard basis of into the complex vector space. Using the previously detailed association of each vector in the standard basis with a string of n bits , such an injection may be written as a function taking a bit string and returning a complex sum of bit strings. In particular, we have the following definitions:

In general any quantum circuit may be expressed as an operator in this form, hereafter referred to as the SOP (sum-over-paths) form of a quantum circuit.

[024] Prior research has shown [1] that quantum circuits over the basis consisting of CNOT

where is some integer- valued function which is expressible as a sum of with integer coefficients, and / is function from length n bitstrings to length n bitstrings that is linear with respect to binary addition (XOR). In particular,

where is the digit in the binary expansion of is addition mod 2. The coefficients are referred to as the phase coefficients. In general quantum circuits over the basis containing CNOT and Rz gates have SOP form for some integ er d, where are as described above.

[025] The publication [1] gives a method of synthesizing a canonical quantum circuit over the CNOT, T, P and Z gate basis from an SOP description of form Equation 1. This method can be shown to produce circuits that have a number of T, P, and Z gates given by the number of coefficients in P that are odd modulo 8, 4, and 2, respectively. Moreover, it can be used to optimize circuits, as a circuit written over CNOT, Γ, P, and Z gates may have its SOP form computed, then a circuit is re-synthesized from its SOP form, with the additional property that the SOP form results in fewer T gates when re-synthesized. This method can be modified to synthesize circuits with the more general SOP form of Equation 2.

[026] It follows mathematically that since whenever

for every it is the case that

Hence the two quantum operations and

are one and the same.

[027] It is then a possibility for optimization to, given a particular phase function, find one that results in an equivalent quantum operation at lower cost. If the coefficients of the phase function

are written as an ordered set or vector then it follows that the vector of

coefficients above have the following relation where addition between

vectors is pointwise and

for all }

. We define the set of all such vectors c for particular values of n and d to be the set is in fact a iinear integer code. Hence given a vector of 2 — 1 coefficients a defining the function , finding some coefficients has minimal circuit cost may be framed as a decoding problem where a is decoded as c in C(n, d) minimizing the circuit cost of + c. It will be appreciated that a specific quantum circuit may be attributed a cost (also referred to as circuit cost), which estimates the amount of physical resources required to implement the circuit on quantum hardware. In this case, we seek to reduce or minimize the cost of certain phase gates, since they tend to require more physical resources (e.g. physical qubits and physical operations) to implement on a physical device.

[028] FIG. 2 depicts a method for optimizing quantum circuits expressed over the basis consisting of CNOT and gates for any integers fc greater than 0 using the just

detailed principle. First an n-qubit circuit is received as an input to the method 200. The circuit necessarily implements a unitary operator U having definition for some d, where may be expressed as an integer- valued sum of XORs of the binary values Specifically,

for some integer coefficients

[029] The method next proceeds by computing the value of d and the expression of in the form of Equation 3 for the input circuit 202. This can be performed by a modification of the method given in [1] . The coefficients are then extracted from 204. Next, the vector a is decoded as a codeword c of the linear code using some suitable decoding procedure 206. Finally a new circuit is synthesized for the operator

where the coefficients of a e given by the vector a + c 208. By the

definition of is equal to U.

[030] In an example implementation of the process described in FIG. 2, a binary computer receives a binary or digital file that represents an n-qubit circuit as the input. In an alternative embodiment, the binary computer receives a binary or digital file that includes a phase polynomial that represents a quantum operation. The quantum operation may, for example, be derived from an initial n-qubit quantum circuit. A binary computer is a computer that operates using Is and 0s, and is used to describe current computers (e.g. server computers, desktop computers, laptops, mobile devices, etc.) and future computers that also operate in the binary fashion.

[031] The binary computer also outputs a binary or digital file that represents the optimized circuit, as computed according to FIG. 2. In a further example embodiment, the binary or digital file that represents the optimized circuit is then transmitted to a quantum computing device, which then uses the received data to execute a quantum circuit in accordance with the digital file that represents the optimized quantum circuit. [032] FIG. 3 details an exemplary decoder for the code for use in 206. In this decoder, the received vector 300 is decomposed into its binary residue 304 and the remainder

302. It is proven in the attached manuscript that the binary residue of the code

equal to the binary punctured Reed-Muller code of length 2 ⁿ — 1 and order n— k— 1 for the greatest A; such that 2 ^k divides d [2, 3]. The binary vector w is thus decoded as w' in the punctured Reed-Muller code of length 2 ⁿ — 1 and order n— k— 1 306. The vector w' is further decomposed as a sum (mod 2) of binary vectors where each Vi is equal to the vector of evaluations of some n-variable binary monomial of degree at most n— k— 1 (see the attached manuscript). This sum is then reinterpreted as a sum over the integers mod d to compute

which is necessarily a codeword of Finally c 312 is summed together with 6 314 and w 316 to obtain the optimized vector a + c 318.

[033] The decoder depicted in FIG. 3, insofar as the Reed-Muller decoder used in 306 attains minimal distance decoding, minimizes the number of gates in the resulting circuit.

In one exemplary situation, the number of T gates in a circuit consisting of CNOT, T, P = T ² and Z = T ⁴ gates may require minimization. The decoder in FIG. 3 can be used in the method of FIG. 2 to perform this minimization.

[034] The decoder in FIG. 3 is but one exemplary decoding procedure. It is not intended to limit the scope of the decoding-based optimization method of FIG 2.

[035] FIG. 4 illustrates the result of applying the circuit optimization method of FIG. 2 with decoder FIG. 3 to an exemplary (4-qubit) quantum circuit. The initial circuit 400 is input into the procedure FIG. 2 which computes a denominator of d— 2 ³ and phase function

From this phase function it extracts the vector

coefficients from the function, which is then decoded using the method of FIG. 3. Specifically, the binary residue decoded in the 0

order length 15 punctured Reed-Muller code resulting in the vector

A new circuit 402 is then synthesized from the phase function having coefficients

The optimized circuit 402 contains 7 T gates, compared to the 14 T gates in the original circuit 400, and attains the exact minimal number of T gates for this quantum operation.

[036] It is understood that the methods previously described pertain not only to the optimization of circuits consisting of only CNOT and Rz gates, but in addition to their use in optimizing subsets of circuits over a larger quantum gate set. For example, the present invention may be used to optimize quantum circuits over any gate set by applying the optimization to a relevant subcircuit. As an illustration, in one particular embodiment the circuit shown in FIG. 1 is optimized by taking the marked subcircuit 110 and applying the invention to obtain a new circuit, which is then used to replace the subcircuit 110.

[037] In an example embodiment shown in FIG. 5, a system includes a binary computer 500 that is in data communication with a quantum computer 502. The binary computer includes one or more processor devices 504, one or memory devices 506 and one or more communication devices 508. The processor 504 and the memory 506 include currendy known and future known digital technologies. The quantum computer includes one or more quantum computing devices 510 and one or more communication devices 512. In an example embodiment, the physical implementation of the quantum computing device is reconfigurable to generate different quantum circuits. It will be appreciated that currently and future known quantum computing devices that can implement different quantum circuits are applicable to the principles described herein.

[038] Using the system of FIG. 5, an binary input representing an initial quantum circuit is received by the binary computer 500 and is stored in memory 506. By performing the computations on the binary computer via the processor(s) 504 according to the method described herein, the binary computer is able to generate and output a binary file that represents a new quantum circuit that has a lower circuit cost compared to the initial quantum circuit, but still has the same function. This binary file representing the new quantum circuit is transmitted to the quantum computer 502. The quantum computer 502 then uses the received binary file to adjust the parameters of the quantum computing devices to perform the new quantum circuit. In other words, the quantum computer executes physical CNOT and Rz transformations in accordance with the binary form of the new quantum circuit.

[039] It should be noted that, while some of the methods and systems disclosed have been described in the abstract language of mathematics, the current application is directed towards the production of tangible, physical representations of efficient quantum circuits. For example, in one embodiment of the methods disclosed, the optimization procedure of FIG. 2 with the decoder of FIG. 3 are performed by a computer program designed to be run on a conventional computer. The input and output are circuits stored in an appropriate binary format in the physical memory -- for example, a magnetic-disk (hard disk) -- of the computer. Such a physical representation of a quantum circuit in an electronic storage medium may then later be used to implement the operation with a particular quantum computing technology. Examples of applicable quantum computing technology include a classical simulator for quantum computing technology or a hybrid classical/quantum devices. For example, the digital representation of the optimized circuit as a sequence of CNOT, Γ, / ^* , and Z gates may be used to determine a sequence of physical pulses needed to perform the operation on a quantum computer using topological quantum error correcting codes running on

superconducting qubits. Alternatively, the operations may be performed by a series of pulses and other physical operations on a quantum computer consisting of trapped ions, or spin qubits in silicon, or nitrogen vacancy qubits in diamond, or qubits encoded in topologically ordered states of matter, or other realizations and variations, including hybrid devices.

[040] Example embodiments are described below.

[041] In an example embodiment, a method for synthesizing a quantum circuit is provided, and it includes: determining an ordered set or vector of phase coefficients; specifying a linear permutation; and determining a sequence of CNOT and Rz gates using the set of phase coefficients and the linear permutation, such that the number of Rz gates is minimized.

[042] In an example aspect, the method further includes: replacing said first set of phase coefficients with a second set of phase coefficients, wherein the first set of phase coefficients and the second set of phase coefficients represent the same quantum operation; and reducing the number of Rz gates required.

[043] In another example aspect, the method further includes the use of a decoding algorithm to determine said second set of phase coefficients.

[044] In an example aspect, a method is provided for optimizing a quantum circuit, expressed as a sequence of CNOT and Rz gates, wherein the circuit is first analyzed to obtain a set of phase coefficients and a linear permutation, and then the following operations are utilized to synthesize a new circuit: determining an ordered set or vector of phase coefficients;

specifying a linear permutation; and determining a sequence of CNOT and z gates using the set of phase coefficients and the linear permutation, such that the number of Rz gates is minimized.

[045] In an example aspect, a Reed-Muller decoding method is utilized to determine an alternate set of phase coefficients minimizing the number of Rz gates required.

[046] In an example aspect, the Reed-Muller decoder is used to decode the binary residue of the set of phase coefficients, the result of which is then used to generate the alternate set of phase coefficients.

[047] In an example aspect, the method is implemented as a computer program, wherein a processor receives a quantum circuit expressed over CNOT and Rz gates in suitable digital form, and then produces an optimized circuit in suitable digital form performing the same function.

[048] In an example aspect, a non-transitory computer readable medium is provided for synthesizing a new quantum circuit, the non-transitory computer readable medium including thereon computer executable instructions according to the above method operations.

[049] In an example embodiment, a computing system is provided for optimizing a quantum circuit, which includes: a memory device that stores a first digital form of an initial quantum circuit expressed as a sequence of CNOT and Rz gates; a processor device that obtains and analyzes the first digital form to determine an ordered set or vector of phase coefficients and to specify a linear permutation; the processor device determines a sequence of CNOT and Rz gates using the set of phase coefficients and the linear permutation, such that the number of Rz gates is reduced; the processor device subsequently computes a second digital form of a new quantum circuit; and the memory devices stores the second digital form.

[050] In an example embodiment, a process of producing a quantum circuit is provided and it includes: obtaining a digital form of an initial n - qubit quantum circuit expressed over CNOT and Rz gates; a binary computer analyzing the digital form of the initial quantum circuit to obtain a set of phase coefficients and a linear permutation; the binary computer determining a sequence of CNOT and Rz gates using the set of phase coefficients and the linear permutation, and computing a digital form of a new n-qubit quantum circuit from the sequence having a reduced number of Rz gates compared to the initial quantum circuit, and the new quantum circuit performing the same function as the initial quantum circuit; and executing physical CNOT and Rz transformations in a quantum computer in accordance with the digital form of the new quantum circuit.

[051] In an example embodiment, a system is provided for producing a quantum circuit and it includes: a binary computer in data communication with a quantum computer; and the binary computer comprising a memory device that stores a digital form of an initial n - qubit quantum circuit expressed over CNOT and Rz gates. The binary computer includes a processor device to: analyze the digital form of the initial quantum circuit to obtain a set of phase coefficients and a linear permutation; determine a sequence of CNOT and Rz gates using the set of phase coefficients and the linear permutation; and compute a digital form of a new n-qubit quantum circuit from the sequence having a reduced number of Rz gates compared to the initial quantum circuit, wherein the new quantum circuit performs the same function as the initial quantum circuit. The binary computer further includes a

communication device to transmit the digital form of the new quantum circuit to the quantum computer. The quantum computer includes a communication device to receive the digital form of the new quantum circuit. The quantum computer also includes devices to execute physical CNOT and Rz transformations in the quantum computer in accordance with the digital form of the new quantum circuit.

[052] It will be appreciated that different features of the example embodiments of the system, the method and the apparatus, as described herein, may be combined with each other in different ways. In other words, different operations, devices and components may be used together according to other example embodiments, although not specifically stated.

[053] The steps or operations in the flow diagrams described herein are just for example. There may be many variations to these steps or operations without departing from the spirit of the invention or inventions. For instance, the steps may be performed in a differing order, or steps may be added, deleted, or modified.

[054] Although the above has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the scope of the claims appended hereto.

[055] References

[1] M. Amy, D. Maslov, M. Mosca, "Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 10, pp 1476— 1489, 2014.

[2] D. E. Muller, "Application of Boolean algebra to switching circuit design and to error detection," Transactions on the I.R.E. Professional Group on Electronic Computers, vol EC-3, no. 3, pp. 6— 12, 1954.

[3] I. Reed, "A class of multiple-error-correcting codes and the decoding scheme," Transactions on the I.R.E. Professional Group on Information Theory, vol 4, no. 4, pp. 38— 49, 1954.

The entire contents of the above references [1], [2] and [3] are herein incorporated by reference.