Patent ID: 12210502

DETAILED DESCRIPTION

If efficiently realized, computations performed using a quantum computing device promise a computational speed-up for particular classes of problems over any computation that can be performed on a classical computer. Efficient realization of quantum computations depends on the design of the quantum computing device architecture, e.g., the design of the underlying quantum circuitry of the quantum computer. For example, a quantum circuit included in a quantum computing device should be space efficient. As another example, since T gates are an important component for building fault tolerant quantum circuits but are inherently expensive, a quantum computing device should have a low T count. In fact, constructing quantum circuits that perform certain computations with a reduced or even optimal number of T gates is an important task for near term realizations of quantum computing devices.

This specification describes a quantum circuit construction called a unary iteration quantum circuit for performing indexed operations. Indexed operations (including ranged indexed operations or other complex variants derived from indexed operations) are important building blocks for performing a wide range of computational tasks, e.g., data loading or encoding electronic structure spectra in quantum circuits.

Performing an indexed operation involves performing an operation on one or more target qubits conditioned on a bit value in an index register. The performed operation can, for example, be any single-qubit unitary. For example, this specification describes a quantum circuit construction and method for implementing indexed operations as given below in Equation (1).
|l|ψ→|lGl|ψ(1)
In Equation (1), G represents any single-qubit unitary operator, e.g., a Pauli operator, |lrepresents an index register of qubits that encodes an index value l, |ψrepresents a target register of target qubits, and |lGl|ψ) represents application of the operator G to an l-th target qubit (the qubit at offset l in the target register |ψ).) The operator G does not need to be the same across the whole target register of qubits. For example, the indexed operation G could be defined as one particular type of operation for an index register value smaller than some fixed value, and another particular type of operation for an index register value larger or equal than the same fixed value.

The unary iteration quantum circuit described in this specification is both space efficient and T count efficient, as described in more detail below. The space- and T-gate-count-efficiency is achieved by a unary iteration technique where qubits are made available one by one (iteration) and the values produced correspond to the one-hot (unary) bits of the index register's value. The one hot encoding means that the condition that the index register is storing a particular value corresponds to a specific qubit being set or not being set at a particular time in the circuit. For an index register storing an index in the interval [0, L), the space overhead of converting the index register into a unary register using currently known techniques is L qubits. By comparison, the unary iteration quantum circuits and techniques described in this specification are exponentially more space-efficient without any increased T complexity, requiring only log L control qubits. In addition, the unary iteration quantum circuits and techniques described in this specification have a T-count of at most 4L−4 and can be parallelized without increasing the T-count.

Conventional Techniques for Implementing Indexed Operations

A known, suboptimal way to implement an indexed operation, e.g., an indexed NOT gate Xl, includes totally controlling the application of Xlon all possible binary values that could occur in the index register |l. For example, in order to apply X158when |l=|158, the total-control approach includes placing a NOT gate targeting the qubit at offset 158, but with a control on each index qubit. The control's type (ON or OFF) would be determined by the binary representation of 158 (15810=100111102), so there would be a must-be-OFF control on the low bit (least significant bit) of the index register (because the low bit of 158 in binary is 0), a must-be-ON control on the next bit (because the next bit of 158 in binary is 1), and so forth for the rest of the index bits (terminating at the most significant bit.) In order to cover every case, this process would be repeated for every integer from 0 up to L−1. This produces L different NOT operations, each targeting a different qubit in the target register and each having a number of controls equal to the size of the index register (i.e., log L). Thus, it takes O(L log L) T gates to apply Equation (1) using this approach. As described below, unary iteration asymptotically improves this T-count to 4L−4.

The unary iteration construction described in this specification can be defined by applying a specifically constructed fixed set of transformations and optimizations to the conventional total-control circuit, as described below with reference toFIGS.1-5.

FIG.1shows an example total control circuit100for performing an indexed operation. For convenience, the example total control circuit100is described as performing a controlled indexed NOT operation Xlwith 0≤l≤L=11, however the total control circuit may be used to perform other indexed operations and may be used to perform indexed operations with fewer or more indices.

The example total control circuit100includes an index register102. In this example, the index register102includes four qubits l0, l1, l2, l3, with qubit l3storing the least significant bit, i.e., 20, and qubit l0storing the most significant bit, i.e., 23. The example total control circuit100further includes a control register104. In this example, the control register204includes one qubit |c=(control). The example total control circuit100further includes a system or target register106. In this example, the target register106includes at least 11 target qubits which, for convenience, are represented as |ψ=(ψ0, ψ1, . . . , ψ10)T.

To perform a controlled NOT operation on a l-th target qubit using the total control circuit100, a NOT gate Xltargeting the l-th target qubit ψlis placed in the target register. Controls corresponding to the value l are then placed on each index qubit in the index register. In the example total control circuit100, black dots, e.g., dot108, represent must-be-ON controls and empty circles, e.g., empty circle110, represent must-be-OFF controls that correspond to the logical inverse of the input index qubit.

For example, to perform an indexed operation X5on target qubit ψ5, the index register qubits are set to l0=0, l1=1, l2=0, l3=1 since the binary representation of 5 in a four bit register is 0101. Consequently, only the controls for the indexed operation X5in the total control circuit all have a truth value that corresponds to ON such that a NOT operation is performed only on the corresponding target qubit ψ5.

