Journal
PHYSICAL REVIEW A
Volume 90, Issue 2, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.90.022302
Keywords
-
Categories
Funding
- Direct For Mathematical & Physical Scien
- Division Of Physics [1068331] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 and 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available