论文标题
量子辅助贪婪算法
Quantum-Assisted Greedy Algorithms
论文作者
论文摘要
我们展示了如何利用量子退火器（QAS）更好地选择贪婪算法中的候选人。与传统的贪婪算法在每个阶段采用特定问题的启发式方法来做出本地选择，我们使用QAS在低温温度下从依赖问题的汉密尔顿人的基础状态进行采样，并使用检索到的样品估算问题变量的概率分布。更具体地说，我们将Ising模型的每个自旋视为一个随机变量，并收缩所有问题变量，其相应的不确定性可以忽略不计。我们对D-WAVE 2000Q量子处理器的经验结果表明，与量子退火领域中的最新技术相比，所提出的量子辅助贪婪算法（QAGA）方案可以找到相比要更好的解决方案。
We show how to leverage quantum annealers (QAs) to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use QAs that sample from the ground state of problem-dependent Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin of the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results on a D-Wave 2000Q quantum processor demonstrate that the proposed quantum-assisted greedy algorithm (QAGA) scheme can find notably better solutions compared to the state-of-the-art techniques in the realm of quantum annealing
