Strengths and Weaknesses of Quantum Computing
1997/01/01 by Charles H. Bennett, Ethan Bernstein, Gilles Brassard +1 · 1,498 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Complexity class #Computability, Logic, AI Algorithms #Computation #Computer science #Discrete mathematics #Mathematics #Oracle #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Turing machine #Quantum algorithm #Quantum complexity theory #Quantum computer #Quantum error correction #Quantum mechanics #Quantum sort #Time complexity #Time hierarchy theorem #Turing machine #Universal Turing machine #quant-ph
paper · pdf · doi:10.1137/s0097539796300933
published in SIAM Journal on Computing 26(5), 1510-1523 (Society for Industrial and Applied Mathematics) · 18 pages, latex, no figures, to appear in SIAM Journal on Computing (special issue on quantum computing)
arxiv created 1997/01/01 · openalex publication_date 1997/10/01 · arxiv updated 2020/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of \NP can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class \NP cannot be solved on a quantum Turing machine (QTM) in time o(2n/2). We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class \NP ∩ \coNP cannot be solved on a QTM in time o(2n/3). The former bound is tight since recent work of Grover [in \it Proc. 28th Annual ACM Symposium Theory Comput., 1996] shows how to accept the class \NP relative to any oracle on a quantum computer in time O(2n/2).
Citations
Cited by
- The Limits of Quantum Computers for Power Flow
- Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization
- The Quantum Optimization Benchmarking Library
- On Estimating the Trace of Quantum State Powers
- Separating QMA from QCMA with a classical oracle
- The hidden subgroup problem for infinite groups
- Quantum Complexity Theory
- Is partial quantum search of a database any easier?
- Spatial search using the discrete time quantum walk
- Separating Quantum and Classical Advice with Good Codes
- The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
- Bibliographic guide to the foundations of quantum mechanics and quantum information
- Quantum Lower Bounds by Polynomials
- Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
- Quantum Heaviside Eigen Solver
- Quantum Computing: Lecture Notes
- Quantum-Amplified M/G/1/K Simulation: A Comparator-Controlled Framework for Arbitrary Service Distributions
- A Grover-compatible manifold optimization algorithm for quantum search
- Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle
- The Multiplicative Quantum Adversary
- A Note on Oracle Separations for BQP
- Quantum computing
- A Study of Parallel Self-Organizing Map
- A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
- Random Permutations in Computational Complexity
- Strongly symmetric spectral convex bodies are Jordan algebra state spaces
- The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems
- Why haven't more quantum algorithms been found?
- On Quantum Obfuscation
- Two-Bit Gates are Universal for Quantum Computation
- Near-Optimal Quantum Algorithms for String Problems
- Quantum Algorithms with Fixed Points: The Case of Database Search
- Binary Subdivision for Quantum Search
- Quantum automated theorem proving
- Oracle Separations for Quantum Statistical Zero-Knowledge
- Quantum Computing in the NISQ era and beyond
- Fast parallel circuits for the quantum Fourier transform
- Quantum Algorithm for Commutativity Testing of a Matrix Set
- A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
- Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
- Tight Quantum Time-Space Tradeoffs for Permutation Inversion
- Quantum Domain Theory - Definitions and Applications
- End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
- Quantum Algorithm for Binary Vector Encoding and Retrieval Utilizing the Permutation Trick
- On Limits on the Provable Consequences of Quantum Pseudorandomness
- On the Cryptographic Futility of Non-Collapsing Measurements
- A framework for fast quantum mechanical algorithms
- Linear-Size QAC0 Channels: Learning, Testing and Hardness
- Quantum NP and a Quantum Hierarchy
- Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality
- Quantum bounded query complexity
- Bisection Grover’s Search Algorithm and Its Application in Analyzing CITE-seq Data
- Grover Speedup from Many Forms of the Zeno Effect
- An Economic Model for Quantum Key-Recovery Attacks against Ideal Ciphers
- Optimal phase change for a generalized Grover's algorithm
- Knot theory and quantum computing
- Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography
- Stochastic Simulation of Grover's Algorithm
- Quantum Computing for Molecular Biology**
- Exponential Quantum Speedup in Simulating Coupled Classical Oscillators
- Efficient decoding for the Hayden-Preskill protocol
- 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
- Connecting Quantum Computing with Classical Stochastic Simulation
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- A Survey of Quantum Learning Theory
- A Lambda Calculus for Quantum Computation
- Notes on Randomized Algorithms
- Dynamics of quantum adiabatic evolution algorithm for Number Partitioning
- Improved Quantum Lifting by Coherent Measure-and-Reprogram
- Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties
- Nested Grover's Algorithm for Tree Search
- Introduction to Quantum Algorithms
- Quantum lower bounds by quantum arguments
- Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices
- A note on the quantum query complexity of permutation symmetric functions
- Quantum Computation by Adiabatic Evolution
- Optimal quantum simulation of linear non-unitary dynamics
- Adversary lower bounds in the Hamiltonian oracle model
- Classical lower bounds from quantum upper bounds
- Multi-player conflict avoidance through entangled quantum walks
- Local Hamiltonians in Quantum Computation
- Qudit-based scalable quantum algorithm for solving the integer programming problem
- Bounds on quantum ordered searching
- Feynman Path Integral Approach on Superconducting Qubits and Readout Process
- NP in BQP with Nonlinearity
- Quantum speedups need structure
- Brief history of quantum cryptography: a personal perspective
- Expressivity Limits in Quantum Walk-based Optimization
- Lower Bounds for Quantum Search and Derandomization
- The Power of Unentanglement
- Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
- Deterministic Quantum Search via Recursive Oracle Expansion
- The Quantum Query Complexity of AC0
- A quantum computer only needs one universe
- Quantum statistical zero-knowledge
- Quantum Mechanical Square Root Speedup in a Structured Search Problem
- Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits
- Quantum computations (course of lectures)
- Grover's algorithm is an approximation of imaginary-time evolution
- Quantum Computation Beyond the Circuit Model
- Quantum-resistant digital signatures schemes for low-power IoT
- Precise Time Evolution of Superconductive Phase Qubits
- Quantum Optimization Problems
- A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
- On the query complexity of unitary channel certification
- Quantum speedups for convex dynamic programming
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- A Polynomial Time Bounded-error Quantum Algorithm for Boolean\n Satisfiability
- New Approaches for Quantum Copy-Protection
- On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
- Quantum Search of Spatial Regions
- Quantum subroutine problem and the robustness of quantum complexity classes
- Quantum Evaluation of Multi-Valued Boolean Functions
- Quantum key distribution and cryptography: a survey
- Spatial search and the Dirac equation
- The Complexity of the Consistency and N-representability Problems for Quantum States
- Quantum Computing: an undergraduate approach using Qiskit
- Model Predictive Path Integral Control as a Quantum Query Problem
- Quantum vs. Classical Communication and Computation
- Efficient Quantum Transforms
- Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer
- Quantum Money from Hidden Subspaces
- Structured Adiabatic Quantum Search
- Decoherence, Control, and Symmetry in Quantum Computers
- Quadratic speedup of global search using a biased crossover of two good solutions
- Adversary Lower Bound for the Orthogonal Array Problem
- One Complexity Theorist's View of Quantum Computing
- A note on quantum one-way permutations
- A quantum-inspired classical algorithm for recommendation systems
- Experimental realization of the one qubit Deutsch-Jozsa algorithm in a quantum dot
- Quantum computing and the entanglement frontier
- Using Cloning to Solve NP Complete Problems
- Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems
- Quantum Search for Gravitational Wave of Massive Black Hole Binaries
- Universal construction for the unsorted quantum search algorithms
- Variations on Quantum Adversary
- On computation with 'probabilities' modulo k
- Benincasa-Dowker causal set actions by quantum counting
- Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
- Computational Complexity of Some Quantum Theories in 1+1 Dimensions
- On Finding Quantum Multi-collisions
- Quantum Communication-Query Tradeoffs
- Quantum pattern matching fast on average
- No-signaling, intractability and entanglement
- A quantum query algorithm for the graph collision problem
- Spatial search by quantum walk
- On The Power of Exact Quantum Polynomial Time
- Quantum search processes in the cyclic group state spaces
- Applications of the Adversary Method in Quantum Query Algorithms
- The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions
- Speedup of iterated quantum search by parallel performance
- Quantum versus Classical Learnability
- Solving the quantum search problem in polynomial time on an NMR quantum computer
- Decoherence in quantum walks – a review
- Tight Quantum Time-Space Tradeoffs for Function Inversion
- The Fiat-Shamir Transformation in a Quantum World
- Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
- Information and computation: Classical and quantum aspects
- Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
- An Introduction to Quantum Complexity Theory
- Guest Column
- Simulating Ising spin glasses on a quantum computer
- Algebraic analysis of quantum search with pure and mixed states
- A fast quantum mechanical algorithm for database search
- Limit on the Speed of Quantum Computation in Determining Parity
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- The role of relative entropy in quantum information theory
- Groverian measure of entanglement for mixed states
- The lambda-q calculus can efficiently simulate quantum computers
- Quantum algorithms for the ordered search problem via semidefinite programming
- Communication Capacity of Quantum Computation
- Spin-system dynamics and fault detection in threshold networks
- Guest Column: NP-complete problems and physical reality
- Approximating fractional time quantum evolution
- Quantum Computers Can Search Rapidly by Using Almost Any Transformation
- Global Optimization for Parametrized Quantum Circuits
- Quantum lower bounds by polynomials
- Quantum vs. classical communication and computation
- Group Theoretical Formulation of a Quantum Partial Search Algorithm
- Spatial search by continuous-time quantum walks on crystal lattices
- Racing a quantum computer through Minkowski spacetime
- Cryptography in a Quantum World
- Simulated quantum computation of global minima
- Defining and detecting quantum speedup
- Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
- Quantum complexity theory
- The quantum query complexity of approximating the median and related statistics
- Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
- Limits on Efficient Computation in the Physical World
- Public-Key Quantum Fire and Key-Fire From Classical Oracles
- The quest and hope of Majorana zero modes in topological superconductor for fault-tolerant quantum computing: An introductory overview
- BQP and the polynomial hierarchy
- Quantum Search with In-Place Queries
- The Hardness of Learning Quantum Circuits and its Cryptographic Applications
- How powerful is adiabatic quantum computation?
- Quantum search by measurement
- Quantum Algorithms for Evaluating MIN-MAX Trees
- A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement
- QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
- Quantum search with interacting Bose-Einstein condensates
- Orthogonal Vector Computations
- Quantum optimization for combinatorial searches
- Generalized Grover’s Algorithm for Multiple Phase Inversion States
- Quantum computation speedup limits from quantum metrological precision bounds
- Quantum Adaptive Self-Attention for Quantum Transformer Models
- Cryptomania v.s. Minicrypt in a Quantum World
- The Landauer resistance and band spectra for the counting quantum turing machine
- Quantum computing: pro and con
- Umesh Vazirani [wikipedia]
Related