Jakie mogą być przyszłe zastosowania algorytmu HHL?

17

Uwaga do słownictwa: słowo „hamiltonian” jest używane w tym pytaniu, aby mówić o matrycach pustelniczych.


Algorytm HHL wydaje się być aktywnym przedmiotem badań w dziedzinie obliczeń kwantowych, głównie dlatego, że rozwiązuje bardzo ważny problem polegający na znalezieniu rozwiązania liniowego układu równań.

Według oryginalnego artykułu Algorytm kwantowy do rozwiązywania liniowych układów równań (Harrow, Hassidim i Lloyd, 2009) oraz niektóre pytania zadawane na tej stronie

algorytm HHL jest ograniczony do niektórych szczególnych przypadków. Oto podsumowanie (które może być niekompletne!) Cech algorytmu HHL:


Algorytm HHL

Algorytm HHL rozwiązuje układ liniowy równania z następującymi ograniczeniami:

A|x=|b

Ograniczenia :A

Ograniczenia dotyczące :|b

  • |b powinien być sprawnie przygotowany. Dotyczy to:
    1. Określone wyrażenia . Na przykład stan to skutecznie przygotowane.| b = n i = 0 ( | 0 + | 1 |b
      |b=i=0n(|0+|12)
    2. |b reprezentujący dyskretyzację efektywnie integrowalnego rozkładu prawdopodobieństwa (patrz Tworzenie superpozycji, które odpowiadają efektywnie integrowalnym rozkładom prawdopodobieństwa (Grover i Rudolph, 2002) ).

Ograniczenia dotyczące (wynik):|x

  • | x x | M | x |xNie można w pełni odzyskać przez pomiar. Jedyne informacje, które możemy odzyskać z to „informacje ogólne” („wartość oczekiwana” to termin użyty w oryginalnym dokumencie HHL), takie jak|x
    x|M|x

Pytanie: Biorąc pod uwagę wszystkie te ograniczenia i wyobrażając sobie, że jesteśmy w 2050 r. (A może w 2025 r., Kto wie?) Z odpornymi na uszkodzenia wielkoskalowymi układami kwantowymi (tj. Nie jesteśmy ograniczeni sprzętowo), jakie problemy w świecie rzeczywistym czy algorytm HHL może rozwiązać (w tym problemy, w których HHL jest używany tylko jako podprogram)?

Znam pracę Analiza zasobów betonowych algorytmu kwantowego układu liniowego zastosowanego do obliczenia przekroju rozpraszania elektromagnetycznego celu 2D (Scherer, Valiron, Mau, Alexander, van den Berg & Chapuran, 2016) oraz odpowiednią implementację w język programowania Quipper i szukam innych przykładów rzeczywistych gdzie HHL miałyby zastosowanie w praktyce. Nie wymagam opublikowanego artykułu, nawet niepublikowanego, chcę tylko podać przykłady rzeczywistych przypadków użycia.


EDYTOWAĆ:

Nawet jeśli jestem zainteresowany każdym przypadkiem użycia, wolałbym niektóre przykłady, w których HHL jest bezpośrednio używany, tj. Nie jest używany jako podprogram innego algorytmu.

Jeszcze bardziej interesują mnie przykłady układów liniowych wynikające z dyskretyzacji operatora różnicowego, które można rozwiązać za pomocą HHL.

Ale jeszcze raz podkreślę , że interesuje mnie każdy przypadek użycia (podprogramy lub nie), o których wiesz .

Nelimee
źródło
Wspominasz, że chcesz kilka przykładów, w których HHL jest „bezpośrednio używany”. Nie bardzo rozumiem, co przez to rozumiesz. Znam niektóre algorytmy (które potencjalnie mogą mieć praktyczne zastosowania), w których HHL jest jednym z podstawowych kroków, ale na pewno nie jedynym . Czy coś takiego jak rozpoznanie sekwencji genetycznych wykorzystujących HHL jako jeden z podstawowych etapów (z zastrzeżeniem wszystkich wspomnianych ograniczeń), byłoby odpowiednią odpowiedzią? Pozostałe podstawowe etapy dotyczą głównie symulacji Hamiltona i przygotowania stanu.
Sanchayan Dutta
Ja wolę kilka przykładów, gdzie jest bezpośrednio stosowane HHL. Oznacza to, że problem można sformułować bezpośrednio jako liniowy układ równań do rozwiązania. Jest tak w przypadku rozwiązywania równań różniczkowych: dyskrecjonujemy równanie i rozwiązujemy dyskretny problem, który jest w większości rzadkim układem liniowym. Ale inne przykłady są mile widziane.
Nelimee,

Odpowiedzi:

6

Kilka lat temu w algorytmach kwantowych i metodzie elementów skończonych Montanaro i Pallister wykazali, że algorytm HHL można zastosować w metodzie elementów skończonych (FEM), która jest „techniką skutecznego znajdowania przybliżeń numerycznych rozwiązań wartości brzegowej problemy (BVP) dla równań różniczkowych cząstkowych, oparte na dyskretyzacji przestrzeni parametrów za pomocą skończonej siatki " .

Wykazali, że w tym kontekście HHL można wykorzystać do osiągnięcia (być może co najwyżej) przyspieszenia wielomianowego w stosunku do standardowego algorytmu klasycznego („metoda gradientu sprzężonego”).

W odniesieniu do rzeczywistych przypadków użycia twierdzą, że

„Jednym z przykładowych zastosowań jest każdy problem dynamiczny z udziałem ciał, co implikuje rozwiązanie PDE zdefiniowanego w przestrzeni konfiguracyjnej o wymiarze 2n. Ponadto może występować znacząca przewaga w problemach z finansami matematycznymi; na przykład wycena opcji wielu zestawów wymaga rozwiązania czarnego - Równanie Scholesa w domenie o wymiarze podanym przez liczbę zasobów ”n

Otwiera to cały obszar potencjalnych przypadków użycia HHL (przy założeniu, że warunki dotyczące rzadkości mogą być spełnione).A

SLesslyTall
źródło
2
Nie mam teraz czasu na przeczytanie tego artykułu, ale ze streszczenia wydaje się, że artykuł jest interesujący. Przeczytałem szybko część III i nie mogłem znaleźć żadnych odniesień do wartości własnych ale pozostałe punkty są albo trywialne ( jest pustelnikiem), ujęte w innych artykułach (hamiltonowska symulacja rzadkiej macierzy ) lub ujęte w artykuł (przygotowanie państwowe). Nie wiedziałem o tym artykule, a aplikacja jest dla mnie szczególnie interesująca (elementy skończone są ściśle powiązane z PDE). Masz moją opinię (i prawdopodobnie nagrodę) :)M Mss=3
Nelimee,
0

