话说量子计算机算 n 皇后问题 的复杂度是不是 O(1)

[flowfire]

忽然想到来着

[typetraits]

时间复杂度和硬件无关……

[xomix]

没有更换计算框架就变更计算逻辑的说法。

[bruce0]

时间复杂度和算力没有关系,只和算法有关
只要算法没变,时间复杂度就不会变

算力提高,会降低计算时间
假设, 普通计算机需要算 10 分钟,量子计算机可能不用 1 秒就算完了

[misdake]

在最理想的情况下，在创建所有可能性之后，想要剔除掉不正确的答案也要 O(n)次检查吧

[flowfire]

@typetraits #1 物理规则改变之后。。。。是有关的

[kop1989]

lz 的意思是，因为量子计算机是叠加态（即可以一次性得出所有组合），所以 n 无论是多少都是一次穷举 /回溯，所以都是 1 ？
不太了解量子计算机的本质原理，但是我理解是不是穷举可以一次性得出，但是回溯法是不是不行？

[kop1989]

而且穷举之后的检查能不能利用量子计算？毕竟检查输出的是布尔。

[across]

好像是的··· 穷举算力的会退化到 O(1)吧。 类似 GPU 并行处理机制，太早看的，忘了··· 反正 20 年里用不上。

[gwy15]

n 皇后问题是 NP 完全问题，经典计算机最佳时间复杂度是 O(n!)，Rounak Jha, 2018 [1] 提出一种基于量子计算的算法，其时间复杂度为 O(N^3)，空间复杂度 O(N^2) 并在 IBM 量子实验平台上进行了模拟。

[1] A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience. arXiv:1806.10221

[learningman]

楼上几位可能真错了，量子计算机不能算经典计算机
我记得新闻见过一个亿级库的 O(1)查找量子算法

[xupefei]

量子计算机不是非确定性图灵机。

[chocovon]

算法的复杂度确实跟硬件无关，降低复杂度的前提就是要换算法，只是量子计算机可以运行某些特定的算法而已

[elfive]

@typetraits #1 话没有错，不过应用到量子计算机上，肯定不是采用现在的算法了嘛，利用了量子的特性开发出来的算法，理论上是应该可以降低复杂度的。

[aguesuka]

说时间复杂度和算法无关的没学过模电吗？如果知道模拟电路里加减乘除模方对数都是 o(1)不知作何感想。

[aguesuka]

"算法"=>"硬件"

[jorneyr]

查表法就是 O(1) 了 =_=!!!

[lengyihan]

量子计算机到底是啥。