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

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting

Factorization of Numbers and Gauss Sums

Wolfgang P. Schleich

Published Jan 1, 2007• 1 citation
Publisher

Abstract

Gauss sums play an important role in number theory as well as quantum physics. We analyze quantum systems which implement Gauss sums and allow us to factor large integers. We review recent experiments. Article not available.
DOI
10.1364/cqo.2007.cmh2

Related papers

Factorization of numbers with Gauss sums: I. Mathematical background

Sabine Wölk, W. Merkel, Wolfgang P. Schleich +2 more

We use the periodicity properties of generalized Gauss sums to factor numbers. Moreover, we derive rules for finding the factors and illustrate this factorization scheme for various examples. This algorithm relies solely on interference and scales exponentially.

arXiv:1210.6474•New Journal of Physics•Oct 7, 2011•22 citations

Factorization with Gauss sums: scaling properties of ghost factors

M. Štefaňák, W. Merkel, W. P. Schleich +2 more

Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N . This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show that a proper choice of the truncation parameter of the Gauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.

New Journal of Physics•Oct 12, 2007•25 citations

Factorization of numbers with Gauss sums: III. Algorithms with entanglement

S Wölk, W P Schleich

We propose two algorithms to factor numbers using Gauss sums and entanglement: (i) in a Shor-like algorithm we encode the standard Gauss sum in one of two entangled states and (ii) in an interference algorithm we create a superposition of Gauss sums in the probability amplitudes of two entangled states. These schemes are rather efficient provided that there exists a fast algorithm that can detect a period of a function hidden in its zeros.

arXiv:1210.6491•New Journal of Physics•Jan 24, 2012•4 citations

Factorizing numbers with the Gauss sum technique: NMR implementations

T. S. Mahesh, Nageswaran Rajendran, Xinhua Peng +1 more

Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.

arXiv:quant-ph/0701205•Physical Review A•Jun 4, 2007•42 citations

Quantum Mechanics Meets Number Theory

Sabine Wölk, C. Feiler, Wolfgang P. Schleich

We suggest a way to determine the Riemann zeta function with the help of quantum mechanics. Furthermore, we discuss the factoring abilities of Gauss sums and introduce a way to calculate them with the help of entanglement.

International Conference on Quantum Information•Jan 1, 2011•0 citations

Comment on "NMR Experiment Factors Numbers with Gauss Sums"

Julia A. Wei Xiaohua Jones

Mehring et al. have recently described an elegant nuclear magnetic resonance (NMR) experiment implementing an algorithm to factor numbers based on the properties of Gauss sums. Similar experiments have also been described by Mahesh et al. In fact these algorithms do not factor numbers directly, but rather check whether a trial integer $\ell$ is a factor of a given integer $N$. Here I show that these NMR schemes cannot be used for factor checking without first implicitly determining whether or not $\ell$ is a factor of $N$.

arXiv:0704.2065•Apr 16, 2007•2 citations
Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N . This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show that a proper choice of the truncation parameter of the Gauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.
Several physics-based algorithms for factorizing large numbers were recently presented. A notable recent algorthm by Schleich et al. uses Gauss sums for distinguishing between factors and nonfactors. We demonstrate two NMR techniques that evaluate Gauss sums and thus implement their algorithm. The first one is based on differential excitation of a single spin magnetization by a cascade of rf pulses. The second method is based on spatial averaging and selective refocusing of magnetization for Gauss sums corresponding to factors. All factors of 16 637 and 52 882 363 are successfully obtained.
Mehring et al. have recently described an elegant nuclear magnetic resonance (NMR) experiment implementing an algorithm to factor numbers based on the properties of Gauss sums. Similar experiments have also been described by Mahesh et al. In fact these algorithms do not factor numbers directly, but rather check whether a trial integer ℓ\ellℓ is a factor of a given integer NNN. Here I show that these NMR schemes cannot be used for factor checking without first implicitly determining whether or not ℓ\ellℓ is a factor of NNN.