绝热量子计算机

绝热量子计算机 (AQC)是一种量子计算机的形式，依赖绝热理论进行计算 。AQC与量子退火紧密相关，甚至可认为是量子退火的一个子类。

描述

首先要找到一个基态能够描述我们所感兴趣的问题的解的哈密顿量（这个量可能是复杂的）。接下来准备一个简单哈密顿量的系统并将其初始化至基态。最后，将该简单哈密顿量绝热演化为我们所求的复杂哈密顿量.。根据绝热理论，该系统会保持在基态，所以最终该系统所处的状态将可以描述该问题的解。绝热量子计算在多项式运算方面展示出了和传统量子计算一样的能力。

绝热量子计算的时间复杂度是指完成绝热演算所需的时间，与哈密顿量的本征能隙（谱隙）有关。具体地说，如果系统处于基态，基态与第一激发态之间的能隙提给出了演化速度的上界当谱隙很小时，演化速度也会很慢。 整个算法的运行时间可以被约束为：

$T=O\left({\frac {1}{g_{min}^{2}}}\right)$

这里$g_{min}$代表$H(t)$的最小频谱距 。

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

普遍来讲，在绝热模型中的结果依赖于量子复杂性和QMA-问题。如果k≥2， k-local的哈密顿量是QMA完备的 QMA难度的结果已知于量子比特的现实晶格模型 ， 。

$H=\sum _{i}h_{i}Z_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}$

$Z,X$代表泡利矩阵$\sigma _{z},\sigma _{x}$.这种模型被用于通用绝热量子计算。QMA-完备问题的哈密顿量也可以被限制作用在量子比特的两维网格上或一条每个有12种状态的量子颗粒上。如果这种模型被证明是物理可行的，它们也可以用来构建通用绝热量子计算机的基础。

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

绝热量子计算的可满足性问题

已隐藏部分未翻译内容，欢迎参与翻译。

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 $C_{1}\wedge C_{2}\wedge \cdots \wedge C_{M}$. This expression contains the satisfiability of M clauses, each clause $C_{i}$ has the value True or False, and can involve n bits. Each bit here is a variable $x_{j}\in \{0,1\}$ so $C_{i}$ is a Boolean value function of $x_{1},x_{2},\dots ,x_{n}$. QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian $H_{B}$:

where $H_{B_{i}}$ shows the Hamiltonian corresponding to the clause $C_{i}$, usually the choice of $H_{B_{i}}$ 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 $H_{P}$:

$H_{P}=\sum \limits _{C}^{}H_{P,C}$

where $H_{P,C}$ is the satisfying Hamiltonian of clause C. It has eigenvalues:

$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}}$

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

According to the adiabatic theorem, we start from the ground state of Hamiltonian $H_{B}$ at beginning, go through an adiabatic process, and at last ending in the ground state of problem Hamiltonian $H_{P}$. Then we measure the z-component of each of the n spins in the final state, this will produce a string $z_{1},z_{2},\dots ,z_{n}$ 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 $\varepsilon /g_{\mathrm {min} }^{2}$, where $g_{\mathrm {min} }=\min _{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))$ is the minimum energy gap between ground state and first excited state.

D-波量子处理器

The D-Wave One is a device made by a Canadian company D-Wave Systems which describes it as doing quantum annealing. In 2011, Lockheed-Martin purchased one for about US$10 million; in May 2013, Google purchased a D-Wave Two with 512 qubits. 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.