IP Library › Granted Patent US 12,198,002
Granted Patent B2
US 12,198,002 · App. 17/304,421 · Granted Jan 14, 2025

System and method for optimizing quantum circuit synthesis

Inventors: Michele Mosca (Waterloo, CA); Priyanka Mukhopadhyay (Waterloo, CA)
Assignee: Michele Mosca
G06N10/00G06F30/20G06F2115/10
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,198,002
App. No.
17/304,421
Granted
Jan 14, 2025
Kind
B2
Abstract

A method is provided for synthesizing quantum circuits while reducing the T-count, comprising, for a plurality of qubits: determining a target unitary and executing a set of candidate operations W with a single T gate and computing a specific function f of U W −1 keeping the values of W that correspond to specific multiplicities such that after the first collection of W operators is selected a collection of unitaries U W −1 is determined to consider in the next round to build a tree. A method of synthesizing quantum circuits while reducing the T-depth is also provided, comprising, for a plurality of qubits: determining a target unitary and execute a set of candidate operations W with T depth of one and computing a specific function f of U W −1 , keeping the values of W that correspond to specific multiplicities such that after the first collection of W operators is selected a collection of unitaries U W −1 is determined to consider in the next round to build a tree. A method of re-synthesizing quantum circuits while reducing T-depth is also provided, comprising, for a plurality of qubits considering all cluster sizes up to a maximum sized cluster, and continuing recursively.

Claims (41)

1. A method of synthesizing a quantum circuit for a plurality of qubits, comprising:

initializing one or more target unitaries (U) as one or more input unitaries;

iteratively determining one or more subsequent target unitaries by:

executing a set of candidate operations (W) having a T-gate property via a channel representation function (f) for each of the one or more target unitaries (U);

selecting one or more subsequent target unitaries based on values of the channel representation function (f) which satisfy one or more multiplicity criteria; and

updating the one or more target unitaries (U) to include the selected one or more subsequent target unitaries.

2. The method of claim 1 , where the candidate operations (W) are inverses of channel representations (W −1 ), and the T-gate property is one of having a single T-gate or having a T-depth of one.

3. The method of claim 2 , wherein the one or more multiplicity criteria are defined by channel representation function (f) values grouped by: (sde(U W −1 ) increases), (sde(U W −1 ) decreases), and (sde(U W −1 ) is unchanged).

4. The method of claim 2 , wherein the one or more multiplicity criteria are defined by channel representation function (f) values grouped by: (sde (U W −1 ) increases, Hamming weight increases), (sde(U W −1 ) increases, Hamming weight decreases), (sde(U W −1 ) decreases, Hamming weight increases), (sde(U W −1 ) decreases, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight increases).

5. The method of claim 2 , wherein the one or more multiplicity criteria are defined by channel representation function (f) values grouped by: (sde(U W −1 ) increases, Hamming weight increases), (sde(U W −1 ) increases, Hamming weight decreases), (sde(U W −1 ) decreases, Hamming weight increases), (sde(U W −1 ) decreases, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight increases), (sde(U W −1 ) is unchanged, Hamming weight is unchanged).

6. The method of claim 2 , wherein the one or more multiplicity criteria are defined by channel representation function (f) values grouped by one or both of sde(U W −1 ) and Hamming weights, and wherein the one or more subsequent target unitaries are selected based on channel representation function (f) value groups with a minimum cardinality.

7. The method of claim 6 , wherein:

the one or more subsequent target unitaries are determined for a target unitary count number of iterations; and

the one or more subsequent target unitaries are selected based on channel representation function (f) value groups with sde(U W −1 ) values that can reduce to zero for the remaining iterations.

8. The method of claim 1 , wherein:

the set of candidate operations (W) is computed in time (O) defined by (N 4 /2), where N is a dimension of the set of candidate operations (W), and the set of candidate operations (W) are determined at least in part by copying half the rows of a respective candidate unitary matrix (V), and the remaining N 2 /2 rows of the respective set of candidate operations W are determined by a component-wise addition or subtraction and multiplication among pairs of rows of the respective candidate unitary matrix (V).

