Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Factoring integers with Young’sN-slit interferometer

John F. Clauser, Jonathan P. Dowling

Published Jun 1, 1996• 72 citations
Publisher

Abstract

We show that a Young's N-slit interferometer can be used to factor the integer N. The device could factor four- or five-digit numbers in a practical fashion. This work shows how number theory may arise in physical problems, and may provide some insight as to how quantum computers can carry out factoring problems by interferometric means. \textcopyright{} 1996 The American Physical Society.

DOI
10.1103/physreva.53.4587

Related papers

Factoring integers with Young's N-slit interferometer

John F. Clauser, Jonathan P. Dowling

We show that a Young's N slit interferometer can be used to factor the integer N. The device could factor four- or five-digit numbers in a practical fashion. This work shows how number theory may arise in physical problems, and may provide some insight as to how quantum computers can carry out factoring problems by interferometric means.

arXiv:0810.4372•Oct 24, 2008•5 citations

Factoring integers with Young's N slit interferometer: Classical-analog versus quantum-digital computers

John F. Clauser, Jonathan P. Dowling

Summary form only given. We show that a Young's N-slit interferometer can be used to factor the integer N. When the number of slits is a product of integer factors, then an analysis of the diffraction pattern can be used to determine these factors. This work provides a simple example of number theory's appearance in physics, and can be helpful in understanding the advantages of quantum-digital over classical-analog computers in handling integer factoring problems.

Quantum Electronics and Laser Science Conference•Jun 7, 1996•0 citations

Rydberg-atom experiment for the integer factorization problem

Juyoung Park, Seokho Jeong, Minhyuk Kim +6 more

The task of factoring integers poses a significant challenge in modern cryptography, and quantum computing holds the potential to efficiently address this problem compared to classical algorithms. Thus, it is crucial to develop quantum computing algorithms to address this problem. This study introduces a quantum approach that utilizes Rydberg atoms to tackle the factorization problem. Experimental demonstrations are conducted for the factorization of small composite numbers such as 6 = 2 × 3 , 15 = 3 × 5 , and 35 = 5 × 7 . This approach involves employing Rydberg-atom graphs to algorithmically program binary multiplication tables, yielding many-body ground states that represent superpositions of factoring solutions. Subsequently, these states are probed using quantum adiabatic computing. Limitations of this method are discussed, specifically addressing the scalability of current Rydberg quantum computing for the intricate computational problem. Published by the American Physical Society 2024

arXiv:2312.08703•Physical Review Research•Jun 4, 2024•8 citations

Integer Factorization by Quantum Measurements

Giuseppe Mussardo, Andrea Trombettoni

Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer $N$ is achieved in a number of steps equal to the number $k$ of its prime factors, -- e.g., if $N$ is the product of two primes, two quantum measurements are enough, regardless of the number of digits $n$ of the number $N$. Since $k$ is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.

arXiv:2309.10757•Sep 19, 2023•2 citations

THEORETICAL AND EXPERIMENTAL STUDY OF A NEW ALGORITHM FOR FACTORING NUMBERS

Vincenzo Tamma

The security of codes, for example in credit card and government information, relies on the fact that the factorization of a large integer N is a rather costly process on a classical digital computer. Such a security is endangered by Shor's algorithm which employs entangled quantum systems to find, with a polynomial number of resources, the period of a function which is connected with the factors of N. We can surely expect a possible future realization of such a method for large numbers, but so far the period of Shor's function has been only computed for the number 15. Inspired by Shor's idea, our work aims to methods of factorization based on the periodicity measurement of a given continuous periodic factoring function which is physically implementable using an analogue computer. In particular, we have focused on both the theoretical and the experimental analysis of Gauss sums with continuous arguments leading to a new factorization algorithm. The procedure allows, for the first time, to factor several numbers by measuring the periodicity of Gauss sums performing first-order factoring'' interference processes. We experimentally implemented this idea by exploiting polychromatic optical interference in the visible range with a multi-path interferometer, and achieved the factorization of seven digit numbers. The physical principle behind this factoring interference procedure can be potentially exploited also on entangled systems, as multi-photon entangled states, in order to achieve a polynomial scaling in the number of resources.

•Jan 1, 2010•1 citation

Prime number factorization and degree of coherence of speckled light beams

Tianyu Cao, Xin Liu, Qian Chen +3 more

We discover a connection between a Gauss sum of number theory and the degree of coherence (DOC) of the field in a transverse plane of structured speckled light beams. We theoretically demonstrate and experimentally validate that prime number factorization can be achieved by manipulating the source beam's DOC in Young's double-slit experiment. The determination of whether a number can be factored is based solely on the visibility of the resulting interference patterns. Our findings offer new insights into information encryption and decryption, data compression, etc.

Optics Letters•Sep 3, 2024•5 citations
We show that a Young's N-slit interferometer can be used to factor the integer N. The device could factor four- or five-digit numbers in a practical fashion. This work shows how number theory may arise in physical problems, and may provide some insight as to how quantum computers can carry out factoring problems by interferometric means. \textcopyright{} 1996 The American Physical Society.
The task of factoring integers poses a significant challenge in modern cryptography, and quantum computing holds the potential to efficiently address this problem compared to classical algorithms. Thus, it is crucial to develop quantum computing algorithms to address this problem. This study introduces a quantum approach that utilizes Rydberg atoms to tackle the factorization problem. Experimental demonstrations are conducted for the factorization of small composite numbers such as 6 = 2 × 3 , 15 = 3 × 5 , and 35 = 5 × 7 . This approach involves employing Rydberg-atom graphs to algorithmically program binary multiplication tables, yielding many-body ground states that represent superpositions of factoring solutions. Subsequently, these states are probed using quantum adiabatic computing. Limitations of this method are discussed, specifically addressing the scalability of current Rydberg quantum computing for the intricate computational problem. Published by the American Physical Society 2024
Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer NNN is achieved in a number of steps equal to the number kkk of its prime factors, -- e.g., if NNN is the product of two primes, two quantum measurements are enough, regardless of the number of digits nnn of the number NNN. Since kkk is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.
The security of codes, for example in credit card and government information, relies on the fact that the factorization of a large integer N is a rather costly process on a classical digital computer. Such a security is endangered by Shor's algorithm which employs entangled quantum systems to find, with a polynomial number of resources, the period of a function which is connected with the factors of N. We can surely expect a possible future realization of such a method for large numbers, but so far the period of Shor's function has been only computed for the number 15. Inspired by Shor's idea, our work aims to methods of factorization based on the periodicity measurement of a given continuous periodic factoring function which is physically implementable using an analogue computer. In particular, we have focused on both the theoretical and the experimental analysis of Gauss sums with continuous arguments leading to a new factorization algorithm. The procedure allows, for the first time, to factor several numbers by measuring the periodicity of Gauss sums performing first-order factoring'' interference processes. We experimentally implemented this idea by exploiting polychromatic optical interference in the visible range with a multi-path interferometer, and achieved the factorization of seven digit numbers. The physical principle behind this factoring interference procedure can be potentially exploited also on entangled systems, as multi-photon entangled states, in order to achieve a polynomial scaling in the number of resources.
We discover a connection between a Gauss sum of number theory and the degree of coherence (DOC) of the field in a transverse plane of structured speckled light beams. We theoretically demonstrate and experimentally validate that prime number factorization can be achieved by manipulating the source beam's DOC in Young's double-slit experiment. The determination of whether a number can be factored is based solely on the visibility of the resulting interference patterns. Our findings offer new insights into information encryption and decryption, data compression, etc.