更改

量子计算 (查看源代码)

2020年11月5日 (四) 22:10的版本

添加2,837字节、 2020年11月5日 (四) 22:10

第616行：第616行：

：“因此，描述这种有用的量子计算机在任何给定时刻的状态的连续参数的数量必须是。。。大约10300... 我们能不能学会控制定义这样一个系统量子态的超过10300连续可变的参数？我的回答很简单“不，从来没有”。

−

== Developments ==

+

== Developments 发展==

−

=== Quantum computing models ===

+

=== Quantum computing models 量子计算模型===

There are a number of quantum computing models, distinguished by the basic elements in which the computation is decomposed. The four main models of practical importance are:

+

有许多量子计算模型，其区别在于计算被分解的基本元素。具有实际意义的四种主要模式是：

* [[quantum circuit|Quantum gate array]] (computation decomposed into a sequence of few-qubit [[quantum gate]]s)

−

+

*[[量子电路|量子门阵列]]（计算分解为几个量子比特的序列[[量子门]]s）

* [[One-way quantum computer]] (computation decomposed into a sequence of one-qubit measurements applied to a highly entangled initial state or [[cluster state]])

−

+

*[[单向量子计算机]]（将计算分解为一个量子比特测量序列，应用于高度纠缠的初始状态或[[团簇状态]]）

* [[Adiabatic quantum computation|Adiabatic quantum computer]], based on [[quantum annealing]] (computation decomposed into a slow continuous transformation of an initial [[Hamiltonian (quantum mechanics)|Hamiltonian]] into a final Hamiltonian, whose ground states contain the solution)<ref name="Das 2008 1061–1081">{{cite journal |first1=A. |last1=Das |first2=B. K. |last2=Chakrabarti |title=Quantum Annealing and Analog Quantum Computation | journal=[[Reviews of Modern Physics|Rev. Mod. Phys.]] |volume=80 |issue=3 |pages=1061–1081 |year=2008 |doi=10.1103/RevModPhys.80.1061 |bibcode=2008RvMP...80.1061D|citeseerx=10.1.1.563.9990 |arxiv=0801.2193 |s2cid=14255125 }}</ref>

−

+

*[[绝热量子计算|绝热量子计算机]]，基于[[量子退火]]（计算分解为初始[[哈密顿量（量子力学）|哈密顿量]]到最终哈密顿量的缓慢连续变换，其基态包含解）

