查看“︁绝热量子计算机”︁的源代码

{{Translating|[[:en:Wikipedia]]||tpercent=75|time=2019-06-27T14:00:39+00:00}}
'''绝热量子计算机''' ('''AQC''')是一种[[量子计算机]]的形式，依赖{{le|绝热理论|Adiabatic theorem}}进行计算<ref name="Farhi2000">{{Cite arXiv |last1=Farhi |first1=E. |last2=Goldstone |first2=Jeffrey |author-link2=傑弗里·戈德斯通 |last3=Gutmann |first3=S. |last4=Sipser |first4=M. |eprint=quant-ph/0001106v1 |title=Quantum Computation by Adiabatic Evolution |year=2000}}</ref> 。AQC与[[量子退火]]紧密相关，甚至可认为是量子退火的一个子类<ref>{{Cite journal|title=Quantum annealing in the transverse Ising model|last=Kadowaki|first=T.|last2=Nishimori|first2=H.|date=1998-11-01|journal=Physical Review E|issue=5|doi=10.1103/PhysRevE.58.5355|volume=58|page=5355|arxiv=cond-mat/9804280|bibcode=1998PhRvE..58.5355K}}</ref><ref>{{Cite journal|title=Quantum annealing: A new method for minimizing multidimensional functions|last=Finilla|first=A.B.|last2=Gomez|first2=M.A.|date=1994-03-18|journal=Chemical Physics Letters|issue=5|doi=10.1016/0009-2614(94)00117-0|volume=219|pages=343–348|arxiv=chem-ph/9404003|bibcode=1994CPL...219..343F|last3=Sebenik|first3=C.|last4=Doll|first4=D.J.}}</ref><ref>{{Cite journal|title=Optimization using quantum mechanics: quantum annealing through adiabatic evolution|last=Santoro|first=G.E.|last2=Tosatti|first2=E.|date=2006-09-08|journal=Journal of Physics A|issue=36|doi=10.1088/0305-4470/39/36/R01|volume=39|page=R393|bibcode=2006JPhA...39R.393S}}</ref><ref>{{Cite journal|title=Colloquium: Quantum annealing and analog quantum computation|last=Das|first=A.|last2=Chakrabarti|first2=B.K.|date=2008-09-05|journal=Reviews of Modern Physics|issue=3|doi=10.1103/RevModPhys.80.1061|volume=80|page=1061|arxiv=0801.2193|bibcode=2008RvMP...80.1061D}}</ref>。

== 描述 ==
首先要找到一个基态能够描述我们所感兴趣的问题的解的[[哈密顿算符|哈密顿量]]（这个量可能是复杂的）。接下来准备一个简单哈密顿量的系统并将其初始化至基态。最后，将该简单哈密顿量绝热演化为我们所求的复杂哈密顿量.。根据绝热理论，该系统会保持在基态，所以最终该系统所处的状态将可以描述该问题的解。绝热量子计算在多项式运算方面展示出了和传统量子计算一样的能力<ref>{{Cite journal|title=Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation|last=Aharonov|first=Dorit|last2=van Dam|first2=Wim|date=2007-04-01|journal=SIAM Journal on Computing|doi=10.1137/s0097539705447323|volume=37|page=166|arxiv=quant-ph/0405098|last3=Kempe|first3=Julia|authorlink3=Julia Kempe|last4=Landau|first4=Zeph|last5=LLoyd|first5=Seth}}</ref>。

绝热量子计算的时间复杂度是指完成绝热演算所需的时间，与哈密顿量的本征能隙（谱隙）有关。具体地说，如果系统处于基态，基态与第一激发态之间的能隙提给出了演化速度的上界<ref>{{Cite journal|title=How Powerful is Adiabatic Quantum Computation?|last=van Dam|first=Wim|last2=van Mosca|first2=Michele|journal=Proceedings of the 42nd Annual Symposium on Foundations of Computer Science|page=279|last3=Vazirani|first3=Umesh}}</ref>当谱隙很小时，演化速度也会很慢。 整个算法的运行时间可以被约束为：

<math>T = O\left(\frac{1}{g_{min}^2}\right)</math>

这里<math>g_{min}</math>代表{{Nowrap|<math>H(t)</math>}}的最小频谱距 。

AQC是一个可能解决[[量子耗散]]问题的方法。由于系统处于基态，外界的干涉无法使它向更低的能态移动。如果外界的能量低于基态和第一激发态的能量差，系统跃迁的高能态的可能性将相应的更低。 因此，系统可以依据需求长时间处于单系统本征态。

