A Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT

2016/03/22 by Edward Farhi, Farhi, Edward, Shelby Kimmel +3
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.1603.06985

arxiv created 2016/03/22 · arxiv updated 2016/03/24

Abstract

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 this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n² L² c^-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.

Related

• Efficient algorithm for a quantum analogue of 2-SAT
• Solving Markov Chains with Analog Quantum Computing: The Fine Print
• On Efficient Solutions of General Structured Markov Processes in Quantum Computational Environments
• A Generalization of Deutsch's Example
• Quantum Algorithms for Finite-horizon Markov Decision Processes