Method and system for quantum computing
One embodiment described herein provides a system and method for simulating behavior of a quantum circuit that includes a plurality of quantum gates. During operation, the system receives information that represents the quantum circuit and constructs an undirected graph corresponding to the quantum circuit. A respective vertex within the undirected graph corresponds to a distinct variable in a Feynman path integral used for computing amplitude of the quantum circuit, and a respective edge corresponds to one or more quantum gates. The system identifies a vertex within the undirected graph that is coupled to at least two two-qubit quantum gates; simplifies the undirected graph by removing the identified vertex, thereby effectively removing the two-qubit quantum gates coupled to the identified vertex; and evaluates the simplified undirected graph, thereby facilitating simulation of the behavior of the quantum circuit.
1. A computer-implemented method for simulating behavior of a quantum circuit comprising a plurality of single-qubit quantum gates and a plurality of two-qubit quantum gates, the method comprising:
receiving, by a computing device, information that represents the quantum circuit;
constructing an undirected graph corresponding to the quantum circuit, wherein a respective vertex within the undirected graph corresponds to a distinct variable in a Feynman path integral used for computing amplitude of the quantum circuit, and wherein a respective edge corresponds to one or more quantum gates;
identifying a vertex within the undirected graph that is coupled to at least two two-qubit quantum gates;
simplifying the undirected graph by removing the identified vertex, thereby removing the at least two two-qubit quantum gates coupled to the identified vertex; and
performing a simulation of the behavior of the quantum circuit, which comprises evaluating the simplified undirected graph;
wherein identifying the vertex comprised performing a greedy operation based on an objective function associated with a reduction of an execution time for evaluating the simplified undirected graph.
2. The computer-implemented method of claim 1 , wherein identifying the vertex comprises traversing all vertices in the undirected graph.
3. The computer-implemented method of claim 1 , further comprising computing an initial tensor-contraction ordering by performing a treewidth computing operation.
4. The computer-implemented method of claim 3 , wherein performing the greedy operation comprises:
selecting a local range based on the initial tensor-contraction ordering; and
selecting an optimal vertex for removal within the local range in such a way that removing the optimal vertex results in a minimum time cost associated with evaluating the undirected graph.
5. The computer-implemented method of claim 1 , wherein identifying the vertex comprises performing a dynamic programming operation.
6. The computer-implemented method of claim 1 , wherein the two-qubit quantum gates comprise a two-qubit diagonal quantum gate.
7. The computer-implemented method of claim 6 , wherein the two-qubit diagonal quantum gate comprises a controlled-Z (CZ) gate.
8. The computer-implemented method of claim 1 , wherein the quantum circuit has at least 50 qubits and a depth of at least 30.
9. A computer system for simulating behavior of a quantum circuit comprising a plurality of single-qubit quantum gates and a plurality of two-qubit quantum gates, the system comprising:
a processor; and
a storage device coupled to the processor and storing instructions which when executed by the processor cause the processor to perform a method, wherein the method comprises:
receiving information that represents the quantum circuit;
constructing an undirected graph corresponding to the quantum circuit, wherein a respective vertex within the undirected graph corresponds to a distinct variable in a Feynman path integral used for computing amplitude of the quantum circuit, and wherein a respective edge corresponds to one or more quantum gates;
identifying a vertex within the undirected graph that is coupled to at least two two-qubit quantum gates;
simplifying the undirected graph by removing the identified vertex, thereby removing the at least two two-qubit quantum gates coupled to the identified vertex; and
performing a simulation of the behavior of the quantum circuit, which comprises evaluating the simplified undirected graph;
wherein identifying the vertex comprises performing a greedy operation based on an objective function associated with a reduction of an execution time for evaluating the simplified undirected graph.
10. The computer system of claim 9 , wherein identifying the vertex comprises traversing all vertices in the undirected graph.
11. The computer system of claim 9 , wherein the method further comprises computing an initial tensor-contraction ordering by performing a treewidth computing operation.
12. The computer system of claim 11 , wherein performing the greedy operation comprises:
selecting a local range based on the initial tensor-contraction ordering; and
selecting an optimal vertex for removal within the local range in such a way that removing the optimal vertex results in a minimum time cost associated with evaluating the undirected graph.
13. The computer system of claim 9 , wherein identifying the vertex comprises performing a dynamic programming operation.
14. The computer system of claim 9 , wherein the two-qubit quantum gates comprise a two-qubit diagonal quantum gate, and wherein the two-qubit diagonal quantum gate comprises a controlled-Z (CZ) gate.
15. The computer system of claim 9 , wherein the quantum circuit has at least 50 qubits and a depth of at least 30.
16. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for simulating behavior of a quantum circuit comprising a plurality of single-qubit quantum gates and a plurality of two-qubit quantum gates, the method comprising:
receiving, by a computing device, information that represents the quantum circuit;
constructing an undirected graph corresponding to the quantum circuit, wherein a respective vertex within the undirected graph corresponds to a distinct variable in a Feynman path integral used for computing amplitude of the quantum circuit, and wherein a respective edge corresponds to one or more quantum gates;
identifying a vertex within the undirected graph that is coupled to at least two two-qubit quantum gates;
simplifying the undirected graph by removing the identified vertex, thereby removing the at least two two-qubit quantum gates coupled to the identified vertex; and
performing a simulation of the behavior of the quantum circuit, which comprises evaluating the simplified undirected graph;
wherein identifying the vertex comprises performing a greedy operation based on an objective function associated with a reduction of an execution time for evaluating the simplified undirected graph.
17. The non-transitory computer-readable storage medium of claim 16 , wherein the method further comprises computing an initial tensor-contraction ordering by performing a treewidth computing operation, and wherein performing the greedy operation comprises:
selecting a local range based on the initial tensor-contraction ordering; and
selecting an optimal vertex for removal within the local range in such a way that removing the optimal vertex results in a minimum time cost associated with evaluating the undirected graph.