普遍来讲，在绝热模型中的结果依赖于量子复杂性和[[QMA]]-问题。如果k≥2， k-local的哈密顿量是QMA完备的<ref>{{Cite journal|title=The Complexity of the Local Hamiltonian Problem|last=Kempe|first=J.|last2=Kitaev|first2=A.|date=2006-07-27|journal=SIAM Journal on Computing|issue=5|doi=10.1137/S0097539704445226|volume=35|pages=1070–1097|arxiv=quant-ph/0406180v2|issn=1095-7111|last3=Regev|first3=O.}}</ref> QMA难度的结果已知于[[量子位元|量子比特]]的现实[[Lattice models|晶格模型]]  ， <ref>{{Cite journal|title=Realizable Hamiltonians for Universal Adiabatic Quantum Computers|last=Biamonte|first=J.D.|last2=Love|first2=P.J.|date=2008-07-28|journal=Physical Review A|issue=1|doi=10.1103/PhysRevA.78.012352|volume=78|pages=012352|arxiv=0704.1287|bibcode=2008PhRvA..78a2352B}}</ref>。

<math>
H = \sum_{i}h_i Z_i + \sum_{i<j}J^{ij}Z_iZ_j + \sum_{i<j}K^{ij}X_iX_j
</math>

<math>Z, X</math>代表[[泡利矩陣|泡利矩阵]]{{Nowrap|<math>\sigma_z, \sigma_x</math>.}}这种模型被用于通用绝热量子计算。QMA-完备问题的哈密顿量也可以被限制作用在[[量子比特]]的两维网格上<ref>{{Cite journal|title=The complexity of quantum spin systems on a two-dimensional square lattice|last=Oliveira|first=R.|last2=Terhal|first2=B.M.|date=2008-11-01|journal=Quantum Information & Computation|volume=8|pages=0900–0924|arxiv=quant-ph/0504050|bibcode=2005quant.ph..4050O}}</ref>或一条每个有12种状态的量子颗粒上。<ref>{{Cite journal|title=The Power of Quantum Systems on a Line|last=Aharonov|first=D.|last2=Gottesman|first2=D.|date=2009-04-01|journal=Communications in Mathematical Physics|issue=1|doi=10.1007/s00220-008-0710-3|volume=287|pages=41–65|arxiv=0705.4077|bibcode=2009CMaPh.287...41A|last3=Irani|first3=S.|last4=Kempe|first4=J.|authorlink4=Julia Kempe}}</ref>如果这种模型被证明是物理可行的，它们也可以用来构建通用绝热量子计算机的基础。

在实际计算中仍存在一些问题。因为哈密顿量是逐渐变化，当多个 [[量子位元|量子比特]]接近一个临界点时会产生一些有趣的现象。临界点是指当基态能量很接近第一激发态时。这时，只需要添加少量的能量（来自外界环境或是由于哈密顿量的改变）就能使系统脱离基态从而破坏计算。试图加快计算速度会增加外部能量；改变量子比特的数量会使临界点处能隙变小。

== 绝热量子计算的可满足性问题 ==
{{TransH}}
Adiabatic quantum computation solves satisfiability problems and other combinatorial search problems by the process below. Generally this kind of problem is to seek for a state that satisfies
<math>
	C_1 \wedge C_2 \wedge \cdots \wedge C_M
</math>.
This expression contains the satisfiability of M clauses, each clause <math>C_i</math> has the value True or False, and can involve n bits. Each bit here is a variable <math>x_j\in \{ 0,1\}</math> so <math>C_i</math> is a Boolean value function of <math>x_1, x_2, \dots , x_n</math>. QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian <math>H_B</math>:

where <math>H_{B_i}</math> shows the Hamiltonian corresponding to the clause <math>C_i</math>, usually the choice of <math>H_{B_i}</math> won't depend on different clauses, so only the total number of times each bit involved in all clauses matters. Then it goes through an adiabatic evolution, ending in the Problem Hamiltonian <math>H_P</math>:

<math>
	H_P=\sum\limits_{C}^{} H_{P,C}
</math>

where <math>H_{P,C}</math> is the satisfying Hamiltonian of clause C. It has eigenvalues:

<math>
	h_C(z_{1C},z_{2C}\dots z_{nC})=
	\begin{cases} 
	0 & \mbox{clause } C \mbox{ satisfied} \\ 
	1 & \mbox{clause } C \mbox{ violated}
	\end{cases}
</math>

For a simple path of Adiabatic Evolution with running time T, consider:
<math>
	H(t)=(1-t/T)H_{B}+(t/T)H_{P}
</math>
and let <math>s=t/T</math>, we have:
<math>
	\tilde{H}(s)=(1-s)H_{B}+sH_{P}