A first set of specific transformations that are applied to the total control circuit100includes removing some of the total control circuit controls using the condition that the index register never encodes an out-of-range value l≥L. To illustrate, if the X10operation shown inFIG.1is not conditioned on the lowest bit (least significant bit) of the index register, an X10would also be applied to the target qubit when l=11. However, under the condition that l<L, this is not problematic and several controls can be omitted from the circuit under this condition. For each possible l the corresponding Xlis considered and the control on the b-th index qubit is removed if the following conditions are true: (i) the b-th bit of L−1 is not set and (ii) setting the b-th bit of l would change l into a value larger than L−1. Visually, this removes “runs” of must-be-OFF controls as long as the run reaches the right side of the circuit.

After removing the above described controls, the remaining controls can be carefully expanded into nested AND operations, where the nests are nested so that lower controls are inside higher controls and control qubits associated with an AND operation are placed just below its lowest input qubit. Example AND operations defined in terms of Toffoli gates and Clifford+T gates are described below with reference toFIG.2.FIG.3shows a transformed circuit achieved by removing the above described total control circuit controls and expanding the remaining controls into nested AND operations. By iteratively optimizing adjacent AND operations, using the relation illustrated inFIG.4below, the circuit shown inFIG.3is optimized into the unary iteration circuit, as described below with reference toFIG.5.

FIG.2shows example circuits200and250for computing and uncomputing an AND operation. InFIG.2, computing a logical AND operation202between two control qubits204and206is represented as a qubit wire208emerging vertically from the two controls on the control qubits204and206then heading rightwards. Uncomputing the logical AND operation is represented as a qubit wire258coming in from the left then merging vertically into the two control qubits204and206that created it.

To compute the logical AND operation202, an ancilla qubit210in a T-state is obtained. A CNOT gate212between the control qubit206and the ancilla qubit210is applied. The Hermitian conjugate of a T gate214is applied to the ancilla qubit210. A CNOT gate216is applied between the control qubit204and the ancilla qubit210. A T gate218is applied to the ancilla qubit210. A CNOT gate220is applied between the control qubit206and the ancilla qubit210. In sequence, a Hermitian conjugate of a T gate222, a Hadamard gate224, and, optionally, a SWAP gate S226are applied to the ancilla qubit210. The T count of the operation202is therefore 4 (including the T gate required to prepare the T-state of the ancilla qubit210).

Uncomputing the logical AND operation202includes performing a measure-and-correct process. A Hadamard gate260is applied to the ancilla qubit210. The ancilla qubit210is measured262. A CZ gate264is applied to the control qubits204,206if the generated measurement result from measurement operation262indicates that the two control qubits204,206are both ON. The T count of the uncomputation is zero.

FIG.3shows an example transformed circuit300achieved by removing specific total control circuit controls from the total control circuit100described with reference toFIG.1and expanding remaining controls into nested AND operations.

The transformed circuit300shows a sawtooth pattern302where each tooth, e.g., tooth304, is associated with one of the indexed NOT operations Xldescribed above with reference toFIG.1. Each tooth includes respective nested AND computations, e.g., nested AND operations306, and subsequent respective uncomputations of the same AND operations, e.g., uncomputations308, the computations and uncomputations being described above with reference toFIG.2.

For example, the first tooth304corresponds to indexed operation X0and begins with computing a first logical AND between a first control qubit and the logical inverse of a first index register qubit l0that represents the most significant index register bit. The result of this operation is stored in a second control qubit. A second logical AND between the second control qubit storing the result of the previous AND operation and the logical inverse of a second index register qubit l1that represents the second most significant index register bit is computed. The result of this computation is stored in a third control qubit. A third logical AND between the third control qubit storing the result of the previous AND operation and the logical inverse of a third index register qubit l2that represents the third most significant index register bit is computed. The result of this computation is stored in a fourth control qubit. A fourth logical AND of the fourth control qubit storing the result of the previous AND operation and the logical inverse of a fourth index register qubit l3that represents the fourth most or, in this example, the least significant index register bit, is computed and the result is stored in a fifth or, in this example, final control qubit. If the truth value of the fifth control qubit corresponds to ON, the corresponding indexed operation X0controlled by the fifth control qubit is performed on the target qubit ψ0. Afterwards, the previously described control qubits are uncomputed in an order reverse to the order they were computed in. Note that, during the computation phase306and uncomputation phase308, the control qubits are made available in sequence.

FIG.4is an illustration400of how to optimize adjacent AND operations for three exemplary cases. In total there are sixteen possible cases where an AND uncomputation is adjacent to an AND computation and all of them can be optimized into NOT or CNOT gates in an analogous manner. As shown in sub illustration402, for adjacent uncomputation402aand re-computation402bof AND operations with must-be-ON controls, the controls can be removed402c. As shown in sub illustration404, an adjacent uncomputation404aand re-computation404bof AND operations where the second qubit in the AND re-computation404bis a must-be-OFF control can be replaced by a CNOT operation404con the third qubit with the first qubit acting as the control. As shown in sub illustration406, an adjacent uncomputation406aand re-computation406bof AND operations where both the first and second qubit in the AND re-computation is a must-be-OFF control can be replaced by a CNOT operation406con the third qubit with the first qubit acting as the control, followed by a CNOT operation406don the third qubit with the second qubit acting as the control, followed by a NOT operation406eon the third qubit. Each merger402,404and406saves 4 T gates.

