Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates

Shelly Garion1 and Andrew W. Cross2

1IBM Quantum, IBM Research Haifa, Haifa University Campus, Mount Carmel, Haifa, 3498825, Israel
2IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In this note we present explicit canonical forms for all the elements in the two-qubit CNOT-Dihedral group, with minimal numbers of controlled-$S$ ($CS$) and controlled-$X$ ($CX$) gates, using the generating set of quantum gates $[X, T, CX, CS]$. We provide an algorithm to successively construct the $n$-qubit CNOT-Dihedral group, asserting an optimal number of controlled-$X$ ($CX$) gates. These results are needed to estimate gate errors via non-Clifford randomized benchmarking and may have further applications to circuit optimization over fault-tolerant gate sets.

CNOT-Dihedral circuits are certain quantum circuits that are generated using the quantum gates X, T and controlled-X (CX). These circuits can be efficiently simulated in polynomial time using a classical computer and have applications for quantum error correction codes and for estimating quantum gate errors using a benchmarking process. It is therefore important to efficiently synthesize CNOT-Dihedral circuits using a minimal number of physical basic gates, in particular, two-qubit gates.
In this note we characterize all the two-qubit CNOT-Dihedral circuits, allowing a synthesis of such circuits with optimal number of certain two-qubit gates, and provide an algorithm to successively construct n-qubit CNOT-Dihedral circuits, asserting an optimal number of CX gates.

► BibTeX data

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70: 052328, Nov 2004. 10.1103/​PhysRevA.70.052328. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.70.052328.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[2] M. Amy, D. Maslov, M. Mosca, and M. Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32 (6): 818–830, 2013. 10.1109/​TCAD.2013.2244643.
https:/​/​doi.org/​10.1109/​TCAD.2013.2244643

[3] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology, 4 (1): 015002, sep 2018a. 10.1088/​2058-9565/​aad8ca. URL https:/​/​doi.org/​10.1088.
https:/​/​doi.org/​10.1088/​2058-9565/​aad8ca

[4] Matthew Amy, Jianxin Chen, and Neil J. Ross. A finite presentation of cnot-dihedral operators. Electronic Proceedings in Theoretical Computer Science, 266: 84–97, 2018b. 10.4204/​eptcs.266.5. URL https:/​/​app.dimensions.ai/​details/​publication/​pub.1101260386 and https:/​/​arxiv.org/​pdf/​1701.00140.
https:/​/​doi.org/​10.4204/​eptcs.266.5
https:/​/​app.dimensions.ai/​details/​publication/​pub.1101260386%20%20and%20https:/​/​arxiv.org/​pdf/​1701.00140

[5] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52: 3457–3467, Nov 1995. 10.1103/​PhysRevA.52.3457. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.52.3457.
https:/​/​doi.org/​10.1103/​PhysRevA.52.3457

[6] H. Bombin and M. A. Martin-Delgado. Topological computation without braiding. Phys. Rev. Lett., 98: 160502, Apr 2007. 10.1103/​PhysRevLett.98.160502. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.98.160502.
https:/​/​doi.org/​10.1103/​PhysRevLett.98.160502

[7] Héctor Bombín. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New Journal of Physics, 17 (8): 083002, aug 2015. 10.1088/​1367-2630/​17/​8/​083002. URL https:/​/​doi.org/​10.1088.
https:/​/​doi.org/​10.1088/​1367-2630/​17/​8/​083002

[8] Sergey Bravyi. Compiling clifford operators.

[9] Sergey Bravyi and Robert König. Classification of topologically protected gates for local stabilizer codes. Phys. Rev. Lett., 110: 170503, Apr 2013. 10.1103/​PhysRevLett.110.170503. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.110.170503.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.170503

[10] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group, 2020. URL https:/​/​arxiv.org/​abs/​2003.09412.
arXiv:2003.09412

[11] Earl T. Campbell and Mark Howard. Unifying gate synthesis and magic state distillation. Phys. Rev. Lett., 118: 060501, Feb 2017. 10.1103/​PhysRevLett.118.060501. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.118.060501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.060501

[12] Arnaud Carignan-Dugas, Joel J. Wallman, and Joseph Emerson. Characterizing universal gate sets via dihedral benchmarking. Phys. Rev. A, 92: 060302, Dec 2015. 10.1103/​PhysRevA.92.060302. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.92.060302.
https:/​/​doi.org/​10.1103/​PhysRevA.92.060302

