Quantum Complexity Theory
1997/10/01 by Ethan Bernstein, Umesh Vazirani · 1,546 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Computer science #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum complexity theory #Quantum mechanics
paper · doi:10.1137/s0097539796300921
published in SIAM Journal on Computing 26(5), 1411-1473 (Society for Industrial and Applied Mathematics)
openalex publication_date 1997/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26
Abstract
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log T) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class \BPP. The class \BQP of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies \BPP ⊆ \BQP ⊆ \Ptime\SP. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Citations
Cited by
- Strengths and Weaknesses of Quantum Computing
- Do we have a quantum computer? Expert perspectives on current state and future prospects
- 1-way quantum finite automata: strengths, weaknesses and generalizations
- A quantum Goldreich-Levin theorem with cryptographic applications
- Quantum computing: A taxonomy, systematic review and future directions
- The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
- Optimal Quantum Sample Complexity of Learning Algorithms
- Quantum feedback for measurement and control
- Could the physical world be emergent instead of fundamental, and why should we ask? (short version)
- Quantum Simulations of the Non-Unitary Time Evolution and Applications to Neutral-Kaon Oscillations
- Quantum Edge Detection for Image Segmentation in Optical Environments
- Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
- Quantum Oracle Separations from Complex but Easily Specified States
- On Quantum Turing Machine Halting Deterministically
- The Multiplicative Quantum Adversary
- Exponential improvements for quantum-accessible reinforcement learning
- Quantum Mechanics: Bell and Quantum Entropy for the Classroom
- A Study of Parallel Self-Organizing Map
- Lower bounds for quantum communication complexity
- Fault Tolerant Quantum Computation with Constant Error
- Quantum Robust Fitting
- Is Quantum Mechanics An Island In Theoryspace?
- Gate-Based Quantum Simulation of Gaussian Bosonic Circuits on Exponentially Many Modes
- Approximate Equivalence Checking of Noisy Quantum Circuits
- Quantum Key Recovery Attack on SIMON Block Cipher
- Algorithms for Boolean Function Query Properties
- Towards A Theory Of Quantum Computability
- SANQ: A Simulation Framework for Architecting Noisy Intermediate-Scale Quantum Computing System
- Quantum Miss-in-the-Middle Attack
- Classical-Quantum Noise Mitigation for NISQ Hardware
- QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
- Quantum Cellular Automata from Lattice Field Theories
- How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
- A small 1-way quantum finite automaton
- The class of languages recognizable by 1-way quantum finite automata is not closed under union
- Comparing EQP and MODpkP using Polynomial Degree Lower Bounds
- Interactive proofs for BQP via self-tested graph states (extended abstract)
- Approximation, Proof Systems, and Correlations in a Quantum World
- Tripartite Blind Quantum Computation
- Wave-Style Token Machines and Quantum Lambda Calculi (Long Version)
- Quantum Domain Theory - Definitions and Applications
- An Almost-Quadratic Lower Bound for Quantum Formula Size
- Quantum Kolmogorov Complexity
- Most tensor problems are NP-hard
- A framework for fast quantum mechanical algorithms
- Quantum NP and a Quantum Hierarchy
- An Optimal Separation of Randomized and Quantum Query Complexity
- Upper bound by Kolmogorov complexity for the probability in computable POVM measurement
- Quantum bounded query complexity
- Self-testing of universal and fault-tolerant sets of quantum gates
- Multilinear formulas and skepticism of quantum computing
- Quantum Harmonic Sieve: Learning DNF with a Classical Example Oracle
- The Hidden Subgroup Problem - Review and Open Problems
- The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
- Grover's Algorithm: Quantum Database Search
- A Lambda Calculus for Quantum Computation
- A Non-Interactive Quantum Bit Commitment Scheme that Exploits the Computational Hardness of Quantum State Distinction
- Quantum Neural Networks
- Succinct quantum proofs for properties of finite groups
- Exponential algorithmic speedup by a quantum walk
- Introduction to Quantum Algorithms
- A Quantum Algorithm for Testing Juntas in Boolean Functions
- Preparing students for the quantum information revolution: Interdisciplinary teaching, curriculum development, and advising in quantum information science and engineering
- Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation to a New Level
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem
- Classical lower bounds from quantum upper bounds
- Computational Distinguishability of Quantum Channels
- Quantum oracle interrogation: getting all information for almost half the price
- The query complexity of order-finding
- Some relations between quantum Turing machines and Turing machines
- A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
- Quantum Computing, Postselection, and Probabilistic Polynomial-Time
- A Quantum Abacus based encoding system
- Using Bernstein-Vazirani Algorithm to Attack Block Ciphers
- Quantum Kolmogorov Complexity and the Quantum Turing Machine
- A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks
- Confluence Results for a Quantum Lambda Calculus with Measurements
- A Quantum Time-Space Lower Bound for the Counting Hierarchy
- Managing approximation errors in quantum programs
- On quantum and classical space-bounded processes with algebraic transition amplitudes
- Undecidability of the Spectral Gap (short version)
- Quantum Lambda Calculi with Classical Control: Syntax and Expressive Power
- The Quantum Computer Puzzle (Expanded Version)
- Search by quantum walks on two-dimensional grid without amplitude amplification
- Compiling Quantum Circuits using the Palindrome Transform
- Quantum Optimization Problems
- Robust Quantum Algorithms for Oracle Identification
- The non-adaptive query complexity of testing k-parities
- Interaction in Quantum Communication Complexity
- Quantum speedups for convex dynamic programming
- A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure
- Monte Carlo Quantum Computing
- Quantum Computers Can Find Quadratic Nonresidues in Deterministic Polynomial Time
- Algorithmic Randomness and Kolmogorov Complexity for Qubits
- Level Reduction and the Quantum Threshold Theorem
- Quantum Complexity Classes
- Quantum algorithms for learning a hidden graph and beyond
- Quantum Computation: A Computer Science Perspective
- Quantum Computers: Noise Propagation and Adversarial Noise Models
- Quantum Evaluation of Multi-Valued Boolean Functions
- Quantum information processing, operational quantum logic, convexity, and the foundations of physics
- The Complexity of the Consistency and N-representability Problems for Quantum States
- A quantum Fourier transform algorithm
- The Quantum Frontier
- Efficient Quantum Transforms
- A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction
- Decoherence, Control, and Symmetry in Quantum Computers
- Quantum coin flipping with arbitrary small bias is impossible
- On the query complexity of connectivity with global queries
- Optimizing the walk coin in the quantum random walk search algorithm through machine learning
- A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
- One Complexity Theorist's View of Quantum Computing
- Hypercomputability of quantum adiabatic processes: Fact versus Prejudices
- TILT: Achieving Higher Fidelity on a Trapped-Ion Linear-Tape Quantum Computing Architecture
- Decidability of the Equivalence of Multi-Letter Quantum Finite Automata
- Using Cloning to Solve NP Complete Problems
- A new quantum lower bound method, with an application to strong direct product theorem for quantum search
- Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
- On Information-Theoretic Classical Verification of Quantum Computers
- Quantum Principles and Mathematical Computability
- An integer factorization algorithm which uses diffusion as a\n computational engine
- A new sibling of BQP
- Power of photonic states: from quantum computation to cosmology
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- Strictly contractive quantum channels and physically realizable quantum computers
- Applying computational complexity to the emergence of classicality
- Universal construction for the unsorted quantum search algorithms
- Quantum Darwinism and Computability Theory
- On computation with 'probabilities' modulo k
- Computational Complexity of Some Quantum Theories in 1+1 Dimensions
- Quantum Communication-Query Tradeoffs
- On Perfect Completeness for QMA
- Characterizations of 1-Way Quantum Finite Automata
- A comparison of Zeroes and Ones of a Boolean Polynomial
- On the Quantum Black-Box Complexity of Majority
- Evaluating NISQ Devices with Quadratic Nonresidues
- On The Power of Exact Quantum Polynomial Time
- Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
- Entanglement Theory and the Quantum Simulation of Many-Body Physics
- Approximation and robustness of fuzzy finite automata
- Quantum computation: Algorithms and Applications
- The Quantum Setting with Randomized Queries for Continuous Problems
- On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata
- Applications of the Adversary Method in Quantum Query Algorithms
- Dynamical Aspects of Information Storage in Quantum-Mechanical Systems
- Speedup of iterated quantum search by parallel performance
- Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines
- Quantum versus Classical Learnability
- Classical and quantum computation with small space bounds (PhD thesis)
- Quantum Formulas: a Lower Bound and Simulation
- Tight Quantum Time-Space Tradeoffs for Function Inversion
- The Fiat-Shamir Transformation in a Quantum World
- Distance measures to compare real and ideal quantum processes
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Quantum Algorithms for Learning and Testing Juntas
- Exploiting Long-Distance Interactions and Tolerating Atom Loss in Neutral Atom Quantum Architectures
- Quantum computational chemistry
- Cosmological lower bound on the circuit complexity of a small problem in logic
- Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem
- Sharp Quantum vs. Classical Query Complexity Separations
- Unbounded-error quantum computation with small space bounds
- Quantum algorithms for fermionic simulations
- Distinguishing symmetric quantum oracles and quantum group multiplication
- Quantum advantage for computations with limited space
- Quantum Nondemolition Circuit for Testing Bipartite Complementarity
- Universal resources for approximate and stochastic measurement-based quantum computation
- Comparative Computational Strength of Quantum Oracles
- Quantum computing, postselection, and probabilistic polynomial-time
- An Optimum Algorithm for Quantum Search
- An exact quantum polynomial-time algorithm for Simon's problem
- Computational Complexity
- More period finding with adiabatic quantum computation
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- High Fidelity Quantum Gates with Vibrational Qubits
- Local Convertibility and the Quantum Simulation of Edge States in Many-Body Systems
- Simulated quantum computation of global minima
- Reasoning about Recursive Quantum Programs
- Higher-order perturbation theory for decoherence in Grover’s algorithm
- One-dimensional quantum walk with unitary noise
- Lower Bounds on Stabilizer Rank
- Limits on Efficient Computation in the Physical World
- Emerging quantum computing algorithms for quantum chemistry
- Use of mathematical logical concepts in quantum mechanics: an example
- Undecidability of the Spectral Gap (full version)
- BQP and the polynomial hierarchy
- Superpolynomial Speedups Based on Almost Any Quantum Circuit
- The definition of a random sequence of qubits: from Noncommutative Algorithmic Probability Theory to Quantum Algorithmic Information Theory and back
- Quantum solvability of noisy linear problems by divide-and-conquer strategy
- Quantum Kolmogorov complexity and quantum key distribution
- Categorical Quantum Dynamics
- Phase-space-simulation method for quantum computation with magic states on qubits
- Pattern recognition on a quantum computer
- On Halting Process of Quantum Turing Machine
- Quantum advantage with shallow circuits
- Systematic Crosstalk Mitigation for Superconducting Qubits via Frequency-Aware Compilation
- BQP [wikipedia]
- Church–Turing thesis [wikipedia]
- Quantum computing [wikipedia]
Related