Example Unary Iteration Quantum Circuits

FIG.5shows an example unary iteration quantum circuit500for performing an indexed operation on a corresponding target qubit. For convenience and in line withFIG.1above, the example unary iteration quantum circuit500is illustrated as performing a controlled indexed operation Xlwith 0≤l≤L=11, however the unary iteration quantum circuit may be used to perform other indexed operations and may be used to perform indexed operations with fewer or more indices, as shown below with reference toFIGS.7A and7B.

The example unary iteration quantum circuit500includes an index register including four index qubits502a-d. The index register is configured to encode an index value. In some implementations, the index register may be configured to encode only in-range index values, i.e., index values less than L.

The example unary iteration quantum circuit500includes a control register including five control qubits504a-e. The control qubits are interleaved with the index qubits to form a combined register, with the first control qubit504aat the top of the combined register, followed by the index qubit502arepresenting the most significant bit, followed by the second control qubit504b, followed by the second index qubit502brepresenting a second most significant bit, etc., until the penultimate control qubit504dis followed by the index qubit502drepresenting the least significant bit then the final control qubit504e.

The example unary iteration quantum circuit500includes a target register506including multiple target qubits. For convenience, the target register506is drawn as a single wire inFIG.5.

The control register encodes the index value encoded in the index register via an iterative cascade508of multiple logical AND operations performed between respective pairs of control qubits and index qubits, where each control qubit504a-eis made available to the cascade of operations in sequence and not in parallel (in contrast to the total control circuit100described above with reference toFIG.1). At the end of the iterative cascade508, the result of the logical AND operation510between an inverse of the index qubit502drepresenting the least significant bit and the penultimate control qubit504dstoring a result of a previous logical AND operation is stored in the final control qubit504e. Each logical AND operation may be implemented using the circuitry described above with reference toFIG.2.

The example unary iteration quantum circuit500repeatedly computes and uncomputes the control qubits504b-eto perform the operation on a corresponding target qubit in the target register506. The number of repetitions included in a unary iteration quantum circuit depends on the number of distinct operations that may be applied to the target register and/or the number of index qubits in the index register. For example, the example unary iteration quantum circuit500includes four index qubits502a-dand eleven distinct operations (since the number of controlled X operations on different targets in the register is eleven). Therefore, in this case, the number of compute/un-compute repetitions is equal to 11−1=10 (intuitively, this is because if numbers 1 through 10 are recognized, number 11 can be performed unconditionally and then undone as part of the 1 through 10 parts).

A repetition of computing and uncomputing the control qubits includes performing the operation on a target qubit for the repetition if the final control qubit is in an ON state, iteratively un-computing a number of logical AND operations (as described in more detail below with reference toFIG.9), performing a CNOT operation between a control qubit corresponding to the last uncomputed logical AND operation and a next highest control qubit, wherein the next highest control qubit acts as a control for the CNOT operation, and iteratively computing a number of logical AND operations to re-compute the final control qubit (as described in more detail below with reference toFIG.9).

For example, in a first repetition, the operation X is performed on a target qubit corresponding to index value 0 if the final control, qubit504eis in an ON state. No uncomputations of logical AND operations are then performed (as explained below with reference toFIG.9). A CNOT operation is then performed between the final control qubit504eand the next highest control qubit504d. No computations of logical AND operations are then performed, since no uncomputations were performed.

In a second repetition, the operation X is performed on a target qubit corresponding to index value 1 if the final control qubit504eis in an ON state. One uncomputation of a logical AND operation is then performed (as explained below with reference toFIG.9). A CNOT operation is then performed between the control qubit504dand the next highest control qubit504c. One logical AND operations is then computed.

The circuit ends by uncomputing the iteratively computed cascade508of logical AND operations using a second cascade512of uncomputations. Each control qubit504a-eis made available to the cascade512of uncomputations in sequence and not in parallel.

The example unary iteration quantum circuit500uses 10 logical AND operations. Since each AND operation requires 4 T gates (seeFIG.3above), and no T gates to un-compute, and there are no other T-consuming operations in the circuit, the T count of the circuit500is 40=4(L−1) where in this case L=11.

The example circuit500is a specific example of a unary iteration quantum circuit, and various extensions or variations of the circuit500exist. For example, a unary iteration quantum circuit can be constructed for any number of target qubits, two examples of which are given below inFIGS.7A and7B.

As another example, a unary iteration quantum circuit can be used to implement Pauli operations to sets of qubits that are any (classically pre-computed) function of the index register. As another variation, the target of each individually controlled operation can be easily changed and therefore the qubit to which the operation is applied does not need to match the value of the index register. The indexed operations that are being applied to the target register do not need to be the same across the whole target register. The indexed operation Glcould, for example, be defined as Gl=Xlwhen l<10 and Gl=Ylwhen l≥10, Xldenotes a Pauli-X or NOT operation and Yla Pauli-Y operation. In addition, the indexed operations can include ranged operations, as described below with reference toFIGS.8A and8B.

