⚛️ quantum physics

A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications

该论文提出了一种电路深度仅为 $\mathcal{O}(n^2+nt)$ 的无赖交替量子行走（LAQW）算法，显著降低了计算开销使其适用于含噪中等规模量子（NISQ）设备，并展示了其在基于混沌的对称密钥生成方案中的有效性与可复现性。

原作者： Natalie Gibson, Niklas Keckman, Andrea Marchesin, Matti Raasakka, Ilkka Tittonen

发布于 2026-04-17

📖 1 分钟阅读🧠 深度阅读

原作者： Natalie Gibson, Niklas Keckman, Andrea Marchesin, Matti Raasakka, Ilkka Tittonen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为LAQW（懒散交替量子行走）的新算法，旨在解决当前量子计算机（被称为 NISQ 设备，即“含噪声的中等规模量子计算机”）的一个大难题：电路太深，容易出错。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成**“在迷宫里找宝藏”**的故事。

1. 背景：迷宫里的“量子探险家”

想象有一个叫“量子探险家”的小人，他在一个巨大的网格迷宫（量子格点）里行走。

传统方法（CAQW）： 以前的方法（CAQW）就像是一个极其严格的指挥官。探险家每一步都必须严格听从指令：要么向左，要么向右，要么向上，要么向下。
- 问题： 为了控制这个探险家在巨大的迷宫里不乱跑，指挥官需要发出非常复杂、非常长的指令序列（电路深度）。在现在的量子计算机上，指令太长意味着等待时间太久，量子比特（探险家的“能量”）还没走到终点就“睡着”了（退相干/噪声），导致结果全是乱码。
- 后果： 虽然这种方法能产生很好的随机性（适合做加密），但现在的机器跑不动，跑起来全是错。

2. 创新：引入“懒散”的探险家（LAQW）

作者们想出了一个绝妙的主意：让探险家变得“懒散”一点（Lackadaisical）。

新规则： 在 LAQW 模型中，探险家不仅可以选择向左或向右，还可以选择**“原地踏步”**（在格点上打个盹，或者原地转圈）。
比喻： 想象你在玩一个电子游戏。以前的游戏里，你必须每帧都按方向键，稍微慢一点就掉坑里。现在的游戏里，你可以按“暂停”或者“原地待机”。
神奇的效果：
1. 更简单： 因为允许“原地踏步”，我们不需要那么复杂的指令来控制探险家。这就好比把原本需要绕地球一圈的复杂路线，简化成了几条直路。
2. 更深层的随机性： 这种“懒散”反而让探险家的路径更加不可预测。就像你在拥挤的集市里，如果允许大家偶尔停下来发呆，人群的流动模式会比大家一直机械地走更难以预测。
3. 核心突破： 这种新方法将所需的“指令长度”（电路深度）从原来的 $O(n^2t)$ 降低到了 $O(n^2 + nt)$ 。
- 通俗解释： 以前跑完这个迷宫需要 10000 步指令，现在只需要 1000 步。这就像把原本需要跑马拉松的路程，缩短成了短跑，现在的量子计算机完全能跑完，而且不容易累（出错）。

3. 应用：用“量子混沌”造一把“万能钥匙”

既然探险家的路径变得既不可预测（像混沌系统）又可重复（只要给同样的初始条件），作者们就用它来制造加密密钥。

造钥匙的过程：
1. 设定初始条件： 就像给探险家设定一个“出生点”和“心情参数”（初始参数）。
2. 开始行走： 让探险家在迷宫里跑 $t$ 步。
3. 拍照统计： 跑完后，统计探险家出现在迷宫各个位置的概率。
4. 提取密钥： 把这些概率数据通过一套“翻译器”（后处理算法，包括素数取模等），变成一串 0 和 1 的密码（密钥）。
为什么安全？
- 混沌特性： 就像蝴蝶效应，初始条件只要有一丁点变化（比如参数变了 1%），探险家最后的位置分布就会完全不同。这意味着，黑客如果想猜出你的钥匙，哪怕猜错了一个小数点，生成的钥匙也会完全不同，完全无法破解。
- 可重复性： 对于合法的通信双方，只要他们手里拿着完全一样的“初始条件”（种子），他们就能生成完全一样的钥匙，从而进行加密和解密。

