Quantum interference as a resource for quantum speedup

Abstract

Quantum states can in a sense be thought of as generalizations of classical probability distributions, but are more powerful than probability distributions when used for computation or communication. Quantum speedup therefore requires some feature of quantum states that classical probability distributions lack. One such feature is interference. We quantify interference and show that there can be no quantum speedup due to a small number of operations incapable of generating large amounts of interference (although large numbers of such operations can in fact lead to quantum speedup). Low-interference operations include sparse unitaries, Grover reflections, short time/low energy Hamiltonian evolutions, and the Haar wavelet transform. Circuits built from such operations can be classically simulated via a Monte Carlo technique making use of a convex combination of two Markov chains. Applications to query complexity, communication complexity, and the Wigner representation are discussed.

Various fixes and additions suggested by reviewers

References in corpus (9)

• Exponential algorithmic speedup by quantum walk
• The Resource Theory of Stabilizer Computation
• Instantaneous non-local computation of low T-depth quantum circuits
• Universal quantum computation with little entanglement
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• On the simulation of quantum circuits
• The quantum FFT can be classically simulated
• Classical simulability and the significance of modular exponentiation in Shor's algorithm
• Simulating Concordant Computations

Cited by in corpus (42)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• Resource theory of quantum non-Gaussianity and Wigner negativity
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Generalised phase kick-back: the structure of computational algorithms from physical principles
• Unbiased Simulation of Near-Clifford Quantum Circuits
• From estimation of quantum probabilities to simulation of quantum circuits
• Higher-order interference in extensions of quantum theory
• Deriving Grover's lower bound from simple physical principles
• The computational landscape of general physical theories
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Oracles and query lower bounds in generalised probabilistic theories
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Bounds on the power of proofs and advice in general physical theories
• Quantum Complexity Fluctuations from Nuclear and Hypernuclear Forces
• Clifford recompilation for faster classical simulation of quantum circuits
• Simulating Quantum Circuits with Sparse Output Distributions
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Exact and Efficient Simulation of Concordant Computation
• Phase-space negativity as a computational resource for quantum kernel methods
• Universal resources for quantum computing
• On computation with 'probabilities' modulo k
• Faster Born probability estimation via gate merging and frame optimisation
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Partial Distinguishability as a Coherence Resource in Boson Sampling
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Normalizer Circuits and Quantum Computation
• Heralded dissipative preparation of nonclassical states in a Kerr oscillator
• Ghost factors in Gauss-sum factorization with transmon qubits
• Sequency Hierarchy Truncation (SeqHT) for Adiabatic State Preparation and Time Evolution in Quantum Simulations
• Characterisation of multi-level quantum coherence without ideal measurements
• Strong analog classical simulation of coherent quantum dynamics
• Improved Strong Simulation of Universal Quantum Circuits
• Measure-independent description of wave-particle duality via coherence
• Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Electron dynamics induced by quantum cat-state light
• Oracle problems as communication tasks and optimization of quantum algorithms