In some cases unary iteration quantum circuits can be optimized to reduce circuit depth, as illustrated below with reference toFIG.6. In some cases unary iteration quantum circuits can be mapped, filtered, zipped, aggregated, batched, flattened, or grouped. Unary iteration quantum circuits can be applied in various settings, such as data loading, as described below with reference toFIGS.10and11.

FIG.6shows an example optimized unary iteration quantum circuit600. The example optimized unary iteration quantum circuit600is an optimized version of the example unary iteration quantum circuit500shown inFIG.5. The example unary iteration quantum circuit500has been optimized by merging CNOT operations, thus reducing circuit depth. The merging strategy is as follows. CNOTs can be merged when they are adjacent and have the same control. To create a situation where this is possible, CNOTs must be moved around and, in particular, over other CNOTs. When the order in which (i) a CNOT from qubit B onto qubit C and (ii) a CNOT from qubit A onto qubit B is swapped, a third CNOT from qubit A onto qubit C must be introduced to compensate for the fact that the swapped operations do not commute. But, if this new operation can be merged with existing CNOTs and swapping the order of the original operations allows one of them to be merged with yet another CNOT operation, then a small depth saving is achieved, since one operation was introduced but two mergers were performed. In the specific case ofFIG.5above, the order of the X1CNOT and the CNOT to its left can be swapped. This will introduce an X1controlled by in2h, but it can be merged into the CNOT already controlled by in2h. Then the original controlled X1can be merged into the controlled X0. The general strategy is to consider each operation in turn, swap it as far left as possible, and repeat until the circuit reached a stable state. Then check whether there are any operations that could be merged by moving right, without creating a situation that would introduce new CNOTs, and use those opportunities.

An additional example of a unary iteration quantum circuit with fewer target qubits than the example shown inFIG.5is illustrated inFIG.7.FIG.7shows a second example unary iteration quantum circuit700with four target qubits, two index qubits and three control qubits.

FIG.8shows an example unary iteration quantum circuit800for performing ranged indexed operations. Although the circuit800illustrates the index register and control register separately (and not interleaved, as inFIG.5), the unary iteration techniques performed by the circuit800are equivalent to those performed by the circuit500ofFIG.5.

In a ranged indexed operation, an operation G is applied to multiple target qubits instead of just a single target qubit. An example ranged operation is given below in Equation (2).
|l|ψ→|lG0·G1· . . . ·Gl-1|ψ=|lΠk=0l-1Gk|ψ(2)
In Equation (2), G0·G1· . . . ·Gl-1represents a ranged operation that applies the operation G to target qubits ψ0, ψ1, . . . , ψl-1.

The unary iteration quantum circuit described in this specification can be extended and used to implement such ranged indexed operations using additional accumulator qubits, e.g., accumulator qubit802. Each time the final control qubit804is computed, a CNOT operation is performed between the additional accumulator qubit802and the final control qubit804, with the final control qubit804acting as the control. As a result, the accumulator qubit802will remain in an ON state until the lthfinal control qubit804toggles it OFF. The accumulator qubit802will then remain in an OFF state. By conditioning indexed operations on the accumulator qubit802instead of on the final control qubit804, the circuit can perform ranged indexed operations.

Various extensions of the circuit800are possible. For example, in some cases multiple accumulator qubits may be used to perform multiple operations over different ranges. As another example, in some cases a unary iteration quantum circuit may perform both ranged index operations and indexed operations, as illustrated in circuit850ofFIG.8B. Since an accumulator qubit can be cleared without having to repeat the unary iteration process, performing ranged indexed operations and indexed operations does not increase the T-count.

Method for Performing Indexed Operations

FIG.9is a flowchart of an example process900for performing an indexed operation using a unary iteration quantum circuit. For convenience, the process900will be described as being performed by a quantum computing device in communication with one or more classical computing devices located in one or more locations. For example, the system1200ofFIG.12, appropriately programmed in accordance with this specification, can perform the process900.

The system encodes an index value in an index register including one or more index qubits (step902). For example, as illustrated above with reference toFIG.5, the system may include an index register with N qubits and encode an index value l with 0≤l≤2N−1. In some cases the index register may not encode an out-of-range value l≥2N.

The system encodes the index value in a control register including multiple control qubits (step904). Encoding the index value in the control register may include iteratively computing multiple logical AND operations between respective pairs of control qubits and index qubits to store a result of a logical AND operation between an inverse of a least significant index qubit and a penultimate control qubit storing a result of a previous logical AND operation in a final control qubit.

For example, as illustrated above with respect toFIG.5, the index qubits may be interleaved with the control qubits, with a first control qubit at the top of the combined register, followed by a most significant index qubit, followed by a second control qubit, followed by a second most significant index qubit, etc., until a penultimate control qubit is followed by a least significant index qubit then a final control qubit. In this case, iteratively performing computing multiple logical AND operations between respective pairs of control qubits and index qubits to store a result of a logical AND operation between an inverse of the least significant index qubit and a control qubit storing the result of a previous logical AND operation may include, for a first iteration, performing a logical AND operation between the first control qubit (optionally prepared in an ON state) at the top of the combined register and an inverse of the most significant index qubit. The result of the logical AND operation may then be stored in the second control qubit. In this manner, the multiple control qubits are made available in sequence and not in parallel and correspond to a one-hot encoding of the stored index value.

