Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers

Tad Hogg

The deep structure of constraint satisfaction problems explains the association of hard search instances with a phase transition in problem solubility. This structure is also the basis of a quantum search algorithm exhibiting the phase trausition. In this paper, this algorithm is modified to incorporate additional problem structure. This modification is an example of a general method for inchding heuristics in quantum search. The new algorithm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.