Stuttgart 2012 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

Q: Fachverband Quantenoptik und Photonik

Q 35: Poster 2

Q 35.32: Poster

Mittwoch, 14. März 2012, 16:30–19:00, Poster.I+II

A universal integrator for sparse qubit Hamiltonians:
Probing Adiabatic Quantum Computation for an NP-hard problem — •Michael Hofmann, Gernot Schaller, and Tobias Brandes — Institut für Theoretische Physik, Technische Universität Berlin, Berlin

The adiabatic paradigm of quantum computation allows to solve problems via adiabatically preparing a sought-after ground state of a problem Hamiltonian by slow deformations starting from a simple initial Hamiltonian. Simulating a quantum system with n qubits classically requires exponential (2ⁿ) resources and is even further hindered if the time-dependent Hamiltonian is not stored efficiently. We relax this second constraint by introducing a size-scalable universal decomposition of the Hamiltonian into tensor products of Pauli matrices, which allows for an efficient storage and matrix-vector multiplication for k-local Hamiltonians. At the example of the NP-complete problem Exact Cover 3, we study the efficiency of the quantum algorithm for different adiabatic preparation schemes on a hard subset of problem instances that has not been considered before. Even though the worst-case scaling of the algorithm is probably exponential, we find significant performance differences between the different schemes on the average problem.