Patent Description:
Classical computers have memories made up of bits, where each bit can represent either a zero or a one. Quantum computers maintain sequences of quantum bits, called qubits, where each quantum bit can represent a zero, one or any quantum superposition of zeros and ones. Quantum computers operate by setting qubits in an initial state and controlling the qubits, e.g., according to a sequence of quantum logic gates.

"<NPL>) discloses a fault-tolerant construction to implement a composite quantum operation of four overlapping Toffoli gates. The same construction can produce two independent Toffoli gates.

"<NPL>) discloses the construction of a universal set of fault-tolerant gates without state distillation by using only transversal controlled-controlled-Z, transversal Hadamard, and fault-tolerant error correction.

Performing error corrected quantum computations involves implementing sequences of unitary operations and measurements, where intermediate measurement results are used to determine future unitary operations. For example, in the surface code, performing logical T and T† gates involves a measurement dependent future S gate.

The measurement depth of a quantum circuit (defined as the minimum number of T gates implemented sequentially to complete execution) determines how many times a classical control system will: perform a set of measurements, decide which basis to use for the next set of measurements, and start those measurements. The speed at which the classical control system can run this loop, and work through the measurements, determines the speed of the quantum computation. The characteristic time taken for the classical control system to react to a measurement and perform a following dependent measurement is referred as the control system's "reaction time". A quantum computation whose speed is limited by the measurement depth of the circuit and the reaction time of the classical control system is referred to as a "reaction limited computation".

This specification describes techniques for decreasing the space overhead of reaction limited computations and improving qubit routing in reaction limited computations. The techniques include: an optimized reaction limited selective CZ operation, referred to herein as a delayed choice CZ, techniques for producing and consuming AutoCCZ states, which make routing easier because they decouple the consumption of the CCZ state from the fixup operations needed to complete a gate teleportation, an improved CCZ distillation factory, and apparatus for performing addition operations and lookup operations.

<FIG> depicts an example quantum computation system <NUM>. The system <NUM> is an example of a system implemented as quantum and classical computer programs on one or more quantum computing devices and classical computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

The system <NUM> includes a quantum computing device <NUM> in data communication with one or more classical processors <NUM>. For convenience, the quantum computing device <NUM> and classical processors <NUM> are illustrated as separate entities, however in some implementations the classical processors <NUM> may be included in the quantum computing device <NUM>.

The quantum computing device <NUM> includes components for performing quantum computation. For example, the quantum computing device <NUM> includes quantum circuitry <NUM> and control devices <NUM>.

The quantum circuitry <NUM> includes components for performing quantum computations, e.g., components for implementing the various quantum circuits and operations described in this specification. For example, the quantum circuitry may include a quantum system that includes one or more multi-level quantum subsystems, e.g., qubits <NUM>. The qubits <NUM> are physical qubits that may be used to perform algorithmic operations or quantum computations. The specific realization of the one or more qubits and their interactions may depend on a variety of factors including the type of quantum computations that the quantum computing device <NUM> is performing. For example, the qubits may include qubits that are realized via atomic, molecular or solid-state quantum systems. In other examples the qubits may include, but are not limited to, superconducting qubits, e.g., Gmon or Xmon qubits, or semi-conducting qubits. Further examples of realizations of multi-level quantum subsystems include fluxmon qubits, silicon quantum dots or phosphorus impurity qubits. In some cases to the quantum circuitry may further include one or more resonators attached to one or more superconducting qubits. In some cases ion traps, photonic devices or superconducting cavities (with which states may be prepared without requiring qubits) may be used.

In this specification, the term "quantum circuit" is used to refer to a sequence of quantum logic operations that can be applied to a qubit register to perform a respective computation. Quantum circuits comprising different quantum logic operations, e.g., single qubit gates, multi-qubit gates, etc., may be constructed using the quantum circuitry <NUM>. Constructed quantum circuits can be operated/implemented using the control devices <NUM>.

The type of control devices <NUM> included in the quantum system depend on the type of qubits included in the quantum computing device. For example, in some cases the multiple qubits can be frequency tunable. That is, each qubit may have associated operating frequencies that can be adjusted using one or more control devices. Example operating frequencies include qubit idling frequencies, qubit interaction frequencies, and qubit readout frequencies. Different frequencies correspond to different operations that the qubit can perform. For example, setting the operating frequency to a corresponding idling frequency may put the qubit into a state where it does not strongly interact with other qubits, and where it may be used to perform single-qubit gates. In these examples the control devices <NUM> may include devices that control the frequencies of qubits included in the quantum circuitry <NUM>, 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 devices <NUM> may further include measurement devices, e.g., readout resonators. Measurement results obtained via measurement devices may be provided to the classical processors <NUM> for processing and analyzing. Measurement devices perform physical measurements on properties of the qubits, either directly or indirectly, from which the state(s) of the qubits can be inferred. Measurement devices perform physical measurements on properties of the qubits, either directly or indirectly, from which the state(s) of the qubits can be inferred.

The quantum computing device <NUM> can further include one or more quantum state factories, e.g., T factories, that produce and store quantum states, e.g., T or CCZ states, to be used in computations performed by the system <NUM>.

Known techniques for performing delayed choice CZ operations are often not optimal. For example, teleporting a CCZ gate produces up to three possible CZ fixup operations. Using known techniques based on controllable multiplexers and de-multiplexers to delay the choice of whether or not the various CZ fixups should be applied would produce eight routing qubits per potential CZ (because there are two qubits involved in a CZ and each must go through a multiplexer/de-multiplexer pair). The presently described techniques is more compact and may only use two routing qubits.

<FIG> is a flow diagram of an example process <NUM> for performing a delayed choice CZ operation on a first data qubit and a second data qubit. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system prepares a first routing qubit and a second routing qubit in a magic state (step <NUM>). For example, the system may prepare the first routing qubit in a plus state, prepare the second routing qubit in a plus state, and perform a CZ operation on the first routing qubit and the second routing qubit.

The system interacts i) the first data qubit with the first routing qubit, and ii) the second data qubit with the second routing qubit using a first CNOT operation and a second CNOT operation, respectively (step <NUM>). The first data qubit and second data qubit act as a first control and a second control for the first CNOT operation and the second CNOT operation, respectively. Optionally, the system stores the states of the first routing qubit and second routing qubit.

The system receives a first classical bit from a classical processor. In some implementations the first classical bit may be an output of a classical computation that determines whether or not a classical controlled Z operation is to be performed on the first data qubit and second data qubit. The system determines whether the first classical bit represents an off state or an on state (step <NUM>). The system determines whether the first classical bit represents the off state or on state by determining whether the first classical bit is <NUM> (where the first classical bit represents an on state) or <NUM> (where the first classical bit represents an off state).

In response to determining that the first classical bit represents an on state at step <NUM>, the system performs the below described steps <NUM>-<NUM>. The system applies a first Hadamard gate to the first routing qubit and applies a second Hadamard gate to the second routing qubit (step <NUM>).

The system measures the first routing qubit using a Z basis measurement to obtain a second classical bit and measures the second routing qubit using a Z basis measurement to obtain a third classical bit (step <NUM>).

The system performs classically controlled fix up operations on the first data qubit and second data qubit using the second classical bit and the third classical bit (step <NUM>). To perform the classically controlled fix up operations the system: applies a classically controlled swap operation to the second classical bit and third classical bit, where the first classical bit acts as a control for the classically controlled swap operation, applies a first classically controlled Z operation to the second data qubit, where the third classical bit acts as a control for the first classically controlled Z operation, and applies a second classically controlled Z operation to the first data qubit, where the second classical bit acts as a control for the second classically controlled Z operation.

In response to determining that the first classical bit represents an off state at step <NUM>, the system performs the below described steps <NUM>-<NUM>. The system measures the first routing qubit using a Z basis measurement to obtain a fourth classical bit (step <NUM>). The system measures the second routing qubit using a Z basis measurement to obtain a fifth classical bit (step <NUM>). The system performs classically controlled fix up operations on the first data qubit and second data qubit using the obtained fourth classical bit and fifth classical bit (step <NUM>).

To perform the classically controlled fix up operations on the first data qubit and the second data qubit, the system: applies a classically controlled swap operation to the fourth classical bit and fifth classical bit, where the first classical bit acts as a control for the classically controlled swap operation, applies a first classically controlled Z operation to the second data qubit, where the fifth classical bit acts as a control for the first classically controlled Z operation, and applies a second classically controlled Z operation to the first data qubit, where the fourth classical bit acts as a control for the second classically controlled Z operation.

<FIG> is a circuit diagram of an example quantum circuit <NUM> for performing a delayed choice CZ operation <NUM> on a first data qubit <NUM> and a second data qubit <NUM>, as shown in box <NUM>. The example quantum circuit <NUM> includes a CZ operation <NUM> applied to a first routing qubit <NUM> and a second routing qubit <NUM>, where both the first routing qubit <NUM> and the second routing qubit <NUM> are prepared in a plus state. Operation <NUM> corresponds to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> further includes a first CNOT operation 316a and a second CNOT operation 316b. The first CNOT operation 316a targets the first routing qubit and uses the first data qubit <NUM> as a control. The second CNOT operation 316b targets the second routing qubit and uses the second data qubit <NUM> as a control. Operations 316a, 316b correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> further includes a first Hadamard gate 318a applied to the first routing qubit <NUM> and a second Hadamard gate 318b applied to the second routing qubit <NUM>. Hadamard gates 318a and 318b are only applied when a classical bit <NUM> represents an on state (i.e., when the classical bit is a <NUM>). Operations 318a, 318b correspond to steps <NUM>-<NUM> of example process <NUM>.

