V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
flowfire
V2EX  ›  程序员

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

  •  
  •   flowfire · 2020-09-07 16:35:34 +08:00 · 3288 次点击
    这是一个创建于 1298 天前的主题,其中的信息可能已经有所发展或是发生改变。

    忽然想到来着

    17 条回复    2020-09-09 20:58:48 +08:00
    typetraits
        1
    typetraits  
       2020-09-07 16:45:09 +08:00   ❤️ 8
    时间复杂度和硬件无关……
    xomix
        2
    xomix  
       2020-09-07 16:48:24 +08:00
    没有更换计算框架就变更计算逻辑的说法。
    bruce0
        3
    bruce0  
       2020-09-07 16:48:52 +08:00   ❤️ 1
    时间复杂度和算力没有关系,只和算法有关
    只要算法没变,时间复杂度就不会变

    算力提高,会降低计算时间
    假设, 普通计算机需要算 10 分钟,量子计算机可能不用 1 秒就算完了
    misdake
        4
    misdake  
       2020-09-07 16:58:37 +08:00
    在最理想的情况下,在创建所有可能性之后,想要剔除掉不正确的答案也要 O(n)次检查吧
    flowfire
        5
    flowfire  
    OP
       2020-09-07 17:17:53 +08:00
    @typetraits #1 物理规则改变之后。。。。是有关的
    kop1989
        6
    kop1989  
       2020-09-07 17:23:03 +08:00   ❤️ 1
    lz 的意思是,因为量子计算机是叠加态(即可以一次性得出所有组合),所以 n 无论是多少都是一次穷举 /回溯,所以都是 1 ?
    不太了解量子计算机的本质原理,但是我理解是不是穷举可以一次性得出,但是回溯法是不是不行?
    kop1989
        7
    kop1989  
       2020-09-07 17:24:06 +08:00
    而且穷举之后的检查能不能利用量子计算?毕竟检查输出的是布尔。
    across
        8
    across  
       2020-09-07 17:24:29 +08:00
    好像是的··· 穷举算力的会退化到 O(1)吧。 类似 GPU 并行处理机制,太早看的,忘了··· 反正 20 年里用不上。
    gwy15
        9
    gwy15  
       2020-09-07 17:29:44 +08:00   ❤️ 10
    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
        10
    learningman  
       2020-09-07 19:05:48 +08:00
    楼上几位可能真错了,量子计算机不能算经典计算机
    我记得新闻见过一个亿级库的 O(1)查找量子算法
    xupefei
        11
    xupefei  
       2020-09-07 19:15:27 +08:00 via iPhone
    量子计算机不是非确定性图灵机。
    chocovon
        12
    chocovon  
       2020-09-07 20:48:27 +08:00
    算法的复杂度确实跟硬件无关,降低复杂度的前提就是要换算法,只是量子计算机可以运行某些特定的算法而已
    elfive
        13
    elfive  
       2020-09-07 21:15:42 +08:00 via iPhone
    @typetraits #1 话没有错,不过应用到量子计算机上,肯定不是采用现在的算法了嘛,利用了量子的特性开发出来的算法,理论上是应该可以降低复杂度的。
    aguesuka
        14
    aguesuka  
       2020-09-08 00:10:20 +08:00 via Android
    说时间复杂度和算法无关的没学过模电吗?如果知道模拟电路里加减乘除模方对数都是 o(1)不知作何感想。
    aguesuka
        15
    aguesuka  
       2020-09-08 00:12:07 +08:00 via Android   ❤️ 1
    "算法"=>"硬件"
    jorneyr
        16
    jorneyr  
       2020-09-08 09:00:18 +08:00
    查表法就是 O(1) 了 =_=!!!
    lengyihan
        17
    lengyihan  
       2020-09-09 20:58:48 +08:00 via Android
    量子计算机到底是啥。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5319 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 48ms · UTC 09:16 · PVG 17:16 · LAX 02:16 · JFK 05:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.