Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Bounds for Approximation in Total Variation Distance by Quantum Circuits   It was recently shown that for reasonable notions of approximation of states
and functions by quantum circuits, almost all states and functions are
exponentially hard to approximate [Knill 1995]. The bounds obtained are
asymptotically tight except for the one based on total variation distance
(TVD). TVD is the most relevant metric for the performance of a quantum
circuit. In this paper we obtain asymptotically tight bounds for TVD. We show
that in a natural sense, almost all states are hard to approximate to within a
TVD of 2/e-\epsilon even for exponentially small \epsilon. The quantity 2/e is
asymptotically the average distance to the uniform distribution. Almost all
states with probability amplitudes concentrated in a small fraction of the
space are hard to approximate to within a TVD of 2-\epsilon. These results
imply that non-uniform quantum circuit complexity is non-trivial in any
reasonable model. They also reinforce the notion that the relative information
distance between states (which is based on the difficulty of transforming one
state to another) fully reflects the dimensionality of the space of qubits, not
the number of qubits.

16
The categories of this paper are: stat
21
The categories of this paper are: adap-org
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
30
The categories of this paper are: q-alg
27
The categories of this paper are: comp-gas
33
The categories of this paper are: plasm-ph
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat
37
The categories of this paper are: supr-con
36
The categories of this paper are: cmp-lg
20
The categories of this paper are: acc-phys
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
1
The categories of this paper are: cs
5
The categories of this paper are: gr-qc