Hybrid Quantum-Classical Approaches to NP-complete Problems

The observations by Feynman and the landmark discoveries of Deustch, Shor, Grover and others has opened the door toward huge advancements in computational power possible by shifting toward the paradigm of quantum computing. Problems in the computational complexity class \textbf{NP-complete} pose a unique challenge as there are no known algorithms to efficiently solve these problems in either the classical or quantum framework. It is known however, that many of these \textbf{NP-complete} problems admit a formulation as an unstructured search problem and can benefit from the quadratic speedup of Grover's algorithm. In many problems of practical interest this can amount to a monumental time savings and open the door to new classes of applications. Current quantum computing systems are highly constrained in the number of qubits they can support. In this presentation we look at a particular instance of a \textbf{NP-complete} problem known as 3SAT and investigate the speedups possible by switching to a hybrid approach using a small number of qubits.