QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis
arXiv:2012.09835
Abstract
The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.
References in corpus (31)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- A Quantum Approximate Optimization Algorithm
- Quantum Algorithms Revisited
- Two-Bit Gates are Universal for Quantum Computation
- Dynamical Quantum Phase Transitions in the Transverse Field Ising Model
- Training Schrödinger's cat: quantum optimal control
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Quantum advantage with shallow circuits
- tket : A Retargetable Compiler for NISQ Devices
- A new quantum ripple-carry addition circuit
- Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- Exact synthesis of multiqubit Clifford+T circuits
- ScaffCC: Scalable Compilation and Analysis of Quantum Programs
- Efficient synthesis of universal Repeat-Until-Success circuits
- Phonon-derived ultrafast relaxation of spin-valley polarized states in MoS_{2}
- Quantum factoring, discrete logarithms and the hidden subgroup problem
- Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers
- Quantum Circuit Placement
- Compiling quantum algorithms for architectures with multi-qubit gates
- Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
- Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning
- An Introduction to Cartan's KAK Decomposition for QC Programmers
- Approximate Quantum Circuit Synthesis using Block-Encodings
- The block-ZXZ synthesis of an arbitrary quantum circuit
- QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space
- On an implementation of the Solovay-Kitaev algorithm