Patent Description:
To perform quantum computations, techniques are needed so that a universal set of quantum gates can be implemented fault-tolerantly. Most error correcting codes allow fault-tolerant implementation of gates from the Clifford group - a non-universal set of gates. Fully functional quantum computation can be attained by adding the Toffoli or π/<NUM> phase gate to the Clifford group. Performing these gates includes preparing high-fidelity magic states which are used to inject a gate into a main computation. These magic states are typically needed in vast quantities, and their preparation requires a significant portion of a device to operate as a dedicated magic state factory.

<NPL>) that the overhead for magic-state distillation can be reduced by merging distillation with the implementation of Toffoli gates. The disclosed routine distills <NUM> one-qubit magic states directly to a Toffoli state, which can be used without further magic to perform a Toffoli gate.

<NPL>) that lattice surgery reduces the storage overhead by over a factor of <NUM>, and the distillation overhead by nearly a factor of <NUM>, making it possible to run algorithms with <NUM><NUM> T gates using only <NUM>×<NUM><NUM> physical qubits capable of executing gates with error p ~ <NUM>-<NUM>.

This specification describes magic state factory methods and constructions for distilling CCZ states and T states.

The disclosed subject matter can be implemented in particular ways so as to realize one or more of the following advantages.

In fault-tolerant quantum computation based on the surface code - a likely component of future error corrected quantum computers due to the surface code's comparatively high threshold and planar connectivity requirements - the cost of a quantum algorithm can be well approximated by the number of non-Clifford operations included in the algorithm. This is because non-Clifford operations are performed via magic state distillation, and the cost of state distillation is high. For example, the spacetime volume (qubit-seconds) of some existing T state factories is two orders of magnitude larger than the volume of a CNOT operation between adjacent qubits. The non-Clifford operation count will likely be particularly significant for the earliest error corrected quantum computers, which may not have enough space to distill magic states in parallel.

The presently described method and factory construction for producing CCZ states (herein referred to as a CCZ state factory) has a footprint of 12d × 6d, where d represents surface code distance, produces one CCZ state every <NUM>. 5d surface code cycles, and can produce <NUM><NUM> states before an error occurs (on average, assuming a physical gate error rate of <NUM>-<NUM>). Compared to using known T state factories, e.g., 12d×8d×<NUM>. 5d T state factories, the presently described CCZ state factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, such as some quantum chemistry algorithms. Furthermore, reducing the footprint of the method and factory construction for producing CCZ states can make them more suited for implementation on early quantum computers with limited space.

The presently described method and factory construction for producing T states (herein referred to as a T state factory) uses a CCZ state, e.g., as output by the presently described CCZ state factory, and a catalyst T state to exactly transform a single CCZ state into two T states. The T state factory has a footprint that is <NUM>% smaller than other known T factories, and outputs T states twice as quickly. The presently described CCZ state factory and T state factory can be combined to produce an efficient T state factory.

A generalization of a catalysis circuit to arbitrary phase angles is also described. The generalization can be used to produce <MAT> states at an order of magnitude more efficiently than previous techniques - for example, two <MAT> states can be produced using <NUM> T states.

This specification describes new magic state factory constructions and state distillation techniques for producing T states <MAT> and CCZ states (defined as the output of a CCZ gate applied to an input state | + +<NUM>〉) with improved footprint and spacetime volume.

<FIG> shows an example quantum computing system <NUM>. The system <NUM> is an example of a system implemented as quantum and/or classical computer programs on one or more quantum computing devices and/or 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 one or more classical processors may be included in quantum computing device <NUM>.

The quantum computing device <NUM> includes components for performing quantum computation. For example, the quantum computing device <NUM> includes at least 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., a register of qubits <NUM>. The qubits 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. 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., the single qubit gates, two qubit gates, and three qubit gates described in this specification, 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.

The quantum circuitry <NUM> can further include one or more magic state factories, e.g., CCZ state factory <NUM> and T state factory <NUM>. The CCZ state factory <NUM> generates CCZ states that may be consumed by the quantum circuitry <NUM> when performing quantum computations. For example, the CCZ state factory <NUM> may be a <MAT> factory that generates CCZ states according to the techniques described below with reference to <FIG>. (In this specification factories are referred to using the notation <MAT>. The left hand side |In〉 represents the state input into the factory, the right hand side |Out〉 represents the state output from the factory, and the function f(ε) above the arrow indicates an amount of error suppression up to leading terms, i.e. f(ε)is shorthand for the true suppression f(ε) + O(εf(ε))). For example, the T state distillation based on the known <NUM>-qubit Reed-Muller code is referred to as the <MAT> factory.

The T state factory <NUM> generates T states that may be consumed by the quantum circuitry <NUM> when performing quantum computations. For example, the T state factory <NUM> may be a |T〉-catalyzed |CCZ〉 → <NUM>|T〉 factory that generates T states according to the techniques described below with reference to <FIG>.

The CCZ state factory <NUM> and T state factory <NUM> can also be combined to produce a <MAT> factory that generates T states according to the techniques described below with reference to <FIG>.

Operating the hardware: Example methods performed by the <MAT> factory.

<FIG> is a flowchart of an example process for distilling a CCZ 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>. In addition, for convenience the operations described below are described with reference to an ordered list of steps, however the order of some of the operations can change and different groups of operations can be performed in parallel.

The system prepares a register of qubits in a zero state (step <NUM>). In other words, the system prepares each qubit in the register of qubits in a zero state. The register of qubits includes multiple target qubits, multiple ancilla qubits, and multiple stabilizer qubits. The target qubits are qubits that will encode the distilled CCZ state. The multiple ancilla qubits and stabilizer qubits are auxiliary qubits (in this specification the term "stabilizer qubits" is used to distinguish between different groups of qubits in the register of qubits, and describes a second multiple of ancilla qubits). An example register of qubits is illustrated and described below with reference to <FIG>.

For each stabilizer qubit, the system performs an X gate on i) multiple ancilla qubits, or ii) multiple ancilla qubits and one of the target qubits, using the stabilizer qubit as a control (step <NUM>). In some implementations the stabilizer qubit can be used as an X axis control by applying a Hadamard gate to the stabilizer qubit before and after the stabilizer qubit is used as a control.

