Elementary gates for quantum computation
1995/11/01 by Adriano Barenco, Charles H. Bennett, Richard Cleve +7 · 132 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata
paper · doi:10.1103/physreva.52.3457
Abstract
We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath\bigoplusy)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(2n)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.
Citations
Cited by
- Spin qubits in multielectron quantum dots
- Applying Grover's algorithm to AES: quantum resource estimates
- Generation and Detection of Quantum Correlations and Entanglement on a Spin-Based Quantum Information Processor
- New designs of reversible sequential devices
- Quantum computation and decision trees
- Low-overhead constructions for the fault-tolerant Toffoli gate
- One Gate Scheme to Rule Them All: Introducing a Complex Yet Reduced Instruction Set for Quantum Computing
- Measurement-based quantum computation on cluster states
- Space-Time Topology in Teleportation-Based Quantum Computation
- Josephson-junction qubits with controlled couplings
- Logic Synthesis for Quantum Computing
- Creating Boolean Functions for the Five-EPR-Pair, Single-Error-Correcting Code
- Two-qubit Projective Measurements are Universal for Quantum Computation
- Logic Synthesis for Fault-Tolerant Quantum Computers
- Near-Optimal Quantum Algorithms for String Problems
- Pseudospin Quantum Computation in Semiconductor Nanostructures
- A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver
- Quantum Cellular Automata from Lattice Field Theories
- Optimizing Quantum Compilation via High-Level Quantum Instructions
- An algorithm for minimization of quantum cost
- Clifford Transformations for Fermionic Quantum Systems: From Paulis to Majoranas to Fermions
- Fast parallel circuits for the quantum Fourier transform
- A Spin-Optical Quantum Computing Architecture
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits
- Shor's algorithm on a nearest-neighbor machine
- Quantum Hamiltonian simulation of linearised Euler equations in complex geometries
- Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits
- Dynamic watermarking scheme for quantum images based on Hadamard transform
- Minimal Equational Theories for Quantum Circuits
- Quantum Search in Superposed Quantum Lattice Gas Automata and Lattice Boltzmann Systems
- Study of Decoherence in Quantum Computers: A Circuit-Design Perspective
- Both Toffoli and Controlled-NOT need little help to do universal quantum computation
- Pulse Protocols for Quantum Computing with Electron Spins as Qubits
- Quantum Circuit for Quantum Fourier Transform for Arbitrary Qubit Connectivity Graphs
- An Almost-Quadratic Lower Bound for Quantum Formula Size
- Quantum Algorithms in Cybernetics
- End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
- A Hardware-Efficient Mølmer-Sørensen Gate for Superconducting Quantum Computers
- Mirrored Entanglement Witnesses for Multipartite and High-Dimensional Quantum Systems
- Nonlocal Properties of Two-Qubit Gates and Mixed States, and the Optimization of Quantum Computations
- One rig to control them all
- Ion-Based Characterization of Laser Beam Profiles for Quantum Information Processing
- Decidable and undecidable problems about quantum automata
- Pre-Distillation of Magic States via Composite Schemes
- Provably Optimal Quantum Circuits with Mixed-Integer Programming
- Visualizing the state space and transformations of higher order quantum logics via toric geometry
- Introduction to Quantum Information Processing
- Quantum gates with topological phases
- One-way communication complexity and the Neciporuk lower bound on formula size
- Robust quantum information processing with techniques from liquid state NMR
- Perturbation theory, irrep truncations, and state preparation methods for quantum simulations of SU(3) lattice gauge theory
- Unitary synthesis with fewer T gates
- Self-testing of universal and fault-tolerant sets of quantum gates
- Scalable Spin Qubit Architecture with Donor-Cluster Arrays in Silicon
- Stable organic radical qubits and their applications in quantum information science
- Discrete Wigner function and quantum-state tomography
- A Review on Quantum Circuit Optimization using ZX-Calculus
- Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
- Quantum algorithms for the Goldreich-Levin learning problem
- Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks
- Stochastic Simulation of Grover's Algorithm
- Quantum algorithms revisited
- Graph comparison via nonlinear quantum search
- Efficient quantum state preparation with Walsh series
- The Hidden Subgroup Problem - Review and Open Problems
- Realization of pvalued Deutsch quantum gates
- Grover's Algorithm: Quantum Database Search
- Connecting Quantum Computing with Classical Stochastic Simulation
- K-Means Clustering on Noisy Intermediate Scale Quantum Computers
- Photon Blockade Mediated by Two-Photon Absorption in an Optical Parametric Amplifier
- Hamiltonian truncation and quantum simulation of strong-field QED beyond tree level
- Equiangular tight frames in real symplectic space: Zauner's conjecture and the skew Hadamard conjecture
- From virtual Z gates to virtual Z pulses
- A complete set of transformation rules for reversible circuits
- A generalized quantum SWAP gate
- A Lambda Calculus for Quantum Computation
- Towards Efficient Superconducting Quantum Processor Architecture Design
- Borrowing Dirty Qubits in Quantum Programs
- Exploiting Timing Side-Channels in Quantum Circuits Simulation Via ML-Based Methods
- A framework for reversible circuit complexity
- Quantum Neural Networks
- Gradients, parallelism, and variance of quantum estimates
- Hybrid Quantum Neural Networks for Efficient Protein-Ligand Binding Affinity Prediction
- Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition
- Loss Behavior in Supervised Learning with Entangled States
- Quantum Dots: Coulomb Blockade, Mesoscopic Fluctuations, and Qubit\n Decoherence
- Decomposing Quantum Generalized Toffoli with an Arbitrary Number of Ancilla
- Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
- Universality of a standard two-qubit gate by catalytic embedding
- Time-frequency Entangled Photon Mediated CCZ Gate
- Genetic optimization of ansatz expressibility for enhanced variational quantum algorithm performance
- Improving initial-state-dependent quantum circuit optimization by introducing state labels
- Practical Fidelity Limits of Toffoli Gates in Superconducting Quantum Processors
- Introduction to Quantum Algorithms
- Quantum Circuit Design using Complex valued Neural Network in Stiefel Manifold
- Introduction to NMR Quantum Information Processing
- CNOT Oriented Synthesis for Small-Scale Boolean Functions Using Spatial Structures of Parallelotopes
- Tensor Networks in a Nutshell
- ProjectQ: an open source software framework for quantum computing
- Block Encoding of Sparse Matrices via Coherent Permutation
- Quantum algorithms for equational reasoning
- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
- Optimizing Compilation for Distributed Quantum Computing via Clustering and Annealing
- Efficient multi-qubit subspace rotations via topological quantum walks
- High-fidelity realisation of CNOT gate in Majorana-based optical platform
- Computation by measurements: A unifying picture
- Experimental Demonstration of Efficient High-dimensional Quantum Gates with Orbital Angular Momentum
- The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
- Software mitigation of coherent two-qubit gate errors
- Clarification on the Mapping of Reversible Circuits to the NCV-v1\n Library
- Single Molecule Magnetic Resonance and Quantum Computation
- A Parallel Quantum Computer Simulator
- NP in BQP with Nonlinearity
- Compiling gate networks on an Ising quantum computer
- Classical Cryptosystems In A Quantum Setting
- Quantum Algorithm for Estimating Intrinsic Geometry
- Experimental Realization of an NMR Quantum Switch
- Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing
- Thermodynamic Signature of Logical Depth in Quantum Circuits
- Von Neumann Quantum Processors
- Sandwich test for Quantum Phase Estimation
- Quantum Games and Programmable Quantum Systems
- Factorizing time evolution into elementary steps
- A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search
- An efficient quantum circuits optimizing scheme compared with QISKit
- Scalable native multiqubit gates via engineered noncomputational-state interactions in superconducting fluxonium qubits
- Quantum-state engineering with Josephson-junction devices
- Universal simulation of Hamiltonian dynamics for quantum systems with finite-dimensional state spaces
- An analysis of reversible multiplier circuits
- Feasible Surface Plasmon Routing Based on The Self-assembled InGaAs/GaAs Semiconductor Quantum Dot Located between Two Silver Metallic Waveguides
- Compiling Quantum Circuits using the Palindrome Transform
- Noisy intermediate-scale quantum algorithms
Related