Strengths and Weaknesses of Quantum Computing
From MaRDI portal
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 . We also show that relative to a permutation oracle chosen uniformly at random, with probability 1, the class cannot be solved on a quantum Turing machine in time . 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 .
Recommendations
Cited in
(only showing first 100 items - show all)- Quantum approaches to graph colouring
- A new connection between quantum circuits, graphs and the Ising partition function
- Quantum lower bounds for the Goldreich-Levin problem
- An oracle builder's toolkit
- On the simulation of quantum Turing machines.
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- New quantum algorithm for studying NP-complete problems
- Diagonalization of diffusion matrix in Grover's algorithm
- Quantum search on structured problems
- The Landauer resistance and band spectra for the counting quantum Turing machine.
- Quantum computing and quadratically signed weight enumerators
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
- A review on quantum search algorithms
- Quantum algorithm design: techniques and applications
- Oracles and query lower bounds in generalised probabilistic theories
- A modified quantum search algorithm
- New quantum algorithm solving the NP complete problem
- Spatial search using the discrete time quantum walk
- An optical model of computation
- Quantum computers and unstructured search: finding and counting items with an arbitrarily entangled initial state
- Computing with quanta -- impacts of quantum theory on computation.
- Quantum communication and complexity.
- Almost-everywhere superiority for quantum polynomial time
- Searching a database under decoherence
- Mathematical models of quantum computation
- One complexity theorist's view of quantum computing
- A lower bound on the quantum query complexity of read-once functions
- Quantum speed-up for unsupervised learning
- Intricacies of quantum computational paths
- Complexity limitations on quantum computation
- Coloring invariants of knots and links are often intractable
- Quantum partial search for uneven distribution of multiple target items
- On the role of dealing with quantum coherence in amplitude amplification
- Controlled quantum search
- Quantum-access-secure message authentication via blind-unforgeability
- On the compressed-oracle technique, and post-quantum security of proofs of sequential work
- Towards quantum computing based community detection
- Dynamic multi-party quantum key agreement protocol based on commutative encryption
- The variational quantum eigensolver: a review of methods and best practices
- Evaluation of exact quantum query complexities by semidefinite programming
- Entanglement measures of a pentapartite W-class state in the noninertial frame
- Quantum search degeneration under amplitude noise in queries to the oracle
- Optimal merging in quantum k-xor and k-sum algorithms
- New approaches for quantum copy-protection
- Layering quantum-resistance into classical digital signature algorithms
- Multi-party quantum key agreement protocol for detection of collusive attacks in each sub-circle segment by headers
- PKP-based signature scheme
- The Python's lunch: geometric obstructions to decoding Hawking radiation
- A relational time-symmetric framework for analyzing the quantum computational speedup
- Key establishment à la Merkle in a quantum world
- Quantum branch-and-bound algorithm and its application to the travelling salesman problem
- Quantum de Finetti theorems under local measurements with applications
- The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
- An \(R||C_{\max}\) quantum scheduling algorithm
- Progress in quantum algorithms
- Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- Approximate span programs
- A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions
- Evolutionary algorithms for quantum computers
- A universal quantum circuit scheme for finding complex eigenvalues
- Quantum partial search of a database with several target items
- Quantum mechanical search and harmonic perturbation
- Quantum certificate complexity
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- Polynomial degree vs. quantum query complexity
- Improved bounds on quantum learning algorithms
- On the complexity of searching for a maximum of a function on a quantum computer
- Discrete quantum walks hit exponentially faster
- Quantum and classical tradeoffs
- Universal test for quantum one-way permutations
- Quantum commitments from complexity assumptions
- Challenges of adiabatic quantum evaluation of NAND trees
- Dynamical analysis of Grover's search algorithm in arbitrarily high-dimensional search spaces
- Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions
- Super-quantum discord in ferromagnetic and antiferromagnetic materials
- Total functions in QMA
- Optimal fixed-point quantum search in an interacting Ising spin system
- Quantum advantage in deciding NP-complete problems
- Implementation of efficient quantum search algorithms on NISQ computers
- Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness
- Improved classical and quantum algorithms for subset-sum
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- Quantum computation and NP-complete problems
- The space ``just above BQP
- Post-quantum cryptography: state of the art
- Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
- On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
- BQP and the polynomial hierarchy
- Quantum distributed computing applied to Grover's search algorithm
- Spatial search on a honeycomb network
- Quantum algorithms for algebraic problems
- Information and computation: Classical and quantum aspects
- The role of relative entropy in quantum information theory
- Random matrix model of adiabatic quantum computing
- Lower bound for quantum phase estimation
- Algebraic analysis of quantum search with pure and mixed states
- Quantum computing and hidden variables
- Spatial search and the Dirac equation
This page was built for publication: Strengths and Weaknesses of Quantum Computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376184)