Rebentrost i in. Niedawno zastosował algorytm HHL09 w pracy A Quantum Hopfield Neural Network (2018) do optymalizacji funkcji energetycznej sieci Hopfield .

Zasadniczo, jeśli Lagrangian (który służy do optymalizacji energii sieci biorąc pod uwagę ograniczenie ) to:E=12xTWx+θTxPxx(inc)=0

L=12xTWx+θTxλT(Pxx(inc))+γ2xTx
następnie równania optymalizacyjne i można zapisać w postaci . Zauważ, że w wyrażeniu jest parametrem regularyzacji. Musimy znaleźć która ekstremalizuje energię sieci podlegającą ograniczeniom a zatem potrzebujemy techniki odwracania macierzy. W artykule zrobili to dokładnie i do inwersji macierzy wykorzystali algorytm HHL09. Zobacz str. 4 artykułu.Lx=0Lλ=0Av=wγvPx=x(inc)


Krótko mówiąc, uważam, że gdy będziemy mieli komputery kwantowe o wystarczająco dużej liczbie kubitów i czasie dekoherencji, algorytm HHL będzie jedną z najbardziej przydatnych podprogramów dla dowolnego algorytmu kwantowego uczenia maszynowego (ponieważ prawie wszystkie uczenie maszynowe i sieć neuronowa algorytmy obejmują jakąś formę „spadku gradientu” lub „optymalizacji”).

Sanchayan Dutta
źródło