Global Synthesis of CNOT Circuits with Holes

Abstract

A common approach to quantum circuit transformation is to use the properties of a specific gate set to create an efficient representation of a given circuit's unitary, such as a parity matrix or stabiliser tableau, and then resynthesise an improved circuit, e.g. with fewer gates or respecting connectivity constraints. Since these methods rely on a restricted gate set, generalisation to arbitrary circuits usually involves slicing the circuit into pieces that can be resynthesised and working with these separately. The choices made about what gates should go into each slice can have a major effect on the performance of the resynthesis. In this paper we propose an alternative approach to generalising these resynthesis algorithms to general quantum circuits. Instead of cutting the circuit into slices, we "cut out" the gates we can't resynthesise leaving holes in our quantum circuit. The result is a second-order process called a quantum comb, which can be resynthesised directly. We apply this idea to the RowCol algorithm, which resynthesises CNOT circuits for topologically constrained hardware, explaining how we were able to extend it to work for quantum combs. We then compare the generalisation of RowCol using our method to the naive "slice and build" method empirically on a variety of circuit sizes and hardware topologies. Finally, we outline how quantum combs could be used to help generalise other resynthesis algorithms.

arXiv commentIn Proceedings QPL 2023, arXiv:2308.15489

References in corpus (13)

• Improved Simulation of Stabilizer Circuits
• Quantum Circuits Architecture
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Quantum circuit optimizations for NISQ architectures
• Semicausal operations are semilocalizable
• Scalable quantum computer with superconducting circuits in the ultrastrong coupling regime
• On the qubit routing problem
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Optimization of CNOT circuits on limited connectivity architecture
• Architecture aware compilation of quantum circuits via lazy synthesis
• Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures