Deriving Grover's lower bound from simple physical principles

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.

Updated title and exposition in response to referee comments. 6+2 pages, 5 figures

References in corpus (10)

• A generalized no-broadcasting theorem
• Almost quantum correlations
• Higher-order interference and single-system postulates characterizing quantum theory
• Generalised phase kick-back: the structure of computational algorithms from physical principles
• 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
• 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