Southwest Quantum Information and Technology

Solving 3-SAT through simulated quantum evolution

Presenting Author: Trevor Kling, Chapman University
Contributing Author(s): Dr. Justin Dressel

In 2008, Aharonov et al. proved that the field of adiabatic quantum computation is equivalent to standard quantum computation. We present an explicit analysis of how such adiabatic computation can be used to solve a particular NP-complete problem: the 3-SAT problem.The boolean satisfiability problem of 3 variables, known as 3-SAT, is a simple NP-complete problem with applications in bounded model checking and product configurations. We analyze a quantum algorithm that computes a maximally correct set of boolean values via Hamiltonian evolution, both in an analog quantum device and in a simulated quantum circuit model.

(Session 5 : Saturday from 5:00pm - 7:00pm)