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)


SQuInT Chief Organizer
Akimasa Miyake, Associate Professor

SQuInT Co-Organizer
Brian Smith, Associate Professor UO

SQuInT Program Committee
Postdoctoral Fellows:
Markus Allgaier (UO OMQ)
Sayonee Ray (UNM CQuIC)
Pablo Poggi (UNM CQuIC)
Valerian Thiel (UO OMQ)

SQuInT Event Co-Organizers (Oregon)
Jorjie Arden
Holly Lynn

SQuInT Event Administrator (Oregon)
Brandy Todd

SQuInT Administrator (CQuIC)
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director

Tweet About SQuInT 2020!