dorsal/arxiv
View SchemaApproximation by Quantum Circuits
| Authors | E. Knill |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9508006 |
| URL | https://arxiv.org/abs/quant-ph/9508006 |
Abstract
In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.
{
"annotation_id": "fe40d89b-c11f-4cc2-a1d2-70bcd4bb8791",
"date_created": "2026-03-02T18:02:37.878000Z",
"date_modified": "2026-03-02T18:02:37.878000Z",
"file_hash": "137c1665771bc1b153944da35c45aa1a626ada7eaa3083e2b8387571de142666",
"private": false,
"record": {
"abstract": "In a recent preprint by Deutsch et al. [1995] the authors suggest the\npossibility of polynomial approximability of arbitrary unitary operations on\n$n$ qubits by 2-qubit unitary operations. We address that comment by proving\nstrong lower bounds on the approximation capabilities of g-qubit unitary\noperations for fixed g. We consider approximation of unitary operations on\nsubspaces as well as approximation of states and of density matrices by quantum\ncircuits in several natural metrics. The ability of quantum circuits to\nprobabilistically solve decision problem and guess checkable functions is\ndiscussed. We also address exact unitary representation by reducing the upper\nbound by a factor of n^2 and by formalizing the argument given by Barenco et\nal. [1995] for the lower bound. The overall conclusion is that almost all\nproblems are hard to solve with quantum circuits.",
"arxiv_id": "quant-ph/9508006",
"authors": [
"E. Knill"
],
"categories": [
"quant-ph",
"math.CO"
],
"title": "Approximation by Quantum Circuits",
"url": "https://arxiv.org/abs/quant-ph/9508006"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "02592c88-7aeb-40f4-b1ac-0333014b1fab",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}