dorsal/arxiv
View SchemaBounds for Approximation in Total Variation Distance by Quantum Circuits
| Authors | E. Knill |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9508007 |
| URL | https://arxiv.org/abs/quant-ph/9508007 |
Abstract
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.
{
"annotation_id": "18a04456-bac0-43a2-bbb3-198c94417937",
"date_created": "2026-03-02T18:02:38.137000Z",
"date_modified": "2026-03-02T18:02:38.137000Z",
"file_hash": "ef3663d9b7bb84d5b1bd45ac5e684e740f6cec7921205bda243c44bbcf621e25",
"private": false,
"record": {
"abstract": "It was recently shown that for reasonable notions of approximation of states\nand functions by quantum circuits, almost all states and functions are\nexponentially hard to approximate [Knill 1995]. The bounds obtained are\nasymptotically tight except for the one based on total variation distance\n(TVD). TVD is the most relevant metric for the performance of a quantum\ncircuit. In this paper we obtain asymptotically tight bounds for TVD. We show\nthat in a natural sense, almost all states are hard to approximate to within a\nTVD of 2/e-\\epsilon even for exponentially small \\epsilon. The quantity 2/e is\nasymptotically the average distance to the uniform distribution. Almost all\nstates with probability amplitudes concentrated in a small fraction of the\nspace are hard to approximate to within a TVD of 2-\\epsilon. These results\nimply that non-uniform quantum circuit complexity is non-trivial in any\nreasonable model. They also reinforce the notion that the relative information\ndistance between states (which is based on the difficulty of transforming one\nstate to another) fully reflects the dimensionality of the space of qubits, not\nthe number of qubits.",
"arxiv_id": "quant-ph/9508007",
"authors": [
"E. Knill"
],
"categories": [
"quant-ph",
"math.CO"
],
"title": "Bounds for Approximation in Total Variation Distance by Quantum Circuits",
"url": "https://arxiv.org/abs/quant-ph/9508007"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "2cf6bfff-01e0-4e81-a97d-d082e63165a6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}