561
个编辑
更改
跳到导航
跳到搜索
第692行：
第692行： − 对于物理实现量子计算机，人们正在寻找许多不同的候选方案，其中包括（以实现量子比特的物理系统为区别）：+ − + 第701行：
第701行： + + 第707行：
第709行： + + + + 第715行：
第721行： − + − 有界误差的量子计算机能有效地解决的一类问题称为BQP，即“有界误差，量子，多项式时间”。更正式地说，BQP是一类可以用多项式时间量子图灵机求解的问题，其错误概率最大为1/3。作为一类概率问题，BQP是BPP（“有界误差，概率，多项式时间”）的量子对应物，BPP是一类可由具有有界误差的多项式时间概率图灵机求解的问题。众所周知，BPP<math>\subseteq</math>BQP，并被广泛怀疑为BQP<math>\nsubseteq</math>BPP，这直观地意味着量子计算机在时间复杂性方面比经典计算机更强大。+ − + − + 第748行：
第754行： − + 第761行：
第767行： − + 第768行：
第774行： − + 第774行：
第780行： − + 第782行：
第788行： − + − + 第875行：
第881行： − + − + 第946行：
第952行： − + − +
→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):
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]])
*[[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]])
*[[超导量子计算]]<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>（由小型超导电路状态实现的量子比特（[[约瑟夫森结]])
<!-- Power and limits of quantum computers -->
<!-- Power and limits of quantum computers -->
*[[Trapped ion quantum computer]] (qubit implemented by the internal state of trapped ions)
*[[Trapped ion quantum computer]] (qubit implemented by the internal state of trapped ions)
*[[束缚离子量子计算机]]（由束缚离子的内部状态实现的量子比特）
While quantum computers cannot solve any problems that classical computers cannot already solve, it is suspected that they can solve many problems faster than classical computers. For instance, it is known that quantum computers can efficiently factor integers, while this is not believed to be the case for classical computers. However, the capacity of quantum computers to accelerate classical algorithms has rigid upper bounds, and the overwhelming majority of classical calculations cannot be accelerated by the use of quantum computers.
While quantum computers cannot solve any problems that classical computers cannot already solve, it is suspected that they can solve many problems faster than classical computers. For instance, it is known that quantum computers can efficiently factor integers, while this is not believed to be the case for classical computers. However, the capacity of quantum computers to accelerate classical algorithms has rigid upper bounds, and the overwhelming majority of classical calculations cannot be accelerated by the use of quantum computers.
*Neutral atoms in [[Optical lattice]]s (qubit implemented by internal states of neutral atoms trapped in an optical lattice)<ref>{{Cite journal|last1=Khazali|first1=Mohammadsadegh|last2=Mølmer|first2=Klaus|date=2020-06-11|title=Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited-State Manifolds of Rydberg Atoms and Superconducting Circuits|journal=Physical Review X|volume=10|issue=2|pages=021054|doi=10.1103/PhysRevX.10.021054|bibcode=2020PhRvX..10b1054K|doi-access=free}}</ref><ref>{{Cite journal|last1=Henriet|first1=Loic|last2=Beguin|first2=Lucas|last3=Signoles|first3=Adrien|last4=Lahaye|first4=Thierry|last5=Browaeys|first5=Antoine|last6=Reymond|first6=Georges-Olivier|last7=Jurczak|first7=Christophe|date=2020-06-22|title=Quantum computing with neutral atoms|journal=Quantum|volume=4|page=327|doi=10.22331/q-2020-09-21-327|arxiv=2006.12326|s2cid=219966169}}</ref>
*Neutral atoms in [[Optical lattice]]s (qubit implemented by internal states of neutral atoms trapped in an optical lattice)<ref>{{Cite journal|last1=Khazali|first1=Mohammadsadegh|last2=Mølmer|first2=Klaus|date=2020-06-11|title=Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited-State Manifolds of Rydberg Atoms and Superconducting Circuits|journal=Physical Review X|volume=10|issue=2|pages=021054|doi=10.1103/PhysRevX.10.021054|bibcode=2020PhRvX..10b1054K|doi-access=free}}</ref><ref>{{Cite journal|last1=Henriet|first1=Loic|last2=Beguin|first2=Lucas|last3=Signoles|first3=Adrien|last4=Lahaye|first4=Thierry|last5=Browaeys|first5=Antoine|last6=Reymond|first6=Georges-Olivier|last7=Jurczak|first7=Christophe|date=2020-06-22|title=Quantum computing with neutral atoms|journal=Quantum|volume=4|page=327|doi=10.22331/q-2020-09-21-327|arxiv=2006.12326|s2cid=219966169}}</ref>
*[[光学晶格]]s中的中性原子（由被困在光学晶格中的中性原子的内部状态实现的量子比特）<ref>{{Cite journal|last1=Khazali|first1=Mohammadsadegh|last2=Mølmer|first2=Klaus|date=2020-06-11|title=Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited-State Manifolds of Rydberg Atoms and Superconducting Circuits|journal=Physical Review X|volume=10|issue=2|pages=021054|doi=10.1103/PhysRevX.10.021054|bibcode=2020PhRvX..10b1054K|doi-access=free}}</ref><ref>{{Cite journal|last1=Henriet|first1=Loic|last2=Beguin|first2=Lucas|last3=Signoles|first3=Adrien|last4=Lahaye|first4=Thierry|last5=Browaeys|first5=Antoine|last6=Reymond|first6=Georges-Olivier|last7=Jurczak|first7=Christophe|date=2020-06-22|title=Quantum computing with neutral atoms|journal=Quantum|volume=4|page=327|doi=10.22331/q-2020-09-21-327|arxiv=2006.12326|s2cid=219966169}}</ref>
*[[Quantum dot]] computer, spin-based (e.g. the [[Loss-DiVincenzo quantum computer]]<ref>{{cite journal |last1=Imamog¯lu |first1=A. |last2=Awschalom |first2=D. D. |last3=Burkard |first3=G. |last4=DiVincenzo |first4=D. P. |last5=Loss |first5=D. |last6=Sherwin |first6=M. |last7=Small |first7=A. |title=Quantum Information Processing Using Quantum Dot Spins and Cavity QED |journal=Physical Review Letters |date=15 November 1999 |volume=83 |issue=20 |pages=4204–4207 |doi=10.1103/PhysRevLett.83.4204 |bibcode=1999PhRvL..83.4204I |arxiv=quant-ph/9904096 |s2cid=18324734 }}</ref>) (qubit given by the spin states of trapped electrons)
*[[Quantum dot]] computer, spin-based (e.g. the [[Loss-DiVincenzo quantum computer]]<ref>{{cite journal |last1=Imamog¯lu |first1=A. |last2=Awschalom |first2=D. D. |last3=Burkard |first3=G. |last4=DiVincenzo |first4=D. P. |last5=Loss |first5=D. |last6=Sherwin |first6=M. |last7=Small |first7=A. |title=Quantum Information Processing Using Quantum Dot Spins and Cavity QED |journal=Physical Review Letters |date=15 November 1999 |volume=83 |issue=20 |pages=4204–4207 |doi=10.1103/PhysRevLett.83.4204 |bibcode=1999PhRvL..83.4204I |arxiv=quant-ph/9904096 |s2cid=18324734 }}</ref>) (qubit given by the spin states of trapped electrons)
*[[量子点]]计算机，基于自旋（例如[[Divencenzo损失差额量子计算机]]<ref>{{cite journal |last1=Imamog¯lu |first1=A. |last2=Awschalom |first2=D. D. |last3=Burkard |first3=G. |last4=DiVincenzo |first4=D. P. |last5=Loss |first5=D. |last6=Sherwin |first6=M. |last7=Small |first7=A. |title=Quantum Information Processing Using Quantum Dot Spins and Cavity QED |journal=Physical Review Letters |date=15 November 1999 |volume=83 |issue=20 |pages=4204–4207 |doi=10.1103/PhysRevLett.83.4204 |bibcode=1999PhRvL..83.4204I |arxiv=quant-ph/9904096 |s2cid=18324734 }}</ref>)（量子比特由俘获电子的自旋态给出）
<!-- Basic definition of BQP -->
<!-- Basic definition of 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>
*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>
*基于空间的量子点计算机（由双量子点中的电子位置给出的量子比特）
*基于空间的量子点计算机（由双量子点中的电子位置给出的量子比特）<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.
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.
有界误差的量子计算机能有效地解决的一类问题称为<font color="#ff8000"> BQP</font>，即“有界误差，量子，多项式时间”。更正式地说，<font color="#ff8000"> BQP</font>是一类可以用多项式时间量子图灵机求解的问题，其错误概率最大为1/3。作为一类概率问题，<font color="#ff8000"> BQP</font>是<font color="#ff8000"> BPP</font>（“有界误差，概率，多项式时间”）的量子对应物，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>
* 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>
*量子计算使用工程量子阱，原则上可以建造在室温下工作的量子计算机
*使用工程量子阱进行量子计算，原则上可以建造在室温下工作的量子计算机<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>
*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>
*耦合的[[量子线|量子线]]（量子比特由一对量子线实现，量子线通过一对量子线耦合[[量子点接触|量子点接触]]）
*耦合的[[量子线|量子线]]（量子比特由一对量子线实现，量子线通过一对量子线耦合[[量子点接触|量子点接触]]）<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>
<!-- Relation of BQP to basic complexity classes -->
<!-- Relation of BQP to basic complexity classes -->
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).
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，即所有能被确定性经典计算机有效解决的问题也能被量子计算机有效地解决，所有能被量子计算机有效解决的问题，也能用多项式空间资源的确定性经典计算机来求解。人们进一步怀疑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中，那么从<font color="#32CD32">NP硬度NP-hardness</font>可以看出NP中的所有问题都在BQP中）。
*[[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)
*[[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)
*[[单分子磁体|分子磁体]]（量子比特由自旋态给出）
*[[单分子磁体|分子磁体]]（量子比特由自旋态给出）<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>
The relationship of BQP to the basic classical complexity classes can be summarized as follows:
The relationship of BQP to the basic classical complexity classes can be summarized as follows:
*[[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>
*[[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]]量子计算机（基于[[内表面富勒烯|被富勒烯包围的原子或分子的电子自旋的量子比特]）
*基于[[富勒烯]]的[[电子顺磁共振| ESR]]<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>量子计算机（基于[[内表面富勒烯|被富勒烯包围的原子或分子的电子自旋的量子比特]）
<math>\mathsf{P \subseteq BPP \subseteq BQP \subseteq PP \subseteq PSPACE}</math>
<math>\mathsf{P \subseteq BPP \subseteq BQP \subseteq PP \subseteq PSPACE}</math>
*[[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>
*[[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>
*[[光学量子计算|非线性光学量子计算机]]（通过线性和[[非线性光学|非线性]]元件处理光的不同[[正常模式|模式]]状态实现的量子比特）
*[[光学量子计算|非线性光学量子计算机]]（通过线性和[[非线性光学|非线性]]元件处理光的不同[[正常模式|模式]]状态实现的量子比特）<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<sup>#P</sup>), 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.
It is also known that BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P<sup>#P</sup>), 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.
*[[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>
*[[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>
*[[线性光学量子计算|线性光学量子计算机]]（通过线性元件（如反射镜、[[分束器]]和[[相移模块|移相器]]处理光的不同[[正常模式|模式]]状态实现的量子比特）
*[[线性光学量子计算|线性光学量子计算机]]（通过线性元件（如反射镜、[[分束器]]和[[相移模块|移相器]]处理光的不同[[正常模式|模式]]状态实现的量子比特）<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
*[[Diamond-based quantum computer]]<ref name="Nizovtsevetal2004">{{cite journal
*[[金刚石量子计算机]]
*[[金刚石量子计算机]]<ref name="Nizovtsevetal2004">{{cite journal
|journal = Optics and Spectroscopy
|journal = Optics and Spectroscopy
*[[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>
*[[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>
*基于[[玻色-爱因斯坦凝聚体|玻色-爱因斯坦凝聚体]]的量子计算机
*基于[[玻色-爱因斯坦凝聚体|玻色-爱因斯坦凝聚体]]的量子计算机<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
*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
*Rare-earth-metal-ion-doped inorganic crystal based quantum computers<ref name="Ohlsson2002">{{cite journal
*稀土金属离子掺杂无机晶体量子计算机
*稀土金属离子掺杂无机晶体量子计算机<ref name="Ohlsson2002">{{cite journal
|journal = Opt. Commun.
|journal = Opt. Commun.
*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>
*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>
*基于类金属碳纳米球的量子计算机
*基于类金属碳纳米球的量子计算机<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}}
A large number of candidates demonstrates that quantum computing, despite rapid progress, is still in its infancy.{{citation needed|date=May 2020}}
大量的候选者表明，尽管量子计算技术发展迅速，但仍处于初级阶段。
大量的候选者表明，尽管量子计算技术发展迅速，但仍处于初级阶段。{{citation needed|date=May 2020}}
==Relation to computability and complexity theory与可计算性和复杂性理论的关系==
==Relation to computability and complexity theory与可计算性和复杂性理论的关系==