dorsal/arxiv
View SchemaThe quantum FFT can be classically simulated
| Authors | Dorit Aharonov, Zeph Landau, Johann Makowsky |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0611156 |
| URL | https://arxiv.org/abs/quant-ph/0611156 |
Abstract
In this note we describe a simple and intriguing observation: the quantum Fourier transform (QFT) over $Z_q$, which is considered the most ``quantum'' part of Shor's algorithm, can in fact be simulated efficiently by classical computers. More precisely, we observe that the QFT can be performed by a circuit of poly-logarithmic path-width, if the circuit is allowed to apply not only unitary gates but also general linear gates. Recalling the results of Markov and Shi [MaSh] and Jozsa [Jo] which provided classical simulations of such circuits in time exponential in the tree-width, this implies the result stated in the title. Classical simulations of the FFT are of course meaningless when applied to classical input strings on which their result is already known; Our observation might be interesting only in the context in which the QFT is used as a subroutine and applied to more interesting superpositions. We discuss the reasons why this idea seems to fail to provide an efficient classical simulation of the entire factoring algorithm. In the course of proving our observation, we provide two alternative proofs of the results of [MaSh,Jo] which we use. One proof is very similar in spirit to that of [MaSh] but is more visual, and is based on a graph parameter which we call the ``bubble width'', tightly related to the path- and tree-width. The other proof is based on connections to the Jones polynomial; It is very short, if one is willing to rely on several known results.
{
"annotation_id": "7d35d6e4-dede-4932-bf0f-846caf2dbf0e",
"date_created": "2026-03-02T18:02:31.148000Z",
"date_modified": "2026-03-02T18:02:31.148000Z",
"file_hash": "a326511729ad821ea29b8f6e051ed5ab5a4e057b67fdacf558f5f28c275d7768",
"private": false,
"record": {
"abstract": "In this note we describe a simple and intriguing observation: the quantum\nFourier transform (QFT) over $Z_q$, which is considered the most ``quantum\u0027\u0027\npart of Shor\u0027s algorithm, can in fact be simulated efficiently by classical\ncomputers.\n More precisely, we observe that the QFT can be performed by a circuit of\npoly-logarithmic path-width, if the circuit is allowed to apply not only\nunitary gates but also general linear gates. Recalling the results of Markov\nand Shi [MaSh] and Jozsa [Jo] which provided classical simulations of such\ncircuits in time exponential in the tree-width, this implies the result stated\nin the title.\n Classical simulations of the FFT are of course meaningless when applied to\nclassical input strings on which their result is already known; Our observation\nmight be interesting only in the context in which the QFT is used as a\nsubroutine and applied to more interesting superpositions. We discuss the\nreasons why this idea seems to fail to provide an efficient classical\nsimulation of the entire factoring algorithm.\n In the course of proving our observation, we provide two alternative proofs\nof the results of [MaSh,Jo] which we use. One proof is very similar in spirit\nto that of [MaSh] but is more visual, and is based on a graph parameter which\nwe call the ``bubble width\u0027\u0027, tightly related to the path- and tree-width. The\nother proof is based on connections to the Jones polynomial; It is very short,\nif one is willing to rely on several known results.",
"arxiv_id": "quant-ph/0611156",
"authors": [
"Dorit Aharonov",
"Zeph Landau",
"Johann Makowsky"
],
"categories": [
"quant-ph"
],
"title": "The quantum FFT can be classically simulated",
"url": "https://arxiv.org/abs/quant-ph/0611156"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "db8db767-f95d-43cf-bce9-dfa17220a01e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}