7,129
个编辑
更改
→量子复杂性理论
[[File:BQP complexity class diagram.svg|thumb|与几个经典复杂性类的可疑关系。<ref name="Nielsen, p. 42"/>]]
[[File:BQP complexity class diagram.svg|thumb|与几个经典复杂性类的可疑关系。<ref>Nielsen, p. 42</ref>]]
BQP 与P、NP和PSPACE的确切关系尚不清楚。但是，众所周知， P<math>\subseteq</math>BQP<math>\subseteq</math>空间；也就是说，所有确定性经典计算机可以有效解决的问题也可以由量子计算机有效解决，所有量子计算机可以有效解决的问题也可以由具有多项式空间资源的确定性经典计算机解决. 进一步怀疑 BQP 是 P 的严格超集，这意味着存在量子计算机可以有效解决的问题，而确定性经典计算机则无法有效解决。例如，整数分解和离散对数问题已知在 BQP 中并且被怀疑在 P 之外。 关于 BQP 与 NP 的关系，除了一些被认为不在 P 中的 NP 问题也在 BQP（整数分解和例如，离散对数问题都在 NP 中）。怀疑是 NP<math>\nsubseteq</math>BQP; 也就是说，人们认为存在量子计算机无法有效解决的可有效检查的问题。作为这种信念的直接结果，也有人怀疑 BQP 与NP 完全问题的类别不相交（如果 NP 完全问题在 BQP 中，那么从NP难度可以得出NP中的所有问题都在BQP)。<ref name=BernVazi>{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |doi=10.1137/S0097539796300921 |title=Quantum Complexity Theory |year=1997 |pages=1411–1473 |volume=26 |journal=SIAM Journal on Computing |url=http://www.cs.berkeley.edu/~vazirani/bv.ps |issue=5|citeseerx=10.1.1.144.7852 }}</ref>
BQP 与P、NP和PSPACE的确切关系尚不清楚。但是，众所周知， P<math>\subseteq</math>BQP<math>\subseteq</math>空间；也就是说，所有确定性经典计算机可以有效解决的问题也可以由量子计算机有效解决，所有量子计算机可以有效解决的问题也可以由具有多项式空间资源的确定性经典计算机解决. 进一步怀疑 BQP 是 P 的严格超集，这意味着存在量子计算机可以有效解决的问题，而确定性经典计算机则无法有效解决。例如，整数分解和离散对数问题已知在 BQP 中并且被怀疑在 P 之外。 关于 BQP 与 NP 的关系，除了一些被认为不在 P 中的 NP 问题也在 BQP（整数分解和例如，离散对数问题都在 NP 中）。怀疑是 NP<math>\nsubseteq</math>BQP; 也就是说，人们认为存在量子计算机无法有效解决的可有效检查的问题。作为这种信念的直接结果，也有人怀疑 BQP 与NP 完全问题的类别不相交（如果 NP 完全问题在 BQP 中，那么从NP难度可以得出NP中的所有问题都在BQP)。<ref name=BernVazi>{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |doi=10.1137/S0097539796300921 |title=Quantum Complexity Theory |year=1997 |pages=1411–1473 |volume=26 |journal=SIAM Journal on Computing |url=http://www.cs.berkeley.edu/~vazirani/bv.ps |issue=5|citeseerx=10.1.1.144.7852 }}</ref>
据推测，物理学的进一步进步可能会导致更快的计算机。例如，已经表明基于'''玻姆力学 Bohmian Mechanics'''的非局部隐变量量子计算机可以实现对<math>N</math>-- 项目数据库最多<math>O(\sqrt[3]{N})</math>步，比[[Grover算法]]略有加速，它运行在<math>O(\sqrt{N})</math>步。但是请注意，这两种搜索方法都不允许量子计算机在多项式时间内解决[[NP完全问题]]。<ref name="auto">{{cite web|url=http://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref> 量子引力理论，例如M 理论和圈量子引力，可能允许建造速度更快的计算机。然而，由于时间问题，在这些理论中定义计算是一个悬而未决的问题；也就是说，在这些物理理论中，目前没有明显的方法来描述观察者在某个时间点向计算机提交输入然后在稍后的时间点接收输出意味着什么。<ref>{{Cite journal|first=Scott|last=Aaronson|title=NP-complete Problems and Physical Reality|journal=ACM SIGACT News|volume=2005|arxiv=quant-ph/0502072|year=2005|bibcode=2005quant.ph..2072A|author-link=Scott Aaronson}} See section 7 "Quantum Gravity": "[…] to anyone who wants a test or benchmark for a favorite quantum gravity theory,[author's footnote: That is, one without all the bother of making numerical predictions and comparing them to observation] let me humbly propose the following: ''can you define Quantum Gravity Polynomial-Time?'' […] until we can say what it means for a 'user' to specify an 'input' and ‘later' receive an 'output'—''there is no such thing as computation, not even theoretically.''" (emphasis in original)</ref><ref name=":0">{{cite web | url=http://www.dwavesys.com/en/pressreleases.html#lm_2011 |title= D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation |access-date=30 May 2011 |date=25 May 2011 |publisher=D-Wave}}</ref>
据推测，物理学的进一步进步可能会导致更快的计算机。例如，已经表明基于'''玻姆力学 Bohmian Mechanics'''的非局部隐变量量子计算机可以实现对<math>N</math>-- 项目数据库最多<math>O(\sqrt[3]{N})</math>步，比[[Grover算法]]略有加速，它运行在<math>O(\sqrt{N})</math>步。但是请注意，这两种搜索方法都不允许量子计算机在多项式时间内解决[[NP完全问题]]。<ref name="auto">{{cite web|url=http://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref> 量子引力理论，例如M 理论和圈量子引力，可能允许建造速度更快的计算机。然而，由于时间问题，在这些理论中定义计算是一个悬而未决的问题；也就是说，在这些物理理论中，目前没有明显的方法来描述观察者在某个时间点向计算机提交输入然后在稍后的时间点接收输出意味着什么。<ref>{{Cite journal|first=Scott|last=Aaronson|title=NP-complete Problems and Physical Reality|journal=ACM SIGACT News|volume=2005|arxiv=quant-ph/0502072|year=2005|bibcode=2005quant.ph..2072A|author-link=Scott Aaronson}} See section 7 "Quantum Gravity": "[…] to anyone who wants a test or benchmark for a favorite quantum gravity theory,[author's footnote: That is, one without all the bother of making numerical predictions and comparing them to observation] let me humbly propose the following: ''can you define Quantum Gravity Polynomial-Time?'' […] until we can say what it means for a 'user' to specify an 'input' and ‘later' receive an 'output'—''there is no such thing as computation, not even theoretically.''" (emphasis in original)</ref><ref name=":0">{{cite web | url=http://www.dwavesys.com/en/pressreleases.html#lm_2011 |title= D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation |access-date=30 May 2011 |date=25 May 2011 |publisher=D-Wave}}</ref>
<br>
==参考文献==
==参考文献==