dorsal/arxiv
View SchemaQuantum Lower Bounds for Fanout
| Authors | Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0312208 |
| URL | https://arxiv.org/abs/quant-ph/0312208 |
Abstract
We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancill\ae. Under this constraint, this bound is close to optimal. In the case of a non-constant number $a$ of ancillae, we give a tradeoff between $a$ and the required depth, that results in a non-trivial lower bound for fanout when $a = n^{1-o(1)}$.
{
"annotation_id": "c385a2a2-9569-4f24-a53e-08508dd6fa8b",
"date_created": "2026-03-02T18:02:03.602000Z",
"date_modified": "2026-03-02T18:02:03.602000Z",
"file_hash": "50a47b55f4b1ac31544593f50d87f33679d6dce11ef0b3e3357b1bd827ae760f",
"private": false,
"record": {
"abstract": "We prove several new lower bounds for constant depth quantum circuits. The\nmain result is that parity (and hence fanout) requires log depth circuits, when\nthe circuits are composed of single qubit and arbitrary size Toffoli gates, and\nwhen they use only constantly many ancill\\ae. Under this constraint, this bound\nis close to optimal. In the case of a non-constant number $a$ of ancillae, we\ngive a tradeoff between $a$ and the required depth, that results in a\nnon-trivial lower bound for fanout when $a = n^{1-o(1)}$.",
"arxiv_id": "quant-ph/0312208",
"authors": [
"Maosen Fang",
"Stephen Fenner",
"Frederic Green",
"Steven Homer",
"Yong Zhang"
],
"categories": [
"quant-ph"
],
"title": "Quantum Lower Bounds for Fanout",
"url": "https://arxiv.org/abs/quant-ph/0312208"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "97fd318d-b06b-4812-8a44-3667486ed91f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}