For a subsequent iteration, performing computing multiple logical AND operations between respective pairs of control qubits and index qubits to store a result of a logical AND operation between an inverse of a lower significant index qubit and a control qubit storing the result of a previous logical AND operation may include performing a logical AND operation between a control qubit storing the result of a logical AND operation for the previous iteration and an inverse of the index qubit for the iteration, and storing the result of the logical AND operation in a subsequent control qubit. For example, for a second iteration this may include performing a logical AND operation between the second control qubit and an inverse of the second most significant index qubit. The result of the logical AND operation may then be stored in the third control qubit. For a final iteration, this may include performing a logical AND operation between the penultimate control qubit and an inverse of the least most significant index qubit. The result of the logical AND operation may then be stored in the final control qubit.

As described above with reference toFIG.5and illustrated above with reference toFIG.2, in some implementations performing a logical AND operation may include performing a temporary AND operation that is defined in terms of Toffoli gates and Clifford+T gates and that requires 4 T gates.

The system repeatedly computes and uncomputes the control qubits to perform, conditioned on the state of the control qubits, the operation on a target qubit corresponding to the index value (step906). Computing and uncomputing one or more control qubits may include repeatedly, for each target qubit in sequence:a) determining whether the final control qubit is in an ON state, and in response to determining that the final control qubit is in an ON state, performing the operation on the target qubit;b) determining a number of uncomputations of the iteratively computed logical AND operations described with reference to step904to perform;c) performing the determined number of uncomputations;d) performing a CNOT operation between a control qubit corresponding to the last uncomputed logical AND operation and a next highest control qubit, wherein the next highest control qubit acts as a control for the CNOT operation;e) iteratively computing a number of logical AND operations as described above with reference to step904to recompute the final control qubit.

Determining a number of uncomputations of the iteratively computed logical AND operations described with reference to step904to perform includes determining how many bits are flipped when changing the binary representation of an index value corresponding to a final control qubit to the next (or, equivalently, the number of times it is possible to divide the index value in base 10 by 2 before the result becomes a non-integer). The number of uncomputations to perform is then equal to the determined number of required bit flips minus 1. Alternatively, the number of uncomputations to perform is equal to the number of times the value of the next index value can be divided by 2 before a non-integer result is obtained.

For example, after each even index value, only one bit flip is required to change the binary representation of the even index value to the next odd value. Therefore, after each even index value no uncomputations are performed, and the method described above includes only steps a) and d).

After each odd index value, different numbers of bit flips are required to change the binary representation of the odd index value to the next even value. For example, to change a bit representation for an index value 3→011 to 4→100 three bit flips are required. Therefore, the number of uncomputations determined and performed at steps b) and c) above is equal to 2. Alternatively, the number of times the value 4 can be divided by 2 before a non-integer result is obtained is 2.

In some implementations, as shown inFIG.5, the steps a) to e) described above may vary for a last target qubit in the circuit. For example, as shown inFIG.5, in cases where a final bit flip is left, e.g., in this example to go from index value 9 to 10, steps d) and e) for target qubit 9 and steps a), b) and c) for target qubit 10 may vary. This is because the circuit is truncated at index value 10—there are no target qubits corresponding to index values 12 to 15—and therefore the same amount of information encoded into the final control qubit for the previous index values is not required. Instead, the encoded information in the second least significant bit is sufficient, and performing one less AND computation/uncomputation can further reduce the T count.

The last question is in part also answered by this. In addition, you use the penultimate here because you can because there is no additional differentiation necessary since there is no X11. In other words, the value of the second least significant bit is already sufficient in this particular case. And then you also want to do that if it is possible because it saves you one or more AND computations which require costly T gates.

In some implementations, the system may further uncompute the iteratively computed multiple logical AND operations between respective pairs of control qubits and index qubits, as described above with reference to step902, to reset the index register to encode the index value.

As described above with reference toFIG.5, the total number of AND operations included in the unary iteration circuit performing the index operation is equal to the total number of distinct operations on the target qubits 2Nminus 1. Therefore, in implementations where performing the AND operations requires 4 T gates per AND operation, the unary iteration circuit has a T count of 4(2N−1).

Application of Unary Iteration to Data Loading:

FIG.10shows an example data loading quantum circuit1000. For convenience, the example data loading quantum circuit1000is illustrated as being configured to load 8 data items, however in some cases the circuit may be expanded (or reduced) and configured to load an arbitrary number of data items.

The example data loading quantum circuit1000includes an index register1002including the index qubits. The upper most index qubit represents the most significant bit, and the lowest index qubit represents the least significant bit. The index register1002is configured to store an index value. As described above with reference toFIG.5, in some implementations the index register may be configured to encode only in-range index values, i.e., index values less than L.

The example data loading quantum circuit1000includes a control register1004including four control qubits. In this description (and as describe above with reference toFIG.5), the lowest control qubit is referred to as the final control qubit. The example data loading quantum circuit1000also includes a data register1006including eight data qubits.

The control register1004encodes the index value encoded in the index register1002via an iterative cascade of multiple logical AND operations performed between respective pairs of control qubits and index qubits, where each control qubit is made available to the cascade of operations in sequence and not in parallel. This process is described in detail above with reference toFIG.5. At the end of the iterative cascade, the result of a logical AND operation between an inverse of the index qubit representing the least significant bit and the penultimate control qubit storing a result of a previous logical AND operation is stored in the final control qubit. Each logical AND operation may be implemented using the circuitry described above with reference toFIG.2.

