Prime factorization using quantum variational imaginary time evolution

Raja Selvarajan; Vivek Dixit; Xingshan Cui; Travis S. Humble; Sabre Kais

doi:10.1038/s41598-021-00339-x

Prime factorization using quantum variational imaginary time evolution

Raja Selvarajan, Vivek Dixit, Xingshan Cui, Travis S. Humble, Sabre Kais

Quantum Science Center

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

The road to computing on quantum devices has been accelerated by the promises that come from using Shor’s algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as O(n⁵d) , where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method’s performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

Original language	English
Article number	20835
Journal	Scientific Reports
Volume	11
Issue number	1
DOIs	https://doi.org/10.1038/s41598-021-00339-x
State	Published - Dec 2021

Funding

We would like to thank Dr. Mario Motta and Dr. Stefan Woerner of IBM for useful discussion. We would like to acknowledge the support from National Science Foundation under award number 1955907. This material is based upon work supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Quantum Science Center. This manuscript has been authored by UT-Battelle, LLC, under contract DE-AC05-00OR22725 with the US Department of Energy (DOE). The US government retains and the publisher, by accepting the article for publication, acknowledges that the US government retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for US government purposes. DOE will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/ doe-public-access-plan).

Funders	Funder number
National Quantum Information Science Research Centers
Quantum Science Center
National Science Foundation	1955907
U.S. Department of Energy
Office of Science
Center for Selective C-H Functionalization, National Science Foundation
Center for Hierarchical Manufacturing, National Science Foundation
Savannah River Operations Office, U.S. Department of Energy
Idaho Operations Office, U.S. Department of Energy	DE-AC05-00OR22725

Access to Document

10.1038/s41598-021-00339-x

Cite this

@article{caeb955a9c77492e87f541219fed4c33,

title = "Prime factorization using quantum variational imaginary time evolution",

abstract = "The road to computing on quantum devices has been accelerated by the promises that come from using Shor{\textquoteright}s algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as O(n5d) , where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method{\textquoteright}s performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.",

author = "Raja Selvarajan and Vivek Dixit and Xingshan Cui and Humble, {Travis S.} and Sabre Kais",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2021",

month = dec,

doi = "10.1038/s41598-021-00339-x",

language = "English",

volume = "11",

journal = "Scientific Reports",

issn = "2045-2322",

publisher = "Nature Research",

number = "1",

}

TY - JOUR

T1 - Prime factorization using quantum variational imaginary time evolution

AU - Selvarajan, Raja

AU - Dixit, Vivek

AU - Cui, Xingshan

AU - Humble, Travis S.

AU - Kais, Sabre

PY - 2021/12

Y1 - 2021/12

N2 - The road to computing on quantum devices has been accelerated by the promises that come from using Shor’s algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as O(n5d) , where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method’s performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

AB - The road to computing on quantum devices has been accelerated by the promises that come from using Shor’s algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as O(n5d) , where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method’s performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

UR - http://www.scopus.com/inward/record.url?scp=85117728812&partnerID=8YFLogxK

U2 - 10.1038/s41598-021-00339-x

DO - 10.1038/s41598-021-00339-x

M3 - Article

C2 - 34675287

AN - SCOPUS:85117728812

SN - 2045-2322

VL - 11

JO - Scientific Reports

JF - Scientific Reports

IS - 1

M1 - 20835

ER -

Prime factorization using quantum variational imaginary time evolution

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this