The system measures the stabilizer qubits to determine respective stabilizer qubit states (step <NUM>). For example, the system can perform respective Pauli product measurements on the stabilizer qubits to determine respective stabilizer qubit states. In some implementations, whenever an X axis control directly precedes a measurement operation, the measurement operation may be a Pauli product measurement.

The system performs a Z<NUM>/<NUM> quantum gate followed by a Hadamard quantum gate on each of the ancilla qubits (step <NUM>).

The system measures each of the ancilla qubits to determine respective ancilla qubit states (step <NUM>).

The system performs, conditioned on each determined ancilla qubit state, i) a NOT operation on a selected stabilizer qubit, or ii) a NOT operation on the selected stabilizer qubit and a Z gate on one or more respective target qubits (step <NUM>).

The system performs, on each target qubit and conditioned on a determined state of a respective stabilizer qubit, a Z gate on the target qubit (step <NUM>).

The system performs an X gate on each of the target qubits to obtain the CCZ state (step <NUM>). The system can provide the obtained CCZ state for use in subsequent computations, e.g., as input to example process <NUM>.

In some implementations the system may further perform a classical post selection operation implemented by classical control software to determine whether to keep or discard the obtained CCZ state. For example, the system may determine whether an error occurred or not using a parity computation performed on the selected stabilizer qubit. If an error occurred, the system may discard the obtained CCZ state. If an error did not occur, the system may keep the obtained CCZ state, e.g., provide the CCZ state for use in subsequent computations as described above.

In some implementations the system may perform the example process <NUM> twice to distill a first CCZ state and a second CCZ state. In these implementations, the system can perform the two process concurrently and partially overlap executions of operations corresponding to the distillation of the first CCZ state and the distillation of the second CCZ state (which may require some reordering of the steps of the example process <NUM> prior to overlapping execution of the operations), as illustrated below with reference to <FIG>.

<FIG> is a diagram of an example quantum circuit <NUM> for distilling a CCZ state. The example quantum circuit <NUM> operates on a register of qubits, represented in <FIG> by the horizontal lines. The register of qubits includes three target qubits labelled <NUM>, <NUM>, and <NUM>. The register of qubits further includes eight ancilla qubits labelled a-h and four stabilizer qubits labelled X<NUM>Xabcd, Xabcdefgh, X<NUM>Xaceg, X<NUM>Xabef. Each qubit in the register of qubits is initialized in a zero state <NUM>, as described above with reference to step <NUM> of <FIG>.

The example quantum circuit <NUM> includes a first set of operations <NUM>. The first set of operations <NUM> corresponds to steps <NUM> and <NUM> of <FIG>. Operations in the first set of operations <NUM> include multiple X gates, e.g., X gate <NUM>. Each X gate in the first set of operations <NUM> is applied to an ancilla qubit or a target qubit and is controlled by a respective stabilizer qubit. In example quantum circuit <NUM>, the controls are X axis controls, e.g., X axis control <NUM>, which represent application of a Hadamard gate to the stabilizer qubit before and after the stabilizer qubit is used as a control.

For example, the X gates can include a first X gate applied to the first target qubit <NUM>, a second X gate applied to the first ancilla qubit a, a third X gate applied to the second ancilla qubit b, a fourth X gate applied to the third ancilla qubit c, and a fifth X gate applied to the fourth ancilla qubit d. Each of the first, second, third, fourth and fifth X gates uses the first stabilizer qubit X<NUM>Xabcd as a control. The X gates further include a sixth X gate applied to the first ancilla qubit a, a seventh X gate applied to the second ancilla qubit b, an eighth X gate applied to the third ancilla qubit c, a ninth X gate applied to the fourth ancilla qubit d, a tenth X gate applied to the fifth ancilla qubit e, an eleventh X gate applied to the sixth ancilla qubit f, a twelfth X gate applied to the seventh ancilla qubit g, and a thirteenth X gate applied to the eighth ancilla qubit h. Each of the sixth-thirteenth X gates use the second stabilizer qubit Xabcdefgh as a control. The X gates further include a fourteenth X gate applied to the third target qubit <NUM>, a fifteenth X gate applied to the first ancilla qubit a, a sixteenth X gate applied to the third ancilla qubit c, a seventeenth X gate applied to the fifth ancilla qubit e, and a eighteenth X gate applied to the seventh ancilla qubit g. Each of the fourteenth-eighteenth X gates use the third stabilizer qubit X<NUM>Xaceg as a control. The X gates further include a nineteenth X gate applied to the second target qubit <NUM>, a twentieth X gate applied to the first ancilla qubit a, a twenty-first X gate applied to the second ancilla qubit b, a twenty-second X gate applied to the fifth ancilla qubit e, and a twenty third X gate applied to the sixth ancilla qubit f. Each of the nineteenth-twenty-third X gates use the fourth stabilizer qubit X<NUM>Xabet as a control.

The first set of operations <NUM> further includes four measurement operations, e.g., measurement operation <NUM>. Each measurement operation is applied to a respective stabilizer qubit. In some implementations the measurement operations may be Pauli product measurements.

The example quantum circuit <NUM> further includes multiple Z<NUM>/<NUM> gates (T gates), e.g., Z<NUM>/<NUM> gate <NUM> and multiple Hadamard gates, e.g., Hadamard gate <NUM>. The multiple Z<NUM>/<NUM> gates and multiple Hadamard gates are applied to the ancilla qubits a-h. For example, each ancilla qubit a-h is operated on by one Z<NUM>/<NUM> gate followed by a Hadamard gate. The example quantum circuit <NUM> further includes multiple measurement operations that are applied to the ancilla qubits a-h after the Z<NUM>/<NUM> gates and Hadamard gates are applied.

