On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
arXiv:1508.03273 · doi:10.1103/PhysRevA.93.022311
Abstract
Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over regular Toffoli gate is their smaller circuit size. However, their use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative phase deviations would prevent the relative phase Toffolis from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the CNOT-count, T-count, as well as the number of ancillae used. We suggest that a further study of the relative phase Toffoli implementations and their use may yield other optimizations.
14 pages
References in corpus (3)
Cited by in corpus (78)
- Toward the first quantum simulation with quantum speedup
- Quantum Computer Systems for Scientific Discovery
- Accelerated Variational Quantum Eigensolver
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Automated optimization of large quantum circuits with continuous parameters
- Basic circuit compilation techniques for an ion-trap quantum machine
- Towards Large-scale Functional Verification of Universal Quantum Circuits
- High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
- Quantum Computing for Neutrino-nucleus Scattering
- Variational quantum algorithm based on the minimum potential energy for solving the Poisson equation
- Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
- Distributed Quantum Computing and Network Control for Accelerated VQE
- Verifying Results of the IBM Qiskit Quantum Circuit Compilation Flow
- Scalable algorithm simplification using quantum AND logic
- Use of global interactions in efficient quantum circuit constructions
- T-count optimization and Reed-Muller codes
- Equivalence Checking of Quantum Circuits with the ZX-Calculus
- Quantum Circuits for Sparse Isometries
- Measurement-free fault-tolerant quantum error correction in near-term devices
- Implementation of efficient quantum search algorithms on NISQ computers
- Constrained Optimization via Quantum Zeno Dynamics
- Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
- MQT QMAP: Efficient Quantum Circuit Mapping
- Grover search revisited; application to image pattern matching
- Constructing quantum circuits with global gates
- SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation
- Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers
- Resource-Optimized Fermionic Local-Hamiltonian Simulation on Quantum Computer for Quantum Chemistry
- Linear and logarithmic time compositions of quantum many-body operators
- Qudits for decomposing multiqubit gates and realizing quantum algorithms
- Variational Quantum-Based Simulation of Waveguide Modes
- Efficient variational synthesis of quantum circuits with coherent multi-start optimization
- Subdivided Phase Oracle for NISQ Search Algorithms
- Decision Diagrams for Quantum Computing
- One-step implementation of Toffoli gate for neutral atoms based on unconventional Rydberg pumping
- Fault-tolerant measurement-free quantum error correction with multi-qubit gates
- Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
- Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
- Quantum search on noisy intermediate-scale quantum devices
- Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
- Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
- Application of Permutation Group Theory in Reversible Logic Synthesis
- High-Round QAOA for MAX -SAT on Trapped Ion NISQ Devices
- Logic Synthesis for Quantum Computing
- Partial Equivalence Checking of Quantum Circuits
- Power-optimal, stabilized entangling gate between trapped-ion qubits
- Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
- Uncomputation in the Qrisp high-level Quantum Programming Framework
- Direct Implementation of High-Fidelity Three-Qubit Gates for Superconducting Processor with Tunable Couplers
- Signal processing techniques for efficient compilation of controlled rotations in trapped ions
- The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
- The phase/state duality in reversible circuit design
- Linear and non-linear relational analyses for Quantum Program Optimization
- Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach
- Automatic Post-selection by Ancillae Thermalisation
- Neural-network-designed three-qubit gates robust against charge noise and crosstalk in silicon
- Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer
- Characterization, synthesis, and optimization of quantum circuits over multiple-control -rotation gates: A systematic study
- Quasiprobability fluctuation theorem behind the spread of quantum information
- Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
- Quantum-accelerated algorithms for generating random primitive polynomials over finite fields
- Quantum State Preparation Using an Exact CNOT Synthesis Formulation
- Linear decomposition of approximate multi-controlled single qubit gates
- Quantum Circuit for Random Forest Prediction
- Applying Grover's algorithm to AES: quantum resource estimates
- Efficient unstructured search implementation on current ion-trap quantum processors
- High-precision and low-depth quantum algorithm design for eigenstate problems
- Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
- Design Automation and Design Space Exploration for Quantum Computers
- qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking
- Classification and transformations of quantum circuit decompositions for permutation operations
- Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
- Constructing all qutrit controlled Clifford+T gates in Clifford+T
- A T-depth two Toffoli gate for 2D square lattice architectures
- Quantum Circuits in Additive Hilbert Space
- ROS: Resource-constrained Oracle Synthesis for Quantum Computers
- Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
- Ancilla-Input and Garbage-Output Optimized Design of a Reversible Quantum Integer Multiplier