Cargando…

Prime factorization using quantum annealing and computational algebraic geometry

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 just over 200000, the largest...

Descripción completa

Detalles Bibliográficos
Autores principales: Dridi, Raouf, Alghassi, Hedayat
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Nature Publishing Group 2017
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5318873/
https://www.ncbi.nlm.nih.gov/pubmed/28220854
http://dx.doi.org/10.1038/srep43048
_version_ 1782509271121920000
author Dridi, Raouf
Alghassi, Hedayat
author_facet Dridi, Raouf
Alghassi, Hedayat
author_sort Dridi, Raouf
collection PubMed
description 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 just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians.
format Online
Article
Text
id pubmed-5318873
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher Nature Publishing Group
record_format MEDLINE/PubMed
spelling pubmed-53188732017-02-24 Prime factorization using quantum annealing and computational algebraic geometry Dridi, Raouf Alghassi, Hedayat Sci Rep Article 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 just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians. Nature Publishing Group 2017-02-21 /pmc/articles/PMC5318873/ /pubmed/28220854 http://dx.doi.org/10.1038/srep43048 Text en Copyright © 2017, The Author(s) http://creativecommons.org/licenses/by/4.0/ This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/
spellingShingle Article
Dridi, Raouf
Alghassi, Hedayat
Prime factorization using quantum annealing and computational algebraic geometry
title Prime factorization using quantum annealing and computational algebraic geometry
title_full Prime factorization using quantum annealing and computational algebraic geometry
title_fullStr Prime factorization using quantum annealing and computational algebraic geometry
title_full_unstemmed Prime factorization using quantum annealing and computational algebraic geometry
title_short Prime factorization using quantum annealing and computational algebraic geometry
title_sort prime factorization using quantum annealing and computational algebraic geometry
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5318873/
https://www.ncbi.nlm.nih.gov/pubmed/28220854
http://dx.doi.org/10.1038/srep43048
work_keys_str_mv AT dridiraouf primefactorizationusingquantumannealingandcomputationalalgebraicgeometry
AT alghassihedayat primefactorizationusingquantumannealingandcomputationalalgebraicgeometry