[13] A. D. Córcoles, Jay M. Gambetta, Jerry M. Chow, John A. Smolin, Matthew Ware, Joel Strand, B. L. T. Plourde, and M. Steffen. Process verification of two-qubit quantum gates by randomized benchmarking. Phys. Rev. A, 87: 030301, Mar 2013. 10.1103/​PhysRevA.87.030301. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.87.030301.
https:/​/​doi.org/​10.1103/​PhysRevA.87.030301

[14] Andrew W Cross, Easwar Magesan, Lev S Bishop, John A Smolin, and Jay M Gambetta. Scalable randomised benchmarking of non-clifford gates. npj Quantum Information, 2 (1), 2016. 10.1038/​npjqi.2016.12. URL https:/​/​doi.org/​10.1038/​npjqi.2016.12.
https:/​/​doi.org/​10.1038/​npjqi.2016.12

[15] Meuli G., Soeken M., and De Micheli G. Sat-based CNOT, T quantum circuit synthesis. Kari J., Ulidowski I. (eds) Reversible Computation. RC 2018. Lecture Notes in Computer Science, 11106, 2018. 10.1007/​978-3-319-99498-7_12.
https:/​/​doi.org/​10.1007/​978-3-319-99498-7_12

[16] Shelly Garion, Naoki Kanazawa, Haggai Landa, David C. McKay, Sarah Sheldon, Andrew W. Cross, and Christopher J. Wood. Experimental implementation of non-clifford interleaved randomized benchmarking with a controlled-s gate, 2020. URL https:/​/​arxiv.org/​abs/​2007.08532.
arXiv:2007.08532

[17] Andrew N. Glaudell, Neil J. Ross, and Jacob M. Taylor. Optimal two-qubit circuits for universal fault-tolerant quantum computation, 2020. URL https:/​/​arxiv.org/​abs/​2001.05997.
arXiv:2001.05997

[18] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo. An algorithm for the t-count. Quantum Info. Comput., 14 (15–16): 1261–1276, November 2014. ISSN 1533-7146. URL https:/​/​dl.acm.org/​doi/​10.5555/​2685179.2685180.
https:/​/​dl.acm.org/​doi/​10.5555/​2685179.2685180

[19] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402: 390–393, 1999. ISSN 1476-4687. 10.1038/​46503. URL https:/​/​doi.org/​10.1038/​46503.
https:/​/​doi.org/​10.1038/​46503

[20] Daniel Eric Gottesman. Stabilizer codes and quantum error correction, 1997. URL https:/​/​resolver.caltech.edu/​CaltechETD:etd-07162004-113028. https:/​/​arxiv.org/​abs/​quant-ph/​9705052v1.
arXiv:quant-ph/9705052v1
https:/​/​resolver.caltech.edu/​CaltechETD:etd-07162004-113028

[21] Luke E Heyfron and Earl T Campbell. An efficient quantum compiler that reduces t count. Quantum Science and Technology, 4 (1): 015004, sep 2018. 10.1088/​2058-9565/​aad604. URL https:/​/​doi.org/​10.1088.
https:/​/​doi.org/​10.1088/​2058-9565/​aad604

[22] Tomas Jochym-O'Connor, Aleksander Kubica, and Theodore J. Yoder. Disjointness of stabilizer codes and limitations on fault-tolerant logical gates. Phys. Rev. X, 8: 021047, May 2018. 10.1103/​PhysRevX.8.021047. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevX.8.021047.
https:/​/​doi.org/​10.1103/​PhysRevX.8.021047

[23] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland. Randomized benchmarking of quantum gates. Phys. Rev. A, 77: 012307, Jan 2008. 10.1103/​PhysRevA.77.012307. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.77.012307.
https:/​/​doi.org/​10.1103/​PhysRevA.77.012307

[24] Easwar Magesan, J. M. Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Phys. Rev. Lett., 106: 180504, May 2011. 10.1103/​PhysRevLett.106.180504. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.106.180504.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.180504

[25] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Phys. Rev. A, 85: 042311, Apr 2012a. 10.1103/​PhysRevA.85.042311. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.85.042311.
https:/​/​doi.org/​10.1103/​PhysRevA.85.042311

[26] Easwar Magesan, Jay M. Gambetta, B. R. Johnson, Colm A. Ryan, Jerry M. Chow, Seth T. Merkel, Marcus P. da Silva, George A. Keefe, Mary B. Rothwell, Thomas A. Ohki, Mark B. Ketchen, and M. Steffen. Efficient measurement of quantum gate error by interleaved randomized benchmarking. Phys. Rev. Lett., 109: 080505, Aug 2012b. 10.1103/​PhysRevLett.109.080505. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.109.080505.
https:/​/​doi.org/​10.1103/​PhysRevLett.109.080505

