Kristan Temme, Sergey Bravyi, et al.
Physical Review Letters
We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves these decision problems with high probability for n qubits, L clauses, and promise gap c in time O(n2L2c−2). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Schöning’s probabilistic algorithm for k-SAT.
Kristan Temme, Sergey Bravyi, et al.
Physical Review Letters
Youngseok Kim, Andrew Eddins, et al.
Nature
Alberto Di Meglio, Karl Jansen, et al.
PRX Quantum
Vojtěch Havlíček, Sergii Strelchuk, et al.
Physical Review A