000			04412nam a22004215i 4500
999			_c387566 _d387566
001			387566
003			ES-MaUEC
005			20230326103435.0
006			a||||fo|||| 00| 0
007			cr nn 008mamaa
008			220601s2014 sz | s |||| 0|eng d
020			_a9783031025198
024	7		_a10.1007/978-3-031-02519-8 _2doi
040			_aES-MaUEC _bspa _cES-MaUEC _dES-MaUEC
050		4	_aQA76.889 _b2014 EB
100	1		_aCruz-Santos, William _eautor _4aut _4http://id.loc.gov/vocabulary/relators/aut _9687623
245	1	0	_aApproximability of Optimization Problems through Adiabatic Quantum Computation _cby William Cruz-Santos, Guillermo Morales-Luna
250			_a1st edition 2014
264		1	_aCham _bSpringer International Publishing _c2014
300			_a1 recurso en línea (XV, 97 páginas)
336			_atexto _btxt _2rdacontent
337			_aelectrónico _bc _2rdamedia
338			_arecurso electrónico _bcr _2rdacarrier
347			_aarchivo de texto _bPDF
490	0		_aSynthesis Lectures on Quantum Computing _x1945-9734
505	0		_aPreface -- 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.
520			_aThe 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.
988			_aSynthesis Collection of Technology_2014
650		7	_2embne _9687622 _aSimetría (Matemáticas)
650		7	_2embne _9157651 _aOptimización combinatoria
700	1		_aMorales-Luna, Guillermo _eautor _4aut _4http://id.loc.gov/vocabulary/relators/aut _9687624
776	0	8	_iPrinted edition: _z9783031013911
776	0	8	_iPrinted edition: _z9783031036477
856	4	0	_uhttps://go.openathens.net/redirector/universidadeuropea.es?url=https://doi.org/10.1007/978-3-031-02519-8 _zAcceso a este recurso digital (usuarios Universidad Europea de Madrid)
942			_2lcc _cLE
998			_b03/2023 _dz _esc _zSI