Prime factorization using quantum annealing and computational algebraic geometry

Article, Preprint English OPEN
Dridi, Raouf ; Alghassi, Hedayat (2017)
  • Publisher: Nature Publishing Group
  • Journal: Scientific Reports, volume 7 (issn: 2045-2322, eissn: 2045-2322)
  • Related identifiers: doi: 10.1038/srep43048, pmc: PMC5318873
  • Subject: G.1.6 | Mathematics - Commutative Algebra | Mathematics - Algebraic Geometry | E.3 | I.1.2 | Article | Quantum Physics | Computer Science - Cryptography and Security

We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to ... View more
  • References (15)
    15 references, page 1 of 2

    C.J.C. Burges, Factoring as optimization, Tech. Report MSR-TR-2002-83, Microsoft Research, January 2002.

    Cristian S. Calude, Elena Calude, and Michael J. Dinneen, Guest column: Adiabatic quantum computing challenges, SIGACT News 46 (2015), no. 1, 40{61.

    Vicky Choi, Minor-embedding in adiabatic quantum computation: I. the parameter setting problem, Quantum Information Processing 7 (2008), no. 5, 193{209.

    David A. Cox, John B. Little, and Donal O'Shea, Using algebraic geometry, Graduate texts in mathematics, Springer, New York, 1998.

    M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Quantum annealing with manufactured spins, Nature 473 (2011), no. 7346, 194{198.

    Cai Jun, G. Macready William, and Roy Aidan, A practical heuristic for nding graph minors, Preprint arXiv:1406.2741 (2014).

    A.Yu. Kitaev, Quantum measurements and the abelian stabilizer problem, quant-ph/9511026 (1995).

    T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, S. Uchaikin, A. B. Wilson, and G. Rose, Entanglement in a quantum annealing processor, Phys. Rev. X 4 (2014), 021041.

    [MNM+16] Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, and Rainer Blatt, Realization of a scalable shor algorithm, Science 351 (2016), no. 6277, 1068{1070.

    [SS10] [SSV13] [Stu96] [TAA15] Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), no. 5, 1484{1509. MR 1471990

  • Metrics
    No metrics available
Share - Bookmark