Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Zhongguo kexue. Wulixue Lixue Tianwenxue

Research progress on low-resource quantum algorithms for integer factorization

YAN Bao, Wentao Yang, shijie wei, Guilu Long

Published Apr 23, 2026• 0 citations
Publisher

Abstract

大数分解问题是经典 RSA 公钥密码体系安全基石。 Shor 量子算法虽能在多项式时间内求解该问题,但其实现所需的巨量物理资源使得短期内无法对实用规模 RSA 构成实际威胁。清华大学物理系龙桂鲁研究组围绕低资源大数分解量子算法展开系列研究。一方面,团队提出“经典格基约化 + 量子优化”的量经混合分解算法(HAIFA),在国际上首次实现了在量子硬件的 48 位整数分解,刷新量子硬件设备分解整数的世界纪录。另一方面,针对 Regev 高维分解算法,团队提出基于中间去计算技术的时空复杂度可调通用计算框架 (STAIF),从理论上将空间复杂度从 O (n 3/2) 降至 O(n log n),并完成相关方案的实验验证。这些研究为大数分解提供“近期可用”和“远期优化”的两种互补的方案,为评估量子计算对经典密码体系的威胁提供了新的分析依据。

DOI
10.1360/sspma-2026-0168

Related papers

The status and prospect of quantum-classical combination integer factorization algorithm

Bao YAN, Shijie Wei, Guilu LONG

整数分解问题不仅是经典的数学难题,更是广泛应用的 RSA 公钥密码体制的安全基石。自上世纪八十年代 RSA 密码问世以来,它受到了前所未有的关注,并得到了广泛而深入的研究。对该问题的研究推动了多个领域的发展,尤其是 Shor 量子大数分解算法提出后,更是直接推动了量子计算领域的发展。本文简要回顾了该问题的研究历史及重要进展,以及随着量子计算技术的发展,该问题研究的技术路线与研究角度所发生的变化,特别是2022年中国学者提出的可以利用现在一代的量子计算机运行的量子经典融合大数分解算法的原理,及其加速机制。国际最新进展表明,该技术路线的分解能力已从算法初期的48比特(2022年)提升至100比特(2024年),意大利与德国联合团队基于格基约化理论与张量网络的复杂性分析,进一步验证了其比特资源与时间复杂度均满足多项式约束。本文系统梳理该领域的技术演进脉络,并基于算法扩展性实验与抗量子密码迁移进程,探讨其对未来信息安全体系的潜在影响。

Scientia Sinica Informationis•May 26, 2025•3 citations

Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm

Wentao Yang, Bao Yan, Muxi Zheng +3 more

The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from \( O(n^{3/2}) \) to \( O(n^{5/4}) \), and refined strategies achieve \( O(n \log n) \)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor \( N = 35 \), verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.

quant-pharXiv:2511.18198•Nov 25, 2025•0 citations

An Overview of Regev’s Quantum Factoring Algorithm and Its Recent Developments

Rick Lan Chen

Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.

Applied and Computational Engineering•Nov 28, 2024•2 citations

An Overview of Quantum Algorithms

Seiichiro Tani

量子コンピュータは,量子力学の原理を用いて計算を行うコンピュータであり,現在のコンピュータを超える計算能力を発揮することが期待されている.そのためには,量子コンピュータのハードウェアを効果的に使って計算を行うアルゴリズム(量子アルゴリズム)が必要となる.本稿では,これまで行われてきた量子アルゴリズム研究を概観し,課題と展望について議論する

Denshi Jouhou Tsuushin Gakkai Tsuushin Sosaieti magajin/B-plus/Denshi Jouhou Tsuushin Gakkai Tsuushin Sosaeti magajin•Jan 1, 2020•0 citations

A Novel Hybrid Quantum Circuit for Integer Factorization: End-to-End Evaluation in Simulation and Real Quantum Hardware

Jesse Van Griensven Thé, Victor Oliveira Santos, Bahram Gharabaghi

The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.

Journal of Cybersecurity and Privacy•Apr 10, 2026•0 citations

Development and research of software and methods for constructing quantum algorithms for solving NP class problems

С. М. Гушанский, Viktor Potapov, Максим Сергеевич Коваленко

В современных науке и технике постоянно возникает необходимость в решении таких стратегически важных задач, как предсказание погоды и расчет климатических изменений, создание онкологических препаратов, обработка сигналов из Вселенной для поиска внеземных цивилизаций, обработка символьной информации, криптоанализ, опережающий расчет траекторий движущихся воздушных и космических объектов и другие задачи. Практическая реализация перечисленных задач на современных, даже суперкомпьютерных, системах требует недопустимо большого промежутка времени или вообще невозможна. Научная новизна данного направления выражается в разработке методики построения модульной моделирующей системы квантовых вычислений с открытой архитектурой, а также моделирующей системы выполнения квантовых алгоритмов. Целью работы является рассмотрение приемов моделирования квантовых вычислений и реализации алгоритмов решения задач NP класса. In modern science and technology, there is a constant need to solve such strategically important tasks as predicting the weather and calculating climatic changes, creating cancer drugs, processing signals from the Universe to search for extraterrestrial civilizations, processing symbolic information, cryptanalysis, and anticipatory calculation of the trajectories of moving air and space objects, etc. The practical implementation of the listed tasks on modern, even supercomputer systems requires an unacceptably long period of time or is impossible at all. The scientific novelty of this direction is expressed in the development of a methodology for constructing a modular modeling system of quantum computing with an open architecture, as well as a modeling system for executing quantum algorithms. The aim of the work is to consider techniques for modeling quantum computations and implementing algorithms for solving NP class problems.