The example data loading quantum circuit1000repeatedly computes and uncomputes the control qubits to load a data item, e.g., one of data items d0-d7, corresponding to the index value to the data register of data qubits. In between each repetition, a CNOT operation is performed between the last uncomputed control qubit and the next most highest control qubit, with the next most highest control qubit acting as the control. For example, between repetition 1 and repetition 2, a CNOT gate1008is performed between the third control qubit and the second control qubit, with the second control qubit acting as the control. Between repetition 2 and 3, a CNOT gate is performed between the second control qubit and the first control qubit, with the first control qubit acting as the control.

The number of repetitions included in a data loading quantum circuit depends on the number of distinct data loading operations and/or the number of index qubits in the index register. For example, the example data loading quantum circuit1000includes three index qubits and eight distinct data loading operations. Therefore, in this case, the number of compute/uncompute repetitions is equal to 4.

A repetition of computing and uncomputing the control qubits includes iteratively computing one or more logical AND operations between pairs of control and index qubits to store a result of the computations in the final control qubit. If the final control qubit is in an ON state, a multi target CNOT operation is performed on the data register qubits with the final control qubit acting as a control for the multi target CNOT operation. The multi target CNOT operation is dependent on a binary encoding of the data item. For example, if the data item has a binary representation of 10000001, the multi target CNOT operation may include a multi target CNOT operation controlled by the final control qubit that targets the qubits in the data register at offset 0 and 7, i.e., applies CNOTs to the first and the last qubit in the data register. As another example, if the data item has a binary representation of 00001111, the multi target CNOT operation may include a multi target CNOT operation controlled by the final control qubit that targets the last four qubits in the data register.

A CNOT operation is then performed between the final control qubit and the penultimate control qubit, where the penultimate control qubit acts as the control for the CNOT operation. Then, if the final control qubit is in an ON state, a multi target CNOT operation is performed on the data register qubits, again where the multi target CNOT operation is dependent on a binary encoding of the data item. Pairs of control and index qubits are then iteratively uncomputed.

The number of iterative computations and uncomputations performed in a repetition depends which repetition is being performed. This concept is described in detail above with reference toFIG.5.

The data loading quantum circuit1000ends by uncomputing the iteratively computed cascade of logical AND operations using a second cascade of uncomputations. Each control qubit is made available to the cascade of uncomputations in sequence and not in parallel.

The above described data loading quantum circuit1000and variations thereof can be used to construct a “read only” type of QRAM, referred to herein as QROM. A QROM can read classical data indexed by a quantum register using a data loading quantum circuit, i.e. perform the transformation given below in Equation (3),

QROMd·∑i=0L-1al⁢❘"\[LeftBracketingBar]"l〉⁢❘"\[LeftBracketingBar]"0〉=∑i=0L-1al⁢❘"\[LeftBracketingBar]"l〉⁢❘"\[LeftBracketingBar]"dl〉(3)

In Equation (3), l represents an index to be read and dlrepresents a word at offset l in a classical list d containing L words (items of data), with each word consisting of D bits, and alare arbitrary amplitudes. The left hand side of Equation (3) describes an arbitrary superposition over the index register's L possible values with a second register in the state10) and the left-multiplication of QROMdindicates the application of the QROM circuit. The right hand side of Equation (3) describes the state resulting from the application of the QROM circuit which has the data bits dlin the second register entangled with each possible computational basis state of the first register.

The data loading quantum circuit1000(and therefore the QROM construction) has a gate complexity of O(L D), since each of the D bits in each of the L words or data items from the QROM determines whether or not a CNOT gate is present and it is possible that all of the QROM's bits are set. However, because the CNOT is a Clifford operation, it is cheap to apply. This is especially so for multi-target CNOT operations, which can be combined into a single braiding operation in the surface code. The T-count of the circuit comes entirely from the unary iteration process (and is independent of data item size) whose T-count is upper bounded by 4L−4.

Furthermore, since the T count is independent of data item size, the data item size can be (artificially) increased without affecting the T count by reading d′l=concat(d2l, d2l+1) instead of dl. This changes the T-count from 4L to 2L+4D, which is beneficial as long as D is less than L/2.

Example Method for Performing Data Loading

FIG.11is a flowchart of an example process1100for loading data using unary iteration techniques, e.g., the techniques described above with reference toFIGS.5to9. For convenience, the process1100will be described as being performed by a quantum computing device in communication with one or more classical computing devices located in one or more locations. For example, the system1200ofFIG.12, appropriately programmed in accordance with this specification, can perform the process1100.

The system encodes an index value in an index register comprising one or more index qubits (step1102), wherein the index value may be obtained through the process of some larger quantum computation. For example, as illustrated above with reference toFIG.10, the system may include an index register with N qubits and encode an index value l with 0≤l<2N-1In some cases the index register may not encode an out-of-range value l≥2N-1.

The system encodes the index value in a control register comprising multiple control qubits (step1104). Encoding the index value in the control register may include iteratively computing multiple logical AND operations between respective pairs of control qubits and index qubits to store a result of a logical AND operation between an inverse of a least significant index qubit and a penultimate control qubit storing a result of a previous logical AND operation in a final control qubit, as described in detail at step904ofFIG.9above.

