Synthesis of Quantum Logic Circuits
arXiv:quant-ph/0406176 · doi:10.1109/TCAD.2005.855930
Abstract
We discuss efficient quantum logic circuits which perform two tasks: (i) implementing generic quantum computations and (ii) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state-space of an n-qubit register is not finite and contains exponential superpositions of classical bit strings. Our proposed circuits are asymptotically optimal for respective tasks and improve published results by at least a factor of two. The circuits for generic quantum computation constructed by our algorithms are the most efficient known today in terms of the number of expensive gates (quantum controlled-NOTs). They are based on an analogue of the Shannon decomposition of Boolean functions and a new circuit block, quantum multiplexor, that generalizes several known constructions. A theoretical lower bound implies that our circuits cannot be improved by more than a factor of two. We additionally show how to accommodate the severe architectural limitation of using only nearest-neighbor gates that is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.
18 pages; v5 fixes minor bugs; v4 is a complete rewrite of v3, with 6x more content, a theory of quantum multiplexors and Quantum Shannon Decomposition. A key result on generic circuit synthesis has been improved to ~23/48*4^n CNOTs for n qubits
References in corpus (20)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- Two-Bit Gates are Universal for Quantum Computation
- On the role of entanglement in quantum computational speed-up
- Optimal Quantum Circuits for General Two-Qubit Gates
- Quantum Circuits for General Multiqubit Gates
- Universality in Quantum Computation
- Minimal Universal Two-qubit Quantum Circuits
- A universal quantum circuit for two-qubit transformations with three CNOT gates
- Efficient decomposition of quantum gates
- Approximation by Quantum Circuits
- Exact two-qubit universal quantum circuit
- Recognizing Small-Circuit Structure in Two-Qubit Operators and Timing Hamiltonians to Compute Controlled-Not Gates
- An Arbitrary Two-qubit Computation In 23 Elementary Gates
- A Rudimentary Quantum Compiler
- A Quantum Computer Architecture using Nonlocal Interactions
- Realization of a General Three-Qubit Quantum Gate
- Compiling Quantum Circuits using the Palindrome Transform
- Smaller Circuits for Arbitrary n-qubit Diagonal Computations
Cited by in corpus (275)
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Toward the first quantum simulation with quantum speedup
- Qudits and high-dimensional quantum computing
- Quantum autoencoders for efficient compression of quantum data
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Quantum-state preparation with universal gate decompositions
- Variational quantum algorithms for nonlinear problems
- Synthesis and Optimization of Reversible Circuits - A Survey
- Low Depth Quantum Simulation of Electronic Structure
- Quantum Circuit Simplification and Level Compaction
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Automated Search for new Quantum Experiments
- The Bitter Truth About Quantum Algorithms in the NISQ Era
- Option Pricing using Quantum Computers
- Quantum Circuits for Isometries
- Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
- Challenges and Opportunities of Near-Term Quantum Computing Systems
- Emerging quantum computing algorithms for quantum chemistry
- A divide-and-conquer algorithm for quantum state preparation
- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
- High-precision quantum algorithms for partial differential equations
- Quantum Algorithm for Linear Regression
- Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
- Reversible Circuit Synthesis Using a Cycle-Based Approach
- Quantum algorithm for simulating real time evolution of lattice Hamiltonians
- Lower bounds on the non-Clifford resources for quantum computations
- Quantum Simulation of Open Quantum Systems Using a Unitary Decomposition of Operators
- Quantum control of bosonic modes with superconducting circuits
- Deterministic Preparation of Dicke States
- Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
- Biology and medicine in the landscape of quantum advantages
- Universal discriminative quantum neural networks
- Global optimization of quantum dynamics with AlphaZero deep exploration
- Requirements for fault-tolerant factoring on an atom-optics quantum computer
- Optimized Quantum Circuit Partitioning
- Trading T gates for dirty qubits in state preparation and unitary synthesis
- Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
- Synthesis of Multivalued Quantum Logic Circuits by Elementary Gates
- Simple factorization of unitary transformations
- Universal qudit gate synthesis for transmons
- Non-Abelian Floquet Spin Liquids in a Digital Rydberg Simulator
- Quantum Channel Construction with Circuit Quantum Electrodynamics
- Quantum linear systems algorithms: a primer
- A Library-Based Synthesis Methodology for Reversible Logic
- Quantum Circuit Design for Solving Linear Systems of Equations
- Optimizing quantum phase estimation for the simulation of Hamiltonian eigenstates
- Qudit Quantum Computation in the Jaynes-Cummings Model
- Synthesis of multi-qudit Hybrid and d-valued Quantum Logic Circuits by Decomposition
- Simulating Hadronic Physics on NISQ devices using Basis Light-Front Quantization
- Quantum algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method
- Efficient State Preparation for Quantum Amplitude Estimation
- Use of global interactions in efficient quantum circuit constructions
- Efficient compression of quantum information
- Approaching the theoretical limit in quantum gate decomposition
- Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer
- Efficient decomposition of unitary matrices in quantum circuit compilers
- Block-encoding structured matrices for data input in quantum computing
- Quantum Circuits for Sparse Isometries
- Variational quantum compiling with double Q-learning
- Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
- LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach
- Semi-Clifford operations, structure of hierarchy, and gate complexity for fault-tolerant quantum computation
- Highly Efficient Processing Multi-photon States
- Minimum Hardware Requirements for Hybrid Quantum-Classical DMFT
- Configurable sublinear circuits for quantum state preparation
- Optimal synthesis of the Fredkin gate in a multilevel system
- Probing confinement in a lattice gauge theory on a quantum computer
- Realization of quantum signal processing on a noisy quantum computer
- A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions
- Artificial Intelligence for Quantum Computing
- Lattice Boltzmann-Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number
- Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost
- Double sparse quantum state preparation
- Application of a variational hybrid quantum-classical algorithm to heat conduction equation
- Relativistic quantum chemistry on quantum computers
- Medium induced jet broadening in a quantum computer
- Grover search revisited; application to image pattern matching
- Realization of arbitrary discrete unitary transformations using spatial and internal modes of light
- Constructive Quantum Shannon Decomposition from Cartan Involutions
- Approximate Quantum Circuit Synthesis using Block-Encodings
- A variational quantum algorithm for the Feynman-Kac formula
- Variational Quantum Evolution Equation Solver
- Quantum Circuits for Quantum Channels
- Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods
- How many CNOT gates does it take to generate a three-qubit state ?
- Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
- Quantum integration of elementary particle processes
- An -depth Quantum Adder on a 2D NTC Quantum Computer Architecture
- Scattering in the Ising Model Using Quantum Lanczos Algorithm
- On the complexity of implementing Trotter steps
- Universal Programmable Quantum Circuit Schemes to Emulate an Operator
- DDMF: An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction
- Universal quantum multi-qubit entangling gates with auxiliary spaces
- On the experimental feasibility of quantum state reconstruction via machine learning
- Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
- Quantum circuit design for accurate simulation of qudit channels
- The block-ZXZ synthesis of an arbitrary quantum circuit
- Low-rank quantum state preparation
- Variational Quantum Linear Solver with Dynamic Ansatz
- QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space
- An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
- An efficient quantum algorithm for preparation of uniform quantum superposition states
- Quantum simulation of in-medium QCD jets: momentum broadening, gluon production, and entropy growth
- Preparing Valence-Bond-Solid states on noisy intermediate-scale quantum computers
- When Machine Learning Meets Quantum Computers: A Case Study
- Entanglement in highly symmetric multipartite quantum states
- Sachdev-Ye-Kitaev model on a noisy quantum computer
- Scalable Benchmarks for Gate-Based Quantum Computers
- Efficient Deterministic Preparation of Quantum States Using Decision Diagrams
- Primitive Quantum Gates for an SU(3) Discrete Subgroup:
- Efficient variational synthesis of quantum circuits with coherent multi-start optimization
- Optimal synthesis of multivalued quantum circuit
- Fixed-Depth Two-Qubit Circuits and the Monodromy Polytope
- Representation of binary classification trees with binary features by quantum circuits
- Hybrid Stabilizer Matrix Product Operator
- Decomposition of bipartite and multipartite unitary gates into the product of controlled unitary gates
- Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion
- Efficient Hamiltonian Simulation for Solving Option Price Dynamics
- Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
- Implementing efficient selective quantum process tomography of superconducting quantum gates on the IBM quantum processor
- Quantum Gaussian process regression
- Optimization of CNOT circuits on limited connectivity architecture
- Quantum algorithm for credit valuation adjustments
- Minimal computational-space implementation of multi-round quantum protocols
- Certification of quantum states with hidden structure of their bitstrings
- Approximate encoding of quantum states using shallow circuits
- Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
- Experimental implementation of optimal linear-optical controlled-unitary gates
- Towards optimization of quantum circuits
- Supervised Learning with Quantum Measurements
- Quantum circuit synthesis using Householder transformations
- On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
- Berry Phase Estimation in Gate-Based Adiabatic Quantum Simulation
- Quantum-classical eigensolver using multiscale entanglement renormalization
- Triply efficient shadow tomography
- Estimating Patterns of Classical and Quantum Skyrmion States
- Qutrit and Qubit Circuits for Three-Flavor Collective Neutrino Oscillations
- Data classification by quantum radial basis function networks
- An algorithm for DNA read alignment on quantum accelerators
- Quantum Logic Gate Synthesis as a Markov Decision Process
- A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
- Playing Atari with Hybrid Quantum-Classical Reinforcement Learning
- On quantum algorithms for the Schrödinger equation in the semi-classical regime
- Introduction to UniversalQCompiler
- A Regular Representation of Quantum Circuits
- Long-lived Particles Anomaly Detection with Parametrized Quantum Circuits
- An Ancilla Based Quantum Simulation Framework for Non-Unitary Matrices
- An analysis of reversible multiplier circuits
- Efficient and precise quantum simulation of ultra-relativistic quark-nucleus scattering
- Variational quantum state discriminator for supervised machine learning
- Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
- A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates
- Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers
- Automatic quantum circuit encoding of a given arbitrary quantum state
- Fundamental limitations for measurements in quantum many-body systems
- Simulating noisy quantum channels via quantum state preparation algorithms
- Supervised Learning Enhanced Quantum Circuit Transformation
- Efficient Quantum Lattice Gas Automata
- Encoding classical data into a quantum computer
- An algorithm for minimization of quantum cost
- Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm
- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
- Quantum state preparation for multivariate functions
- Quantum Computing Simulation of a Mixed Spin-Boson Hamiltonian and Its Performance for a Cavity Quantum Electrodynamics Problem
- Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs
- Universal classical optical computing inspired by quantum information process
- Quantum circuits for spin and flavor degrees of freedom of quarks forming nucleons
- Hybrid Genetic Optimisation for Quantum Feature Map Design
- Efficient quantum interpolation of natural data
- A Case for Synthesis of Recursive Quantum Unitary Programs
- Two-qudit topological phase evolution under dephasing
- Algebraic Characterization of CNOT-Based Quantum Circuits with its Applications on Logic Synthesis
- TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
- Solving reaction dynamics with quantum computing algorithms
- Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
- Scalable simulation of non-equilibrium quantum dynamics via classically optimised unitary circuits
- Robust and Resource-Efficient Quantum Circuit Approximation
- Simulation of positive operator-valued measures and quantum instruments via quantum state preparation algorithms
- Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
- Ansatz-Independent Variational Quantum Classifier
- Spin-s Dicke states and their preparation
- Implementation of a Quantum Algorithm to Estimate the Energy of a Particle in a Finite Square Well Potential on IBM Quantum Computer
- Reinforcement Learning Generation of 4-Qubits Entangled States
- Deep Quantum Circuit Simulations of Low-Energy Nuclear States
- Block encoding bosons by signal processing
- A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
- Generating Universal Adversarial Perturbations for Quantum Classifiers
- Efficient solution of the non-unitary time-dependent Schrodinger equation on a quantum computer with complex absorbing potential
- Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
- Anderson impurity solver integrating tensor network methods with quantum computing
- Quantum Pathways for Charged Track Finding in High-Energy Collisions
- Quantum Radio Astronomy: Data Encodings and Quantum Image Processing
- Streamlined Krylov construction and classification of ergodic Floquet systems
- Numerical circuit synthesis and compilation for multi-state preparation
- Defining Quantum Control Flow
- Optimization of Quantum Circuit Mapping using Gate Transformation and Commutation
- Optimisation-free Classification and Density Estimation with Quantum Circuits
- Quantum density estimation with density matrices: Application to quantum anomaly detection
- Algorithmic Primitives for Quantum-Assisted Quantum Control
- Quantum encoder for fixed Hamming-weight subspaces
- Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
- Synthesizing quantum circuits via numerical optimization
- Efficient Circuits for Exact-Universal Computations with Qudits
- An upper bound on the time required to implement unitary operations
- High-fidelity state transfer via quantum walks from delocalized states
- New designs of reversible sequential devices
- Quartic quantum speedups for planted inference
- Multi-controlled Phase Gate Synthesis with ZX-calculus applied to Neutral Atom Hardware
- Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
- Quantum Multiplexer Simplification for State Preparation
- Quantum-Logic Synthesis of Hermitian Gates
- Optimized synthesis of circuits for diagonal unitary matrices with reflection symmetry
- Compression of Entanglement Improves Quantum Communication
- Quantum eigenvalue processing
- An Amplitude-Based Implementation of the Unit Step Function on a Quantum Computer
- : A Quantum Programming Environment
- Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Linear decomposition of approximate multi-controlled single qubit gates
- Quantum Algorithm for Radiative Transfer Equation
- Empirical determination of the simulation capacity of a near-term quantum computer
- Straddling-gates problem in multipartite quantum systems
- Quantum-assisted Rendezvous on Graphs: Explicit Algorithms and Quantum Computer Simulations
- Quantum advantage in temporally flat measurement-based quantum computation
- Detecting Measurement-Induced Entanglement Transitions With Unitary Mirror Circuits
- Cost of Locally Approximating High-Dimensional Ground States of Contextual Quantum Models
- Efficient Sparse State Preparation via Quantum Walks
- On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
- Trotterless Simulation of Open Quantum Systems for NISQ Quantum Devices
- Quantum Pattern Detection: Accurate State- and Circuit-based Analyses
- Path Matters: Industrial Data Meet Quantum Optimization
- Efficient implementation of unitary transformations
- Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
- Compiling universal quantum circuits
- Simultaneous Quantum Machine Learning Training and Architecture Discovery
- Quantum circuit and mapping algorithms for wavepacket dynamics: case study of anharmonic hydrogen bonds in protonated and hydroxide water clusters
- An Evolutionary Approach to Optimizing Communication Cost in Distributed Quantum Computation
- Sublinear Classical-to-Quantum Data Encoding using -Toffoli Gates
- Classification using a two-qubit quantum chip
- Measurement Schemes for Quantum Linear Equation Solvers
- End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
- High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
- Fast Tensor Disentangling Algorithm
- Quantum Pseudo-fractional Fourier Transform and its application to quantum phase estimation
- Quantum Circuit Unoptimization
- All You Need is pi: Quantum Computing with Hermitian Gates
- Structured decomposition for reversible Boolean functions
- Performance Evaluations of Signed and Unsigned Noisy Approximate Quantum Fourier Arithmetic
- Halving the cost of quantum multiplexed rotations
- An Alternative Quantization Protocol for the History Dependent Parrondo Game
- Three-Qubit State Preparation: Classification and Explicit Circuits
- Collective unitary evolution with linear optics by Cartan decomposition
- Quantum Algorithms for State Preparation and Data Classification based on Stabilizer Codes
- Efficient Simulation of Open Quantum Systems on NISQ Trapped-Ion Hardware
- Fully Quantum Algorithm for the 1-dimensional linear Lattice Boltzmann Method
- Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique
- Quantum phase estimation with optimal confidence interval using three control qubits
- Adaptive time Compressed QITE (ACQ) and its geometrical interpretation
- Universal quantum gates for photon-atom hybrid systems assisted by bad cavities
- Nontrivial multi-product commutation relation toward reducing T-count in sequential Pauli-based computation
- Quantum-Processing-Assisted Classical Communications
- On Binomial Summations and a Generalised Quantum SWAP Gate
- AccQOC: Accelerating Quantum Optimal Control Based Pulse Generation
- Decomposition of Diagonal Hermitian Quantum Gates Using Multiple-Controlled Pauli Z Gates
- Quantum generative classification with mixed states
- A Reed Muller-based approach for optimization of general binary quantum multiplexers
- Schmidt quantum compressor
- Mapping of Topological Quantum Circuits to Physical Hardware
- Quantum circuit synthesis with SQiSW
- Sample Optimal and Memory Efficient Quantum State Tomography
- A quantum eigenvalue solver based on tensor networks
- A generalized quantum SWAP gate
- Quantum State Preparation and Non-Unitary Evolution with Diagonal Operators