The example quantum circuit <NUM> further includes a first measurement operation 322a applied to the first routing qubit <NUM> and a second measurement operation 322b applied to the second routing qubit <NUM>. Operations 322a, 322b correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> includes a classically controlled swap operation <NUM> that swaps the output of the measurement operations 322a, 322b if the classical bit <NUM> represents an on state (i.e., when the classical bit <NUM> is a <NUM>). The example quantum circuit <NUM> further includes a first classically controlled Z gate <NUM> that is applied to the first data qubit <NUM> if an output of the classically controlled swap operation <NUM> corresponding to the first routing qubit represents an on state. The example quantum circuit <NUM> further includes a second classically controlled Z gate <NUM> that is applied to the second data qubit <NUM> if an output of the classically controlled swap operation <NUM> corresponding to the second routing qubit represents an on state. Operations <NUM>-<NUM> correspond to step <NUM> of example process <NUM>.

Three instances of the construction for performing delayed choice CZ operations as described in example process <NUM> of <FIG> can be embedded directly into a CCZ state, so that there is one delayed choice CZ for each CZ fixup that may be needed when performing gate teleportation. This augments the CCZ state into an "Auto-CCZ" state, so called because required fixup operations are automatically performed (through insertion of conditional Hadamard gates within the quantum circuit where remaining Pauli fixup operations can be performed within the control-software) and do not require conditional insertion of CZ gates based on measurement results. This makes consuming the state simpler, because no corrections are needed at the consumption site.

<FIG> is a flow diagram of an example process <NUM> for performing an auto corrected CCZ operation on a first, second and third data qubit. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system prepares nine routing qubits in a magic state (step <NUM>). For example, the system may prepare each of the nine routing qubits in a plus state, perform a CCZ operation on the first, fourth and seventh routing qubits, and perform CZ operations on pairs of neighboring routing qubits.

The system interacts i) the first data qubit with a first routing qubit using a first CNOT operation, ii) the second data qubit with a fourth routing qubit using a second CNOT operation, and iii) the third data qubit with a seventh routing qubit using a third CNOT operation (step <NUM>). The first data qubit acts as a control for the first CNOT operation, the second data qubit acts as a control for the second CNOT operation, and the third data qubit acts as a control for the third CNOT operation.

The system measures the first, fourth and seventh routing qubits to obtain a first, fourth and seventh classical bit (step <NUM>).

Optionally, the system stores the second routing qubit, third routing qubit, fifth routing qubit, sixth routing qubit, eighth routing qubit and ninth routing qubit.

The system determines whether the first classical bit represents an off state or an on state. In response to determining that the first classical bit represents an on state, the system applies a first Hadamard gate to the fifth routing qubit and applies a second Hadamard gate to the sixth routing qubit (step <NUM>). The system measures the fifth routing qubit using a Z basis measurement to obtain a fifth classical bit and measures the sixth routing qubit using a Z basis measurement to obtain a sixth classical bit (step <NUM>). In response to determining that the first classical bit represents an off state, the system does not perform the first Hadmard gate or second Hadamard gate and directly performs step <NUM>.

The system determines whether the fourth classical bit represents an off state or an on state. In response to determining that the fourth classical bit represents an on state, the system applies a third Hadamard gate to the eighth routing qubit and applies a fourth Hadamard gate to the ninth routing qubit (step <NUM>). The system measures the eighth routing qubit using a Z basis measurement to obtain a eighth classical bit and measures the ninth routing qubit using a Z basis measurement to obtain a ninth classical bit (step <NUM>). In response to determining that the fourth classical bit represents an off state, the system does not apply the third and fourth Hadamard gates and directly performs step <NUM>.

The system determines whether the seventh classical bit represents an off state or an on state. In response to determining that the seventh classical bit represents an on state, the system applies a fifth Hadamard gate to the second routing qubit and applies a sixth Hadamard gate to the third routing qubit (step <NUM>). The system measures the second routing qubit using a Z basis measurement to obtain a second classical bit and measures the third routing qubit using a Z basis measurement to obtain a third classical bit (step <NUM>). In response to determining that the seventh classical bit represents an off state, the system does not apply the fifth and sixth Hadamard gates and directly performs step <NUM>.

