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

arXiv:0810.4372

Factoring integers with Young's N-slit interferometer

John F. Clauser, Jonathan P. Dowling

Published Oct 24, 2008• 5 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.0810.4372

Related papers

Factoring integers with Young’sN-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. \textcopyright{} 1996 The American Physical Society.

Physical Review A•Jun 1, 1996•72 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

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

Factoring and Fourier transformation with a Mach-Zehnder interferometer

Johann Summhammer

The scheme of Clauser and Dowling [Phys. Rev. A 53, 4587 (1996)] for factoring $N$ by means of an $N$-slit interference experiment is translated into an experiment with a single Mach-Zehnder interferometer. With dispersive phase shifters, the ratio of the coherence length to wavelength limits the numbers that can be factored. A conservative estimate permits $N\ensuremath{\approx}{10}^{7}$. It is furthermore shown that sine and cosine Fourier coefficients of a real periodic function can be obtained with such an interferometer.

arXiv:quant-ph/9708047•Physical Review A•Nov 1, 1997•22 citations

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.
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.
The scheme of Clauser and Dowling [Phys. Rev. A 53, 4587 (1996)] for factoring NNN by means of an NNN-slit interference experiment is translated into an experiment with a single Mach-Zehnder interferometer. With dispersive phase shifters, the ratio of the coherence length to wavelength limits the numbers that can be factored. A conservative estimate permits $N\ensuremath{\approx}{10}^{7}$. It is furthermore shown that sine and cosine Fourier coefficients of a real periodic function can be obtained with such an interferometer.
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.