The example quantum circuit <NUM> further includes a second set of operations <NUM>. The second set of operations <NUM> corresponds to step <NUM> of <FIG>. Operations in the second set of operations <NUM> include multiple Z gates, e.g., Z gate <NUM>. Each Z gate in the second set of operations <NUM> is applied to a target qubit conditioned on a measured state of a respective ancilla qubit, as indicated by the solid circles, e.g., circle <NUM>. For example, the Z gates can include a first Z gate applied to the first target qubit <NUM>, a second Z gate applied to the second target qubit <NUM>, and a third Z gate applied to the third target qubit <NUM>. Each of the first, second and third Z gates are performed conditioned on the measured state of the first ancilla qubit a, e.g., are performed if the measured state of the first ancilla qubit was a <NUM>. The Z gates can further include a fourth Z gate applied to the first target qubit <NUM> and a fifth Z gate applied to the second target qubit <NUM>. The fourth and fifth Z gates are performed conditioned on the measured state of the second ancilla qubit b. The Z gates can further include a sixth Z gate applied to the first target qubit <NUM> and a seventh Z gate applied to the third target qubit <NUM>. The sixth and seventh Z gates are performed conditioned on the measured state of the third ancilla qubit c. The Z gates further include an eighth Z gate applied to the first target qubit <NUM>. The eighth Z gate is performed conditioned on the measured state of the fourth ancilla qubit d. The Z gates further include a ninth Z gate applied to the second target qubit <NUM> and a tenth Z gate applied to the third target qubit <NUM>. The ninth and tenth Z gates are performed conditioned on the measured state of the fifth ancilla qubit e. The Z gates further include an eleventh Z gate applied to the second target qubit <NUM>. The eleventh Z gate is performed conditioned on the measured state of the sixth ancilla qubit f. The Z gates further include a twelfth Z gate applied to the third target qubit <NUM>. The twelfth Z gate is performed conditioned on the measured state of the seventh ancilla qubit g.

The second set of operations <NUM> further includes multiple NOT operations, e.g., NOT operation <NUM>. Each NOT operation is performed on a same stabilizer qubit - the second stabilizer qubit Xabcdefgh - and is conditioned on a measured state of a respective ancilla qubit. The total number of NOT operations is equal to the total number of ancilla qubits. For example, the NOT operations can include a first NOT operation that is performed on the second stabilizer qubit Xabcdefgh conditioned on the measured state of the first ancilla qubit a, second NOT operation that is performed on the second stabilizer qubit Xabcdefgh conditioned on the measured state of the second ancilla qubit b, a third NOT operation that is performed on the stabilizer qubit Xabcdefgh conditioned on the measured state of the third ancilla qubit c, etc..

The example quantum circuit <NUM> further includes three Z gates 322a-c that are respectively applied to each of the target qubits <NUM>-<NUM>. Each of the three Z gates 322a-c are performed conditioned on a measured state of a respective stabilizer qubit. For example, Z gate 322a is performed on the first target qubit <NUM> conditioned on a measured state of the first stabilizer qubit X<NUM>Xabcd. Z gate 322b is performed on the third target qubit <NUM> conditioned on a measured state of the third stabilizer qubit X<NUM>Xaceg. Z gate 322c is performed on the second target qubit <NUM> conditioned on a measured state of the fourth stabilizer qubit X<NUM>Xabef.

The example quantum circuit <NUM> further includes three X gates, e.g., X gate <NUM>, that are each applied to a respective target qubit <NUM>-<NUM>. The three target qubits <NUM>-<NUM> are then output as a |CCZ〉 state <NUM>.

The example quantum circuit <NUM> further includes a post-selection operation <NUM>. The post-selection operation <NUM> is performed by classical control software and is implemented to determine whether an error was detected during the state distillation process. If the post-selection operation indicates the presence of an error and therefore "fails," the output CCZ state <NUM> can be discarded.

The operations included in the example quantum circuit <NUM> can be translated into lattice surgery operations. <FIG> shows example time slices <NUM> of lattice surgery activity during production of a CCZ state using example quantum circuit <NUM> of <FIG>. The example time slices <NUM> correspond to one of many possible translations of example quantum circuit <NUM> into lattice surgery operations, and are therefore one of many possible time slices (with matching qubit labels and operation labels). In <FIG>, the squares correspond to different qubits (identified by the label inside the squares) and the shaded rectangles correspond to X stabilizer measurements between sets of qubits. Each arrow labelled T corresponds to a noisy T state entering the system.

Time slice 400a corresponds to the first column of X gates (applied to the first target qubit, first ancilla qubit, second ancilla qubit, third ancilla qubit and fourth ancilla qubit, controlled by the first stabilizer qubit) included in example quantum circuit <NUM> and the measurement of the first stabilizer qubit.

Time slice 400b corresponds to the second column of X gates (applied to each ancilla qubit a-h and controlled by the second stabilizer qubit) included in the example quantum circuit <NUM> and the measurement of the second stabilizer qubit. In time slice 400b, no operations are performed on the first target qubit <NUM>.

Time slice 400c corresponds to the third column of X gates (applied to the ancilla qubits a, c, e, g controlled by the third stabilizer qubit) included in the example quantum circuit <NUM> and the measurement of the third stabilizer qubit. In time slice 400c, no operations are performed on the ancilla qubits b, d, f, h and target qubit <NUM>.

Time slice 400d corresponds to the fourth column of X gates (applied to the second target qubit <NUM> and ancilla qubits a, b, e, f controlled by the fourth stabilizer qubit) included in the example quantum circuit <NUM> and the measurement of the fourth stabilizer qubit. Target qubits <NUM> and <NUM> are moved, with no other operation performed on them. Time slice 400d also corresponds to the T gates (Z^<NUM>/<NUM> gates), Hadamard gates and measurement operations applied to ancilla qubits c, g, d, and h at steps <NUM> and <NUM> of <FIG>.

Time slice 400e corresponds to the remaining T gates (Z^<NUM>/<NUM> gates), Hadamard gates and measurement operations applied to ancilla qubits a, b, e, and f at steps <NUM> and <NUM> of <FIG>. Time slice 400e also corresponds to operations performed on target qubits <NUM> and <NUM> during the second set of operations <NUM> of <FIG>, e.g., the third, fourth, seventh and eighth columns in the second set of operations <NUM>.

Time slice 400f corresponds to the remaining operations included in the the second set of operations <NUM> of <FIG>, e.g., the first, second, fifth and sixth columns in the second set of operations <NUM>.

