The adiabatic quantum computation (AQC) is based on the adiabatic theorem to approximate
solutions of the Schrödinger equation. The design of an AQC algorithm involves the construction
of a Hamiltonian that describes the behavior of the quantum system. This Hamiltonian is
expressed as a linear interpolation of an initial Hamiltonian whose ground state is easy to
compute and a final Hamiltonian whose ground state corresponds to the solution of a given
combinatorial optimization problem. The adiabatic theorem asserts that if the time evolution of
a quantum system described by a Hamiltonian is large enough then the system remains close to
its ground state. An AQC algorithm uses the adiabatic theorem to approximate the ground state
of the final Hamiltonian that corresponds to the solution of the given optimization problem. In
this book we investigate the computational simulation of AQC algorithms applied to the MAX-SAT
problem. A symbolic analysis of the AQC solution is given in order to understand the involved
computational complexity of AQC algorithms. This approach can be extended to other
combinatorial optimization problems and can be used for the classical simulation of an AQC
algorithm where a Hamiltonian problem is constructed. This construction requires the
computation of a sparse matrix of dimension 2n × 2n by means of tensor products where n is
the dimension of the quantum system. Also a general scheme to design AQC algorithms is
proposed based on a natural correspondence between optimization Boolean variables and quantum
bits. Combinatorial graph problems are in correspondence with pseudo-Boolean maps that are
reduced in polynomial time to quadratic maps. Finally the relation among NP-hard problems is
investigated as well as its logical representability and is applied to the design of AQC
algorithms. It is shown that every monadic second-order logic (MSOL) expression has associated
pseudo-Boolean maps that can be obtained by expanding the given expression and also can be
reduced to quadratic forms.Table of Contents: Preface Acknowledgments Introduction
Approximability of NP-hard Problems Adiabatic Quantum Computing Efficient Hamiltonian
Construction AQC for Pseudo-Boolean Optimization A General Strategy to Solve NP-Hard
Problems Conclusions Bibliography Authors' Biographies
