Approximation by Quantum Circuits

Abstract

In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.

uuencoded, compressed postscript, LACES 68Q-95-29

Cited by in corpus (55)

• Circuit-centric quantum classifiers
• A Theory of Quantum Error-Correcting Codes
• Complexity and Shock Wave Geometries
• Synthesis of Quantum Logic Circuits
• Information and Computation: Classical and Quantum Aspects
• Chaos and complexity by design
• Cluster-state quantum computation
• Quantum algorithms for algebraic problems
• Minimal Universal Two-qubit Quantum Circuits
• Quantum Circuits for Isometries
• Linear growth of quantum circuit complexity
• Asymptotically Optimal Quantum Circuits for d-level Systems
• Lower bounds on the non-Clifford resources for quantum computations
• Predicting Research Trends with Semantic and Neural Networks with an application in Quantum Physics
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Quantum linear systems algorithms: a primer
• Entanglement, quantum randomness, and complexity beyond scrambling
• Efficient Quantum Pseudorandomness
• Black-box Hamiltonian simulation and unitary implementation
• Constructive Quantum Shannon Decomposition from Cartan Involutions
• Universal Adversarial Examples and Perturbations for Quantum Classifiers
• Decoherence, Control, and Symmetry in Quantum Computers
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Closed-form analytic expressions for shadow estimation with brickwork circuits
• Markovianization with approximate unitary designs
• Computational Complexity and Black Hole Horizons
• Certainty and Uncertainty in Quantum Information Processing
• Numerical analysis of quantum circuits for state preparation and unitary operator synthesis
• Quantum circuit synthesis using Householder transformations
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Introduction to UniversalQCompiler
• Quantum State Tomography for Matrix Product Density Operators
• Variational quantum state discriminator for supervised machine learning
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Limitations on the simulation of non-sparse Hamiltonians
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Smaller Circuits for Arbitrary n-qubit Diagonal Computations
• Polynomial Equivalence of Complexity Geometries
• Numerical circuit synthesis and compilation for multi-state preparation
• Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs
• Wavefunction branching: when you can't tell pure states from mixed states
• Unitary $t$-designs from $relaxed$ seeds
• Efficient Circuits for Exact-Universal Computations with Qudits
• Decomposition of unitary matrices and quantum gates
• Fidelity decay and error accumulation in random quantum circuits
• Comparative Computational Strength of Quantum Oracles
• Implementation of single-qubit measurement-based t-designs using IBM processors
• The universal quantum driving force to speed up a quantum computation -- The unitary quantum dynamics
• Equilibration and Typicality in Quantum Processes
• Simultaneous Quantum Machine Learning Training and Architecture Discovery
• Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
• Stochastic search for approximate compilation of unitaries
• A complete transformation rule set and a minimal equation set for CNOT-based 3-qubit quantum circuits (Draft)
• Decomposition of quantum gates
• Acceleration of quantum algorithms using three-qubit gates