Approximability of Optimization Problems through Adiabatic Quantum Computation.

By: Cruz-Santos, WilliamContributor(s): Morales-Luna, GuillermoMaterial type: TextTextSeries: eBooks on DemandSynthesis Lectures on Quantum Computing: Publisher: San Rafael : Morgan & Claypool Publishers, 2014Description: 1 online resource (115 p.)ISBN: 9781627055574Subject(s): Adiabatic invariants | Invariants adiabatiques | Quantum computers -- MathematicsGenre/Form: Electronic books.Additional physical formats: Print version:: Approximability of Optimization Problems through Adiabatic Quantum ComputationDDC classification: 004.1 LOC classification: QA76.889Online resources: Click here to view this ebook.
Contents:
Preface; Acknowledgments; Introduction; Approximability of NP-hard Problems; Basic Definitions; Probabilistic Proof Systems; Optimization Problems; Approximation Algorithms; Randomized Complexity Classes; The Complexity Class BPP; The Complexity Class RP; The Complexity Class ZPP; Quantum Complexity; Randomness and Determinism; Derandomization of the Class BPP; Derandomization Techniques; Adiabatic Quantum Computing; Basic Definitions; Linear Operators; Quantum States and Evolution; The Adiabatic Theorem; Adiabatic Evolution; Quantum Computation by Adiabatic Evolution; Adiabatic Paths
Geometric Berry PhasesGeometric Quantum Computation; Efficient Hamiltonian Construction; AQC Applied to the MAX-SAT Problem; Satisfiability Problem; AQC Formulation of SAT; Procedural Hamiltonian Construction; Hyperplanes in the Hypercube; The Hamiltonian Operator H_E; The Hamiltonian Operator H_Z_; AQC for Pseudo-Boolean Optimization; Basic Transformations ; AQC for Quadratic Pseudo-Boolean Maps; Hadamard Transform; _x Transform; k-Local Hamiltonian Problems; Reduction of Graph Problems to the 2-Local Hamiltonian Problem; Graph Structures and Optimization Problems; Relational Signatures
First-Order LogicSecond-Order Logic; Monadic Second-Order Logic Decision and Optimization Problems; MSOL Optimization Problems and Pseudo-Boolean Maps; A General Strategy to Solve NP-Hard Problems; Background; Basic Notions; Tree Decompositions; Procedural Modification of Tree Decompositions; Modification by the Addition of an Edge; Iterative Modification; Branch Decompositions; Comparison of Time Complexities; A Strategy to Solve NP-Hard Problems; Dynamic Programming Approach; The Courcelle Theorem; Examples of Second-Order Formulae; Dynamic Programming Applied to NP-Hard Problems
The Classical Ising ModelQuantum Ising Model; Conclusions; Bibliography; Authors'' Biographies
Summary: 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 l
Tags from this library: No tags from this library for this title. Log in to add tags.
Item type Current location Call number URL Status Date due Barcode
Electronic Book UT Tyler Online
Online
QA76.889 (Browse shelf) http://uttyler.eblib.com/patron/FullRecord.aspx?p=1812521 Available EBL1812521

Preface; Acknowledgments; Introduction; Approximability of NP-hard Problems; Basic Definitions; Probabilistic Proof Systems; Optimization Problems; Approximation Algorithms; Randomized Complexity Classes; The Complexity Class BPP; The Complexity Class RP; The Complexity Class ZPP; Quantum Complexity; Randomness and Determinism; Derandomization of the Class BPP; Derandomization Techniques; Adiabatic Quantum Computing; Basic Definitions; Linear Operators; Quantum States and Evolution; The Adiabatic Theorem; Adiabatic Evolution; Quantum Computation by Adiabatic Evolution; Adiabatic Paths

Geometric Berry PhasesGeometric Quantum Computation; Efficient Hamiltonian Construction; AQC Applied to the MAX-SAT Problem; Satisfiability Problem; AQC Formulation of SAT; Procedural Hamiltonian Construction; Hyperplanes in the Hypercube; The Hamiltonian Operator H_E; The Hamiltonian Operator H_Z_; AQC for Pseudo-Boolean Optimization; Basic Transformations ; AQC for Quadratic Pseudo-Boolean Maps; Hadamard Transform; _x Transform; k-Local Hamiltonian Problems; Reduction of Graph Problems to the 2-Local Hamiltonian Problem; Graph Structures and Optimization Problems; Relational Signatures

First-Order LogicSecond-Order Logic; Monadic Second-Order Logic Decision and Optimization Problems; MSOL Optimization Problems and Pseudo-Boolean Maps; A General Strategy to Solve NP-Hard Problems; Background; Basic Notions; Tree Decompositions; Procedural Modification of Tree Decompositions; Modification by the Addition of an Edge; Iterative Modification; Branch Decompositions; Comparison of Time Complexities; A Strategy to Solve NP-Hard Problems; Dynamic Programming Approach; The Courcelle Theorem; Examples of Second-Order Formulae; Dynamic Programming Applied to NP-Hard Problems

The Classical Ising ModelQuantum Ising Model; Conclusions; Bibliography; Authors'' Biographies

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 l

Description based upon print version of record.

There are no comments on this title.

to post a comment.