Cooling-Assist Adiabatic Computing

adiabatic-computing

---

生成3EC问题的实例

对于3EC问题，每一个子式 $C_i$ 是一个三变量的真值函数。当且仅当这三个变量中有一个为1时才为真。对于n个变元，每次随机地选出三个变量产生一个子式$C_i$，然后检查

$$C_1\land C_2 \dots \land C_i$$

的满足赋值的个数，若为1，则成功产生了一个3EC实例

绝热计算

绝热计算使用时间演化算符 $exp(-iHdt)$来计算，在实际计算的时候取$dt = 1$，演化100步。

在演化过程中插入冷却

由于冷却时概率性地冷却，有可能加热也有可能冷却，可以通过选择某个符合条件地冷却参数来控制这个概率。

利用Demon-like algorithm cooling地量子算法所获得的量子态为

$$\frac{1}{2}(1-ie^{i\gamma}U)|\psi_{in}\rangle |0\rangle +\frac{1}{2}(1+ie^{i\gamma}U)|\psi_{in}\rangle|1\rangle$$

其中$U = e^{-iH_s t}$是时间演化算符

通过对辅助比特测量就可以以一定概率获得冷却了的量子态

$$(1\pm ie^{i\gamma}U)|\psi_{in}\rangle = (1\pm ie^{i\gamma}U)\sum_{k} c_k |e_k\rangle$$

这个量子态的模具有这样的形式

$$|(1\pm ie^{i\gamma}U)|e_k\rangle|^2 = 2(1\pm \sin{\phi_k})$$

其中

$$\phi_k = E_k t -\gamma$$

这样每个本征值也就乘了一个系数$1\pm \sin{\phi_k}$，为了方便我们不妨设对所有的k都有

$$-\frac{\pi}{2}\leq\phi_k\leq\frac{\pi}{2}$$

这样对于cooling的情况（$1-sin{\phi_k}$）就会使获得基态的概率增加

而假若已知所有的本征值$E_k$参数$t,\gamma$应满足

$$-\frac{\pi}{2}\leq E_k t-\gamma \leq \frac{\pi}{2}$$

若$t>0$，$\gamma$就满足

$$E_{min} t-\frac{\pi}{2} \leq \gamma \leq E_{min}t+\frac{\pi}{2}\\ E_{max}t-\frac{\pi}{2} \leq \gamma \leq E_{max}t+\frac{\pi}{2}\\ $$

若

$$E_{max}t-\frac{\pi}{2}\leq E_{min}t+\frac{\pi}{2}$$
即
$$t\leq \frac{\pi}{E_{max}-E_{min}}$$

$$\Rightarrow E_{max}t-\frac{\pi}{2} \leq \gamma \leq E_{min}t + \frac{\pi}{2}$$

否则不等式无解

若已知$\gamma$,且不妨设本征值$E_k$均大于0，则对所有可能的k，t满足

$$\frac{\gamma-\frac{\pi}{2}}{E_k}\leq t \leq \frac{\gamma+\frac{\pi}{2}}{E_k}$$

$$\frac{\gamma+\frac{\pi}{2}}{E_{min}}>\frac{\gamma+\frac{\pi}{2}}{E_{max}}$$

下面分两种情况讨论：

1.$\gamma - \frac{\pi}{2}>0$

$$\frac{\gamma-\frac{\pi}{2}}{E_{min}}>\frac{\gamma-\frac{\pi}{2}}{E_{max}}\\ $$

那么就有

$$\frac{\gamma-\frac{\pi}{2}}{E_{min}}\leq t \leq \frac{\gamma+\frac{\pi}{2}}{E_{max}}$$

2.$\gamma - \frac{\pi}{2}\leq 0$

$$\frac{\gamma-\frac{\pi}{2}}{E_{min}}<\frac{\gamma-\frac{\pi}{2}}{E_{max}}\\ $$

那么就有

$$\frac{\gamma-\frac{\pi}{2}}{E_{max}}\leq t \leq \frac{\gamma+\frac{\pi}{2}}{E_{max}}$$

在这次数值计算中用的是以下的取值

$$\gamma = \frac{E_{max}+E_{min}}{E_{max}-E_{min}}\frac{\pi}{2}*0.1\\ t = \frac{1}{2} (\frac{\gamma-\frac{\pi}{2}}{E_{max(min, if\ \gamma -\frac{\pi}{2})>0}} + \frac{\gamma+\frac{\pi}{2}}{E_{max}})\\ $$

这个取值虽然满足以上约束但是不是最好的，下面讨论如何获得最佳的参数

获得最佳参数，归结为一个优化问题

$$\begin{aligned} &\text{minimize}:&f_0(t,\gamma) = \frac{\sum_j 1-\sin(E_j t - \gamma)}{1-\sin(E_0 t - \gamma)}\\ &\text{subject to}:&f_k(t,\gamma) = E_k t -\gamma\quad f_m(t,\gamma) = -E_m t+\gamma\\ && f_k(t,\gamma)<\frac{\pi}{2},f_m(t,\gamma)<\frac{\pi}{2} \end{aligned}$$

容易知道$f(t,\gamma)<1$，约束函数$f_m,f_k$都是凸函数，但是现在$f_0$为凸函数的条件没找出来（Hessian矩阵的一二阶顺序主子式比较复杂，不能确定其正定的条件，也还没想出来替代的方案），假如能够得到$f_0$为凸的条件，就可以得到一个稍微弱一些的结论(利用凸优化的一些算法)，就是在满足一定条件下，这个冷却算法的最佳参数。否则在具体计算的时候就需要数值搜索出上述优化问题的解。

然后如何将一些非凸函数规约为凸函数的优化问题我还没有学会，所以不知道会不会有更强的结论。

数值结果分析

成功概率

纵坐标是成功概率，横坐标是bit数目，冷却后的成功概率与正常运行的成功概率的差值大约是每增加一个比特除以2的规律在变化。

优化分段数n

上面的过程是在一个绝热演化过程中的1/3，2/3处插入冷却，那么将演化过程分为几段是最好的呢？我用数值的方法探索到8比特

trace 0 是 5比特，trace 1是 6比特，依次类推。

结论是在5~8比特中，将其分为三段对于3EC问题是最佳的。