The system performs classically controlled fix up operations on the first, second and third data qubits using respective classical bits (step <NUM>). For example, the system may: apply a first classically controlled swap operation to the second classical bit and third classical bit, where the seventh classical bit acts as a control for the first classically controlled swap operation, apply a second classically controlled swap operation to the fifth classical bit and sixth classical bit, where the first classical bit acts as a control for the second classically controlled swap operation, apply a third classically controlled swap operation to the eighth classical bit and ninth classical bit, where the fourth classical bit acts as a control for the third classically controlled swap operation, apply multiple classically controlled Z operations to the first, second, and third data qubits, where each classically controlled Z operation uses one of the second, third, fifth, sixth, eighth or ninth classical bits as a control for the classically controlled Z operation, and apply multiple classically controlled-controlled Z operations to the first, second and third data qubits, where each classically controlled-controlled Z operation uses two of the first, fourth and seventh classical bits as controls for the classically controlled-controlled Z operation.

Applying multiple classically controlled Z operations to the first, second, and third data qubits, wherein each classically controlled Z operation uses one of the second, third, fifth, sixth, eighth or ninth classical bits as a control for the classically controlled Z operation, can include: applying a first classically controlled Z operation to the third data qubit, wherein the second classical bit acts as a control for the first classically controlled Z operation; applying a second classically controlled Z operation to the second data qubit, wherein the third classical bit acts as a control for the second classically controlled Z operation; applying a third classically controlled Z operation to the third data qubit, wherein the fifth classical bit acts as the control for the third classically controlled Z operation; applying a fourth classically controlled Z operation to the first data qubit, wherein the sixth classical bit acts as the control for the fourth classically controlled Z operation; applying a fifth classically controlled Z operation to the second data qubit, wherein the eighth classical bit acts as the control for the fifth classically controlled Z operation; and applying a sixth classically controlled Z operation to the first data qubit, wherein the ninth classical bit acts as the control for the sixth classically controlled Z operation.

Applying multiple classically controlled-controlled Z operations to the first, second and third data qubits, wherein each classically controlled-controlled Z operation uses two of the first, fourth and seventh classical bits as controls for the classically controlled-controlled Z operation, can include: applying a first classically controlled-controlled Z operation to the first data qubit, wherein the first classical bit and fourth classical bit act as controls for the first classically controlled-controlled Z operation; applying a second classically controlled-controlled Z operation to the second data qubit, wherein the fourth classical bit and seventh classical bit act as controls for the second classically controlled-controlled Z operation; and applying a third classically controlled-controlled Z operation to the third data qubit, wherein the first classical bit and seventh classical bit act as controls for the third classically controlled-controlled Z operation.

<FIG> is a circuit diagram of an example quantum circuit <NUM> for performing an auto corrected CCZ operation <NUM> on a first data qubit <NUM>, second data qubit <NUM> and a third data qubit <NUM>. The example quantum circuit <NUM> includes a CCZ operation <NUM> applied to a first, fourth and seventh routing qubit in a register <NUM> that includes nine routing qubits, where each routing qubit is prepared in a plus state. The example quantum circuit <NUM> further includes multiple CZ operations, e.g., CZ operation <NUM>, applied to pairs of neighboring routing qubits (with the convention that the last routing qubit neighbors the first routing qubit). For example, the example quantum circuit <NUM> includes a first CZ operation applied to the first and second routing qubits, a second CZ operation applied to the second and third routing qubits, etc. In total the example quantum circuit <NUM> includes nine CZ operations. The CCZ operation <NUM> and multiple CZ operation, e.g., CZ operation <NUM>, correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> includes three CNOT operations, e.g., CNOT operation <NUM>. A first CNOT operation targets the first routing qubit and uses the first data qubit as a control. A second CNOT operation targets the fourth routing qubit and uses the second data qubit as a control. A third CNOT operation targets the seventh routing qubit and uses the third data qubit as a control. The three CNOT operations correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> includes three measurement operations, e.g., measurement operation <NUM>. A first measurement operation measures the first routing qubit. A second measurement operation measures the fourth routing qubit. A third measurement operation measures the seventh routing qubit. The three measurement operations correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> includes multiple Hadamard gates, e.g., Hadamard gate <NUM>. A first Hadamard gate and a second Hadamard gate are applied to the second routing qubit and third routing qubit, respectively, if a measurement result of the measurement operation performed on the seventh routing qubit represents an on state. A third Hadamard gate and a fourth Hadamard gate are applied to the fifth routing qubit and sixth routing qubit, respectively, if a measurement result of the measurement operation performed on the first routing qubit represents an on state. A fifth Hadamard gate and a sixth Hadamard gate are applied to the eighth routing qubit and ninth routing qubit, respectively, if a measurement result of the measurement operation performed on the fourth routing qubit represents an on state. The example quantum circuit <NUM> includes multiple measurement operations, e.g., measurement operation <NUM>, that are applied to the second, third, fifth, sixth, eighth and ninth routing qubits. The Hadamard gates and measurement operations described correspond to steps <NUM>-<NUM> of example process <NUM>.

