Solving Random Satisfiability Problems with Quantum Computers

Abstract

Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.

26 pages

References in corpus (9)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Computing
• Experimental realization of a quantum algorithm
• Quantum Computers, Factoring, and Decoherence
• A Framework for Structured Quantum Search
• Quantum Optimization
• Single-Step Quantum Search Using Problem Structure
• Monte Carlo Simulation of Quantum Computation

Cited by in corpus (1)

• Adiabatic Quantum Computing for Random Satisfiability Problems