4. 实验结果：真的好用吗？

作者们在 IBM 的模拟量子计算机（FakeTorino）上做了测试：

深度大减： 新算法的电路深度比旧方法减少了约 88%。这意味着它非常适合现在的量子电脑。
抗噪能力强： 即使加上真实的量子噪声（就像在嘈杂的房间里听指令），生成的密钥依然高度一致。
随机性达标： 生成的密钥通过了美国国家标准与技术研究院（NIST）的一系列严格随机性测试，证明它真的像“真随机”一样难以预测。

总结

这篇论文就像是在说：

“以前的量子加密算法太‘卷’了，指令太长，现在的量子电脑跑不动。我们发明了一种**‘偷懒’的算法**，让量子粒子可以偶尔‘原地踏步’。这不仅让算法变快了（电路变浅了），让现在的量子电脑能跑得动，而且生成的随机密钥依然非常安全、不可预测。这为未来在量子计算机上实现真正的加密通信铺平了道路。”

一句话概括： 作者通过让量子行走“学会偷懒”，成功把复杂的加密算法简化到了现在的量子电脑能轻松运行的程度，同时保证了极高的安全性。

以下是基于论文《A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications》的详细技术总结：

1. 研究背景与问题 (Problem)

背景：离散时间量子行走（DTQW）因其混沌特性（对初始条件敏感、非线性、非周期性），被广泛应用于基于混沌的密码学应用，如图像加密和对称密钥生成。现有的方案多采用交替量子行走（AQW）或受控交替量子行走（CAQW）。
核心问题：
1. NISQ 设备限制：现有的 CAQW 模型在 $n \times n$ 格点上运行 $t$ 步时，其量子电路深度随 $O(n^2t)$ 增长。对于含噪声中等规模量子（NISQ）设备而言，过深的电路会导致严重的退相干和门错误，使得结果不可复现，无法用于加密解密。
2. 奇偶性限制：传统的 AQW/CAQW 要求格点大小为奇数以避免概率分布的可预测性（即 walker 只能停留在奇数或偶数位置），但这限制了量子傅里叶变换（QFT）等高效电路优化技术的应用，因为 QFT 通常要求系统维度为 2 的幂次（偶数）。
3. 密钥生成挑战：如何在噪声环境下，从量子行走的概率分布中提取出可复现、高熵且统计特性良好的对称密钥。

2. 方法论 (Methodology)

本文提出了一种新颖的**懒惰交替量子行走（Lackadaisical Alternating Quantum Walk, LAQW）**模型，并构建了一套完整的对称密钥生成方案。

A. LAQW 模型创新

核心机制：在 CAQW 的基础上，为格点图的每个节点引入自环（self-loop）。这使得“行走者”在每个时间步有概率“停留”在原位，而不仅仅是向左或向右移动。
优势：
- 解决奇偶性矛盾：自环的引入打破了传统 DTQW 中奇偶位置的严格交替，允许在偶数大小的格点（如 $2n \times 2n$ ）上产生非周期性的概率分布。
- 电路优化：由于引入了自环，移位算符（Shift Operator）对应的矩阵变为循环矩阵（Circulant Matrix）。这使得可以使用基于**量子傅里叶变换（QFT）**的方法来构建移位算符，从而显著降低电路深度。
电路复杂度：LAQW 的电路深度缩放为 $O(n^2 + nt)$ ，而传统 CAQW 为 $O(n^2t)$ 。当 $t$ 较大时，LAQW 具有显著优势。

B. 对称密钥生成方案

