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

    Research output: Contribution to journalArticlepeer-review

    67 Downloads (Pure)

    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. 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
    Volume15
    Issue number12
    Early online date23 Nov 2015
    DOIs
    Publication statusPublished - 1 Dec 2016

    Keywords

    • Quantum computation
    • Interference
    • Algorithms
    • Analogue computers
    • Factorization
    • Exponential sums
    • Gauss sums

    Fingerprint

    Dive into the research topics of 'Analogue algorithm for parallel factorization of an exponential number of large integers: I - theoretical description'. Together they form a unique fingerprint.

    Cite this