The system repeatedly computes and uncomputes the control qubits to load, conditioned on the state of the control qubits, a data item corresponding to the index value to a data register of data qubits (step1106). Computing and uncomputing one or more control qubits may include repeatedly:a) determining whether the final control qubit is in an ON state, and in response to determining that the final control qubit is in an ON state, performing a multi target CNOT operation on the data register qubits, wherein the multi target CNOT operation is dependent on a binary encoding of the data item and the final control qubit acts as the control for the multi target CNOT operation;b) determining a number of uncomputations of the iteratively computed logical AND operations described with reference to step904to perform;c) performing the determined number of uncomputations;d) performing a CNOT operation between a control qubit corresponding to the last uncomputed logical AND operation and a next highest control qubit, wherein the next highest control qubit acts as a control for the CNOT operation;e) iteratively computing a number of logical AND operations as described above with reference to step904to recompute the final control qubit.

As described above with reference toFIG.9, determining a number of uncomputations of the iteratively computed logical AND operations to perform includes determining how many bits are flipped when changing the binary representation of an index value corresponding to a final control qubit to the next (or, equivalently, the number of times it is possible to divide the index value in base 10 by 2 before the result becomes a non-integer). The number of uncomputations to perform is then equal to the determined number of required bit flips minus 1. Alternatively, the number of uncomputations to perform is equal to the number of times the value of the next index value can be divided by 2 before a non-integer result is obtained.

For example, for a first repetition, a multi target CNOT operation1010is performed on the data register qubits1006if the final control qubit is in an ON state, with the multi target CNOT operation1010being dependent on a binary encoding of the data item d0and the final control qubit acting as the control for the multi target CNOT operation1010. No uncomputations are then performed. A CNOT operation1012is then performed between the final control qubit and a penultimate control qubit. No logical AND operations are then performed.

As another example, for a sixth repetition, a multi target CNOT operation1014is performed on the data register qubits1006if the final control qubit is in an ON state, with the multi target CNOT operation1014being dependent on a binary encoding of the data item d5and the final control qubit acting as the control for the multi target CNOT operation1014. One uncomputation is then performed. A CNOT operation1016is then performed between the penultimate control qubit and a next highest control qubit. One logical AND operation is then performed.

In some implementations, the system may further uncompute the iteratively computed multiple logical AND operations between respective pairs of control qubits and index qubits, as described above with reference to step1102, to reset the index register to encode the index value.

Example Hardware

FIG.12depicts an exemplary system1200for implementing unary iteration quantum circuits and data loading quantum circuits. The system1200is an example of a system implemented as quantum or classical computer programs on one or more quantum computing devices or classical computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

The system1200includes a quantum computing device1202in data communication with one or more classical processors1204. For convenience, the quantum computing device1202and classical processors1204are illustrated as separate entities, however in some implementations the one or more classical processors may be included in quantum computing device1202.

The quantum computing device1202includes components for performing quantum computation. For example, the quantum computing device1202includes quantum circuitry1206, control devices1208, and T factories1210.

The quantum circuitry1206includes components for implementing a unary iteration quantum circuit1212. For example, the quantum circuitry may include a quantum system that includes one or more multi-level quantum subsystems, e.g., a register of qubits1214. The type of multi-level quantum subsystems that the system1200utilizes may vary. For example, in some implementations the multi-level quantum subsystems may be superconducting qubits, e.g., Gmon or Xmon qubits. In some cases, it may be convenient to include one or more resonators attached to one or more superconducting qubits. In other cases, ion traps, photonic devices or superconducting cavities (with which states may be prepared without requiring qubits) may be used. Further examples of realizations of multi-level quantum subsystems include fluxmon qubits, silicon quantum dots or phosphorus impurity qubits.

Quantum circuits comprising different quantum logic operations, e.g., single qubit gates, two qubit gates, and three qubit gates such as the logical AND operations as described above with reference toFIG.2, may be constructed using the quantum circuitry1206. Constructed quantum circuits can be operated/implemented using the control devices1208. The type of control devices1208included in the quantum system depend on the type of qubits included in the quantum computing device. For example, in some cases the control devices1208may include devices that control the frequencies of qubits included in the quantum circuitry1206, an excitation pulse generator and control lines that couple the qubits to the excitation pulse generator. The control devices may then cause the frequency of each qubit to be adjusted towards or away from a quantum gate frequency of an excitation pulse on a corresponding control driveline. The control devices1208may further include measurement devices, e.g., readout resonators. Measurement results obtained via measurement devices may be provided to the classical processors1204for processing and analyzing.

Implementations of the digital and/or quantum subject matter and the digital functional operations and quantum operations described in this specification can be implemented in digital electronic circuitry, suitable quantum circuitry or, more generally, quantum computational systems, in tangibly-embodied digital and/or quantum computer software or firmware, in digital and/or quantum computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. The term “quantum computational systems” may include, but is not limited to, quantum computers, quantum information processing systems, quantum cryptography systems, or quantum simulators.

