Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Quantum interference as a resource for quantum speedup   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.

35
The categories of this paper are: mtrl-th
26
The categories of this paper are: bayes-an
28
The categories of this paper are: alg-geom
8
The categories of this paper are: hep-ex
30
The categories of this paper are: q-alg
16
The categories of this paper are: stat
2
The categories of this paper are: math
25
The categories of this paper are: patt-sol
7
The categories of this paper are: hep-th
20
The categories of this paper are: acc-phys
1
The categories of this paper are: cs
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
22
The categories of this paper are: chao-dyn
4
The categories of this paper are: cond-mat