Vi beskriver en effektiv approximationsalgoritm för utvärdering av mark-tillstånd energi av den klassiska Ising Hamiltonian med linjära termer på en godtycklig planar graf. Körtiden för algoritmen växer linjärt med antalet snurr och exponentiellt med 1/ på ett sätt som är det värsta relativa felet. Detta resultat kontrasterar det välkända faktum att exakt beräkning av mark-tillstånd energi för den tvådimensionella Ising spinnglas modell är NP-hård. Vi presenterar också en klassisk approximation algoritm för den lokala Hamiltonian Problem eller Quantum Ising Spin Glass problem på en planar graf med begränsad grad som är känd för att vara ett QMA-komplett problem. Med hjälp av en annan teknik hittar vi en klassisk approximationsalgoritm för quantum Ising spinnglas problem på den enklaste planar graf med obegränsad grad, stjärnan graf.
I ett första resultat på polynom tid approximation algoritmer, Bansal, Bravyi och Terhal REF ge en PTAS för en särskild klass av den lokala Hamiltoniska problemet, så kallade kvant Ising spin glasögon, för det fall där fallet är på en planar graf (och särskilt av begränsad grad).
Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs
{'venue': 'Quant. Inf. Comp. Vol. 9, No.8, p. 0701 (2009)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}