Time slice <NUM> corresponds to the remaining operations in the example quantum circuit <NUM>, e.g., the last four columns of operations in example quantum circuit <NUM>.

Time slice <NUM> corresponds to outputting the CCZ state after verification.

<FIG> shows example time slices of lattice surgery activity during production of |CCZ〉 states using the <MAT> factory and corresponds to two interleaved translations of the example quantum circuit <NUM> to increase utilization.

Time slice <NUM> corresponds to time slices 400f and 400a of <FIG>. That is, a first process for distilling a CCZ state is at time slice 400f when the second process for distilling a CCZ state begins and is at time slice 400a. Time slice <NUM> corresponds to times slices <NUM> and 400b of <FIG>. Time slice <NUM> corresponds to time slices <NUM> and 400c of <FIG>. The first process is then complete. Time slice <NUM> corresponds to time slice 400d of <FIG> and time slice <NUM> corresponds to time slice 400e of <FIG>. Time slice <NUM> corresponds to a beginning of a third process which is at time slice 400a and time slice 400f for the second process. Time slice <NUM> corresponds to time slice 400b and <NUM> of <FIG>. Time slice <NUM> corresponds to 400c and <NUM> of <FIG>. The second is then complete. Time slices <NUM> and <NUM> correspond to 400d and 400e. The loop can then continue to complete the third process and begin a fourth process.

The presently described process for distilling CCZ states has a naive depth of <NUM> (stabilizer measurements) + <NUM> (T state injections) + <NUM> (X or Y basis measurement, depending on T injection measurements) + <NUM> (detect errors) = <NUM>. However, the process can be performed in parallel example where executions of operations can be partially overlapped, resulting in an effective depth of <NUM>.

The error rate of CCZ states produced using the presently described process can be computed as follows: It can be reasonably assumed that the physical gate error rate is <NUM>-<NUM>, and that post-selected state injection techniques can be used to create T<NUM> states with approximately this probability of error. The known <MAT> factory based on the Reed-Muller code can be applied to produce T<NUM> states with chance of error approximately equal to <NUM>(<NUM>-<NUM>)<NUM> ≈ <NUM>-<NUM>. The presently described <MAT>|CCZ〉 factory can then be then applied, resulting in a final error rate of <NUM>(<NUM>-<NUM>)<NUM> ≈ <NUM>-<NUM>. An error rate of <NUM>-<NUM> is sufficient for running classically intractable algorithms. For example, if it is conservatively assumed that Shor's algorithm performs 2n<NUM> Toffoli gates, then the presently described <MAT> factory can support factoring numbers with ten thousand bits with a failure rate below <NUM>%.

<FIG> is a flowchart of a first example process <NUM> for transforming a CCZ state into three output T states. 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>. In addition, for convenience the operations described below are described with reference to an ordered list of steps, however the order of some of the operations can change and different groups of operations can be performed in parallel.

The system obtains a first target qubit, a second target qubit and a third target qubit in a CCZ state (step <NUM>). In some implementations the CCZ state may be a CCZ state output using example process <NUM> and example quantum circuit <NUM>.

The system performs a X-<NUM>/<NUM> gate on the third target qubit (step <NUM>). The system performs an X gate on the first target qubit and the second target qubit using the third target qubit as a control (step <NUM>). The system performs a Z gate on the first target qubit and the second target qubit using the third qubit as a X axis control (step <NUM>). The system performs a Z-<NUM>/<NUM> gate on the third target qubit (step <NUM>). The system performs a Z gate on the first target qubit and the second target qubit using the third qubit as a X axis control to obtain the three T states (step <NUM>).

Because |T〉 states can be used to perform T gates, in some implementations one of the obtained three T states can be used as a catalyst for a subsequent transformation of a CCZ state into three T states. For example, the T gate used to transform the |CCZ〉 into three |T) states can be powered by a |T〉 state output from a previous iteration of the circuit <NUM>. If a |T〉 state output from iteration k is fed into iteration k + <NUM>, then effectively a circuit that takes a |CCZ〉 state and outputs two |T〉 states is obtained. Under this interpretation of the circuit, the third |T〉 state is an ancillary state that is necessary for the transformation to be possible, but is not consumed by the transformation. Therefore, the third |T〉 can be referred to as a catalyst. The circuit <NUM> as a whole is referred is therefore referred to as a |T〉-catalyzed <NUM>|T〉 -> <NUM>|T〉 factory, or "C2T factory" for short.

Although the catalyst |T〉 state is not consumed by the C2T factory, it can accumulate noise from the incoming |CCZ〉 states. If a catalyst |T〉 has cycled through n iterations of the C2T factory, and there is a probability ε of each |CCZ〉 containing an error, then there is an Θ(Nε)chance that the catalyst has been tainted and is causing the factory to produce bad outputs. However, because every error in the catalyst ultimately traces back to an error in a |CCZ〉 state, the chance of there being any error grows like Θ(Nε), instead of Θ(Nε<NUM> )as would be expected from a naive calculation assuming uncorrelated errors. Distillation protocols usually require inputs with uncorrelated errors, so in some implementations it may be beneficial to include the C2T factory as a last step in a distillation chain. This style of usage means that the correlation between errors is a benefit instead of a cost.

<FIG> is a diagram of a first example quantum circuit <NUM> for generating three T states using a CCZ state. The example quantum circuit <NUM> operates on a register of qubits <NUM> that includes three qubits prepared in a CCZ state. The example quantum circuit <NUM> includes an X-<NUM>/<NUM> gate <NUM> that is applied to the third qubit in the register of qubits <NUM>. The example quantum circuit <NUM> also includes a first X gate <NUM> that is applied to the first qubit in the register of qubits <NUM> and a second X gate <NUM> that is applied to the second qubit in the register of qubits <NUM>. X gates <NUM> and <NUM> are controlled by the third qubit. The example quantum circuit <NUM> further includes a first Z gate <NUM> applied to the first qubit and a second Z gate <NUM> applied to the second qubit. Application of the first Z gate <NUM> and second Z gate <NUM> are (X axis) controlled by the third qubit. The example quantum circuit <NUM> further includes a Z-<NUM>/<NUM> gate <NUM> applied to the third qubit. The example quantum circuit <NUM> further includes a third Z gate <NUM> applied to the first qubit and a fourth Z gate <NUM> applied to the second qubit. Application of the third Z gate <NUM> and fourth Z gate <NUM> are (X axis) controlled by the third qubit. The example quantum circuit <NUM> outputs the first qubit, second qubit and third qubit in T states 720a-c.

