Analogue algorithm for parallel factorization of an exponential number of large integers. I: Theoretical description

DOI10.1007/S11128-015-1190-YMaRDI QIDQ513865zbMATH OpenOpenAlexFDO

Authors Vincenzo Tamma

Publication date 8 March 2017

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.04577

zbMATH Keywords

algorithmsinterferenceexponential sumsfactorizationGauss sumsquantum computationanalogue computers

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Factorization (11Y05)

Abstract: We describe a novel analogue algorithm that allows the simultaneous factorization of an exponential number of large integers with a polynomial number of experimental runs. It is the interference-induced periodicity of "factoring" interferograms measured at the output of an analogue computer that allows the selection of the factors of each integer [1,2,3,4]. At the present stage the algorithm manifests an exponential scaling which may be overcome by an extension of this method to correlated qubits emerging from n-order quantum correlations measurements. We describe the conditions for a generic physical system to compute such an analogue algorithm. A particular example given by an "optical computer" based on optical interference will be addressed in the second paper of this series [5].

Recommendations

• Analogue algorithm for parallel factorization of an exponential number of large integers. II: Optical implementation
• Factorization of integers with multi-path optical interference
• Factorization
• New factorization algorithm based on a continuous representation of truncated Gauss sums
• Asymptotically Fast Factorization of Integers

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• Boson sampling with non-identical single photons
• Factorization of numbers with Gauss sums. I: Mathematical background
• Factorization of numbers with Gauss sums. II: Suggestions for implementation with chirped laser pulses
• Factorization of numbers with Gauss sums: III. Algorithms with entanglement
• Factorization of numbers with physical systems
• Factorization of numbers with truncated Gauss sums at rational arguments
• Factorization with exponential sums
• Multi-boson correlation sampling
• New factorization algorithm based on a continuous representation of truncated Gauss sums
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computer Science
• Random renormalization in the semiclassical long-time limit of a precessing spin
• Sampling of bosonic qubits

Cited in

(4)

• Multi-boson correlation sampling
• Multipath correlation interference and controlled-NOT gate simulation with a thermal source
• Factorization of integers with multi-path optical interference
• Analogue algorithm for parallel factorization of an exponential number of large integers. II: Optical implementation

This page was built for publication: Analogue algorithm for parallel factorization of an exponential number of large integers. I: Theoretical description

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513865)