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 .
Odpowiedzi:
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) :
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).
źródło