© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2104.11368 · Physical Review A

Ghost factors in Gauss-sum factorization with transmon qubits

Lin Htoo Zaw, Yuanzheng Paul Tan, Long Hoang Nguyen, Rangga P. Budoyo, Kun Hee Park, Zhi Yang Koh, Alessandro Landra, Christoph Hufnagel, Yung Szen Yap, Teck Seng Koh, Rainer Dumke

Published Dec 7, 2021• 3 citations

Abstract

A challenge in the Gauss-sum factorization scheme is the presence of ghost factors, nonfactors that behave similarly to actual factors of an integer, which might lead to the misidentification of nonfactors as factors or vice versa, especially in the presence of noise. We investigate type II ghost factors, which are the class of ghost factors that cannot be suppressed with techniques previously laid out in the literature. The presence of type II ghost factors and the coherence time of the qubit set an upper limit for the total experiment time, and hence the largest factorizable number with this scheme. Discernibility is a figure of merit introduced to characterize this behavior. We introduce preprocessing as a strategy to increase the discernibility of a system, and demonstrate the technique with a transmon qubit. This can bring the total experiment time of the system closer to its decoherence limit, and increase the largest factorizable number.

DOI: 10.1103/physreva.104.062606

Related papers

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•26 citations

NMR implementation of factoring large numbers with Gauß sums: Suppression of ghost factors

Xinhua Peng, Dieter Suter

Finding the factors of an integer can be achieved by various experimental techniques, based on an algorithm developed by Schleich et al . ( Fortschr. Phys. , 54 (2006) 856), which uses specific properties of Gauß sums. Experimental limitations usually require truncation of these series, but if the truncation parameter is too small, it is no longer possible to distinguish between factors and so-called “ghost" factors. Here, we discuss two techniques for distinguishing between true factors and ghost factors while keeping the number of terms in the sum constant or only slowly increasing. We experimentally test these modified algorithms in a nuclear spin system, using NMR.

arXiv:0803.3396•Europhysics Letters (EPL)•Nov 1, 2008•24 citations

Replication data for: Ghost factors in Gauss sum factorization with transmon qubits

Teck Seng Koh

Data for published figures in paper

•Jan 1, 2021•0 citations

Factorizing numbers with the Gauss sum technique

Dieter Suter, T. S. Mahesh, Nageswaran Rajendran +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.

•Jun 4, 2007•25 citations

Factoring numbers with interfering random waves

S. J. Weber, B. Chatel, B. Girard

We report on a new implementation of the factorisation of numbers using Gauss sums which improves tremendously the efficiency to eliminate all "ghost" factors. We show that by choosing randomly the terms in the Gauss sum, the required number of terms varies as ln N instead of . As an illustration, we present experimental results obtained by interfering thirty ultrashort laser pulses where we factorise 1340333404807. This new approach is totally general and can be implemented for all the experiments based on the Gauss sum.

Europhysics Letters (EPL)•Jul 29, 2008•22 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

A challenge in the Gauss-sum factorization scheme is the presence of ghost factors, nonfactors that behave similarly to actual factors of an integer, which might lead to the misidentification of nonfactors as factors or vice versa, especially in the presence of noise. We investigate type II ghost factors, which are the class of ghost factors that cannot be suppressed with techniques previously laid out in the literature. The presence of type II ghost factors and the coherence time of the qubit set an upper limit for the total experiment time, and hence the largest factorizable number with this scheme. Discernibility is a figure of merit introduced to characterize this behavior. We introduce preprocessing as a strategy to increase the discernibility of a system, and demonstrate the technique with a transmon qubit. This can bring the total experiment time of the system closer to its decoherence limit, and increase the largest factorizable number.

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.

Finding the factors of an integer can be achieved by various experimental techniques, based on an algorithm developed by Schleich et al . ( Fortschr. Phys. , 54 (2006) 856), which uses specific properties of Gauß sums. Experimental limitations usually require truncation of these series, but if the truncation parameter is too small, it is no longer possible to distinguish between factors and so-called “ghost" factors. Here, we discuss two techniques for distinguishing between true factors and ghost factors while keeping the number of terms in the sum constant or only slowly increasing. We experimentally test these modified algorithms in a nuclear spin system, using NMR.

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.

We report on a new implementation of the factorisation of numbers using Gauss sums which improves tremendously the efficiency to eliminate all "ghost" factors. We show that by choosing randomly the terms in the Gauss sum, the required number of terms varies as ln N instead of . As an illustration, we present experimental results obtained by interfering thirty ultrashort laser pulses where we factorise 1340333404807. This new approach is totally general and can be implemented for all the experiments based on the Gauss sum.

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.