[27] D. Maslov and M. Roetteler. Shorter stabilizer circuits via bruhat decomposition and quantum circuit transformations. IEEE Transactions on Information Theory, 64 (7): 4729–4738, 2018. 10.1109/​TIT.2018.2825602.
https:/​/​doi.org/​10.1109/​TIT.2018.2825602

[28] David C. McKay, Stefan Filipp, Antonio Mezzacapo, Easwar Magesan, Jerry M. Chow, and Jay M. Gambetta. Universal gate for fixed-frequency qubits via a tunable bus. Phys. Rev. Applied, 6: 064007, Dec 2016. 10.1103/​PhysRevApplied.6.064007. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevApplied.6.064007.
https:/​/​doi.org/​10.1103/​PhysRevApplied.6.064007

[29] Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. 4: 23, 2018. ISSN 2056-6387. 10.1038/​s41534-018-0072-4. URL https:/​/​doi.org/​10.1038/​s41534-018-0072-4.
https:/​/​doi.org/​10.1038/​s41534-018-0072-4

[30] Neil J. Ross and Peter Selinger. Optimal ancilla-free clifford + t approximation of z-rotations. Quantum Info. Comput., 16 (11–12): 901–953, September 2016. ISSN 1533-7146. URL https:/​/​dl.acm.org/​doi/​abs/​10.5555/​3179330.3179331.
https:/​/​dl.acm.org/​doi/​abs/​10.5555/​3179330.3179331

[31] Joel Wallman, Chris Granade, Robin Harper, and Steven T Flammia. Estimating the coherence of noise. New Journal of Physics, 17 (11): 113020, nov 2015. 10.1088/​1367-2630/​17/​11/​113020. URL https:/​/​doi.org/​10.1088.
https:/​/​doi.org/​10.1088/​1367-2630/​17/​11/​113020

[32] Christopher J. Wood and Jay M. Gambetta. Quantification and characterization of leakage errors. Phys. Rev. A, 97: 032306, Mar 2018. 10.1103/​PhysRevA.97.032306. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.97.032306.
https:/​/​doi.org/​10.1103/​PhysRevA.97.032306

[33] Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. Qfast: Quantum synthesis using a hierarchical continuous circuit space, 2020. URL https:/​/​arxiv.org/​abs/​2003.04462.
arXiv:2003.04462

[34] B. Zeng, A. Cross, and I. L. Chuang. Transversality versus universality for additive quantum codes. IEEE Transactions on Information Theory, 57 (9): 6272–6284, 2011. 10.1109/​TIT.2011.2161917.
https:/​/​doi.org/​10.1109/​TIT.2011.2161917

Cited by

[1] Shelly Garion, Naoki Kanazawa, Haggai Landa, David C. McKay, Sarah Sheldon, Andrew W. Cross, and Christopher J. Wood, "Experimental implementation of non-Clifford interleaved randomized benchmarking with a controlled- S gate", Physical Review Research 3 1, 013204 (2021).

[2] Jahan Claes and Shruti Puri, "Estimating the Bias of CX Gates via Character Randomized Benchmarking", PRX Quantum 4 1, 010307 (2023).

[3] Andrew N. Glaudell, Neil J. Ross, and Jacob M. Taylor, "Optimal two-qubit circuits for universal fault-tolerant quantum computation", npj Quantum Information 7 1, 103 (2021).

[4] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", Electronic Proceedings in Theoretical Computer Science 384, 114 (2023).

[5] Mohannad Ibrahim, Nicholas T. Bronn, and Gregory T. Byrd, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 39 (2023) ISBN:979-8-3503-4323-6.

[6] Jin-Sung Kim, Lev S. Bishop, Antonio D. Córcoles, Seth Merkel, John A. Smolin, and Sarah Sheldon, "Hardware-efficient random circuits to classify noise in a multiqubit system", Physical Review A 104 2, 022609 (2021).

[7] Liam Madden and Andrea Simonetto, "Best Approximate Quantum Compiling Problems", arXiv:2106.05649, (2021).

[8] Ellen Derbyshire, Rawad Mezher, Theodoros Kapourniotis, and Elham Kashefi, "Randomized Benchmarking with Stabilizer Verification and Gate Synthesis", arXiv:2102.13044, (2021).

[9] Mohannad Ibrahim, Nicholas T. Bronn, and Gregory T. Byrd, "Crosstalk-Based Parameterized Quantum Circuit Approximation", arXiv:2305.04172, (2023).

[10] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", arXiv:2306.08530, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-19 04:16:38) and SAO/NASA ADS (last updated successfully 2024-03-19 04:16:39). The list may be incomplete as not all publishers provide suitable and complete citation data.