* [[Topological quantum computer]]<ref name="Nayaketal2008">{{cite journal

−

+

*[[拓扑量子计算机]]

|arxiv = 0707.1889

第676行：第678行：

Conversely, any problem solvable by a quantum computer is also solvable by a classical computer; or more formally, any quantum computer can be simulated by a Turing machine. In other words, quantum computers provide no additional power over classical computers in terms of computability. This means that quantum computers cannot solve undecidable problems like the halting problem and the existence of quantum computers does not disprove the Church–Turing thesis.

−

相反，任何量子计算机可以解决的问题也可以用经典计算机来解决; 或者更正式地说，任何量子计算机都可以用图灵机来模拟。换句话说，就可计算性而言，量子计算机并不比传统计算机提供额外的能力。这意味着量子计算机不能解决不可判定的问题，例如停机问题和量子计算机的存在并不能否定丘奇-~~图灵论点。~~

+

相反，任何量子计算机可以解决的问题也可以用经典计算机来解决; 或者更正式地说，任何量子计算机都可以用图灵机来模拟。换句话说，就可计算性而言，量子计算机并不比传统计算机提供额外的能力。这意味着量子计算机不能解决不可判定的问题，例如停机问题和量子计算机的存在并不能否定''' 丘奇-图灵论点Church–Turing thesis'''。

The [[quantum Turing machine]] is theoretically important but the physical implementation of this model is not feasible. All four models of computation have been shown to be equivalent; each can simulate the other with no more than polynomial overhead.

−

+

[[量子图灵机]]理论上很重要，但是这个模型的物理实现是不可行的。所有四个计算模型都被证明是等价的；每一个都可以用不超过多项式的开销来模拟另一个。

As of yet, quantum computers do not satisfy the strong Church thesis. While hypothetical machines have been realized, a universal quantum computer has yet to be physically constructed. The strong version of Church's thesis requires a physical computer, and therefore there is no quantum computer that yet satisfies the strong Church thesis.

第686行：第688行：

到目前为止，量子计算机还不能满足教会强有力的论点。虽然假想的机器已经被实现，但是通用的量子计算机还有待物理建造。切奇论点的强势版本需要一台物理计算机，因此没有量子计算机能够满足切奇论点的强势。

−

=== Physical realizations ===

+

=== Physical realizations 物理实现===

For physically implementing a quantum computer, many different candidates are being pursued, among them (distinguished by the physical system used to realize the qubits):

−

+

对于物理实现量子计算机，人们正在寻找许多不同的候选方案，其中包括（以实现量子比特的物理系统为区别）：

*[[Superconducting quantum computing]]<ref name="ClarkeWilhelm2008">{{cite journal |last1=Clarke |first1=John |last2=Wilhelm |first2=Frank K. |title=Superconducting quantum bits |journal=Nature |date=18 June 2008 |volume=453 |issue=7198 |pages=1031–1042 |doi=10.1038/nature07128 |pmid=18563154 |bibcode=2008Natur.453.1031C |s2cid=125213662 |url=https://www.semanticscholar.org/paper/7ee1053ce63f33a62f2ea555547c514ce5f21054 }}</ref><ref>{{cite journal |last1=Kaminsky |first1=William M. |last2=Lloyd |first2=Seth |last3=Orlando |first3=Terry P. |title=Scalable Superconducting Architecture for Adiabatic Quantum Computation |arxiv=quant-ph/0403090 |date=12 March 2004 |bibcode=2004quant.ph..3090K }}</ref> (qubit implemented by the state of small superconducting circuits ([[Josephson junctions]])

第710行：第712行：

−

< ! -- ~~bqp~~ 的基本定义 -- >

+

< ! -- BQP 的基本定义 -- >

*Quantum dot computer, spatial-based (qubit given by electron position in double quantum dot)<ref>{{cite journal |last1=Fedichkin |first1=L. |last2=Yanchenko |first2=M. |last3=Valiev |first3=K. A. |title=Novel coherent quantum bit using spatial quantization levels in semiconductor quantum dot |journal=Quantum Computers and Computing |date=June 2000 |volume=1 |page=58 |bibcode=2000quant.ph..6097F |arxiv=quant-ph/0006097 }}</ref>

+

*基于空间的量子点计算机（由双量子点中的电子位置给出的量子比特）

The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP, for "bounded error, quantum, polynomial time". More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with error probability of at most 1/3. As a class of probabilistic problems, BQP is the quantum counterpart to BPP ("bounded error, probabilistic, polynomial time"), the class of problems that can be solved by polynomial-time probabilistic Turing machines with bounded error. It is known that BPP<math>\subseteq</math>BQP and is widely suspected that BQP<math>\nsubseteq</math>BPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity.

−

有界误差的量子计算机能够有效地求解的一类问题称为 BQP，即“有界误差，量子，多项式时间”问题。更正式地说，BQP 是一类问题，可以用多项式时间量子图灵机来解决，错误概率最多为1/3。作为一类概率问题，BQP 是 BPP (“有界误差，概率，多项式时间”)的量子对应物，BPP 是一类可用多项式时间概率图灵机解决的有界误差问题。众所周知，量子计算机比传统计算机在时间复杂度方面更强大，人们普遍怀疑量子计算机比传统计算机更强大。

+

有界误差的量子计算机能有效地解决的一类问题称为BQP，即“有界误差，量子，多项式时间”。更正式地说，BQP是一类可以用多项式时间量子图灵机求解的问题，其错误概率最大为1/3。作为一类概率问题，BQP是BPP（“有界误差，概率，多项式时间”）的量子对应物，BPP是一类可由具有有界误差的多项式时间概率图灵机求解的问题。众所周知，BPP<math>\subseteq</math>BQP，并被广泛怀疑为BQP<math>\nsubseteq</math>BPP，这直观地意味着量子计算机在时间复杂性方面比经典计算机更强大。

+

* Quantum computing using engineered quantum wells, which could in principle enable the construction of quantum computers that operate at room temperature<ref>{{cite journal |last1=Ivády |first1=Viktor |last2=Davidsson |first2=Joel |last3=Delegan |first3=Nazar |last4=Falk |first4=Abram L. |last5=Klimov |first5=Paul V. |last6=Whiteley |first6=Samuel J. |last7=Hruszkewycz |first7=Stephan O. |last8=Holt |first8=Martin V. |last9=Heremans |first9=F. Joseph |last10=Son |first10=Nguyen Tien |last11=Awschalom |first11=David D. |last12=Abrikosov |first12=Igor A. |last13=Gali |first13=Adam |title=Stabilization of point-defect spin qubits by quantum wells |journal=Nature Communications |date=6 December 2019 |volume=10 |issue=1 |page=5607 |doi=10.1038/s41467-019-13495-6 |pmid=31811137 |pmc=6898666 |arxiv=1905.11801 |bibcode=2019NatCo..10.5607I }}</ref><ref>{{cite news |title=Scientists Discover New Way to Get Quantum Computing to Work at Room Temperature |url=https://interestingengineering.com/scientists-discover-new-way-to-get-quantum-computing-to-work-at-room-temperature |work=interestingengineering.com |date=24 April 2020 }}</ref>

+

*量子计算使用工程量子阱，原则上可以建造在室温下工作的量子计算机

*Coupled [[Quantum wire|Quantum Wire]] (qubit implemented by a pair of Quantum Wires coupled by a [[Quantum point contact|Quantum Point Contact]])<ref>{{cite journal |last1=Bertoni |first1=A. |last2=Bordone |first2=P. |last3=Brunetti |first3=R. |last4=Jacoboni |first4=C. |last5=Reggiani |first5=S. |title=Quantum Logic Gates based on Coherent Electron Transport in Quantum Wires |journal=Physical Review Letters |date=19 June 2000 |volume=84 |issue=25 |pages=5912–5915 |doi=10.1103/PhysRevLett.84.5912 |pmid=10991086 |bibcode=2000PhRvL..84.5912B |hdl=11380/303796|hdl-access=free }}</ref><ref>{{cite journal |last1=Ionicioiu |first1=Radu |last2=Amaratunga |first2=Gehan |last3=Udrea |first3=Florin |title=Quantum Computation with Ballistic Electrons |journal=International Journal of Modern Physics B |date=20 January 2001 |volume=15 |issue=2 |pages=125–133 |doi=10.1142/S0217979201003521 |arxiv=quant-ph/0011051 |bibcode=2001IJMPB..15..125I |citeseerx=10.1.1.251.9617 |s2cid=119389613 }}</ref><ref>{{cite journal |last1=Ramamoorthy |first1=A |last2=Bird |first2=J P |last3=Reno |first3=J L |title=Using split-gate structures to explore the implementation of a coupled-electron-waveguide qubit scheme |journal=Journal of Physics: Condensed Matter |date=11 July 2007 |volume=19 |issue=27 |pages=276205 |doi=10.1088/0953-8984/19/27/276205 |bibcode=2007JPCM...19A6205R }}</ref>

+

*耦合的[[量子线|量子线]]（量子比特由一对量子线实现，量子线通过一对量子线耦合[[量子点接触|量子点接触]]）

−

< ! -- ~~bqp~~ 与基本复杂类的关系 -- >

+

< ! -- BQP 与基本复杂类的关系 -- >

*[[Nuclear magnetic resonance quantum computer]] (NMRQC) implemented with the [[nuclear magnetic resonance]] of molecules in solution, where qubits are provided by [[nuclear spin]]s within the dissolved molecule and probed with radio waves

+

*[[核磁共振量子计算机]]（NMRQC）利用溶液中分子的[[核磁共振]]来实现，其中量子比特由溶解分子中的[[核自旋]]s提供，并用无线电波探测

The suspected relationship of BQP to several classical complexity classes.

第733行：第743行：

*Solid-state NMR [[Kane quantum computer]]s (qubit realized by the nuclear spin state of [[phosphorus]] [[Electron donor|donors]] in [[silicon]])

+

*固态NMR[[Kane量子计算机]]s（由[[磷]][[电子施主|施主]]在[[硅]]中的核自旋态实现的量子比特）

The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that P<math>\subseteq</math>BQP<math>\subseteq</math>PSPACE; that is, all problems that can be efficiently solved by a deterministic classical computer can also be efficiently solved by a quantum computer, and all problems that can be efficiently solved by a quantum computer can also be solved by a deterministic classical computer with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, integer factorization and the discrete logarithm problem are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems that are believed not to be in P are also in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NP<math>\nsubseteq</math>BQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of NP-complete problems (if an NP-complete problem were in BQP, then it would follow from NP-hardness that all problems in NP are in BQP).

−

~~BQP 与 p、 NP 和 PSPACE 的确切关系尚不清楚。然而，众所周知，p~~ < math > subseteq </math > BQP < math > subseteq </math > PSPACE; 也就是说，所有可以由确定性经典计算机有效地解决的问题也可以由量子计算机有效地解决，所有可以由量子计算机有效地解决的问题也可以由具有 PSPACE 资源的确定性经典计算机解决。进一步怀疑 BQP 是 p 的严格超集，这意味着有些问题可以通过量子计算机有效地解决，而这些问题不能通过确定性经典计算机有效地解决。例如，整数分解和离散对数问题已知在 BQP 中，并且被怀疑在 p 之外。关于 BQP 与 NP 的关系，除了一些被认为不在 p 中的 NP 问题也在 BQP 中之外，我们知之甚少(例如，整数分解和离散对数问题都在 NP 中)。人们怀疑 NP < math > nsubseteq </math > BQP; 也就是说，人们相信存在有效的检验问题，而量子计算机无法有效地解决这些问题。作为这一信念的直接结果，我们还怀疑 BQP 是与 NP 完全问题类不相交的(如果一个 NP 完全问题在 BQP 中，那么它可以从 NP 难度推出所有 NP 完全问题在 BQP 中)。

+

BQP与P、NP和PSPACE的确切关系尚不清楚。然而，众所周知P<math>\subseteq</math>BQP<math>\subseteq</math>PSPACE，即所有能被确定性经典计算机有效解决的问题也能被量子计算机有效地解决，所有能被量子计算机有效解决的问题，也能用多项式空间资源的确定性经典计算机来求解。人们进一步怀疑BQP是P的严格超集，这意味着量子计算机可以有效地解决一些问题，而确定性经典计算机却不能有效地解决这些问题。例如，整数因式分解和离散对数问题已知在BQP中，并且被怀疑在P之外。关于BQP与NP的关系，除了一些被认为不在P中的NP问题也在BQP中（整数因式分解和离散对数问题都在NP中）之外，人们知之甚少，例如），有人怀疑NP<math>\nsubseteq</math>BQP；也就是说，人们相信存在着量子计算机无法有效解决的有效可检查问题。作为这种观点的直接结果，人们还怀疑BQP与NP完全问题类不相交（如果一个NP完全问题在BQP中，那么从NP硬度可以看出NP中的所有问题都在BQP中）。

+

*Electrons-on-[[helium]] quantum computers (qubit is the electron spin)

−

+

*量子计算机上的电子（量子比特是电子的自旋）

*[[Cavity quantum electrodynamics]] (CQED) (qubit provided by the internal state of trapped atoms coupled to high-finesse cavities)

−

+

*[[腔量子电动力学]]（CQED）（由与高精细腔耦合的囚禁原子的内部状态提供的量子比特）

第747行：第761行：

*[[Single-molecule magnet|Molecular magnet]]<ref>{{cite journal |last1=Leuenberger |first1=Michael N. |last2=Loss |first2=Daniel |title=Quantum computing in molecular magnets |journal=Nature |date=April 2001 |volume=410 |issue=6830 |pages=789–793 |doi=10.1038/35071024 |pmid=11298441 |arxiv=cond-mat/0011415 |bibcode=2001Natur.410..789L |s2cid=4373008 }}</ref> (qubit given by spin states)

+

*[[单分子磁体|分子磁体]]（量子比特由自旋态给出）

The relationship of BQP to the basic classical complexity classes can be summarized as follows:

第753行：第768行：

*[[Fullerene]]-based [[Electron paramagnetic resonance|ESR]] quantum computer (qubit based on the electronic spin of [[Endohedral fullerene|atoms or molecules encased in fullerenes]])<ref>{{cite journal |last1=Harneit |first1=Wolfgang |title=Fullerene-based electron-spin quantum computer |journal= Physical Review A|date=27 February 2002 |volume=65 |issue=3 |page=032322 |doi=10.1103/PhysRevA.65.032322 |bibcode=2002PhRvA..65c2322H }}https://www.researchgate.net/publication/257976907_Fullerene-based_electron-spin_quantum_computer</ref>

−

+

*基于[[富勒烯]]的[[电子顺磁共振| ESR]]量子计算机（基于[[内表面富勒烯|被富勒烯包围的原子或分子的电子自旋的量子比特]）

<math>\mathsf{P \subseteq BPP \subseteq BQP \subseteq PP \subseteq PSPACE}</math>

第759行：第774行：

*[[Optical quantum computing|Nonlinear optical quantum computer]] (qubits realized by processing states of different [[Normal mode|modes]] of light through both linear and [[Nonlinear optics|nonlinear]] elements)<ref name="qc1988">K. Igeta and Y. Yamamoto. "Quantum mechanical computers with single atom and photon fields." International Quantum Electronics Conference (1988) https://www.osapublishing.org/abstract.cfm?uri=IQEC-1988-TuI4</ref><ref name="chuang1995">I.L. Chuang and Y. Yamamoto. "Simple quantum computer." Physical Review A 52, 5, 3489 (1995) https://doi.org/10.1103/PhysRevA.52.3489</ref>

+

*[[光学量子计算|非线性光学量子计算机]]（通过线性和[[非线性光学|非线性]]元件处理光的不同[[正常模式|模式]]状态实现的量子比特）

It is also known that BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P#P), Theories of quantum gravity, such as M-theory and loop quantum gravity, may allow even faster computers to be built. However, defining computation in these theories is an open problem due to the problem of time; that is, within these physical theories there is currently no obvious way to describe what it means for an observer to submit input to a computer at one point in time and then receive output at a later point in time.

−

~~众所周知，BQP 包含在复杂性等级 # p 中(或者更准确地说是相关类型的决策问题 p~~ # p ) ，量子引力理论，如 m 理论和回圈量子重力理论，可能允许建立更快的计算机。然而，由于时间问题，在这些理论中定义计算是一个开放的问题; 也就是说，在这些物理理论中，目前没有明显的方法来描述观察者在一个时间点向计算机提交输入，然后在稍后的时间点接收输出意味着什么。

+

众所周知，BQP包含在复杂性类P中（或者更准确地说，在相关的决策问题类P#P）中，量子引力理论，如M理论和环路量子引力，可以使计算机的速度更快。然而，由于时间问题，在这些理论中定义计算是一个开放的问题；也就是说，在这些物理理论中，目前没有明显的方法来描述观察者在一个时间点向计算机提交输入，然后在以后的时间点接收输出意味着什么。

*[[Linear optical quantum computing|Linear optical quantum computer]] (qubits realized by processing states of different [[Normal mode|modes]] of light through linear elements e.g. mirrors, [[beam splitter]]s and [[phase shift module|phase shifters]])<ref name="KLM2001">{{cite journal |last1=Knill |first1=G. J. |last2=Laflamme |last3=Milburn |title=A scheme for efficient quantum computation with linear optics |journal=Nature |year=2001 |volume=409 |doi=10.1038/35051009 |bibcode = 2001Natur.409...46K |first2=R. |first3=G. J. |issue=6816 |pmid=11343107 |pages=46–52 |s2cid=4362012 |url=https://www.semanticscholar.org/paper/054b680165a7325569ca6e63028ca9cee7f3ac9a }}</ref>

+

*[[线性光学量子计算|线性光学量子计算机]]（通过线性元件（如反射镜、[[分束器]]和[[相移模块|移相器]]处理光的不同[[正常模式|模式]]状态实现的量子比特）

*[[Diamond-based quantum computer]]<ref name="Nizovtsevetal2004">{{cite journal

−

+

*[[金刚石量子计算机]]

|journal = Optics and Spectroscopy

第857行：第875行：

*[[Bose–Einstein condensate|Bose-Einstein condensate]]-based quantum computer<ref>{{cite journal |last1=Anderlini |first1=Marco |last2=Lee |first2=Patricia J. |last3=Brown |first3=Benjamin L. |last4=Sebby-Strabley |first4=Jennifer |last5=Phillips |first5=William D. |last6=Porto |first6=J. V. |title=Controlled exchange interaction between pairs of neutral atoms in an optical lattice |journal=Nature |date=July 2007 |volume=448 |issue=7152 |pages=452–456 |doi=10.1038/nature06011 |pmid=17653187 |lay-url=https://www.nist.gov/news-events/news/2007/07/thousands-atoms-swap-spins-partners-quantum-square-dance |arxiv=0708.2073 |bibcode=2007Natur.448..452A |s2cid=4410355 }}</ref>

+

*基于[[玻色-爱因斯坦凝聚体|玻色-爱因斯坦凝聚体]]的量子计算机

*Transistor-based quantum computer – string quantum computers with entrainment of positive holes using an electrostatic trap

−

+

*基于晶体管的量子计算机——使用静电阱夹带正空穴的串量子计算机

*Rare-earth-metal-ion-doped inorganic crystal based quantum computers<ref name="Ohlsson2002">{{cite journal

−

+

*稀土金属离子掺杂无机晶体量子计算机

|journal = Opt. Commun.

第927行：第946行：

*Metallic-like carbon nanospheres based quantum computers<ref name="Nafradi2016">{{cite journal |last1=Náfrádi |first1=Bálint |last2=Choucair |first2=Mohammad |last3=Dinse |first3=Klaus-Peter |last4=Forró |first4=László |title=Room temperature manipulation of long lifetime spins in metallic-like carbon nanospheres |journal=Nature Communications |date=18 July 2016 |volume=7 |issue=1 |page=12232 |doi=10.1038/ncomms12232 |pmid=27426851 |pmc=4960311 |arxiv=1611.07690 |bibcode=2016NatCo...712232N }}</ref>

−

+

*基于类金属碳纳米球的量子计算机

A large number of candidates demonstrates that quantum computing, despite rapid progress, is still in its infancy.{{citation needed|date=May 2020}}

−

+

大量的候选者表明，尽管量子计算技术发展迅速，但仍处于初级阶段。

−

==Relation to computability and complexity theory==

水流心不竞

561

个编辑

更改

量子计算 (查看源代码)

2020年11月5日 (四) 22:10的版本

导航菜单

搜索