dorsal/arxiv
View SchemaFast parallel circuits for the quantum Fourier transform
| Authors | Richard Cleve, John Watrous |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0006004 |
| URL | https://arxiv.org/abs/quant-ph/0006004 |
Abstract
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2^n with error bounded by epsilon. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log (n/epsilon)). We also give an upper bound of O(n (log n)^2 log log n) on the circuit size of the exact QFT modulo 2^n, for which the best previous bound was O(n^2). As an application of the above depth bound, we show that Shor's factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial-size, in combination with classical polynomial-time pre- and post-processing. In the language of computational complexity, this implies that factoring is in the complexity class ZPP^BQNC, where BQNC is the class of problems computable with bounded-error probability by quantum circuits with poly-logarithmic depth and polynomial size. Finally, we prove an Omega(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically optimal (for a reasonable range of values of epsilon).
{
"annotation_id": "a91cf2b8-915b-4673-bc03-de54b7edc59a",
"date_created": "2026-03-02T18:01:38.730000Z",
"date_modified": "2026-03-02T18:01:38.730000Z",
"file_hash": "d4fadea7ea9dd16b7317b8eb812e2044a2b98dc0ef3f74241e7654bd08aa4602",
"private": false,
"record": {
"abstract": "We give new bounds on the circuit complexity of the quantum Fourier transform\n(QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit\ndepth for computing an approximation of the QFT with respect to the modulus 2^n\nwith error bounded by epsilon. Thus, even for exponentially small error, our\ncircuits have depth O(log n). The best previous depth bound was O(n), even for\napproximations with constant error. Moreover, our circuits have size O(n log\n(n/epsilon)). We also give an upper bound of O(n (log n)^2 log log n) on the\ncircuit size of the exact QFT modulo 2^n, for which the best previous bound was\nO(n^2).\n As an application of the above depth bound, we show that Shor\u0027s factoring\nalgorithm may be based on quantum circuits with depth only O(log n) and\npolynomial-size, in combination with classical polynomial-time pre- and\npost-processing. In the language of computational complexity, this implies that\nfactoring is in the complexity class ZPP^BQNC, where BQNC is the class of\nproblems computable with bounded-error probability by quantum circuits with\npoly-logarithmic depth and polynomial size.\n Finally, we prove an Omega(log n) lower bound on the depth complexity of\napproximations of the QFT with constant error. This implies that the above\nupper bound is asymptotically optimal (for a reasonable range of values of\nepsilon).",
"arxiv_id": "quant-ph/0006004",
"authors": [
"Richard Cleve",
"John Watrous"
],
"categories": [
"quant-ph"
],
"title": "Fast parallel circuits for the quantum Fourier transform",
"url": "https://arxiv.org/abs/quant-ph/0006004"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d5597f45-5b6c-46fe-bc00-9143eb1e3642",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}