Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers
Abstract
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 algoritbm exhibiting the phase transition. In this paper, this algoritbm is modified to incorporate additional problem structure. This modification is an example of a general method for including heuristics in quantum search. The new algoritbm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.
Cite
Text
Hogg. "Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers." AAAI Conference on Artificial Intelligence, 1997.Markdown
[Hogg. "Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers." AAAI Conference on Artificial Intelligence, 1997.](https://mlanthology.org/aaai/1997/hogg1997aaai-exploiting/)BibTeX
@inproceedings{hogg1997aaai-exploiting,
title = {{Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers}},
author = {Hogg, Tad},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1997},
pages = {334-339},
url = {https://mlanthology.org/aaai/1997/hogg1997aaai-exploiting/}
}