参数初始化：选择初始位置 $(x_0, y_0)$ 、硬币旋转参数 $\alpha, \theta_0, \theta_1$ 、步数 $t$ 以及控制比特串 $K$ 。
数据采集与后处理：
- 运行量子行走 $S$ 次（shots），收集各格点位置的计数。
- 区间舍入（Interval Rounding）：将计数映射到整数区间，以消除微小统计波动，确保不同实验间的可复现性。
- 素数模映射（Prime-Modulus Mapping）：将舍入后的计数映射为字节值。利用素数模运算打破原始分布的非均匀性，生成近似均匀的字节分布。
熵估计与密钥提取：
- 使用**最小熵（Min-entropy）**评估量子源的随机性，采用 Clopper-Pearson 方法构建置信区间以获得保守估计。
- 应用**剩余哈希引理（Leftover Hash Lemma, LHL）**确定可提取的均匀密钥长度。
- 实施加权比特提取：根据初始硬币状态参数 $\alpha$ 对多次运行的结果进行加权，提取最终密钥。

3. 主要贡献 (Key Contributions)

提出 LAQW 模型：首次将“懒惰”量子行走（LQW）引入交替量子行走架构，成功在偶数格点上实现了混沌行为，并兼容 QFT 优化。
显著的电路深度降低：证明了 LAQW 的电路深度从 $O(n^2t)$ 降低至 $O(n^2 + nt)$ 。在 IBM FakeTorino 后端模拟中，相比 CAQW 实现了约 88% 的电路深度缩减。
完整的密钥生成协议：设计了一套从量子测量到 128 位对称密钥生成的完整流程，包括去噪、均匀化处理和熵提取。
全面的性能评估：在 NISQ 噪声环境下（使用 IBM FakeTorino 后端）验证了方案的可行性，包括统计随机性、可复现性和抗噪性。

4. 实验结果 (Results)

电路效率：
- 在 $8 \times 8$ 格点（LAQW）与 $7 \times 7$ 格点（CAQW）的对比中，LAQW 在 $t=20$ 时最大深度仅为 550，而 CAQW 高达 5064（在 GenericBackendV2 模拟器下）。
- 在考虑硬件连接拓扑（FakeTorino）后，LAQW 依然保持约 87.8% 的深度优势。
参数敏感性（混沌特性）：
- LAQW 对参数 $\theta_0, \theta_1, \alpha$ 的微小变化（ $\pm 1\%$ ）表现出比 CAQW 更高的敏感性（Hellinger 距离分别高出 30.12%, 29.63%, 18.98%）。
- 但在步数 $t$ 变化时，CAQW 更敏感。总体而言，LAQW 提供了足够的混沌特性以抵抗暴力破解。
统计随机性（NIST 测试）：
- 生成的 128 位密钥通过了 NIST SP 800-22 套件中的多项测试（频率、块频率、游程、最长游程、谱测试、累积和）。
- 原始比特串在“游程测试”中略有偏差，但经过熵提取后，最终密钥完全符合随机性要求。
- 相比之下，CAQW 生成的原始比特串在“块频率测试”中失败，表明其局部不平衡性更强。
可复现性与抗噪性：
- 在 100 次独立试验中，LAQW 生成的 128 位密钥的归一化汉明距离平均为 0.0003（几乎完全一致）。
- 在 IBM FakeTorino 噪声模拟下，密钥的可复现性依然保持极高（平均汉明距离 0.0002），证明方案对硬件噪声具有鲁棒性。

5. 意义与结论 (Significance)

NISQ 时代的可行性：该研究解决了量子行走算法在现有量子硬件上因电路过深而无法实用的瓶颈，为在 NISQ 设备上部署基于量子行走的密码学原语铺平了道路。
安全性提升：通过引入自环和素数模映射，LAQW 不仅提高了电路效率，还增强了密钥生成的统计均匀性和对初始参数的敏感性，从而提升了抵抗暴力破解和统计分析攻击的能力。
未来方向：虽然 LAQW 在电路深度上优于 CAQW，但作者指出当前硬件仍难以支撑大规模格点的运行。未来的工作需进一步优化概率分布的近似方法，并深入研究如何在保证密钥可复现性的同时最大化密钥对初始参数的敏感性。

总结：本文提出了一种针对 NISQ 设备优化的 LAQW 算法，通过引入自环和 QFT 优化技术，显著降低了电路深度，并成功构建了一套可复现、高熵且抗噪的对称密钥生成方案，展示了量子行走技术在混沌密码学领域的巨大潜力。