Method and system for optimal decomposition of single-qubit quantum circuits using standard quantum gates

• US 9,208,280 B2
• Filed: 07/18/2013
• Issued: 12/08/2015
• Est. Priority Date: 07/19/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bocharov, Alexei, Svore, Krysta
• Primary Examiner(s): Ngo, Brian
• Application Number:
  US14/415,572
• Publication Number:
  US 20150186587A1
• Time in Patent Office: 873 Days
• Field of Search: 716/101, 716/104, 716/132
• US Class Current: 1/1
• CPC Class Codes: B82Y 10/00 Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena

Abstract

The current application is directed to methods and systems which produce a design for an optimal approximation of a target single-qubit quantum operation comprising a representation of a quantum-circuit generated from a discrete, quantum-gate basis. The discrete quantum-gate basis comprises standard, implementable quantum gates. The methods and systems employ a database of canonical-form quantum circuits, an efficiently organized canonical-form quantum-circuit, and efficient searching to identify a minimum-cost design for decomposing and approximating an input target quantum operation.

Claims

1. A computer-implemented method of synthesizing a design for a target quantum operation u in a standard-quantum-gate basis, the method comprising:

receiving, by the computer system, the target quantum operation u;

searching, by the computer system, a database of canonical-form quantum circuits to identify a canonical-form quantum circuit from which a minimum-cost design within a distance-metric-value distance to the target quantum operation u can be generated, wherein each canonical-form quantum circuit is represented as a sequence of representations of TH and SH gates that contains no adjacent SH gates, ends in TH, and in which no SH gate occurs before the fifth gate;

generating, by the computer system, the minimum cost design from the identified canonical-form quantum circuit; and

storing, by the computer system, the generated minimum-cost design in one or more of an electronic memory and physical data-storage device.

2. The method of claim 1, wherein the database of canonical-form quantum circuits is partitioned into one or more trace-level partitions, each associated with a range of absolute trace-level values.

3. The method of claim 2, wherein the trace-level partitions are distributed across multiple computational and data-storage nodes of a distributed quantum-circuit-design system.

4. The method of claim 1, wherein searching the database of canonical-form quantum circuits to identify the canonical-form quantum circuit from which the minimum-cost design within the distance-metric-value distance to the target quantum operation u can be generated further comprises:

transforming the target quantum operation u by a right-coset operation followed by an adjoint operation to generate up to a first maximum number of search neighborhoods within a trace space; and

searching the up to the first maximum number of search neighborhoods within the trace space to identify the minimum-cost design within the distance-metric-value distance to the target quantum operation u.

5. The method of claim 4, wherein:

the right-coset operation generates up to a second maximum number of trace-level neighborhoods;

the adjoint operation generates up to a third maximum number of symmetrically related search neighborhoods within each trace-level neighborhood; and

the first maximum number of search neighborhoods is a product of the second and third maximum numbers.

6. The method of claim 4, wherein the right-hand coset and adjoint operations employ elements of the CPH group.

7. The method of claim 1, wherein generating the minimum cost design from the identified canonical-form quantum circuit further comprises applying an adjoint operation followed by a right-coset operation to the identified canonical-form quantum circuit.

8. A database-search-based quantum-circuit design system, comprising:

a number of distributed system nodes, each including one or more processors, one or more electronic memories, and one or more physical data-storage devices;

computer instructions stored in one or more electronic memories and physical data-storage devices within each system node that, when executed on the one or more processors within the system node, control the system node to receive a target quantum operation u;

search a portion of a database of canonical-form quantum circuits to identify a canonical-form quantum circuit from which a minimum-cost design within a distance-metric-value distance to the target quantum operation u can be generated, wherein each canonical-form quantum circuit is represented as a sequence of representations of TH and SH gates that that contains no adjacent SH gates, that ends in TH, and in which no SH gate occurs before the fifth gate; and

when the canonical-form quantum circuit is identified,

generate the minimum cost design from the identified canonical-form quantum circuit,

store the generated minimum-cost design in one or more of an electronic memory and physical data-storage device, and

provide an indication that the canonical-form quantum circuit is identified.

9. The database-search-based quantum-circuit design system of claim 8, wherein the database of canonical-form quantum circuits is partitioned into one or more trace-level partitions, each associated with a range of absolute trace-level values.

10. The database-search-based quantum-circuit design system of claim 9, wherein the trace-level partitions are distributed across the number of distributed system nodes.

11. The database-search-based quantum-circuit design system of claim 9, wherein the target quantum operation u is transformed by a right-coset operation to generate up to a first maximum number of trace-level neighborhoods and the up to the first maximum number of trace-level neighborhoods are each searched by one or more distributed system nodes.

12. The database-search-based quantum-circuit design system of claim 8, wherein a distributed system node searches a trace-level neighborhood by:

transforming the target quantum operation u transformed by the right-coset operation by an adjoint operation to generate up to a second maximum number of search neighborhoods within a trace space; and

searching the up to the second maximum number of search neighborhoods within the trace space to identify the minimum-cost design within the distance-metric-value distance to the target quantum operation u.

13. The database-search-based quantum-circuit design system of claim 12, wherein the right-hand coset and adjoint operations employ elements of the CPH group.

14. The database-search-based quantum-circuit design system of claim 8, wherein a distributed system node generates the minimum cost design from the identified canonical-form quantum circuit by applying an adjoint operation followed by a right-coset operation to the identified canonical-form quantum circuit.

15. The database-search-based quantum-circuit design system of claim 8, wherein the database-search-based quantum-circuit design system selects as a design for the target quantum operation u the minimum-cost design identified by the distributed system nodes.

16. The database-search-based quantum-circuit design system of claim 8, wherein each canonical-form quantum circuit is represented as a sequence of representations of TH and SH gates and is associated with a corresponding normal representation having the same number of TH gates as the canonical-form circuit.

17. A database-search-based quantum-circuit design system, comprising:

one or more processors, one or more electronic memories, and one or more physical data-storage devices; and

computer instructions stored in one or more electronic memories and physical data-storage devices that, when executed on the one or more processors, control the system to;

receive the target quantum operation u;

search a database of canonical-form quantum circuits to identify a canonical-form quantum circuit from which a minimum-cost design within a distance-metric-value distance to the target quantum operation u can be generated, wherein each canonical-form quantum circuit is represented as a sequence of representations of TH and SH gates that that contains no adjacent SH gates, ends in TH, and in which no SH gate occurs before the fifth gate;

generate the minimum cost design from the identified canonical-form quantum circuit; and

store the generated minimum-cost design in one or more of an electronic memory and physical data-storage device.