arXiv:1210.6491 · New Journal of Physics

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

S Wölk, W P Schleich

Published Jan 24, 2012• 4 citations

Abstract

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.

DOI: 10.1088/1367-2630/14/1/013049

Related papers

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

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.

Aug 17, 20164 citations

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.6474New Journal of PhysicsOct 7, 201123 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, 20101 citation

Factorization of numbers with Gauss sums: II. Suggestions for implementation with chirped laser pulses

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

We propose three implementations of the Gauss sum factorization schemes discussed in part I of this series (Wölk et al 2011 New J. Phys. 13 103007): (i) a two-photon transition in a multi-level ladder system induced by a chirped laser pulse, (ii) a chirped one-photon transition in a two-level atom with a periodically modulated excited state and (iii) a linearly chirped one-photon transition driven by a sequence of ultrashort pulses. For each of these quantum systems, we show that the excitation probability amplitude is given by an appropriate Gauss sum. We provide rules on how to encode the number N to be factored in our system and how to identify the factors of N in the fluorescence signal of the excited state.

arXiv:1210.6487New Journal of PhysicsOct 7, 201112 citations

Factorizing numbers with classical interference: several implementations in optics

Andon A. Rangelov

Truncated Fourier, Gauss, Kummer and exponential sums can be used to factorize numbers: for a factor these sums equal unity in absolute value, whereas they nearly vanish for any other number. We show how this factorization algorithm can emerge from superpositions of classical light waves and we present a number of simple implementations in optics.

arXiv:0811.2070Journal of Physics B Atomic Molecular and Optical PhysicsJan 12, 200919 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, 200725 citations