▲ 数独文化 · 脑伴数独教程
量子计算能解数独吗？能。数独是典型的约束满足问题，量子Grover算法可在平方根时间内搜索解空间。2023年研究人员在IBM量子计算机上成功求解4x4数独。
能，而且量子计算在数独这类"约束满足问题"上有理论上的加速。
什么是约束满足问题？数独就是一个典型——你需要找到一组数字，满足所有约束（行列宫不重复）。工厂排产、航班调度、芯片设计都是这类问题。
经典计算机怎么解数独？用回溯算法——试一个数，如果矛盾就退回来。最坏情况下需要试很多次。
量子计算机怎么解数独？理论上，量子计算机可以用"Grover算法"在平方根时间内搜索解空间。经典计算机需要O(2^n)，量子计算机只需要O(2^(n/2))。对于9x9数独，这个加速不明显（因为经典已经很快了），但对于更大的数独（16x16、25x25），量子加速就很重要了。
现实意义：数独是量子算法的"测试床"。研究人员用数独来验证量子算法的正确性，然后把这些算法应用到更复杂的现实问题（如药物分子设计、金融优化）。
目前进展：2023年，研究人员在IBM的量子计算机上成功求解了4x4数独。9x9数独还需要更多量子比特，预计5-10年内可以实现。