The example quantum circuit <NUM> includes multiple classically controlled swap operations, e.g., classically controlled swap operation <NUM>, that swap outputs of respective measurement operations if a respective classical bit represents an on state. For example, classically controlled swap operation <NUM> swaps the outputs of the measurement operations performed on the eighth and ninth routing qubits if the output of the measurement operation performed on the fourth routing qubit represents an on state. A second classically controlled swap operation swaps the outputs of the measurement operations performed on the fifth and sixth routing qubits if the output of the measurement operation performed on the first routing qubit represents an on state. A third classically controlled swap operation swaps the outputs of the measurement operations performed on the second and third routing qubits if the output of the measurement operation performed on the seventh routing qubit represents an on state. The classically control swap operations described correspond to step <NUM> of example process <NUM>.

The example quantum circuit <NUM> includes multiple classically controlled Z gates, e.g., classically controlled Z gate <NUM>, that are applied to the first data qubit <NUM>, second data qubit <NUM> and third data qubit <NUM> based on outputs of the three classically controlled swap operations. For example, a first Z gate is applied to the first data qubit <NUM> if an output of the third classically controlled swap operation corresponding to the second routing qubit represents an on state. A second Z gate is applied to the second data qubit <NUM> if an output of the third classically controlled swap operation corresponding to the third routing qubit represents an on state. A third Z gate <NUM> is applied to the second data qubit <NUM> if an output of the second classically controlled swap operation corresponding to the fifth routing qubit represents an on state. A fourth Z gate is applied to the third data qubit <NUM> if an output of the second classically controlled swap operation corresponding to the sixth routing qubit represents an on state. A fifth Z gate is applied to the third data qubit <NUM> if an output of the first classically controlled swap operation <NUM> corresponding to the eighth routing qubit represents an on state. A sixth Z gate is applied to the first data qubit <NUM> if an output of the first classically controlled swap operation <NUM> corresponding to the ninth routing qubit represents an on state.

A seventh Z gate is applied to the third data qubit if the output of the measurement of the first routing qubit and the fourth routing qubit both represent on states. An eighth Z gate is applied to the first data qubit if the output of the measurement of the seventh routing qubit and the fourth routing qubit both represent on states. A ninth Z gate is applied to the second data qubit if the output of the measurement of the first routing qubit and the seventh routing qubit both represent on states. The multiple classically controlled Z gates correspond to step <NUM> of example process <NUM>.

Operations that are not native to the surface code can be performed using magic state distillation and gate teleportation. A particularly useful magic state is the CCZ state <MAT> This quantum state is particularly useful because the quantum equivalent of the AND gate - the Toffoli gate - is not native to the surface code but can be performed by consuming one CCZ state. Algorithms with a lot of arithmetic, such as Grover's algorithm and Shor's algorithm, perform many Toffoli gates and benefit from using a state specialized to this task.

<FIG> is a flow diagram of an example process <NUM> for producing a CCZ quantum state. For convenience, the process <NUM> will be described as being performed by a system of one or more classical and quantum computing devices located in one or more locations. For example, a quantum computation system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The system obtains a first number of T states of a first quality (step <NUM>). The system can obtain the first number of T states from a level-<NUM> T state factory. In some implementations the system can perform state injection techniques to obtain the first number of T states.

The system distills the first number of T states of the first quality into a second number of T states of a second quality (step <NUM>). The second number is smaller than the first number and the second quality is higher than the first quality. For example, in some implementations the system can implement the Reed-Muller code to distill the first number of T states into the second number of T states. The first number of T states can include at least <NUM> × <NUM> T states and the second number of T states can include <NUM> T states. The system can distill the first number of T states into a second number of T states using a level-<NUM> T state factory.

In some implementations the system distills the first number of T states of the first quality into a second number of T states of a second quality using multiple T factories, where each T factory receives the first number of T states of the first quality at least partially in parallel with stabilizer measurements performed by the T factory.

The system applies, using the second number of T states of the second quality, an error detecting Toffoli operation to a tensor product of plus states to obtain the CCZ quantum state (step <NUM>). The second number of T states can be provided for use in the error detecting operation at least partially in parallel with stabilizer measurements performed during the error detecting operation. The system can obtain the CCZ quantum state using a CCZ factory that includes six level-<NUM> T factories. In some implementations the CCZ quantum state can be obtained using a CCZ factory of depth 5d, where d represents error correcting code distance.

In some implementations the system chooses error correcting code distances for factories producing the first number of T states, second number of T states and CCZ state based on a target error rate and not based on layout considerations. For example, the probability of logical error in a single layer of surface code circuitry covering d × d data qubits with a characteristic physical gate error rate p is approximately pL = <NUM>(<NUM>p)((d+<NUM>)/<NUM>). A typical state distillation structure can involve on the order of <NUM> of such patches. If the target probability of logical failure from the distillation structure is no more than <NUM>-<NUM>, this would set a minimum code distance via <NUM>-<NUM> > <NUM> ∗ <MAT>. If p = <NUM>, which is a typical target physical gate error rate, this would reduce to <MAT>, implying a minimum code distance of <NUM>.

