A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917962979475456 |
|---|---|
| author | Patoary, Abu Musa Vikram, Amit Galitski, Victor |
| author_facet | Patoary, Abu Musa Vikram, Amit Galitski, Victor |
| contents | Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is $O(L^3)$ where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10008 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm Patoary, Abu Musa Vikram, Amit Galitski, Victor Quantum Physics Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is $O(L^3)$ where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized. |
| title | A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2503.10008 |