An Efficient Quantum Factoring Algorithm

Oded Regev

doi:10.1145/3708471

An Efficient Quantum Factoring Algorithm

Oded Regev

Computer Science

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

Abstract

We show that n-bit integers can be factorized by independently running a quantum circuit with gates for times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

Original language	English (US)
Article number	10
Journal	Journal of the ACM
Volume	72
Issue number	1
DOIs	https://doi.org/10.1145/3708471
State	Published - Jan 24 2025

Keywords

integer factorization
quantum computation
Shor's algorithm

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/3708471

Cite this

@article{e41bcc09bd624b429af7ebb3ec4ed4c6,

title = "An Efficient Quantum Factoring Algorithm",

abstract = "We show that n-bit integers can be factorized by independently running a quantum circuit with gates for times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.",

keywords = "integer factorization, quantum computation, Shor's algorithm",

author = "Oded Regev",

note = "Publisher Copyright: {\textcopyright} 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.",

year = "2025",

month = jan,

day = "24",

doi = "10.1145/3708471",

language = "English (US)",

volume = "72",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - An Efficient Quantum Factoring Algorithm

AU - Regev, Oded

PY - 2025/1/24

Y1 - 2025/1/24

N2 - We show that n-bit integers can be factorized by independently running a quantum circuit with gates for times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

AB - We show that n-bit integers can be factorized by independently running a quantum circuit with gates for times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

KW - integer factorization

KW - quantum computation

KW - Shor's algorithm

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

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

U2 - 10.1145/3708471

DO - 10.1145/3708471

M3 - Article

AN - SCOPUS:85217094505

SN - 0004-5411

VL - 72

JO - Journal of the ACM

JF - Journal of the ACM

IS - 1

M1 - 10

ER -

An Efficient Quantum Factoring Algorithm

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this