The production rate of the CCZ factory can be limited by either the level <NUM> or level <NUM> distances. At level <NUM> the production rate of the factory is limited by the factory's depth times the cycle time times the level <NUM> code distance. So, under the assumption of: a reaction time of <NUM> microseconds, a cycle time of <NUM> microsecond, a level <NUM> code distance of <NUM> and a level <NUM> code distance of <NUM>, the level <NUM> part of the factory is technically capable of producing states at a rate of (<NUM>µs · <NUM>)-<NUM> ≈ <NUM>. The level <NUM> part of the factory needs to produce <NUM> level <NUM> T states for each CCZ state that will be output. There are six level <NUM> T factories, and they have a depth of <NUM>. 75di, which means the output rate of the entire factory cannot be larger than (<NUM> · <NUM> · <NUM>µs · <NUM>/<NUM>)-<NUM> ≈ <NUM>. Therefore the level <NUM> code distance is the limiting factor, and the factory runs at <NUM>.

In a reaction limited computation, one CCZ state will be needed per reaction time of the classical control system. That is to say, CCZ states are consumed at a rate of <NUM>. Therefore, given the above assumptions, a reaction limited computation may require [<NUM>/<NUM>]=<NUM> CCZ factories running in parallel.

The above described Auto-CCZ states can be used to construct an improved system layout for performing reaction limited addition operations, e.g., implementing a quantum ripple-carry addition circuit as described in "A new quantum ripple-carry addition circuit," Cuccaro et. , arXiv preprint quant-ph/<NUM>, <NUM>, the disclosure of which is incorporated herein by reference in its entirety. These quantum ripple-carry addition circuits compute the sum of two n-bit numbers a = a<NUM>a<NUM>. an-<NUM> and b = b<NUM>b<NUM>. bn-<NUM> where a<NUM>, b<NUM> represent the lowest order bits. Ai, Bi represent memory locations where ai, bi are initially stored respectively. The numbers a and b are added in place, and at the end Bi contains si, the i-th bit of the sum, replacing bi. There is one additional output location for the high bit sn. The carry string for the addition can be defined recursively - c<NUM> = <NUM> and ci+<NUM> = MAJ(ai, bi, ci) for i ≥ <NUM> where MAJ represents an "in place Majority" operation defined by MAJ(ai, bi, ci) = aibi⊕aici⊕bici such that ci = ai⊕bi⊕ci for all i < n and sn = cn. Each ci can be computed in order, from c<NUM> to cn. To perform an addition of two n-bit numbers a sequence of n MAJ gates is performed. After performing the ladder of MAJ gates a sequence of "UnMajority and Add" (UMA) gates is performed, proceeding in reverse order. Each UMA gate uncomputes a corresponding MAJ gate and performs a three-way <MAT> addition ai⊕bi⊕ci.

The system layout enables some operations of the addition circuit to be laid out in a space-like fashion, so that they can be performed approximately simultaneously (e.g., within limits of the available hardware). This is achieved by implementations of the addition circuit's in-place majority MAJ operations and UnMajority and Add UMA operations that accept CCZ states and propagate involved bits horizontally across space, instead of vertically through time. The entire addition circuit is not laid out in a spacelike fashion, since this would require a number of CCZ factories that is proportional to the size of the addition instead of proportional to the reaction time of the control system. Instead, the addition is performed back and forth across space, performing an amount of carry rippling that keeps the CCZ factories and corresponding classical control system operating at a system-specific optimal rate.

The system layout also enables CCZ states produced by CCZ factories to be efficiently routed into the addition operation. Each "in-place majority" operation has four inputs and three outputs. One of the inputs, and also one of the outputs, is a carry qubit. Another two of the inputs (and outputs) are data qubits - one from the target register and one from the offset register. The remaining input is the three qubits making up the CCZ part of an Auto-CCZ state. These input and output qubits must be routed in a way that causes them to intersect the "in-place majority" operation at the right place and at the right time. The presently described system layout achieves this by moving the carry qubit back and forth along the X axis (right/left through space), while running data qubits through along the Y axis (forward/back through space). CCZ factories are placed in front of and behind the area in which the carry qubit is moved back and forth (referred to herein an operating area), so that their outputs are produced directly adjacent to where they are needed making routing trivial. Gaps are left between adjacent factories, so that data qubits from outside the operating area can be routed through those gaps as needed.

As more and more data qubits are routed from behind the operating area to in front (or vice versa), the operating area is shifted backward (or forward). The two data registers are interleaved into alternating rows, so that qubits that need to reach the same "in-place majority" operation at the same time are adjacent. Within each row there is additional interleaving, spacing out qubits that are sequential in the register. This prevents congestion as the data qubits are routed through the gaps between the factories.

<FIG> shows an example system layout <NUM> for performing a reaction limited ripple-carry addition operation. The example system layout <NUM> is shown from above. That is, the horizontal axis and vertical axis are spatial axes. For example, the example system layout <NUM> can be part of a quantum chip or tiled array of chips. In the example system layout <NUM>, a level <NUM> code distance of <NUM> and a level <NUM> code distance of <NUM> are assumed.

The example system includes multiple qubits. The multiple qubits are arranged in the example system layout <NUM> in a two dimensional array that includes multiple rows <NUM>, where each row includes multiple qubits, e.g., <NUM> logical qubits. The multiple qubits include qubits from a lookup output register, e.g., qubits in row 702a, and from a target register, e.g., qubits in row 702b. Rows of qubits from the lookup output register and rows of qubits from the target register are interleaved to allow qubits in each register to be operated on pairwise, as described above.

Each row is associated with a value at a respective position in a sequence of n bits, where the sequence of bits represents a binary numeric value. The top row of qubits in the multiple rows is associated with a value representing a most significant bit in the sequence of n bits, and increasingly lower rows of qubits in the multiple rows are associated with respective values representing decreasing significant bits in the sequence of n bits.

Rows of qubits from the target register represent the n-bit numbers that are to be added, where alternate qubits in each row of qubits from the target register represent the respective numbers to be added. For example, when adding the number <NUM> to <NUM> (which for illustrative purposes only are given in decimals, not binary), the target register may store <NUM>. If the two-dimensional array of qubits has length <NUM> (e.g., the rows <NUM> include <NUM> qubits) then the rows <NUM> would include four rows of qubits from the target register:.

The example system layer <NUM> further includes multiple CCZ factories <NUM>, e.g., CCZ factory 704a, that produce the presently described Auto-CCZ states and provide produced states for use in the addition operation performed in the operating area <NUM>, e.g., for use in "in-place majority" operations. Each CCZ factory includes two CCZ fixup areas, e.g., area <NUM>, because routing qubits emerging from a CCZ fixup box can extend vertically into a next layer before the control system determines how to measure the routing qubits.

In the example system layout <NUM>, the multiple CCZ factories <NUM> surround an operating area <NUM>. The operating area <NUM> is an area in which the multiple rows of qubits are operated on to perform the addition operation. The CCZ factories <NUM> are separated in space by gaps, e.g., gap <NUM>, to allow qubits to be routed into and through the operating area <NUM>, as described above.

During an addition operation, for each row of qubits in the multiple rows and starting with a row of qubits at the bottom of the multiple rows: qubits in the row are moved through one or more of the gaps and into the operating area where an addition operation is performed using the qubits in the row, and after the addition operation is performed, the qubits in the row are moved through and out of the operating area. For example, continuing the example given above where <NUM> is to be added to <NUM> and the target register initially stores the number <NUM> in four rows of six qubits:.

The addition continues scanning across each row of target qubits.

The output of the ripple carry operation can be obtained by measuring the qubits that have been moved through and out of the operating area.

The example system layout <NUM> can perform ripple-carry addition operations at the reaction limited rate, propagating carry information from qubit to qubit at <NUM>. Under reasonable physical assumptions, it is estimated that the layout would add a pair of thousand-qubit registers in approximately <NUM> milliseconds.

The above described ripple-carry addition operation is ideal for reaction limited computation because it has only a small amount of Clifford operations per Toffoli operation. A table lookup operation (also called a QROM read) is different - for each Toffoli operation performed in a table lookup, there multiple Clifford operations to perform. In particular, each Toffoli triggers a large multi-target CNOT operation that potentially involves all lookup output qubits. Because of this, the limiting factor during a table lookup is not the classical control system's reaction time but rather access to the output qubits.

In order to target a logical qubit with a CNOT, an unused logical-qubit sized patch of surface code adjacent to that logical qubit is needed. The CNOT operation will then use that patch for d cycles, where d is the code distance. For qubits where only one side is accessible, only one CNOT can be performed per d cycles. Under the assumption that a surface code cycle time equals <NUM> microsecond, and using a code distance of <NUM> (as an example), this suggests a maximum CNOT rate of <NUM> (instead of the <NUM> of a reaction limited computation).

It can be possible to work around this CNOT rate limitation. For example, if there are multiple single-control single-target CNOTs all targeting the same qubit, it is possible to fuse the many CNOTs into a single generalized CNOT where the control is a Pauli product of all the individual controls. However, this does not work in the case of table lookups because the set of relevant control qubits differs from output qubit to output qubit. Therefore, to overcome the CNOT rate limitation the presently described example system layout makes two sides of each qubit accessible, instead of just one. The large multi-target CNOT operations can then alternate between using one side, and using the other side. This doubles the achievable Toffoli rate from <NUM> to <NUM>, which is much closer to <NUM>.