Implementations of the digital and/or quantum subject matter described in this specification can be implemented as one or more digital and/or quantum computer programs, i.e., one or more modules of digital and/or quantum computer program instructions encoded on a tangible non-transitory storage medium for execution by, or to control the operation of, data processing apparatus. The digital and/or quantum computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, one or more qubits, or a combination of one or more of them. Alternatively or in addition, the program instructions can be encoded on an artificially-generated propagated signal that is capable of encoding digital and/or quantum information, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode digital and/or quantum information for transmission to suitable receiver apparatus for execution by a data processing apparatus.

The terms quantum information and quantum data refer to information or data that is carried by, held or stored in quantum systems, where the smallest non-trivial system is a qubit, i.e., a system that defines the unit of quantum information. It is understood that the term “qubit” encompasses all quantum systems that may be suitably approximated as a two-level system in the corresponding context. Such quantum systems may include multi-level systems, e.g., with two or more levels. By way of example, such systems can include atoms, electrons, photons, ions or superconducting qubits. In many implementations the computational basis states are identified with the ground and first excited states, however it is understood that other setups where the computational states are identified with higher level excited states are possible.

The term “data processing apparatus” refers to digital and/or quantum data processing hardware and encompasses all kinds of apparatus, devices, and machines for processing digital and/or quantum data, including by way of example a programmable digital processor, a programmable quantum processor, a digital computer, a quantum computer, multiple digital and quantum processors or computers, and combinations thereof. The apparatus can also be, or further include, special purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), or a quantum simulator, i.e., a quantum data processing apparatus that is designed to simulate or produce information about a specific quantum system. In particular, a quantum simulator is a special purpose quantum computer that does not have the capability to perform universal quantum computation. The apparatus can optionally include, in addition to hardware, code that creates an execution environment for digital and/or quantum computer programs, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A digital computer program, which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code, can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a digital computing environment. A quantum computer program, which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code, can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and translated into a suitable quantum programming language, or can be written in a quantum programming language, e.g., QCL or Quipper.

A digital and/or quantum computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or portions of code. A digital and/or quantum computer program can be deployed to be executed on one digital or one quantum computer or on multiple digital and/or quantum computers that are located at one site or distributed across multiple sites and interconnected by a digital and/or quantum data communication network. A quantum data communication network is understood to be a network that may transmit quantum data using quantum systems, e.g., qubits. Generally, a digital data communication network cannot transmit quantum data, however a quantum data communication network may transmit both quantum data and digital data.

The processes and logic flows described in this specification can be performed by one or more programmable digital and/or quantum computers, operating with one or more digital and/or quantum processors, as appropriate, executing one or more digital and/or quantum computer programs to perform functions by operating on input digital and quantum data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA or an ASIC, or a quantum simulator, or by a combination of special purpose logic circuitry or quantum simulators and one or more programmed digital and/or quantum computers.

For a system of one or more digital and/or quantum computers to be “configured to” perform particular operations or actions means that the system has installed on its software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more digital and/or quantum computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by digital and/or quantum data processing apparatus, cause the apparatus to perform the operations or actions. A quantum computer may receive instructions from a digital computer that, when executed by the quantum computing apparatus, cause the apparatus to perform the operations or actions.

Digital and/or quantum computers suitable for the execution of a digital and/or quantum computer program can be based on general or special purpose digital and/or quantum processors or both, or any other kind of central digital and/or quantum processing unit. Generally, a central digital and/or quantum processing unit will receive instructions and digital and/or quantum data from a read-only memory, a random access memory, or quantum systems suitable for transmitting quantum data, e.g. photons, or combinations thereof.

The essential elements of a digital and/or quantum computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and digital and/or quantum data. The central processing unit and the memory can be supplemented by, or incorporated in, special purpose logic circuitry or quantum simulators. Generally, a digital and/or quantum computer will also include, or be operatively coupled to receive digital and/or quantum data from or transfer digital and/or quantum data to, or both, one or more mass storage devices for storing digital and/or quantum data, e.g., magnetic, magneto-optical disks, optical disks, or quantum systems suitable for storing quantum information. However, a digital and/or quantum computer need not have such devices.

Digital and/or quantum computer-readable media suitable for storing digital and/or quantum computer program instructions and digital and/or quantum data include all forms of non-volatile digital and/or quantum memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; CD-ROM and DVD-ROM disks; and quantum systems, e.g., trapped atoms or electrons. It is understood that quantum memories are devices that can store quantum data for a long time with high fidelity and efficiency, e.g., light-matter interfaces where light is used for transmission and matter for storing and preserving the quantum features of quantum data such as superposition or quantum coherence.

Control of the various systems described in this specification, or portions of them, can be implemented in a digital and/or quantum computer program product that includes instructions that are stored on one or more non-transitory machine-readable storage media, and that are executable on one or more digital and/or quantum processing devices. The systems described in this specification, or portions of them, can each be implemented as an apparatus, method, or system that may include one or more digital and/or quantum processing devices and memory to store executable instructions to perform the operations described in this specification.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of what may be claimed, but rather as descriptions of features that may be specific to particular implementations. Certain features that are described in this specification in the context of separate implementations can also be implemented in combination in a single implementation. Conversely, various features that are described in the context of a single implementation can also be implemented in multiple implementations separately or in any suitable sub-combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a sub-combination or variation of a sub-combination.

Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system modules and components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

Particular implementations of the subject matter have been described. Other implementations are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some cases, multitasking and parallel processing may be advantageous.