基于量子行走搜索的子集和问题求解：电路设计与性能分析

《IEEE Transactions on Computers》：Solving the Subset Sum Problem via Quantum Walk Search

本文针对子集和问题(SSP)的量子加速需求，提出了一种基于Johnson图的量子行走搜索算法完整电路实现。研究团队设计了分别优化量子比特数（低宽度）和电路深度（低深度）的两种架构，通过顶点二进制编码(VBE)和新型插入/删除电路实现了无需量子随机存取存储器(QRAM)的多项式级资源消耗。与Grover搜索算法相比，该方案在T-count、T-depth等关键指标上均展现出渐进优势，为密码分析和组合优化问题的量子求解提供了实用化设计范式。

　　

在量子计算迅猛发展的今天，如何利用量子特性解决经典计算机难以应对的NP难问题成为前沿焦点。子集和问题(Subset Sum Problem, SSP)作为典型的NP完全问题，在资源分配、任务调度和密码分析等领域具有广泛应用。传统量子解决方案主要依赖Grover无结构搜索算法，虽然能实现二次加速，但未能充分利用问题本身的结构特性。这促使研究者探索更高效的量子行走(Quantum Walk)搜索框架，通过在特定图结构上的有向搜索来进一步提升计算效率。

意大利米兰理工大学的研究团队在《IEEE Transactions on Computers》上发表了题为"Solving the Subset Sum Problem via Quantum Walk Search"的研究论文，系统阐述了基于Johnson图的量子行走搜索算法完整实现方案。该研究创新性地提出了两种电路架构：低宽度设计最小化量子比特消耗，低深度设计优化电路执行效率，为不同资源约束下的实际应用提供了灵活选择。

研究团队采用了几项关键技术方法：首先利用Dicke态生成电路制备Johnson图顶点的均匀叠加态，通过顶点二进制编码器(VBE)将n元素集合中大小为k的子集编码为有序量子态；其次设计了新型量子行走更新算子，包含W态生成、元素采样和排序维护等模块，支持顶点间的高效转移；最后通过量子相位估计(QPE)实现近似反射算子，完成整个振幅放大流程。所有电路均采用Clifford+T门集进行复杂度量化，确保了在容错量子计算框架下的实际可行性。

电路设计架构

研究团队针对MNRS量子行走搜索算法的三个核心组件进行了精细化设计：顶点初始化电路(U_V)通过Dicke态和VBE编码实现了Johnson图顶点的均匀叠加，仅需O(n)级深度即可完成组合规模的态制备；Oracle电路(U_f)采用级联加法器结构计算子集元素和，通过并行比较实现目标值的标记识别；更新电路(U_U)的创新之处在于设计了历史无关的数据结构，确保插入删除操作后集合仍保持有序性，其中低深度版本采用并行比较交换策略，低宽度版本通过顺序比较最小化辅助量子比特使用。

性能对比分析

通过将量子行走搜索与Grover算法在Clifford+T门集下进行严格对比，研究发现当问题规模参数n≥213时，量子行走方案在T-count和T-depth指标上均表现出明显优势。特别在密码分析相关的大规模参数下（n≥213），量子行走的T-depth可比Grover算法降低约50%。对于衡量实际计算资源的T-depth×width指标，量子行走方案同样展现出渐进优势，证明其在实际量子设备上的应用潜力。

扩展应用前景

该设计可自然扩展至0-1背包问题等更复杂的组合优化场景，只需在Oracle电路中同时实施权重和价值的双重约束检查。研究还指出，量子行走框架可适配其他图结构（如正则图和非正则图），为Syndrome Decoding等密码分析问题提供通用解决方案。

该研究通过系统化的量子电路设计，首次实现了无需QRAM的Johnson图量子行走搜索完整方案，在理论复杂度和实际资源消耗间取得了最佳平衡。相比Grover算法，该方案不仅保持了二次加速特性，更通过利用问题结构信息获得了多项式级的实际改进，为后续量子算法硬件实现奠定了重要基础。随着量子纠错技术的成熟，这种结构化的搜索框架有望在密码分析、药物设计等复杂优化问题中发挥关键作用。