Sparse simulation of Clifford-dominated quantum circuits

1 . A system comprising:

an interface to quantum computing resources; and

one or more classical computing devices configured to implement a quantum computing simulator configured to:

receive information defining a quantum circuit to be simulated;

represent a state of the quantum circuit using:

a Clifford tableau; and

a set of key-value pairs representing possible outcomes of execution of the quantum circuit, wherein respective ones of the key-values pairs comprise:

a key corresponding to a computational basis state representing simulated states of qubits of the executed quantum circuit; and

a value corresponding to a probability amplitude representing a probability that qubits of the executed quantum circuit are in the states of the computational basis state of the key associated with the value;

apply Clifford gates of the quantum circuit by updating the Clifford tableau to reflect the application of the Clifford gates; and

apply non-Clifford gates of the quantum circuit by:

updating the Clifford tableau to reflect application of the non-Clifford gate; and/or

updating the set of key-value pairs to reflect application of the non-Clifford gate; and

provide simulation results of the quantum circuit, wherein the simulation results are used in optimizing the quantum circuit for execution on the quantum computing resources.

2 . The system of claim 1 wherein to apply the non-Clifford gates of the quantum circuit, the quantum computing simulator is configured to:

represent respective ones of the non-Clifford, using a physical decomposition, as a Clifford gate portion and a non-Clifford rotational gate portion.

3 . The system of claim 2 , wherein said updating the Clifford tableau and said updating the set of key-value pairs that are performed as part of applying the non-Clifford gate comprises:

applying the Clifford gate portion of the non-Clifford gates to the Clifford tableau; and

applying the non-Clifford rotational gate portion of the non-Clifford gates to the set of key-value pairs by applying a rotational term that is at most 2-sparse and which causes a number of key-value pairs of the set to increase by at most by a factor of two for each one of the non-Clifford gates that are applied.

4 . The system of claim 1 , wherein to apply the non-Clifford gates of the quantum circuit, the quantum computing simulator is configured to:

represent respective ones of the non-Clifford, using a non-physical decomposition, as a set of projections to be applied.

5 . The system of claim 4 , wherein said updating the Clifford tableau and said updating the set of key-value pairs that are performed as part of applying the non-Clifford gate comprises:

updating the Clifford tableau; and/or

applying the set of projections.

6 . The system of claim 1 , wherein the quantum simulator is further configured to:

receive noise information for a given one of the quantum computing resources; and

use the noise information in determining the simulation results, wherein the simulation results simulate execution of the quantum circuit on the given one of the quantum computing resources.

7 . The system of claim 6 , further comprising:

one or more computing devices configured to implement a quantum computing service configured to:

receive calibration information for a plurality of quantum processing units connected to the quantum computing service via the interface to the quantum computing resources;

cause the quantum computing simulator to simulate the quantum circuit for execution on the plurality of quantum processing units, wherein the respective simulations take into account the received calibration information for the respective quantum processing units; and

select a given one of the quantum processing units to execute the quantum circuit based on the simulated results.

8 . The system of claim 4 , wherein the quantum circuit and the plurality of alternative version of the quantum circuit comprise quantum circuits for performing magic state distillation or magic state injection.

9 . A method of simulating a quantum circuit, comprising:

representing respective ones of a plurality of multi-qubit non-Clifford gates included in the quantum circuit being simulated as a combination of Clifford gates and single qubit non-Clifford gates;

applying a Clifford gate portion of the multi-qubit non-Clifford gates to a Clifford tableau used in representing a state of the quantum circuit being simulated;

applying a non-Clifford rotational term that is at most 2-sparse and which causes a number of key-value pairs of a set of key-value pairs used in representing the state of the quantum circuit being simulated to increase by at most by a factor of two for each one of the single-qubit non-Clifford gates, of the multi-qubit non-Clifford gate representation, that are applied; and

providing simulation results of the quantum circuit.

10 . The method of claim 9 , further comprising:

applying Clifford gates of the quantum circuit by updating the Clifford tableau to reflect the application of the Clifford gates.

11 . The method of claim 9 , wherein at any point during simulation of the quantum circuit a state of the simulator is represented by:

the Clifford tableau; and

the set of key-value pairs, wherein the set of key-value pairs represent possible outcomes of execution of the quantum circuit on a given quantum processing unit, wherein respective ones of the key-values pairs comprise:

a key corresponding to a computational basis state representing simulated states of qubits of the possible execution outcomes of the quantum circuit; and

a value corresponding to a probability amplitude representing a probability that qubits of the quantum circuit are in the states of the computational basis state of the key associated with the value.

12 . The method of claim 9 , wherein the set of key-value pairs is limited to key-value pairs comprising probability amplitudes, for corresponding computational basis states, that are non-zero.

13 . The method of claim 12 , wherein the limited set of key-value pairs with non-zero probability amplitudes included in the set of key-value pairs considered in simulating the quantum circuit are less than a total number of possible computational basis possible based on a qubit count of the quantum circuit being simulated.

14 . The method of claim 9 , wherein providing the simulation results comprises:

measuring a Pauli observable at a given location in the quantum circuit; wherein said measuring comprises:

projecting a state of the simulator at a given location onto an eigenstate of a measurement Pauli observable, wherein the state of the simulator prior to the projection has been transformed due to the application of the rotational term; and

computing a norm of a resulting state, wherein the norm indicates an expectation value.

15 . The method of claim 9 , wherein the quantum circuit being simulated comprises more than 30 total qubits.

16 . The method of claim 9 , wherein the single-qubit non-Clifford gates are rotational gates about the Z-axis.

17 . The method of claim 16 , wherein respective ones of the rotational gates about the Z-axis are given by:

R

z

(

θ

)

=

e

-

0

.

5

⁢

i

⁢

θ

⁢

Z

and the non-Clifford rotational term that is applied comprises:

e

-

0

.

5

⁢

i

⁢

θ

⁢

Q

where Q is an n-qubit Pauli for which a Clifford frame and a conjugate of the Clifford frame have been applied.

18 . One or more non-transitory, computer-readable, storage media storing program instructions, that when executed on or across one or more processors, cause the one or more processors to:

represent respective ones of a plurality of multi-qubit non-Clifford gates included in a quantum circuit being simulated as a combination of Clifford gates and single-qubit non-Clifford gates;

apply a Clifford gate portion of the non-Clifford gates to a Clifford tableau used in representing a state of the quantum circuit being simulated;

apply a non-Clifford rotational term that is at most 2-sparse and which causes a number of key-value pairs of a set of key-value pairs used in representing a state of the quantum circuit being simulated to increase by at most by a factor of two for each one of the single-qubit non-Clifford gates, of the multi-qubit non-Clifford gate representation, that are applied; and

provide simulation results of the quantum circuit.

19 . The one or more non-transitory, computer-readable, storage media of claim 18 ,

wherein the state of the quantum circuit being simulated is represented by:

the Clifford tableau; and

the set of key-value pairs, wherein the set of key-value pairs represent possible outcomes of execution of the quantum circuit on a given quantum processing unit, wherein respective ones of the key-values pairs comprise:

a key corresponding to a computational basis state representing simulated states of qubits of the executed quantum circuit; and

a value corresponding to a probability amplitude representing a probability that qubits of the executed quantum circuit are in the states of the computational basis state of the key associated with the value.

20 . The one or more non-transitory, computer-readable, storage media of claim 18 , wherein the program instruction, when executed on or across the one or more processors, further cause the one or more processors to:

select the sparse simulation with the Clifford tracker from a plurality of supported simulation protocols for simulating the quantum circuit, wherein the selection is based on:

a number of non-Clifford gates included in the quantum circuit to be simulated; and

a number of overall qubits in the quantum circuit to be simulated.