Skip to content

Analogue algorithm for parallel factorization of an exponential number of large integers: I - theoretical description

Research output: Contribution to journalArticlepeer-review

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. 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 (Tamma in Quantum Inf Process 11128:1189, 2015).
Original languageEnglish
Pages (from-to)5259-5280
JournalQuantum Information Processing
Issue number12
Early online date23 Nov 2015
Publication statusPublished - 1 Dec 2016


Related information

Relations Get citation (various referencing formats)

ID: 5090666