On the CNOT-complexity of CNOT-PHASE circuits

Abstract

We study the problem of CNOT-optimal quantum circuit synthesis over gate sets consisting of CNOT and Z-basis rotations of arbitrary angles. We show that the circuit-polynomial correspondence relates such circuits to Fourier expansions of pseudo-Boolean functions, and that for certain classes of functions this expansion uniquely determines the minimum CNOT cost of an implementation. As a corollary we prove that CNOT minimization over CNOT and phase gates is at least as hard as synthesizing a CNOT-optimal circuit computing a set of parities of its inputs. We then show that this problem is NP-complete for two restricted cases where all CNOT gates are required to have the same target, and where the circuit inputs are encoded in a larger state space. The latter case has applications to CNOT optimization over more general Clifford+T circuits. We further present an efficient heuristic algorithm for synthesizing circuits over CNOT and Z-basis rotations with small CNOT cost. Our experiments show a 23% reduction of CNOT gates on average across a suite of Clifford+T benchmark circuits, with a maximum reduction of 43%.

arXiv comment21 pages, 5 figures, 1 table. Version 2 formally verifies the correctness of the benchmark optimizations, 4 out of 39 are left unverified due to size, Quantum Science and Technology, 2018

References in corpus (13)

• A Theory of Fault-Tolerant Quantum Computation
• Demonstration of a small programmable quantum computer with atomic qubits
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• High threshold universal quantum computation on the surface code
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum circuits of T-depth one
• Automated optimization of large quantum circuits with continuous parameters
• Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas
• Unifying gate-synthesis and magic state distillation
• Optimization of Lattice Surgery is NP-Hard
• Quantum circuits and low-degree polynomials over F_2
• A Finite Presentation of CNOT-Dihedral Operators
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique

Cited by in corpus (42)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Reducing T-count with the ZX-calculus
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• A Verified Optimizer for Quantum Circuits
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• staq -- A full-stack quantum processing toolkit
• Quantum Instruction Set Design for Performance
• Reducing the Depth of Linear Reversible Quantum Circuits
• A polynomial time and space heuristic algorithm for T-count
• Synthesis of and compilation with time-optimal multi-qubit gates
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• The Impact of Imperfect Timekeeping on Quantum Control
• Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices
• Synthesizing efficient circuits for Hamiltonian simulation
• Robustness of quantum algorithms against coherent control errors
• Classical simulation of quantum circuits by half Gauss sums
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• Architecture aware compilation of quantum circuits via lazy synthesis
• Experimental implementation of quantum algorithm for association rules mining
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• A Case for Synthesis of Recursive Quantum Unitary Programs
• The phase/state duality in reversible circuit design
• Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation
• Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation
• Multi-controlled Phase Gate Synthesis with ZX-calculus applied to Neutral Atom Hardware
• Lower T-count with faster algorithms
• On the role of coherence for quantum computational advantage
• Approximate real-time evolution operator for potential with one ancillary qubit and application to first-quantized Hamiltonian simulation
• A graph-state based synthesis framework for Clifford isometries
• The Parity Flow Formalism: Tracking Quantum Information Throughout Computation
• Minimum Synthesis Cost of CNOT Circuits
• ROS: Resource-constrained Oracle Synthesis for Quantum Computers
• Quantum circuit synthesis with SQiSW
• Resource-Efficient Quantum Optimization via Higher-Order Encoding