Application of the Z-<NUM>/<NUM> gate <NUM> requires a T state, therefore, in some cases a T state output by a first implementation of the example quantum circuit <NUM> may be provided as a catalytic input to a second implementation of the example quantum circuit <NUM>, as indicated by arrow <NUM>.

The example quantum circuit <NUM> is compact but not in an ideal form for embedding into lattice surgery. <FIG> and <FIG> show an equivalent circuit that can be translated into lattice surgery. The result of the translation is shown in <FIG>, which shows example time slices of lattice surgery operations occurring as the factory operates.

<FIG> is a flow diagram of a second example process <NUM> for generating three T states using a CCZ 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>. In addition, for convenience the operations described below are described with reference to an ordered list of steps, however the order of some of the operations can change and different groups of operations can be performed in parallel.

The system obtains a qubit register (step <NUM>). The qubit register includes a first target qubit, second target qubit and third target qubit prepared in a CCZ state. For example, the CCZ state may be a CCZ distilled using example process <NUM> of <FIG>. The qubit register further includes a first ancilla qubit prepared in a T state. The qubit register further includes multiple additional ancilla qubits each prepared in a zero state, e.g., a second, third and fourth ancilla qubit each prepared in a zero state, The qubit register further includes multiple stabilizer qubits prepared in a zero state, e.g., a first, second, third, fourth and fifth stabilizer qubit each prepared in a zero state. An example qubit register is illustrated and described below with reference to <FIG>.

The system performs an X gate on a target qubit and an additional ancilla qubit using a first stabilizer qubit as a control (step <NUM>). For example, continuing the example above, the system may perform an X gate on the third target qubit using the first stabilizer qubit as a control and perform an X gate on the third ancilla qubit using the first stabilizer qubit as a control. In this description, when a stabilizer qubit is used as a control the control may be an X axis control that includes application of a Hadamard gate to the stabilizer qubit before and after the stabilizer qubit is used as a control.

The system then measures the first stabilizer qubit to determine a state of the first stabilizer qubit.

The system performs an X gate on multiple target qubits and an additional ancilla qubit using a second stabilizer qubit as a control (step <NUM>). The system then measures the second stabilizer qubit to determine a state of the second stabilizer qubit. For example, continuing the example above, the system may perform an X gate on: the first target qubit using the second stabilizer qubit as a control, the second target qubit using the second stabilizer qubit as a control, and the fourth ancilla qubit using the second stabilizer qubit as a control. The system then measures the second stabilizer qubit to determine a state of the second stabilizer qubit.

The system performs an X<NUM>/<NUM> gate on an additional ancilla qubit (step <NUM>). For example, the system may perform the X<NUM>/<NUM> gate on the third ancilla qubit;.

The system performs a Z gate on each of multiple target qubits and on the first ancilla qubit using a third stabilizer qubit as a control for each Z gate (step <NUM>). For example, continuing the example above, the system may perform a Z gate on the first, second and third target qubits and the first ancilla qubit using the third stabilizer qubit as a control in each case.

The system performs a Hadamard gate on the first ancilla qubit and measures the first ancilla qubit, an additional ancilla qubit, and a third stabilizer qubit to determine respective qubit states (step <NUM>). For example, after performing the Hadamard gate the system may measure the first ancilla qubit, third ancilla qubit and third stabilizer qubit to determine respective states if the first ancilla qubit, third ancilla qubit and third stabilizer qubit.

The system performs an X<NUM>/<NUM> gate on an additional ancilla qubit (step <NUM>). For example, the system may perform an X<NUM>/<NUM> gate on the second ancilla qubit.

The system performs a Z gate on a target qubit and an additional ancilla qubit using a fourth stabilizer qubit as a control for each Z gate (step <NUM>). For example, the system may perform a Z gate on the third target qubit using the fourth stabilizer qubit as a control and perform a Z gate on the fourth ancilla qubit using the fourth stabilizer qubit as a control.

The system performs a Hadamard gate on an additional ancilla qubit and measures the additional ancilla qubit and the fourth stabilizer qubit to determine respective qubit states (step <NUM>). For example, the system may perform a Hadamard gate on the fourth ancilla qubit and measure the fourth ancilla qubit and the fourth stabilizer qubit.

The system performs one NOT operation on a stabilizer qubit using an additional ancilla qubit as a control and performs two NOT operations on the additional ancilla qubit and the stabilizer qubit using a different stabilizer qubit as a control (step <NUM>). For example, the system may perform a NOT operation on the third stabilizer qubit using the third ancilla qubit as a control, perform a NOT operation on the third stabilizer qubit using the first stabilizer qubit as a control, and perform a NOT operation on the third ancilla qubit using the first stabilizer qubit as a control.

The system performs a respective Z gate on multiple target qubits and an additional ancilla qubit using two stabilizer qubits as a control (step <NUM>). For example, the system may perform a Z gate on each of the three target qubits and the second ancilla qubit using the third and fifth stabilizer qubits as a control.

The system performs a Hadamard gate on an additional ancilla qubit (step <NUM>). For example, the system may perform a Hadamard operation on the second ancilla qubit. The system then measures the additional ancilla qubit, e.g., second ancilla qubit, and the fifth stabilizer qubit to determine respective qubit states.

The system performs multiple classically controlled Pauli operators on the three target qubits conditioned on the determined states of the ancilla qubits (step <NUM>). Performing the multiple classically controlled Pauli operators on the three target qubits conditioned on the determined states of the ancilla qubits can reduce decoherence.

