Strengths and Weaknesses of Quantum Computing
1997/10/01 by Charles H. Bennett, Ethan Bernstein, Gilles Brassard +1 · 161 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Computability, Logic, AI Algorithms #Quantum Information and Cryptography
paper · doi:10.1137/s0097539796300933
Abstract
Recently a great deal of attention has focused on quantum computation following a sequence of results 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 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 quantum Turing machine in time o(2n/3). The former bound is tight since recent work of Grover 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\n 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\n 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
- Umesh Vazirani [wikipedia]
Related