量子科技中心_量科网

求解非线性丢番图系统是整数优化和密码学的数学核心。虽然一般无界问题不可判定，但即使在有界整数域上，最坏情况下它仍然是经典难解的。在这项工作中，该团队引入了一个完全可逆的量子算法框架，专门用于求解有界整数域上的任意多项式丢番图方程。该团队方法的核心是显式地、在门级综合一个用于振幅放大的评估预言机。通过使用原位二进制补码算术和路由操作将多项式约束相干地评估到单个回收累加器中，这种无垃圾策略实现了底层非线性算术的紧凑且可扩展的综合。通过分析推导和经验电路模拟，该团队证明了对于 \(n\) 个变量、最大次数 \(d\) 和区间长度 \(N\)，整体空间复杂度由 \(q = \mathcal{O}((n + d^2)\log_2 N)\) 个逻辑量子比特界定。非克利福德Toffoli深度上界为 \(\mathcal{O}(q^2)\)。这种结构缩放指数对变量数量保持不变，仅由系数的汉明权重线性调制。通过超越抽象黑盒假设，这种显式架构综合保证了必要的量子算术仅作为有界多项式开销。这确保了相对于经典穷举搜索的二次加速，无论是检索唯一赋值还是动态枚举未知数量的解。