Performing multiple classically controlled Pauli operators on the three target qubits conditioned on the determined states of the ancilla qubits includes performing multiple Z gates on one or more of the target qubits using at least one of i) one or more stabilizer qubits and ii) one or more ancilla qubits as a control. For example, the system can perform a sequence of operations from a set of operations that includes: application of a Z gate on the first, second and third target qubits using the third and fifth stabilizer qubits as a control, application of a Z gate on the first, second and third target qubits using the third ancilla qubit and third stabilizer qubits as a control, application of a Z gate on the first, second and third target qubits using the second ancilla and third stabilizer qubits as a control, application of a Z gate on the third target qubit using the second stabilizer qubit as a control, application of a Z gate on the third target qubit using the fourth ancilla qubit as a control, application of a Z gate on the first, second and third target qubits using the first ancilla qubit as a control. The system can then perform X gates on one or more of the target qubits using a stabilizer qubit or ancilla qubit as a control, e.g., an X gate on the first and second target qubit using the fourth stabilizer qubit as a control, and an X gate on the first, second and third target qubit using the third ancilla qubit as a control, and perform an X gate on a target qubit, e.g., the third target qubit.

The system can provide the three target states, which after step <NUM> are each T states, for use in subsequent computations. For example, in some implementations the system may provide one or more of the T states as input to subsequent implementations of example process <NUM>. The remaining T states may then be used in some subsequent computations being performed by the quantum computing device. In some cases the system may only provide output T states for use in subsequent computations or as input to a subsequent implementation of example process <NUM> if the output T states have not accumulated an amount of error higher than a predetermined acceptable threshold. If an output T state has accumulated an amount of error higher than the predetermined acceptable threshold the system may discard the state and/or provide a different T state to the subsequent computation/implementation, e.g., a stored T state.

<FIG> is a diagram of a second example quantum circuit <NUM> for generating three T states using a CCZ state. The example quantum circuit <NUM> operates on a register of qubits <NUM>, where each qubit is represented by a respective horizontal lines. The register of qubits <NUM> includes three target qubits labelled <NUM>, <NUM>, and <NUM>. The target qubits <NUM>, <NUM>, <NUM> are prepared in a CCZ state. The register of qubits <NUM> further includes a first ancilla qubit labelled T prepared in a T state. The register of qubits <NUM> further includes a second, third and fourth ancilla qubit labelled S, B, and A, respectively. The second, third and fourth ancilla qubits are each prepared in a zero state. The register of qubits <NUM> further includes five stabilizer qubits labelled X<NUM>XB, X<NUM>XA, Z<NUM>ZT, Z<NUM>ZA, Z<NUM>ZS. The five stabilizer qubits are each prepared in a zero state.

The example quantum circuit <NUM> includes multiple product-of-Paulis measurements <NUM>-<NUM>. The first product-of-Paulis measurement <NUM> corresponds to step <NUM> of <FIG>. The first product-of-Paulis measurement <NUM> includes a first X gate, e.g., X gate <NUM>, applied to the third target qubit and a second X gate applied to the third ancilla qubit B. The first stabilizer qubit X<NUM>XB acts as an X axis control for both X gates included in the first product-of-Paulis measurement <NUM>. The first product-of-Paulis measurement <NUM> further includes a measurement operation applied to the first stabilizer qubit X<NUM>XB.

The second product-of-Paulis measurement <NUM> corresponds to step <NUM> of <FIG>. The second product-of-Paulis measurement <NUM> includes a first X gate applied to the first target qubit, a second X gate applied to the second target qubit, and a third X gate applied to the fourth ancilla qubit A. The second stabilizer qubit X<NUM>XA acts as an X axis control for each X gate included in the second product-of-Paulis measurement <NUM>. The second product-of-Paulis measurement <NUM> further includes a measurement operation applied to the second stabilizer qubit X<NUM>XA.

After the second product-of-Paulis measurement <NUM>, an X<NUM>/<NUM> gate <NUM> is applied to the third ancilla qubit B. The X<NUM>/<NUM> gate <NUM> corresponds to step <NUM> of <FIG>.

The third product-of-Paulis measurement <NUM> corresponds to steps <NUM> and <NUM> of <FIG>. The third product-of-Paulis measurement <NUM> includes a first Z gate, e.g., Z gate <NUM>, applied to the first target qubit, a second Z gate applied to the second target qubit, a third Z gate applied to the third target qubit, and a fourth Z gate applied to the first ancilla qubit. The third stabilizer qubit Z<NUM>ZT acts as an X axis control for each Z gate included in the third product-of-Paulis measurement <NUM>. The third product-of-Paulis measurement <NUM> further includes a Hadamard gate <NUM> and measurement operation that are applied to the first ancilla qubit T. The third product-of-Paulis measurement <NUM> further includes a measurement operation applied to the third ancilla qubit B and a measurement operation applied to the third stabilizer qubit Z<NUM>ZT.

After the third product-of-Paulis measurement <NUM>, an X<NUM>/<NUM> gate <NUM> is applied to the second ancilla qubit S. The X<NUM>/<NUM> gate <NUM> corresponds to step <NUM> of <FIG>.

The fourth product-of-Paulis measurement <NUM> corresponds to steps <NUM> and <NUM> of <FIG>. The fourth product-of-Paulis measurement <NUM> includes a first Z gate applied to the third target qubit <NUM> and a second Z gate applied to the fourth ancilla qubit. The fourth stabilizer qubit Z<NUM>ZA acts as an X axis control for each Z gate included in the fourth product-of-Paulis measurement <NUM>. The fourth product-of-Paulis measurement <NUM> further includes a Hadamard gate and measurement operation that are applied to the fourth ancilla qubit A. The fourth product-of-Paulis measurement <NUM> further includes a measurement operation applied to the fourth stabilizer qubit Z<NUM>ZA.

After the fourth product-of-Paulis measurement <NUM>, a first NOT operation, e.g., NOT operation <NUM>, is performed on the third stabilizer qubit Z<NUM>ZT using the third ancilla qubit B as a control. A second NOT operation is performed on the third stabilizer qubit Z<NUM>ZT using the first stabilizer qubit X<NUM>XB as a control, and a third NOT operation is performed on the third ancilla qubit B using the first stabilizer qubit X<NUM>XB as a control. Application of the first and second NOT operations corresponds to step <NUM> of <FIG>.

