ON CLASSICAL AND QUANTUM CONSTRAINT SATISFACTION PROBLEMS IN THE TRIAL AND ERROR MODEL

Abstract

This thesis studies quantum satisfiability (QSAT) and classical constraint satisfaction problems (CSP) in the trial and error model recently formalized by Bei, Chen and Zhang (STOC13). The principal component in this setting involves an oracle which accepts assignments from the domain of the CSP as trials and reveals either that the trial is a valid solution or some information about the error that caused the assignment to fail. We provide a systematic framework to analyze how the complexity of a CSP with unknown inputs changes with respect to the information revealed by the oracle. Additionally, two different modifications to this oracle are considered with the aim of determining the minimum amount of information required to solve 2SAT and find if a graph possesses some property. Finally, a new linear time algorithm for Quantum 2SAT is presented which improves on Bravyi’s algorithm (2006) with its quartic time dependence on input size.