期刊
2022 IEEE INTERNATIONAL GEOSCIENCE AND REMOTE SENSING SYMPOSIUM (IGARSS 2022)
卷 -, 期 -, 页码 4911-4914出版社
IEEE
DOI: 10.1109/IGARSS46834.2022.9884795
关键词
Greedy Algorithms; Optimization; Quantum Annealing; Quantum Computing
资金
- NASA [NNH16ZDA001N-AIST 16-0091]
- NIH-NIGMS Initiative for Maximizing Student Development Grant [2 R25-GM55036]
- Google Lime scholarship
This paper demonstrates how to improve candidate selection in greedy algorithms by leveraging quantum annealers (QAs). By sampling from the ground state of a problem-dependent Hamiltonian using QAs and estimating the probability distribution of problem variables, the proposed quantum-assisted greedy algorithm (QAGA) scheme outperforms state-of-the-art techniques in quantum annealing.
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 a 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据