Approximability of optimization problems through adiabatic quantum computation / William Cruz-Santos, Guillermo Morales-Luna.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 87-95).

1. Introduction --

2. Approximability of NP-hard problems -- 2.1 Basic definitions -- 2.2 Probabilistic proof systems -- 2.3 Optimization problems -- 2.3.1 Approximation algorithms -- 2.4 Randomized complexity classes -- 2.4.1 The complexity class BPP -- 2.4.2 The complexity class RP -- 2.4.3 The complexity class ZPP -- 2.4.4 Quantum complexity -- 2.5 Randomness and determinism -- 2.5.1 Derandomization of the class BPP -- 2.5.2 Derandomization techniques --

3. Adiabatic quantum computing -- 3.1 Basic definitions -- 3.1.1 Linear operators -- 3.2 Quantum states and evolution -- 3.3 The adiabatic theorem -- 3.3.1 Adiabatic evolution -- 3.3.2 Quantum computation by adiabatic evolution -- 3.4 Adiabatic paths -- 3.4.1 Geometric berry phases -- 3.4.2 Geometric quantum computation --

4. Efficient Hamiltonian construction -- 4.1 AQC applied to the MAX-SAT problem -- 4.1.1 Satisfiability problem -- 4.1.2 AQC formulation of SAT -- 4.2 Procedural Hamiltonian construction -- 4.2.1 Hyperplanes in the hypercube -- 4.2.2 The Hamiltonian operator HE -- 4.2.3 The Hamiltonian operator HZ --

5. AQC for pseudo-Boolean optimization -- 5.1 Basic transformations -- 5.2 AQC for quadratic pseudo-Boolean maps -- 5.2.1 Hadamard transform -- 5.2.2 [theta x] transform -- 5.3 K-local Hamiltonian problems -- 5.3.1 Reduction of graph problems to the 2-local Hamiltonian problem -- 5.4 Graph structures and optimization problems -- 5.4.1 Relational signatures -- 5.4.2 First-order logic -- 5.4.3 Second-order logic -- 5.4.4 Monadic second-order logic decision and optimization problems -- 5.4.5 MSOL optimization problems and pseudo-Boolean maps --

6. A general strategy to solve NP-hard problems -- 6.1 Background -- 6.1.1 Basic notions -- 6.1.2 Tree decompositions -- 6.2 Procedural modification of tree decompositions -- 6.2.1 Modification by the addition of an edge -- 6.2.2 Iterative modification -- 6.2.3 Branch decompositions -- 6.2.4 Comparison of time complexities -- 6.3 A strategy to solve NP-hard problems -- 6.3.1 Dynamic programming approach -- 6.3.2 The Courcelle theorem -- 6.3.3 Examples of second-order formulae -- 6.3.4 Dynamic programming applied to NP-hard problems -- 6.3.5 The classical Ising model -- 6.3.6 Quantum Ising model --

7. Conclusions -- Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

The adiabatic quantum computation (AQC) is based on the adiabatic theorem to approximate solutions of the Schrodinger 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 x 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.

Also available in print.

Title from PDF title page (viewed on October 16, 2014).