In addition, while performing the lookup, the example system layout includes a tiled row interleaving pattern of R_L_L_R where an L represents a lookup data row, R represents an existing data row not involved in the lookup, and an underscore represents an empty access row that can be used when performing the multi-target CNOTs. The multi-target CNOT operations alternate between using the single inner access row and both of the outer access rows. In order to access the access rows, cross-row access corridors are included on opposing sides of the layout. The multi-target CNOT operations can alternate between using the two access corridors, so that they can branch into individual access rows as needed.

<FIG> shows an example system layout <NUM> for performing a table lookup operation. The example system layout <NUM> is shown from above. That is, the horizontal axis and vertical axis are spatial axes. For example, the example system layout <NUM> can be part of a quantum chip or tiled array of chips. In the example system layout <NUM>, a level <NUM> code distance of <NUM> and a level <NUM> code distance of <NUM> are assumed.

The example system layout <NUM> includes multiple CCZ factories, e.g., CCZ factory <NUM>, that feed the presently described auto-CCZ states into a first operating area <NUM> where the lookup operation is performed. Because the first operating area <NUM> is positioned centrally in the example system layout <NUM>, it is referred to herein as a central operating area <NUM>.

The example system includes a lookup output register that, in turn, includes multiple lookup output qubits. In the example system layout <NUM> the multiple lookup output qubits are arranged in a two-dimensional array that includes multiple rows, e.g., row <NUM>, where each row is associated with a value at a respective position in a sequence of n bits that represents a binary numeric value. A top row of qubits in the two-dimensional array is associated with a value representing a most significant bit in the sequence of n bits, and increasingly lower rows of qubits are associated with respective values representing decreasing significant bits in the sequence of n bits. The example system further includes a target register of qubits that are also arranged in rows, e.g., row <NUM>, that are interleaved between rows of lookup output qubits. The target register is idle during the lookup operation.

Each lookup output qubit is adjacent to one or more second operating areas, e.g., area <NUM>, that are positioned between rows in the multiple rows and that extend from approximately a vertical center of the two-dimensional array of qubits to one of two sides of the array, e.g., side <NUM>, and where third operating areas positioned at each side of the two-dimensional array connect the second operating areas to the first operating area <NUM>. Because the second operating areas extend along the x axis, they are referred to herein as horizontal operating areas or horizontal access rows. Similarly, because the third operating areas extend along the y axis, they are referred to herein as vertical operating areas or vertical access corridors. The vertical access corridors and horizontal access rows provide two distinct ways to simultaneously access all output qubits when performing many-target CNOTs.

In some implementations the example system layout <NUM> further includes a factor register of qubits including a first number of qubits that are idle and a second number of qubits that are used as address bits in the lookup operation, where the factor register is adjacent to the CCZ factories and separate from the central operating area <NUM>.

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. 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.

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 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 it 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.

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.

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.

Claim 1:
A method for implementing a delayed choice CZ operation on a first data qubit and a second data qubit using a quantum computation system (<NUM>), the method comprising:
preparing (<NUM>), by the quantum computation system, a first routing qubit and a second routing qubit in a magic state;
interacting (<NUM>), by the quantum computation system, i) the first data qubit with the first routing qubit, and ii) the second data qubit with the second routing qubit using a first CNOT operation and a second CNOT operation, respectively, wherein the first data qubit and second data qubit act as a first control and a second control for the first CNOT operation and the second CNOT operation, respectively;
storing, by the quantum computation system, the first routing qubit and second routing qubit;
receiving, by the quantum computation system and from a classical processor, a first classical bit;
determining (<NUM>), by the quantum computation system, whether the first classical bit represents an off state or an on state;
in response to determining that the first classical bit represents an on state:
applying (<NUM>), by the quantum computation system, a first Hadamard gate to the first routing qubit and applying a second Hadamard gate to the second routing qubit;
measuring, by the quantum computation system, the first routing qubit using a Z basis measurement to obtain a second classical bit
measuring (<NUM>), by the quantum computation system, the second routing qubit using a Z basis measurement to obtain a third classical bit; and
performing (<NUM>), by the quantum computation system, classically controlled fix up operations on the first data qubit and second data qubit using the second classical bit and the third classical bit, comprising:
applying a classically controlled swap operation to the second classical bit and third classical bit, wherein the first classical bit acts as a control for the classically controlled swap operation; and
applying a first classically controlled Z operation to the second data qubit, wherein the third classical bit acts as a control for the first classically controlled Z operation; and
applying a second classically controlled Z operation to the first data qubit, wherein the second classical bit acts as a control for the second classically controlled Z operation.