9. The method of claim 1 , wherein one or more target unitaries (U) are stored as a ring representation in a tuplet along with an sde value associated with the respective one or more target unitaries.

10. The method of claim 1 , wherein the quantum circuit comprises Clifford and T-gate sets arranged according to the one or more target unitaries (U).

11. A system for synthesizing or re-synthesizing quantum circuits comprising a processor and memory, the memory comprising computer executable instructions that when executed by the processor, cause the processor to:

initialize one or more target unitaries (U) as one or more input unitaries;

recursively determine one or more subsequent target unitaries by:

execute a set of candidate operations (W) having a T-gate property via a channel representation function (f) for each of the one or more target unitaries (U);

select one or more subsequent target unitaries based on values of the channel representation function (f) which satisfy one or more multiplicity criteria; and

update the one or more target unitaries (U) to include the one or more subsequent target unitaries.

12. The system of claim 11 , where the candidate operations (W are inverses of channel representations (W −1 ), and the T-gate property is one of having a single T-gate or having a T-depth of one.

13. The system of claim 11 , wherein the one or more multiplicity criteria are defined by function (f) values grouped by: (sde(U W −1 ) increases), (sde (U W −1 ) decreases) and (sde(U W −1 ) is unchanged).

14. The system of claim 11 , wherein the one or more multiplicity criteria are defined by function (f) values grouped by: (sde(U W −1 ) increases, Hamming weight increases), (sde(U W −1 ) increases, Hamming weight decreases), (sde(U W −1 ) decreases, Hamming weight increases), (sde(U W −1 ) decreases, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight increases).

15. The system of claim 11 , wherein the one or more multiplicity criteria are defined by function (f) values grouped by: (sde(U W −1 ) increases, Hamming weight increases), (sde(U W −1 ) increases, Hamming weight decreases), (sde(U W −1 ) decreases, Hamming weight increases), (sde(U W −1 ) decreases, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight decreases), (sde(U W −1 ) is unchanged, Hamming weight increases), (sde(U W −1 ) is unchanged, Hamming weight is unchanged).

16. The system of claim 11 , wherein the one or more multiplicity criteria are defined by function (f) values grouped by one or both of sde(U W −1 ) and Hamming weights, and wherein the one or more subsequent target unitaries are selected based on function (f) value groups with a minimum cardinality.

17. The system of claim 16 , wherein:

the one or more subsequent target unitaries are determined for a target unitary count number of iterations; and

the one or more subsequent target unitaries are selected based on function (f) value groups with sde(U W −1 ) values that can reduce to zero for the remaining iterations.

18. The system of claim 17 , wherein:

the set of candidate operations (W) is computed in time (O) defined by (N4/2), where N is a dimension of the set of candidate operations (W), and the set of candidate operations (W) are determined at least in part by copying half the rows of a respective candidate unitary matrix (V), and the remaining N2/2 rows of the respective set of candidate operations (W) are determined by a component-wise addition or subtraction and multiplication among pairs of rows of the respective candidate unitary matrix (V).

19. The system of claim 11 , wherein one or more target unitaries (U) are stored as a ring in a tuplet along with an sde value associated with the respective one or more target unitaries.

20. A non-transitory computer readable medium comprising computer executable instructions for synthesizing a quantum circuit for a plurality of qubits, comprising instructions for:

initializing one or more target unitaries (U) as one or more input unitaries;

iteratively determining one or more subsequent target unitaries by:

executing a set of candidate operations (W) having a T-gate property via a channel representation function (f) for each of the one or more target unitaries (U);

selecting one or more subsequent target unitaries based on values of the channel representation function (f) which satisfy one or more multiplicity criteria; and

updating the one or more target unitaries (U) to include the one or more subsequent target unitaries.

Assignments (2)
NUNC PRO TUNC ASSIGNMENT Recorded Apr 22, 2025
From: MOSCA, MICHELE
To: SOFTWAREQ INC.
Reel/Frame 070913/0732 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 4, 2022
From: MUKHOPADHYAY, PRIYANKA
To: MOSCA, MICHELE
Reel/Frame 058544/0547 →
Continuity (2)
Provisional Application 62705294 · Jun 19, 2020
Related Publication 20210406753A1 · Dec 30, 2021
References Cited (40)
US 11049038B2 · Chen · 2021 [cited by examiner]
US 11308252B1 · Piveteau · 2022 [cited by examiner]
US 20220164505A1 · Mosca · 2022 [cited by examiner]
Aaronson, Scott and Gottesman, Daniel; Improved simulation of stabilizer circuits; Physical Review A, 70(5):052328, 2004. [cited by applicant]
Aliferis, Panos; Gottesman, Daniel and Preskill, John; Quantum accuracy threshold for concatenated distance-3 codes; Quantum Information & Computation, 6(2):97-165, 2006. [cited by applicant]
Amy, Matthew; Maslov, Dmitri and Mosca, Michele; Polynomial-time t-depth optimization of clifford+ t circuits via matroid partitioning; IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 33(10… [cited by applicant]
Amy, Matthew; Maslov, Dmitri; Mosca, Michele, and Roetteler, Martin; A meet-in-themiddle algorithm for fast synthesis of depth-optimal quantum circuits; IEEE Transactions on Computer-Aided Design of Integrated Circuits … [cited by applicant]
Abdessaied, Nabila; Soeken, Mathias, and Drechsler, Rolf; Quantum circuit optimization by hadamard gate reduction; In International Conference on Reversible Computation, pp. 149-162. Springer, 2014. [cited by applicant]
Bombin, Héctor; Andrist, Ruben S.; Ohzeki, Masayuki; Katzgraber, Helmut G; and Martín-Delgado, Miguel A.; Strong resilience of topological codes to depolarization; Physical Review X, 2(2):021004, 2012. [cited by applicant]
Bravyi, Sergey and Kitaev, Alexei; Universal quantum computation with ideal clifford gates and noisy ancillas; Physical Review A, 71(2):022316, 2005. [cited by applicant]
Bocharov, Alex ; Roetteler, Martin and Svore, Krysta M.; Efficient synthesis of universal repeat-until-success quantum circuits. Physical review letters, 114(8):080502, 2015. [cited by applicant]
Britton, Joseph W., Sawyer, Brian C., Keith Adam C.; Wang, C-C Joseph; Freericks, James K.; Uys, Hermann; Biercuk, Michael J. and Bollinger, John J.; Engineered two dimensional ising interactions in a trapped-ion quantu… [cited by applicant]
Brown, Kenton R.; Wilson, Andrew C.; Colombe, Yves; Ospelkaus, C.; Meier, Adam M.; Leibfried, E. Knill D. and Wineland, David J.; Single-qubit-gate error below 10-4 in a trapped ion; Physical Review A, 84(3):030303, 201… [cited by applicant]
Chow, Jerry M. et al.; Universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits; Physical review letters, 109(6):060501, 2012. [cited by applicant]
De Beaudrap, Niel; Bian, Xiaoning and Wang, Quanlong; Techniques to reduce π/4 parity phase circuits, motivated by the zx calculus; arXiv preprint arXiv:1911.09039, 2019. [cited by applicant]
Di Matteo, Olivia and Mosca, Michele; Parallelizing quantum circuit synthesis; Quantum Science and Technology, 1(1):015003, 2016. [cited by applicant]
Fowler, Austin G.; Whiteside, Adam C. and Hollenberg, Lloyd CL; Towards practical classical processing for the surface code; Physical review letters, 108(18):180501, 2012. [cited by applicant]
Gottesman, Daniel and Chuang, Isaac L.; Quantum teleportation is a universal computational primitive; arXiv preprint quant-ph/9908010, 1999. [cited by applicant]
Gosset, David; Kliuchnikov, Vadym; Mosca, Michele and Russo, Vincent; An algorithm for the t-count. arXiv preprint arXiv:1308.4134, 2013. [cited by applicant]
Gottesman, Daniel; The heisenberg representation of quantum computers; preprint quant-ph/9807006, 1998. arXiv. [cited by applicant]
Giles, Brett and Selinger, Peter; Exact synthesis of multiqubit clifford+ t circuits; Physical Review A, 87(3):032332, 2013. [cited by applicant]
Jones, Cody; Low-overhead constructions for the fault-tolerant toffoli gate; Physical Review A, 87(2):022328, 2013. [cited by applicant]
Kitaev, A Yu; Fault-tolerant quantum computation by anyons; Annals of Physics, 303(1):2-30, 2003. [cited by applicant]
Kliuchnikov, Vadym; Synthesis of unitaries with clifford+ t circuits; arXiv preprint arXiv:1306.3200, 2013. [cited by applicant]
Kliuchnikov, Vadym; Maslov, Dmitri and Mosca, Michele; Fast and efficient exact synthesis of single qubit unitaries generated by clifford and t gates; arXiv preprint arXiv:1206.5236, 2012. [cited by applicant]
Kliuchnikov, Vadym; Maslov, Dmitri and Mosca, Michele; Asymptotically optimal approximation of single qubit unitaries by clifford and t circuits using a constant number of ancillary qubits; Physical review letters, 110(… [cited by applicant]
Kliuchnikov, Vadym; Maslov, Dmitri and Mosca, Michele; Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and t gates; Quantum Information & Computation, 13(7-8):607-630, 2013. [cited by applicant]
Le Gall, François; Powers of tensors and fast matrix multiplication7; In Proceedings of the 39th international symposium on symbolic and algebraic computation, pp. 296-303. ACM, 2014. [cited by applicant]
Maslov, Dmitri; Advantages of using relative-phase toffoli gates with an applicationto multiple control toffoli optimization; Physical Review A, 93(2):022311, 2016. [cited by applicant]
Paetznick, Adam and Reichardt, Ben W.; Universal fault-tolerant quantum computation with only transversal gates and error correction; Physical review letters, 111(9):090505, 2013. [cited by applicant]
Paetznick, Adam and Svore, Krysta M.; Repeat-until-success: non-deterministic decomposition of single-qubit unitaries; Quantum Information & Computation, 14(1516):1277-1301, 2014. [cited by applicant]
Rigetti, Chad et al; Superconducting qubit in a waveguide cavity with a coherence time approaching 0.1 ms; Physical Review B, 86(10):100506, 2012. [cited by applicant]
Ross, Neil J. and Selinger, Peter; Optimal ancilla-free clifford+ t approximation of z rotations; Quantum Information & Computation, 16(11-12):901-953, 2016. [cited by applicant]
Selinger, Peter; Quantum circuits of t-depth one; Physical Review A, 87(4):042302, 2013. [cited by applicant]
Selinger, Peter, Efficient clifford+ t approximation of single-qubit operators; Quantum Information & Computation, 15(1-2):159-180, 2015. [cited by applicant]
Shor, Peter W.; Algorithms for quantum computation: Discrete logarithms and factoring; In Proceedings 35th annual symposium on foundations of computer science, pp. 124-134. Ieee, 1994. [cited by applicant]
Shor, Peter W.; Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303-332, 1999. [cited by applicant]
Gheorghiu, Vlad; Mosca, Michele and Mukhopadhyay, Priyanka; A quasi-polynomial time heuristic algorithm for synthesizing T-depth optimal circuits, arXiv preprint arXiv:2101.03142, 2021. [cited by applicant]
Mosca, Michele and Mukhopadhyay, Priyanka; A polynomial time and space algorithm for t-count.arXiv preprint arXiv:2006.12440, 2020. [cited by applicant]
Ozols, Maris; Clifford group; Essays at University of Waterloo, Spring, 2008. [cited by applicant]