The fifth product-of-Paulis measurement <NUM> corresponds to steps <NUM> and <NUM> of <FIG>. The fifth product-of-Paulis measurement <NUM> includes a first Z gate applied to the first target qubit <NUM>, a second Z gate applied to the second target qubit <NUM>, a third Z gate applied to the third target qubit <NUM>, and a fourth Z gate applied to the second ancilla qubit S. The third stabilizer qubit Z<NUM>ZT and fifth stabilizer qubit Z<NUM>ZS acts as controls for the Z gates included in the fifth product-of-Paulis measurement <NUM>. The fifth product-of-Paulis measurement <NUM> also includes a Hadamard gate applied to the second ancilla qubit S, a measurement operation applied to the second ancilla qubit S, and a measurement operation applied to the fifth stabilizer qubit Z<NUM>ZS.

The example quantum circuit <NUM> further includes a collection <NUM> of multiple classically controlled Pauli operators. The collection <NUM> of multiple classically controlled Pauli operators correspond to step <NUM> of <FIG>.

The multiple classically controlled Pauli operators include application of a Z gate on the first, second and third target qubits <NUM>-<NUM> using the third Z<NUM>ZT and fifth Z<NUM>ZS stabilizer qubits as a control, application of a Z gate on the first, second and third target qubits <NUM>-<NUM> using the third ancilla qubit B and third stabilizer qubit Z<NUM>ZT as a control, application of a Z gate on the first, second and third target qubits <NUM>-<NUM> using the second ancilla qubit S and third stabilizer qubit Z<NUM>ZT as a control, application of a Z gate on the third target qubit <NUM> using the second stabilizer qubit X<NUM>XA as a control, application of a Z gate on the third target qubit <NUM> using the fourth ancilla qubit A as a control, and application of a Z gate on the first, second and third target qubits <NUM>-<NUM> using the first ancilla qubit T as a control.

The multiple classically controlled Pauli operators further include application of an X gate to the first and second target qubit <NUM>,<NUM> using the fourth stabilizer qubit Z<NUM>ZA as a control, application of an X gate on the first, second and third target qubits <NUM>-<NUM> using the third ancilla qubit B as a control, and application of an X gate on the third target qubit <NUM>. The three target states <NUM>, <NUM>, <NUM> are then each output in a respective T state <NUM>.

As described above, the operations included in the example quantum circuit <NUM> can be translated into lattice surgery operations. <FIG> shows example time slices <NUM> of lattice surgery activity during production of three T states using example quantum circuit <NUM> of <FIG>. Each time slice can be matched to a step from <FIG>, and the qubit labels used in <FIG> correspond to the qubit labels used <FIG>. Black and shaded bars correspond to stabilizer measurements. Ancilla qubits are shown in filled boxes. The code distance of the ancilla qubits is doubled when single-qubit Clifford operations are being applied, to ensure there is sufficient suppression of errors. The CCZ box will be used by the CCZ factory producing CCZ states to be transformed.

Time slice <NUM> corresponds to the first product-of-Paulis measurement <NUM> of <FIG>. Time slice <NUM> corresponds to the second product-of-Paulis measurement <NUM> of <FIG>. Time slice <NUM> corresponds to the third product-of-Paulis measurement <NUM> of <FIG>. Time slice <NUM> corresponds to the fourth product-of-Paulis measurement <NUM> of <FIG>. Time slice <NUM> corresponds to the fifth product-of-Paulis measurement <NUM> of <FIG>. Time slice <NUM> corresponds to the collection <NUM> of multiple classically controlled Pauli operators in <FIG>.

The catalysis technique used in the C2T factory described herein can be generalized to phasing angles other than the T gate's <NUM>°. <FIG>, shows a generalization of <FIG> to arbitrary angles θ. <FIG> is a diagram of an example generalized phase catalysis quantum circuit <NUM> for performing a target phase operation Zθ on a first and second qubit using a third qubit prepared in a phased plus state Zθ|+〉. In example quantum circuit <NUM>, the first qubit, second qubit and third qubit are represented by horizontal lines 1102a-c. Qubits 1102a and 1102b represent the first and second qubit on which the target phase operation Zθ is to be performed. Qubits 1102a and 1102b are provided to the example quantum circuit <NUM> in input states |ψ<NUM>〉 and |ψ<NUM>〉, respectively. The input states |ψ<NUM>〉 and |ψ<NUM>〉 can be initial states of either of the qubits 1102a or 1102b, i.e., qubits 1102a or 1102b may have been prepared in arbitrary initial states, or can be states representing an output of a previous computation. Qubit 1102c represents the third qubit that is prepared in a phased plus state Zθ|+〉. The qubit 1102c can be prepared in the phased plus state using any one of existing techniques.

The example quantum circuit <NUM> includes a sequence of gates that are applied to the qubits 1102a-1102c. The sequence of gates includes a first NOT operation <NUM> that is applied to the third qubit <NUM>102c. A first collection of operations are then applied to the qubits 1102a-1102c to compute a controlled adder operation on the qubits 1102a-1102c. The first collection of operations includes a multi target CNOT gate <NUM> that is applied to the three qubits 1102a-1102c, where the first qubit acts as a control for the multi target CNOT gate. The first collection of operations further includes a logical AND operation <NUM> that is performed between the second and third qubit. The result of the local AND operation is encoded in a fourth qubit <NUM>. The first collection of operations further includes a CNOT gate <NUM> that is applied to the first qubit 302a and the fourth qubit <NUM>, where the first qubit 1102a acts as a control for the CNOT gate.

The sequence of gates further includes a square of the target phase operation <NUM> that is applied to the fourth qubit <NUM>. A second collection of operations is then applied to the qubits 1102a-1102d to uncompute the controlled adder operation performed by the first collection of operations. The second collection of operations includes a CNOT operation <NUM> that is applied to the first qubit 1102a and to the fourth qubit <NUM>, where the first qubit 1102a acts as a control for the CNOT operation <NUM>. The second collection of operations further includes the uncomputation of a logical AND operation between the second qubit 1102b and the third qubit 1102c.

