Analogue algorithm for parallel factorization of an exponential number of large integers I. Theoretical description
arXiv:1505.04577 · doi:10.1007/s11128-015-1190-y
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].
to be published in Quantum Information Processing (QIP)
References in corpus (16)
- Experimental demonstration of Shor's algorithm with quantum entanglement
- Demonstration of Shor's quantum factoring algorithm using photonic qubits
- Factorization of Numbers with the temporal Talbot effect: Optical implementation by a sequence of shaped ultrashort pulses
- Gauss sum factorization with cold atoms
- Multiboson Correlation Interferometry with arbitrary single-photon pure states
- From the Physics to the Computational Complexity of Multiboson Correlation Interference
- Factorizing Numbers with the Gauss Sum Technique: NMR Implementations
- Multi-Boson Correlation Sampling with Multi-mode Thermal Sources
- Factoring numbers with a single interferogram
- Multi-Boson Correlation Sampling
- NMR implementation of Factoring Large Numbers with GaußSums: Suppression of Ghost Factors
- Factorization of numbers with Gauss sums: I. Mathematical background
- Sampling of bosonic qubits
- Boson sampling with non-identical single photons
- Factorization of numbers with Gauss sums: II. Suggestions for implementations with chirped laser pulses
- Factorization of numbers with truncated Gauss sums at rational arguments
Cited by in corpus (6)
- From the Physics to the Computational Complexity of Multiboson Correlation Interference
- Multipath Correlation Interference and Controlled-NOT Gate Simulation with a Thermal Source
- Characterization of two distant double-slits by chaotic light second-order interference
- Spatial interference between pairs of disjoint optical paths with a single chaotic source
- The physics of thermal light second-order interference beyond coherence
- Which role does multiphoton interference play in small phase estimation in quantum Fourier transform interferometers?