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, the method comprising:
constructing, by a computer, a graph corresponding to a quantum circuit comprising a plurality of quantum gates, wherein each vertex within the graph corresponds to a distinct variable used for computing amplitude of the quantum circuit, and wherein the graph comprises at least one edge corresponding to one or more single-qubit gates and at least one edge corresponding to one or more two-qubit quantum gates;
performing a search on the graph to identify a vertex within the graph that is coupled to at least two edges, with each coupled edge corresponding to at least one two-qubit quantum gate;
simplifying the graph by removing the identified vertex, thereby removing the at least two edges coupled to the identified vertex; and
simulating behavior of the quantum circuit, which comprises evaluating the simplified graph.
2. The computer-implemented method of claim 1 , wherein performing the search to identify the vertex comprises traversing all vertices in the graph.
3. The computer-implemented method of claim 1 , wherein performing the search to identify the vertex comprises performing a greedy-search operation based on an objective function associated with an execution time for evaluating the simplified graph.
4. The computer-implemented method of claim 3 , further comprising computing an initial tensor-contraction ordering by performing a treewidth computing operation.
5. The computer-implemented method of claim 3 , wherein performing the greedy-search 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 graph.
6. The computer-implemented method of claim 1 , wherein performing the search to identify the vertex comprises performing a dynamic programming operation.
7. The computer-implemented method of claim 1 , wherein the two-qubit quantum gates comprise a two-qubit diagonal quantum gate.
8. The computer-implemented method of claim 7 , wherein the two-qubit diagonal quantum gate comprises a controlled-Z (CZ) gate.
9. The computer-implemented method of claim 1 , wherein the quantum circuit has at least 50 qubits and a depth of at least 30.
10. A computer 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, the method comprising:
constructing a graph corresponding to a quantum circuit comprising a plurality of quantum gates, wherein each vertex within the graph corresponds to a distinct variable used for computing amplitude of the quantum circuit, and wherein the graph comprises at least one edge corresponding to one or more single-qubit gates and at least one edge corresponding to one or more two-qubit quantum gates;
performing a search on the graph to identify a vertex within the graph that is coupled to at least two edges, with each coupled edge corresponding to at least one two-qubit quantum gate;
simplifying the graph by removing the identified vertex, thereby removing the at least two edges coupled to the identified vertex; and
simulating behavior of the quantum circuit, which comprises evaluating the simplified graph.
11. The computer system of claim 10 , wherein performing the search to identify the vertex comprises traversing all vertices in the graph.
12. The computer system of claim 10 , wherein performing the search to identify the vertex comprises performing a greedy-search operation based on an objective function associated with an execution time for evaluating the simplified graph.
13. The computer system of claim 12 , wherein the method further comprises computing an initial tensor-contraction ordering by performing a treewidth computing operation.
14. The computer system of claim 13 , wherein performing the greedy-search 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 graph.
15. The computer system of claim 10 , wherein performing the search to identify the vertex comprises performing a dynamic programming operation.
16. The computer system of claim 10 , 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.
17. The computer system of claim 10 , wherein the quantum circuit has at least 50 qubits and a depth of at least 30.
18. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
constructing a graph corresponding to a quantum circuit comprising a plurality of quantum gates, wherein each vertex within the graph corresponds to a distinct variable used for computing amplitude of the quantum circuit, and wherein the graph comprises at least one edge corresponding to one or more single-qubit gates and at least one edge corresponding to one or more two-qubit quantum gates;
performing a search on the graph to identify a vertex within the graph that is coupled to at least two edges, with each coupled edge corresponding to at least one two-qubit quantum gate;
simplifying the graph by removing the identified vertex, thereby removing the at least two edges coupled to the identified vertex; and
simulating behavior of the quantum circuit, which comprises evaluating the simplified graph.
19. The non-transitory computer-readable storage medium of claim 18 , wherein performing the search to identify the vertex comprises performing a greedy-search operation based on an objective function associated with an execution time for evaluating the simplified graph.
20. The non-transitory computer-readable storage medium of claim 18 , wherein the method further comprises computing an initial tensor-contraction ordering by performing a treewidth computing operation, and wherein performing the greedy-search 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 graph.