dorsal/arxiv
View SchemaActual computational time-cost of the Quantum Fourier Transform in a quantum computer using nuclear spins
| Authors | A. Saito, K. Kioi, Y. Akagi, N. Hashizume, K. Ohta |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0001113 |
| URL | https://arxiv.org/abs/quant-ph/0001113 |
Abstract
We found that the actual computational time-cost of the QFT is O(n 2^n) for large n in a quantum computer using nuclear spins. The computational cost of a quantum algorithm has usually been estimated as the sum of the universal gates required in such ideal mathematical models as the Quantum Turing Machine(QTM) and the quantum circuit. This cost is proportional to an actual time-cost in the physical implementation where all quantum operations can be achieved in the same time. However, if the implementation takes a different time for each quantum gate, there is a possibility that the actual time-cost will have a different behavior from the ideal cost. So we estimated the actual time-cost of the QFT in these implementations by considering the gating time. The actual time-cost is drastically different from O(n^2) estimated by complexity analysis.
{
"annotation_id": "97c10dbd-de75-4cac-8f78-74fbaf1f059a",
"date_created": "2026-03-02T18:01:35.462000Z",
"date_modified": "2026-03-02T18:01:35.462000Z",
"file_hash": "1140d3b2602c1ceb9e9ac6582a4802eb8bda59c8641c321e3d38d4a4050b6915",
"private": false,
"record": {
"abstract": "We found that the actual computational time-cost of the QFT is O(n 2^n) for\nlarge n in a quantum computer using nuclear spins. The computational cost of a\nquantum algorithm has usually been estimated as the sum of the universal gates\nrequired in such ideal mathematical models as the Quantum Turing Machine(QTM)\nand the quantum circuit. This cost is proportional to an actual time-cost in\nthe physical implementation where all quantum operations can be achieved in the\nsame time. However, if the implementation takes a different time for each\nquantum gate, there is a possibility that the actual time-cost will have a\ndifferent behavior from the ideal cost. So we estimated the actual time-cost of\nthe QFT in these implementations by considering the gating time. The actual\ntime-cost is drastically different from O(n^2) estimated by complexity\nanalysis.",
"arxiv_id": "quant-ph/0001113",
"authors": [
"A. Saito",
"K. Kioi",
"Y. Akagi",
"N. Hashizume",
"K. Ohta"
],
"categories": [
"quant-ph"
],
"title": "Actual computational time-cost of the Quantum Fourier Transform in a quantum computer using nuclear spins",
"url": "https://arxiv.org/abs/quant-ph/0001113"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1da8cded-e8cc-4f80-a34a-0445aa80c1fd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}