Szybka klasyczna symulacja algorytmów kwantowych

Czy istnieją przykłady przypadków, w których klasyczna symulacja algorytmu kwantowego dla problemu przewyższa najlepiej znany wcześniej klasyczny algorytm dla tego problemu? „Lepsze wyniki” nie musi oznaczać innej klasy złożoności, może po prostu być lepsze skalowanie.

To pytanie zostało zainspirowane przypadkiem wydajnej klasycznej symulacji kwantowego algorytmu rekomendacji .

cc.complexity-theory quantum-computing quantum-information

— delete000
źródło

Twoje pytanie, jak stwierdzono, naprawdę nie ma sensu. Klasyczna symulacja algorytmu kwantowego jest specyficznym rodzajem algorytmu klasycznego, więc nie może być szybsza niż najlepszy algorytm klasyczny. Może to być najszybszy znany klasyczny algorytm, ale nie może być lepszy, ponieważ dzięki temu byłby lepszy niż on sam.

— Craig Gidney

Wydaje mi się, że miałeś na myśli „Lepsze niż dotychczas znany klasyczny algorytm”

— Frédéric Grosshans,

Kiedy czytałem pytanie, myślałem o tym zastrzeżeniu, ale spodziewałem się, że jednym z dwóch klasycznych algorytmów będzie „wcześniej znana” niesymulacja algorytmu kwantowego. Teraz wiem lepiej.

— delete000

Twoje pytanie zostało zainspirowane najnowszym, inspirowanym kwantem zaawansowanym algorytmem rekomendacji. Pamiętaj, że nie jest to pierwszy raz, gdy coś takiego się dzieje. W 2015 r. Podobne zmiany miały miejsce w przypadku przybliżonego MAX3LIN : algorytm quanutm przewyższający wszystkie poprzednie znane algorytmy klasyczne motywował do udanego poszukiwania lepszego klasycznego algorytmu. Jednak, o ile mi wiadomo, w obu tych przypadkach klasyczne algorytmy nie wyglądają jak klasyczna symulacja ewolucji kwantowej.

Znam jeden artykuł opisujący klasyczną symulację układu kwantowego pozwalającą na lepsze wyniki niż wcześniej znane algorytmy (pełne ujawnienie: autorzy są moimi przyjaciółmi) :

Algorytm inspirowany kwantem do szacowania trwałości dodatnich macierzy półfinałowych, autorstwa L. Chakhmakhchyana, NJ Cerfa, R. Garcii-Patrona, arXiv: 1609.02416 / Phys. Rev. A 96 , 022329

Jest to oparte na połączeniu między optyką stałą a kwantową, co pokazano za pomocą próbkowania bozonu . W przeciwieństwie do zwykłego podejścia, przyglądają się stanom, o których wiadomo, że są łatwe do symulacji (stany termiczne), i wykorzystują tę symulację do wykonania obliczenia Monte-Carlo trwałej Hermitian dodatnich półfinałowych macierzy. W przypadku niektórych klas macierzy ten algorytm zapewnia lepsze przybliżenie niż najlepiej znany wcześniej algorytm (algorytm Gurvitsa).

— Frédéric Grosshans
źródło