HackerPapers

arXiv:2308.06572quant-ph

An Efficient Quantum Factoring Algorithm

Oded Regev

Abstract

We show that $n$-bit integers can be factorized by independently running a quantum circuit with $\tilde{O}(n^{3/2})$ gates for $\sqrt{n}+4$ times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

arXiv comments
Journal reference
DOI
Subjects
quant-phQuantum Physics cs.CCComputational Complexity

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from Oct 2023 to Oct 2023. Found in 1 HN submission from Sep 2023 to Sep 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Java implementation of a quantum computing resistant cryptographic algorithm 1 comment

    • Quantum factoring may not be quite as far distant as you might think Most importantly, Shor is not the algorithm of choice for first-gen hardware where the central challenge is likely to be circuit depth due to error correction overhead. The current front-runner is a probably…

      japanuspusView on HNParent context

  2. Thirty Years Later, a Speed Boost for Quantum Factoring 1 comment

    • You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in…

      control-kView on HNParent context

  3. Thirty Years Later, a Speed Boost for Quantum Factoring 1 comment

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.