Method and system for quantum computing

{
  "publication_number": "US11699004B2",
  "country": "US",
  "kind": "B2",
  "title": "Method and system for quantum computing",
  "abstract": "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.",
  "claims": [
    "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."
  ],
  "description_excerpt": "This disclosure is generally related to quantum computing. More specifically, this disclosure is related to a system and method for performing distributed simulation of a quantum circuit.\n\nIn recent years, research efforts in quantum computing have made significant progress. Quantum computing refers to the computing based on quantum mechanical principles, such as superposition and entanglement. Large-scale quantum computers can theoretically solve certain problems much more quickly than any classical computers that use the best currently known algorithms. Those problems can include the integer factorization problem and the database search problem, where there is no searchable structure in the collection of all possible answers. Moreover, quantum computers may potentially be able to solve problems that are not practically feasible to be solved by classical computers.\n\nUnlike common digital computing that requires data being encoded into binary digits, each of which is always in one of two defined states (0 or 1), quantum computing uses quantum bits (or qubits), which can be in superpositions of states. A qubit can be a two-state (or two-level) quantum mechanical system, such as the spin of electrons or the polarization state of photons. For example, the spin up state can represent “1,” whereas the spin down state can represent “0.” A spin that is neither up nor down can represent a superposition state. A small number of qubits can hold a relatively large amount of information. For example, the superposition states of 100 particles can represent up to 2 100 numbers.",
  "cpc": [
    "G06F 30/20",
    "G06F 17/16",
    "G06F 30/00",
    "G06F 30/3308",
    "G06F 9/5027",
    "G06N 10/00",
    "G06N 10/20",
    "G06N 5/01"
  ],
  "ipc": [
    "G06F 30/3308",
    "G06N 10/20",
    "G06F 17/16",
    "G06F 30/20"
  ],
  "assignees": [
    "Alibaba Group Holding Ltd"
  ],
  "inventors": [
    "Jianxin Chen",
    "Fang Zhang",
    "Yaoyun Shi",
    "Jiachen Huang",
    "Michael Newman"
  ],
  "filing_date": "2021-03-19",
  "publication_date": "2023-07-11",
  "grant_date": "2023-07-11",
  "priority_date": "2018-04-27",
  "application_number": "US-202117207124-A",
  "family_id": "68291647",
  "cited_by_count": 1,
  "citations": [
    "US20040024750A1",
    "US20140245004A1",
    "US20160132897A1",
    "US10915891B1",
    "US20160323109A1",
    "US20170116693A1",
    "US20180089651A9",
    "US20170243287A1",
    "US20180374173A1",
    "EP3410327A1",
    "WO2017148245A1",
    "US20170330174A1",
    "WO2018024062A1",
    "CN106296390A",
    "US20180039942A1",
    "WO2018032890A1",
    "CN106100981A",
    "CN107967416A",
    "RU2658784C1",
    "US20180294966A1",
    "US20200193432A1",
    "US9882918B1",
    "CN107086920A",
    "CN107358551A",
    "CN107659610A",
    "CN107516245A",
    "CN107622385A",
    "CN107705114A",
    "CN107798650A",
    "CN107657509A",
    "US10135834B1",
    "CN107944717A",
    "US20190163912A1",
    "US20190228369A1",
    "US20190325473A1",
    "US20190385215A1",
    "CN108876560A",
    "CN109255600A",
    "US20200128022A1"
  ]
}