Redukcja trudnych problemów do modeli fizycznych

Szukam przykładów trudnych problemów (w NP lub trudniejszych) z informatyki, które można sprowadzić do modeli procesów fizycznych.

Na przykład max-2-sat można zredukować do minimalizacji energii w modelu Isinga. Chciałbym znaleźć więcej przykładów tego rodzaju redukcji.

Zliczanie problemów z ograniczeniami (#CSP), ocena funkcji partycjonowania wielu modeli fizycznych, a także wielu tematów w klasycznej symulacji stanów / obwodów kwantowych, wszystkie zasadniczo kurczą się sieci tensorowe, co jest problemem # P-zupełnym. Dobry przegląd znajduje się w następujących dokumentach:

Itai Arad, Zeph Landau, obliczenia kwantowe i ocena sieci tensorowych

Cai, Lu, Xia Holograficzne algorytmy z matchgatesami przechwytują precyzyjnie wykonalny planar #CSP

Zobacz zwłaszcza wprowadzenie tego ostatniego w odniesieniu do połączenia z modelami fizycznymi.

Allan Sly udowodnił ostatnio, że MAX-CUT redukuje (w ramach losowej redukcji) do pobierania próbek z rozkładu Gibbs gazu z siatki twardego rdzenia poza przejściem fazowym unikalności na siatce Bethe. Mniej ścisłe wyniki tego rodzaju (gdzie redukcja polega na próbkowaniu z parametrami w obrębie obszaru niejednorodności, a nie dokładnie na progu przejściowym wyjątkowości) są dobrze znane od dłuższego czasu: patrz na przykład [LV97] i [DFJ02] .

Istnieją również prace Schucha, Ciraca i Verstraete pokazujące, że znalezienie stanów podstawowych nawet systemów 1D z odwrotną polaryzacją jest trudne dla NP, nawet jeśli obiecujemy, że stan podstawowy jest stanem macierzowym - patrz http: // arxiv .org / abs / 0802.3351 . Jeśli dobrze pamiętam, redukcja zaczyna się od dowolnego weryfikatora NP, niekoniecznie w przypadku konkretnego problemu, takiego jak MAX-2-SAT.