quantum-computing - 用量子计算机解决国际象棋

Question

鉴于国际象棋游戏的博弈树复杂度至少为¹⁰¹²³，并且量子计算机最终可能会比经典计算机快数百万倍；量子算法是否有可能在一生中处理每种可能的移动组合？

Answer 1

也许吧，但重点是什么——它需要以某种方式存储已经检查过的移动路径，并且考虑到大量可能的路径，这将是不可能的（请记住，路径比已知宇宙中的原子多得多）

Answer 2

这是我对使用量子机解决NP问题的理解：

使用量子机器的效率取决于您对cost function问题建模的实现。

我想定义一个成本函数——多项式包括所有可能的移动组合——并传递给量子机器。每一步都是一个布尔变量。

使用量子机器解决 NP Complete 或 NP 难题有几个要求（约束）：

1. 问题中的变量数小于或等于 Quantum Machine 芯片中的 qubit（量子位）数
2. 多项式必须是QUBO问题（二次无约束二进制优化） - 通过对 2 个量子位施加力（基于当前的量子机技术，希望 HOBO（高阶二进制优化 - 本论文）多项式将来可以被量子芯片接受）

如果满足这些约束，那么我们可以将 NP 问题的复杂性降低到较低的程度。（例如从 O(N^3) 到 O(N^2)）

目前的量子机有多达 512 个量子比特（D-Wave Two System），它可以解决多达 2^512 的复杂度问题。