絕熱量子計算機

絕熱量子計算機 (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_iZ_j + \sum_{i<j}K^{ij}X_iX_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 $<pre> C_1 \wedge C_2 \wedge \cdots \wedge C_M </pre>$.

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

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

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

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

For a simple path of Adiabatic Evolution with running time T, consider:

$$<pre> H(t)=(1-t/T)H_{B}+(t/T)H_{P} </pre>$$ and let $s=t/T$, we have:

$<pre> \tilde{H}(s)=(1-s)H_{B}+sH_{P} </pre>$,

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 $$<pre> g_\mathrm{min}=\min_{0\le s\le 1}(E_1(s)-E_0(s)) </pre>$$ 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.