Вестник Адыгейского государственного университета серия «Естественно-математические и технические науки»•Sep 28, 2021•0 citations
大数分解问题是经典 RSA 公钥密码体系安全基石。 Shor 量子算法虽能在多项式时间内求解该问题,但其实现所需的巨量物理资源使得短期内无法对实用规模 RSA 构成实际威胁。清华大学物理系龙桂鲁研究组围绕低资源大数分解量子算法展开系列研究。一方面,团队提出“经典格基约化 + 量子优化”的量经混合分解算法(HAIFA),在国际上首次实现了在量子硬件的 48 位整数分解,刷新量子硬件设备分解整数的世界纪录。另一方面,针对 Regev 高维分解算法,团队提出基于中间去计算技术的时空复杂度可调通用计算框架 (STAIF),从理论上将空间复杂度从 O (n 3/2) 降至 O(n log n),并完成相关方案的实验验证。这些研究为大数分解提供“近期可用”和“远期优化”的两种互补的方案,为评估量子计算对经典密码体系的威胁提供了新的分析依据。
整数分解问题不仅是经典的数学难题,更是广泛应用的 RSA 公钥密码体制的安全基石。自上世纪八十年代 RSA 密码问世以来,它受到了前所未有的关注,并得到了广泛而深入的研究。对该问题的研究推动了多个领域的发展,尤其是 Shor 量子大数分解算法提出后,更是直接推动了量子计算领域的发展。本文简要回顾了该问题的研究历史及重要进展,以及随着量子计算技术的发展,该问题研究的技术路线与研究角度所发生的变化,特别是2022年中国学者提出的可以利用现在一代的量子计算机运行的量子经典融合大数分解算法的原理,及其加速机制。国际最新进展表明,该技术路线的分解能力已从算法初期的48比特(2022年)提升至100比特(2024年),意大利与德国联合团队基于格基约化理论与张量网络的复杂性分析,进一步验证了其比特资源与时间复杂度均满足多项式约束。本文系统梳理该领域的技术演进脉络,并基于算法扩展性实验与抗量子密码迁移进程,探讨其对未来信息安全体系的潜在影响。
The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from O(n3/2) O(n^{3/2}) O(n3/2) to O(n5/4) O(n^{5/4}) O(n5/4), and refined strategies achieve O(nlog⁡n) O(n \log n) O(nlogn)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor N=35 N = 35 N=35, verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.
Factoring large integers has long been a computationally difficult problem in classical computing, forming the foundation of widely used encryption methods like RSA. In 1994, Shor’s quantum algorithm introduced a revolutionary method for factoring integers exponentially faster than classical algorithms, laying the groundwork for quantum cryptography. Despite numerous attempts to enhance Shor’s algorithm over the last three decades, significant breakthroughs remained elusive until Regev’s discovery in 2023. Regev introduced a novel, multi-dimensional version of the quantum factoring algorithm, achieving a substantial improvement by reducing the required number of quantum gates to O(n^2 lo g⁡n )(n^(3/2) log⁡n ), compared to Shor’s originalO(n^2 lo g⁡n )original O(n^2 log⁡n ) gate complexity. Although Regev’s approach offers a significant speedup, it comes with increased qubit requirements and relies on an unproven number theory assumption. This paper presents an overview of Regev’s factoring algorithm, including a review of Shor’s work for context, followed by an examination of key recent developments and follow-up research. These include efforts to reduce the qubit count, improve error resilience, generalizegeneralise Regev’s algorithm to related problems, and validate the number theory assumption. This review serves as an accessible entry point for researchers interested in the rapidly evolving field of quantum computing and factoring algorithms.
量子コンピュータは,量子力学の原理を用いて計算を行うコンピュータであり,現在のコンピュータを超える計算能力を発揮することが期待されている.そのためには,量子コンピュータのハードウェアを効果的に使って計算を行うアルゴリズム(量子アルゴリズム)が必要となる.本稿では,これまで行われてきた量子アルゴリズム研究を概観し,課題と展望について議論する
The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
В современных науке и технике постоянно возникает необходимость в решении таких стратегически важных задач, как предсказание погоды и расчет климатических изменений, создание онкологических препаратов, обработка сигналов из Вселенной для поиска внеземных цивилизаций, обработка символьной информации, криптоанализ, опережающий расчет траекторий движущихся воздушных и космических объектов и другие задачи. Практическая реализация перечисленных задач на современных, даже суперкомпьютерных, системах требует недопустимо большого промежутка времени или вообще невозможна. Научная новизна данного направления выражается в разработке методики построения модульной моделирующей системы квантовых вычислений с открытой архитектурой, а также моделирующей системы выполнения квантовых алгоритмов. Целью работы является рассмотрение приемов моделирования квантовых вычислений и реализации алгоритмов решения задач NP класса. In modern science and technology, there is a constant need to solve such strategically important tasks as predicting the weather and calculating climatic changes, creating cancer drugs, processing signals from the Universe to search for extraterrestrial civilizations, processing symbolic information, cryptanalysis, and anticipatory calculation of the trajectories of moving air and space objects, etc. The practical implementation of the listed tasks on modern, even supercomputer systems requires an unacceptably long period of time or is impossible at all. The scientific novelty of this direction is expressed in the development of a methodology for constructing a modular modeling system of quantum computing with an open architecture, as well as a modeling system for executing quantum algorithms. The aim of the work is to consider techniques for modeling quantum computations and implementing algorithms for solving NP class problems.