按年被提到
20022017 · 1 次2026
物理与量子›量子计算·arXiv:quant-ph/0205095 · quant-ph

Circuit for Shor's algorithm using 2n+3 qubits

使用 2n+3 个量子比特的 Shor 算法线路
Stephane Beauregard · 2002

把 Shor 分解算法所需量子比特数压到 2n+3 的线路

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2017-12-14 · 最近 2025-04-22
4不同的人
4活跃月份
4讨论串
20被引(OpenAlex)

试图最小化用 Shor 算法分解 n 位整数所需的量子比特数,给出一个使用 2n+3 个量子比特、O(n^3 lg(n)) 个基本量子门、深度为 O(n^3) 的线路。该线路可在经典计算机上于多项式时间内构造,并且完全通用,不依赖待分解整数的任何性质。

HN 为什么提它

评论者用它说明分解 n 位整数的 Shor 算法只需约 2n 个量子比特,并据此推算出 1024 位 RSA 约需 2051 个逻辑量子比特。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1Shor 算法与量子傅里叶变换
2量子线路与量子门
3模算术(modular arithmetic)
4大 O 复杂度记法

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先读 Shor 算法原文,明白需要多少量子比特和哪些步骤,再看如何把它压缩到 2n+3 个比特。

  1. 1
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    目标线路实现的就是 Shor 的分解算法,模幂运算是资源消耗的主要来源。

    读分解化归为求阶的思路、量子傅里叶变换与模幂运算两部分。

  2. 2
    Circuit for Shor's algorithm using 2n+3 qubits使用 2n+3 个量子比特的 Shor 算法线路 · 2002 · 就是这篇

    目标论文:2n+3 量子比特的 Shor 线路。

    读如何用模加法、模乘法构造模幂运算,并复用比特以节省寄存器。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用archgoon · 2017-12

“According to this paper:”

引用论文说明 Shor 算法只需 2n+3 个量子比特
Getting the World Quantum Ready原评论 ↗
引用FartyMcFarter · 2022-07

“According to this paper, one can use 2n+3 qubits to factor an integer with n bits:”

引用论文:分解 n 位整数可以只用 2n+3 个量子比特
Shor, I’ll do it (2007)原评论 ↗
引用smburdick · 2024-03

“It has been shown that, to factor an integer with n bits, Shor's algorithm requires ~2n logical qubits: Circuit for Shor's algorithm using 2n+3 qubits”

引用它说明分解 n 位整数,Shor 算法约需 2n 个逻辑量子比特
Google's threat model for post-quantum cryptography原评论 ↗
引用ryao · 2025-04

“You can crack 1024-bit RSA with 2051 logical qubits according to:”

引用它说明 1024 位 RSA 只需 2051 个逻辑量子比特即可破解
Fujitsu and RIKEN develop world-leading 256-qubit sup quantum computer原评论 ↗