Deriving Grover's lower bound from simple physical principles
From MaRDI portal
(Redirected from Publication:5855095)
Abstract: Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours---currently under experimental investigation---where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.
Recommendations
- Exact quantum lower bound for Grover's problem
- Quantum lower bounds by quantum arguments
- Quantum lower bounds by quantum arguments
- Quantum formulas: A lower bound and simulation
- Lower bound of concurrence for qubit systems
- A simplified basis for Bell-Kochen-Specker theorems
- A lower bound method for quantum circuits
- A derivation of quantum theory from physical requirements
- Lower bound for quantum phase estimation
- Quantum lower bounds by entropy numbers
Cites work
- A histories perspective on characterizing quantum non-locality
- Bounds on the power of proofs and advice in general physical theories
- Computation in generalised probabilisitic theories
- Conditional probability, three-slit experiments, and the Jordan algebra structure of quantum mechanics
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- Higher-order interference and single-system postulates characterizing quantum theory
- Quantum computation and quantum information. 10th anniversary edition
- Quantum mechanics as quantum measure theory
- Ruling out multi-order interference in quantum mechanics
- Strengths and Weaknesses of Quantum Computing
- The space ``just above BQP
- Three slit experiments and the structure of quantum theory
Cited in
(15)- Exotic looped trajectories via quantum marking
- Quantum teleportation and Grover's algorithm without the wavefunction
- Interferometric computation beyond quantum theory
- Oracles and query lower bounds in generalised probabilistic theories
- On defining the Hamiltonian beyond quantum theory
- A no-go theorem for theories that decohere to quantum mechanics
- A simple and quantum-mechanically motivated characterization of the formally real Jordan algebras
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- Decomposing all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
- Computation in a general physical setting
- General probabilistic theories: an introduction
- Density Hypercubes, Higher Order Interference and Hyper-decoherence: A Categorical Approach
- Quantum thermal search: computing ground states via quantum mixing thermal operations
- On the physical basis for the incomparability of NP and BQP
- Quantum interpretations, causality and quantum computation
This page was built for publication: Deriving Grover's lower bound from simple physical principles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855095)
