Lista algorytmów inspirowanych kwantem

Postępy w dziedzinie obliczeń kwantowych doprowadziły do ​​opracowania nowych klasycznych algorytmów. Godne uwagi ostatnie przykłady to inspirowane kwantem algorytmy algebry liniowej:

• Klasyczny algorytm inspirowany kwantem dla systemów rekomendacji
• Klasyczne algorytmy inspirowane kwantem do analizy głównych komponentów i nadzorowanego grupowania
• Inspirowana kwantem regresja stochastyczna niskiej rangi z logarytmiczną zależnością od wymiaru
• Inspirowane kwantem sublinearne klasyczne algorytmy do rozwiązywania układów liniowych niskiego rzędu

i dla Max 3LIN:

• Pokonanie losowego zadania dotyczącego problemów z ograniczeniem stopnia ograniczenia .

Bardzo przydatne może być skompilowanie listy wszystkich znanych klasycznych algorytmów inspirowanych obliczeniami kwantowymi. Jakie inne przykłady są znane?

Jak twierdzi Leslie G. Valiant w swoim pierwszym artykule 1 ,

Algorytmy holograficzne są inspirowane kwantowym modelem obliczeniowym. Są one jednak wykonywalne na klasycznych komputerach i nie wymagają komputerów kwantowych.

Jest to technika projektowania algorytmicznego, która została wykorzystana (przez samego Valianta i innych) do stworzenia algorytmów wielomianowych dla kilku problemów, które są niewielkimi odmianami ważnych problemów trudnych dla NP (więcej na ten temat na wikipedii 2 ).

Niedawno trwają także prace nad niskopoziomowym programowaniem półfinałowym, które, choć nie oparte bezpośrednio na algorytmie kwantowym, wciąż wykorzystuje te same techniki inspirowane kwantem.

Cały proces związany jest z algorytmami ewolucyjnymi inspirowanymi kwantem (QIEA), z faktycznymi algorytmami wykorzystującymi techniki obliczeń kwantowych, patrz badanie (źródło ACM) . Inny algorytm inspirowany kwantem wykorzystuje go do optymalizacji numerycznej .

Algorytm kwantowego wyżarzania kwantowego Monte Carlo (QMC-QA ¹ ) lub algorytm kwantowego wyżarzania dyskretnego (SQA ² ) działał lepiej niż testowane urządzenie D-Wave w ostatnich badaniach :

Ustanawiamy pierwszy przykład korzyści skalowania eksperymentalnego wyżarzania kwantowego w porównaniu z klasycznym symulowanym wyżarzaniem: odkrywamy, że urządzenie D-Wave wykazuje zdecydowanie lepsze skalowanie niż symulowane wyżarzanie, z 95% pewnością, w zakresie rozmiarów problemów, które możemy przetestować . Nie znajdujemy jednak dowodów na przyspieszenie kwantowe: symulowane wyżarzanie kwantowe wykazuje najlepsze skalowanie ze znacznym marginesem.

Ponieważ zarówno urządzenie D-Wave, jak i SQA przewyższają SA w niektórych przypadkach problemowych, sprawia to wrażenie, że SQA jest rodzajem algorytmu inspirowanego kwantem. W nowszych badaniach testujących procesor D-Wave 2000Q stwierdzono również, że jego wydajność lepiej koreluje z zaproponowanym w tym badaniu klasycznym modelem oznaczonym „algorytmem Monte Carlo (SVMC) spin-wektor” niż w przypadku SQA:

Używamy tego, aby argumentować, że kluczowym powodem spowolnienia annealera kwantowego względem SQA jest jego nieoptymalnie wysoka temperatura, która powoduje, że zachowuje się on bardziej jak SVMC. Zatem wysoka wydajność SQA w klasie instancji posadzonej logicznie sugeruje, że ta klasa jest dobrym celem lub podstawą do eksploracji ewentualnego przyspieszenia kwantowego przy użyciu sprzętu QA.

Jeśli zignorujemy historię D-Wave w tle, czy nadal możemy stwierdzić, że SQA jest inspirowanym kwantem algorytmem optymalizacji, który przewyższa klasyczne symulowane wyżarzanie (i może inne algorytmy optymalizacji) w przypadku niektórych problemów? To zależy. Jeśli celem jest znalezienie stanu podstawowego jakiegoś układu kwantowego, odpowiedź brzmi: tak. Ale jeśli celem jest posiadanie algorytmu optymalizacji ogólnego przeznaczenia podobnego do symulowanego wyżarzania, wówczas odpowiedź brzmi „nie”.

1. _{Martoňák, R., Santoro, GE & Tosatti, E. Wyżarzanie kwantowe metodą Monte Carlo-całki całkowej: dwuwymiarowy losowy model Isinga. Phys. Rev. B 66 , 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203}
2. _{Santoro, GE, Martoňák, R., Tosatti, E. & Car, R. Teoria kwantowego wyżarzania szkła obrotowego Ising. Science 295 , 2427–2430 (2002). URL http://dx.doi.org/10.1126/science.1068774 .}

Spójrz na liniowe programowanie genetyczne inspirowane kwantem. Algorytm ten ma na celu wywołanie programów komputerowych w imperatywnych językach. Na przykład:

• https://www.researchgate.net/project/Quantum-Inspired-Linear-Genetic-Programming

• Liniowe programowanie genetyczne inspirowane kwantowo jako system zarządzania wiedzą, sierpień 2013, The Computer Journal 56 (9): 1043-1062, Douglas Mota Dias i Marco Aurelio C. Pacheco https://doi.org/10.1093/comjnl/bxs108