</math>,
which is the adiabatic evolution Hamiltonian of our algorithm.

According to the adiabatic theorem, we start from the ground state of Hamiltonian <math>H_B</math> at beginning, go through an adiabatic process, and at last ending in the ground state of problem Hamiltonian <math>H_P</math>. Then we measure the z-component of each of the n spins in the final state, this will produce a string <math>z_1,z_2,\dots,z_n</math> which is highly likely to be the result of our satisfiability problem. Here the running time T must be sufficiently long to assure the correctness of result, and according to adiabatic theorem, T is about <math>\varepsilon/g_\mathrm{min}^{2}</math>, where
<math>
	g_\mathrm{min}=\min_{0\le s\le 1}(E_1(s)-E_0(s))
</math>
is the minimum energy gap between ground state and first excited state.<ref>{{Cite arXiv|last1=Farhi|title=Quantum Computation by Adiabatic Evolution|eprint=quant-ph/0001106}}</ref>

== D-波量子处理器 ==
The [[D-Wave 系统公司|D-Wave One]] is a device made by a Canadian company [[D-Wave 系统公司|D-Wave Systems]] which describes it as doing quantum annealing.<ref>{{Cite web|title=Quantum Computing: How D-Wave Systems Work|url=http://www.dwavesys.com/quantum-computing|accessdate=2014-08-28|work=[[D-Wave Systems|D-Wave]]|publisher=D-Wave Systems, Inc.|archiveurl=https://web.archive.org/web/20140914205359/http://dwavesys.com/quantum-computing|archivedate=2014-09-14|dead-url=no}}</ref> In 2011, [[洛克希德·马丁|Lockheed-Martin]] purchased one for about US$10 million; in May 2013, [[Google]] purchased a [[D-Wave Two]] with 512 qubits.<ref>{{Cite journal|title=Computing: The quantum company|url=http://www.nature.com/news/computing-the-quantum-company-1.13212|last=Jones|first=Nicola|date=2013-06-20|journal=[[Nature (journal)|Nature]]|accessdate=2014-01-02|issue=7454|doi=10.1038/498286a|volume=498|pages=286–288|bibcode=2013Natur.498..286J|pmid=23783610|archiveurl=https://web.archive.org/web/20140103232050/http://www.nature.com/news/computing-the-quantum-company-1.13212|archivedate=2014-01-03|deadurl=no}}</ref> As of now, the question of whether the D-Wave processors offer a speedup over a classical processor is still unanswered. Tests performed by researchers at [[Quantum Artificial Intelligence Lab]] ([[美国国家航空航天局|NASA]]), [[南加州大学|USC]], [[苏黎世联邦理工学院|ETH Zurich]], and [[Google]] show that as of now, there is no evidence of a quantum advantage.
<ref>{{Cite journal|title=Evidence for quantum annealing with more than one hundred qubits|last=Boixo|first=S.|last2=Rønnow|first2=T.F.|date=2014-02-28|journal=Nature Physics|issue=3|doi=10.1038/nphys2900|volume=10|pages=218–224|arxiv=1304.4595|bibcode=2014NatPh..10..218B|last3=Isakov|first3=S.V.|last4=Wang|first4=Z.|last5=Wecker|first5=D.|last6=Lidar|first6=D.A.|last7=Martinis|first7=J.M.|last8=Troyer|first8=M.}}
</ref><ref>{{Cite journal|title=Defining and detecting quantum speedup|last=Ronnow|first=T.F.|last2=Wang|first2=Z.|date=2014-07-25|journal=Science|issue=6195|doi=10.1126/science.1252319|volume=345|pages=420–424|arxiv=1401.2910|bibcode=2014Sci...345..420R|pmid=25061205|last3=Job|first3=J.|last4=Boixo|first4=S.|last5=Isakov|first5=S.V.|last6=Wecker|first6=D.|last7=Martinis|first7=J.M.|last8=Lidar|first8=D.A.|last9=Troyer|first9=M.}}
</ref><ref>{{Cite journal|title=Quantum Optimization of Fully Connected Spin Glasses|last=Venturelli|first=D.|last2=Mandrà|first2=S.|date=2015-09-18|journal=Physical Review X|issue=3|doi=10.1103/PhysRevX.5.031040|volume=5|pages=031040|arxiv=1406.7553|bibcode=2015PhRvX...5c1040V|last3=Knysh|first3=S.|last4=O'Gorman|first4=B.|last5=Biswas|first5=R.|last6=Smelyanskiy|first6=V.}}
</ref>
{{TransF}}

== 参考 ==
{{Reflist}}

[[Category:物理定理]]
[[Category:量子力学]]
[[Category:有未审阅翻译的页面]]