Eigenpath traversal by phase randomization
Eigenpath traversal by phase randomization
复制标题
通过相位随机化进行特征路径遍历
DOI：
--
复制
发表时间：
2009
影响因子：
1
通讯作者：
R. Somma
中科院分区：
文献类型：
--
作者：
S. Boixo;E. Knill;R. Somma
绝热量子计算的计算是通过遍历连续的汉密尔顿家族的非排效本征态的路径来实现的逆转性将投影量测量近似于所需的特征态，如果可以使用恒定的进化时间来实现量子Zeno效应的版本。开销，然后我们方法所需的平均绝对演变时间是恒定误差概率的O（L2/δ），其中L是特征状态的路径的长度和δ是汉密尔顿成本的最小光谱差距。 δ是最佳的。对于路径长度，对路径长度的依赖性远小于我们方法的复杂性。同样的成本适用于离散的案例，其中给出了一个单一操作员的家族，每个统一及其逆向都可以限制到正面的进化时间。搜索和量子采样尤其是我们讨论用于解决组合优化问题的量子模拟退火算法。通过马尔可夫链蒙特卡洛（Monte Carlo）实施的随机矩阵差距的二次加速。
A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is O(L2/Δ) for constant error probability, where L is the length of the path of eigenstates and Δ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on Δ is optimal. Making explicit the dependence on the path length is useful for cases where L is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.