Phase polynomials synthesis algorithms for NISQ architectures and beyond

Abstract

We present a framework for the synthesis of phase polynomials that addresses both cases of full connectivity and partial connectivity for NISQ architectures. In most cases, our algorithms generate circuits with lower CNOT count and CNOT depth than the state of the art or have a significantly smaller running time for similar performances. We also provide methods that can be applied to our algorithms in order to trade an increase in the CNOT count for a decrease in execution time, thereby filling the gap between our algorithms and faster ones.

References in corpus (26)

• Quantum Computing in the NISQ era and beyond
• A Quantum Approximate Optimization Algorithm
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Roads towards fault-tolerant universal quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Experimental Comparison of Two Quantum Computing Architectures
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Automated optimization of large quantum circuits with continuous parameters
• Reducing T-count with the ZX-calculus
• Quantum Circuit Placement
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Quantum circuit optimizations for NISQ architectures
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• staq -- A full-stack quantum processing toolkit
• On the CNOT-complexity of CNOT-PHASE circuits
• Circuit Transformations for Quantum Architectures
• Optimization of Lattice Surgery is NP-Hard
• A polynomial time and space heuristic algorithm for T-count
• Quantum circuits and low-degree polynomials over F_2
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Architecture aware compilation of quantum circuits via lazy synthesis
• An algorithm for the T-count
• Efficient CNOT Synthesis for NISQ Devices

Cited by in corpus (9)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation
• Lower T-count with faster algorithms
• On the role of coherence for quantum computational advantage
• The Parity Flow Formalism: Tracking Quantum Information Throughout Computation
• A graph-state based synthesis framework for Clifford isometries
• Quantum Circuits in Additive Hilbert Space