dorsal/arxiv
View SchemaExact quantum Fourier transforms and discrete logarithm algorithms
| Authors | Michele Mosca, Christof Zalka |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0301093 |
| URL | https://arxiv.org/abs/quant-ph/0301093 |
Abstract
We show how the quantum fast Fourier transform (QFFT) can be made exact for arbitrary orders (first for large primes). For most quantum algorithms only the quantum Fourier transform of order $2^n$ is needed, and this can be done exactly. Kitaev \cite{kitaev} showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as ``amplitude amplification''. Although unlikely to be of any practical use, this construction e.g. allows to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that ``quantum'' need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely the parameters of the gates can be calculated efficiently.
{
"annotation_id": "c7263a79-1216-4b0b-9c00-244e935402fd",
"date_created": "2026-03-02T18:01:56.004000Z",
"date_modified": "2026-03-02T18:01:56.004000Z",
"file_hash": "e248115cf6303a814800a8d9b237c70cdb6df36d0dc70059de09da8ec167047c",
"private": false,
"record": {
"abstract": "We show how the quantum fast Fourier transform (QFFT) can be made exact for\narbitrary orders (first for large primes). For most quantum algorithms only the\nquantum Fourier transform of order $2^n$ is needed, and this can be done\nexactly. Kitaev \\cite{kitaev} showed how to approximate the Fourier transform\nfor any order. Here we show how his construction can be made exact by using the\ntechnique known as ``amplitude amplification\u0027\u0027. Although unlikely to be of any\npractical use, this construction e.g. allows to make Shor\u0027s discrete logarithm\nquantum algorithm exact. Thus we have the first example of an exact non black\nbox fast quantum algorithm, thereby giving more evidence that ``quantum\u0027\u0027 need\nnot be probabilistic. We also show that in a certain sense the family of\ncircuits for the exact QFFT is uniform. Namely the parameters of the gates can\nbe calculated efficiently.",
"arxiv_id": "quant-ph/0301093",
"authors": [
"Michele Mosca",
"Christof Zalka"
],
"categories": [
"quant-ph"
],
"title": "Exact quantum Fourier transforms and discrete logarithm algorithms",
"url": "https://arxiv.org/abs/quant-ph/0301093"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1a5f01fd-9d5c-476b-bc57-28236c4926cd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}