The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in quantum error correction, randomized benchmarking protocols, and the study of entanglement. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity. First, we consider circuit optimization based on template matching and design Clifford-specific templates that leverage the ability to factor out Pauli and SWAP gates. Second, we introduce a symbolic peephole optimization method. It works by projecting the full circuit onto a small subset of qubits and optimally recompiling the projected subcircuit via dynamic programming. CNOT gates coupling the chosen subset of qubits with the remaining qubits are expressed using symbolic Pauli gates. Software implementation of these methods finds circuits that are only 0.2% away from optimal for 6 qubits and reduces the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average, compared with the Aaronson-Gottesman canonical form.
 Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery. 10.1145/3188745.3188802.
 Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5), November 2004. 10.1103/PhysRevA.70.052328.
 Dorit Aharonov, Itai Arad, and Sandy Irani. Efficient algorithm for approximating one-dimensional ground states. Physical Review A, 82 (1): 012315, 2010. 10.1103/PhysRevA.82.012315.
 Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state entanglement and quantum error correction. Physical Review A, 54 (5): 3824, 1996. 10.1103/PhysRevA.54.3824.
 Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/PhysRevA.71.022316.
 Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the Clifford group. IEEE Transactions on Information Theory, 67 (7): 4546–4563, 2021. 10.1109/TIT.2021.3081415.
 Richard Cleve, Debbie Leung, Li Liu, and Chunhao Wang. Near-linear constructions of exact unitary 2-designs. Quantum Information and Computation, 16 (9 & 10): 0721–0756, 2016.
 Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80 (1): 012304, 2009. 10.1103/PhysRevA.80.012304.
 Shantanu Debnath, Norbert M. Linke, Caroline Figgatt, Kevin A. Landsman, Kevin Wright, and Christopher Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536 (7614): 63–66, 2016. 10.1038/nature18648.
 Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic simplification of quantum circuits with the ZX-calculus. Quantum, 4: 279, 2020. 10.22331/q-2020-06-04-279.
 Timothee Goubaultdebrugiere, Marc Baboulin, Benoit Valiron, Simon Martiel, and Cyril Allouche. Reducing the depth of linear reversible quantum circuits. IEEE Transactions on Quantum Engineering, 2021. 10.1109/TQE.2021.3091648.
 Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16: 1050––1057, 2020. 10.1038/s41567-020-0932-7.
 Emanuel Knill, Dietrich Leibfried, Rolf Reichle, Joe Britton, R. Brad Blakestad, John D. Jost, Chris Langer, Roee Ozeri, Signe Seidelin, and David J. Wineland. Randomized benchmarking of quantum gates. Physical Review A, 77 (1): 012307, 2008. 10.1103/PhysRevA.77.012307.
 Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Physical Review Letters, 106 (18): 180504, 2011. 10.1103/PhysRevLett.106.180504.
 Dmitri Maslov, D. Michael Miller, Gerhard W. Dueck, and Camille Negrevergne. Quantum circuit simplification and level compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27 (3): 436–444, March 2008. 10.1109/TCAD.2007.911334.
 Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8 (3): 282–294, March 2008. ISSN 1533-7146.
 Aditya K. Prasad, Vivek V. Shende, Igor L. Markov, John P. Hayes, and Ketan N. Patel. Data structures and algorithms for simplifying reversible circuits. ACM Journal on Emerging Technologies in Computing Systems, 2 (4): 277–293, October 2006. 10.1145/1216396.1216399.
 Kanav Setia, Richard Chen, Julia E. Rice, Antonio Mezzacapo, Marco Pistoia, and James D. Whitfield. Reducing qubit requirements for quantum simulations using molecular point group symmetries. Journal of Chemical Theory and Computation, 16 (10): 6091–6097, 2020. 10.1021/acs.jctc.0c00113.
 Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t$|$ket$>$: a retargetable compiler for NISQ devices. Quantum Science and Technology, 6 (1): 014003, 2020. 10.1088/2058-9565/ab8e92.
 Ewout van den Berg and Kristan Temme. Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters. Quantum, 4: 322, 2020. 10.22331/q-2020-09-12-322.
 Ruslan Shaydulin and Alexey Galda, 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 291 (2021) ISBN:978-1-6654-1691-7.
 Toshinari Itoko and Rudy Raymond, 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 188 (2021) ISBN:978-1-6654-1691-7.
The above citations are from Crossref's cited-by service (last updated successfully 2023-02-04 09:58:55) and SAO/NASA ADS (last updated successfully 2023-02-04 09:58:56). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.