The sequence of gates further includes a CNOT operation <NUM> that is applied to the second qubit 1102b and the third qubit 1102c, where the second qubit 1102b acts as a control for the CNOT operation <NUM>. The sequence of gates further includes a multi target CNOT operation <NUM> that is applied to the first qubit 1102a, second qubit 1102b and third qubit 1102c, where the first qubit 1102a acts as a control for the multi target CNOT operation <NUM>. The sequence of gates includes a NOT operation <NUM> that is applied to the third qubit 1102c. The NOT operation <NUM> returns the qubit to the original phased plus state Zθ |+〉.

After the example quantum circuit has been applied to the three qubits 1102a-c (and fourth qubit <NUM>), the target phase operation Zθ has been applied to the first qubit 1102a and second qubit 1102b. That is, the example quantum circuit <NUM> operates on a resource state - a | +〉 state that has been phased by an angle equivalent to the target phase operation's angle - and two input states that are to be phased by the angle, phases the two inputs states in the target way, and returns the resource state.

<FIG> is a diagram of an example quantum circuit <NUM> that specializes the generalized phase catalysis circuit <NUM> of <FIG> to θ = <NUM>° , i.e. to the <MAT> gate. This specialized circuit creates two <MAT> states by performing one Toffoli operation and one T gate. The example quantum circuit <NUM> can produce <MAT> states with an order of magnitude less spacetime volume than previous techniques, assuming a physical gate error rate of <NUM>-<NUM> and a target error rate of <NUM>-<NUM>. For example some repeat-until-success circuits use ≈ <NUM> T gates to perform a <MAT> gate at ε = <NUM>-<NUM> and some methods that include direct synthesis of the <MAT> state uses ≈ <NUM> times more volume than direct synthesis of T states (though this ratio improves as the physical gate error rate improves).

Operating the hardware: Example methods implemented by the <MAT> factory.

The CCZ factory described above with reference to <FIG> can be combined with the C2T factory described above with reference to <FIG>, e.g., the example process <NUM> or <NUM> can be appended to example process <NUM>. Combining the two factories/processes produces a T-catalyzed T factory that transforms eight noisy T states into two T states with quadratically less noise, thus achieving a <NUM>:<NUM> ratio of input T states to output T states. This is competitive with a <NUM>:<NUM> ratio of block code state distillation and particularly advantageous because conventionally a larger number of T states must be worked with in order to achieve such good ratios.

In some implementations the CCZ factory (or example process <NUM>) may be modified when being combined with the T-catalyzed T factory (or example processes <NUM>/<NUM>). For example, some or all of the stabilizer measurements may be reordered and the output qubits may be positioned in a different location so that the CCZ factory fits tightly into the T catalyzed T factory. This means that some of the steps of example process <NUM> and <NUM> (or <NUM>) can be combined and the ordering may change. In addition, the factory does not have to be interleaved with itself any more.

<FIG> shows example time slices of lattice surgery activity during a combined operation of a T-catalyzed factory and a CCZ factory. Qubit labels can be matched up with <FIG> for verification that the correct stabilizers are being measured (though in a different order).

Time slice <NUM> corresponds to time slice 400c of <FIG> and <NUM> of <FIG>. Time slice <NUM> corresponds to time slice 400d of <FIG> and <NUM> of <FIG>. Time slice <NUM> corresponds to time slice 400a of <FIG> and <NUM> of <FIG>. Time slice <NUM> corresponds to time slice 400b of <FIG> and <NUM> of <FIG>. Time slice <NUM> corresponds to time slices 400d and 400e of <FIG> and time slice <NUM> of <FIG>. Time slice <NUM> corresponds to time slices 400e-h of <FIG> and time slice <NUM> of <FIG>.

<FIG> is a diagram of the spatial layout and data flow of a known <MAT> |T) factory construction <NUM>, the presently described <MAT> factory construction <NUM>, and the presently described |T〉-catalyzed <MAT> factory <NUM>. The displayed error rates assume a physical gate error rate of <NUM>-<NUM> and assume that the code distance is large enough for the dominant source of error in the outputs to be distillation error. The level-<NUM> T factories 1408a-f are performed at half code distance to balance the contributions from distillation error and code error. <FIG> shows how the presently described CCZ factory and T-catalyzed T factory constructions have smaller footprints, faster output, and an amount of suppression sufficient to run proposed algorithms beyond the classical simulation regime.

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.

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 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), or an ASIC (application-specific integrated circuit).

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 and/or quantum computer program may, but need not, correspond to a file in a file system. 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 by a combination of special purpose logic circuitry 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 include a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and digital and/or quantum data. 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, but rather as descriptions of features that may be specific to particular implementations. 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, 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.

Claim 1:
A method for distilling a CCZ state, wherein the CCZ state is defined as the output of a CCZ gate applied to an input state | + + <NUM>〉, the method comprising:
preparing (<NUM>) a register of qubits (<NUM>) of a quantum computing device in a zero state, the register comprising three target qubits, a plurality of ancilla qubits and a plurality of stabilizer qubits;
after preparing the register of qubits:
performing (<NUM>), for each stabilizer qubit, an X gate on i) multiple ancilla qubits, or ii) multiple ancilla qubits and one of the three target qubits using the stabilizer qubit as a control;
measuring (<NUM>) the stabilizer qubits to determine respective stabilizer qubit states;
after measuring the stabilizer qubits:
performing (<NUM>), on each of the ancilla qubits, a Z<NUM>/<NUM> quantum gate and a Hadamard quantum gate;
measuring (<NUM>) the ancilla qubits to determine respective ancilla qubit states;
after measuring the ancilla qubits, performing (<NUM>), conditioned on each determined ancilla qubit state, i) a NOT operation on a selected stabilizer qubit, or ii) a NOT operation on the selected stabilizer qubit and a Z gate on one or more of the three target qubits;
subsequently,
performing (<NUM>), on each target qubit of the three target qubits and conditioned on a determined state of a respective stabilizer qubit, a Z gate on the target qubit; and
performing (<NUM>) an X gate on each of the three target qubits to obtain the CCZ state encoded in the three target qubits.