Deriving Grover's lower bound from simple physical principles
arXiv:1604.03118 · doi:10.1088/1367-2630/18/9/093047
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.
arXiv commentUpdated title and exposition in response to referee comments. 6+2 pages, 5 figures
References in corpus (26)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- In defense of the epistemic view of quantum states: a toy theory
- Grover's quantum searching algorithm is optimal
- Informational derivation of Quantum Theory
- Probabilistic theories with purification
- Quantum Mechanics as Quantum Measure Theory
- A generalized no-broadcasting theorem
- Ruling Out Multi-Order Interference in Quantum Mechanics
- Almost quantum correlations
- Higher-order interference and single-system postulates characterizing quantum theory
- Generalized Probabilistic Theories Without the No-Restriction Hypothesis
- The structure of reversible computation determines the self-duality of quantum theory
- Quantum Measure Theory and its Interpretation
- Three Slit Experiments and the Structure of Quantum Theory
- Quantum interference as a resource for quantum speedup
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- On the superposition principle in interference experiments
- Testing Born's Rule in Quantum Mechanics with a Triple Slit Experiment
- Higher-order interference in extensions of quantum theory
- The computational landscape of general physical theories
- Bounding quantum contextuality with lack of third-order intereference
- Conditional probability, three-slit experiments, and the Jordan algebra structure of quantum mechanics
- A histories perspective on characterising quantum non-locality
- Grover search and the no-signaling principle
- Bounds on the power of proofs and advice in general physical theories
Cited by in corpus (29)
- General probabilistic theories: An introduction
- Towards device-independent information processing on general quantum networks
- A no-go theorem on the nature of the gravitational field beyond quantum theory
- Higher-order interference in extensions of quantum theory
- Reconstructing quantum theory from diagrammatic postulates
- The computational landscape of general physical theories
- Ruling out higher-order interference from purity principles
- Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
- Oracles and query lower bounds in generalised probabilistic theories
- Quantum computation is the unique reversible circuit model for which bits are balls
- Post-quantum steering is a stronger-than-quantum resource for information processing
- Interferometric computation beyond quantum theory
- Agents, subsystems, and the conservation of information
- Strongly symmetric spectral convex bodies are Jordan algebra state spaces
- On defining the Hamiltonian beyond quantum theory
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Compositional resource theories of coherence
- A simple and quantum-mechanically motivated characterization of the formally real Jordan algebras
- Correlations constrained by composite measurements
- Device-independent certification of non-classical joint measurements via causal models
- Exotic looped trajectories via quantum marking
- Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
- A no-go theorem for theories that decohere to quantum mechanics
- Density Hypercubes, Higher Order Interference and Hyper-Decoherence: a Categorical Approach
- Computation in a general physical setting
- Paradoxical consequences of multipath coherence: perfect interaction-free measurements
- Quantum teleportation and Grover's algorithm without the wavefunction
- Complete extension: the non-signaling analog of quantum purification
- Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions