Jakie problemy w świecie rzeczywistym (z wyjątkiem kryptografii) można skutecznie rozwiązać za pomocą algorytmu kwantowego?

11

To pytanie jest bardzo podobne, ponieważ Czy istnieje jakieś ogólne stwierdzenie dotyczące tego, jakie problemy można rozwiązać bardziej efektywnie za pomocą komputera kwantowego?

Jednak odpowiedzi na te pytania dotyczyły głównie teoretycznego / matematycznego punktu widzenia.

W przypadku tego pytania bardziej interesuje mnie praktyczny / inżynierski punkt widzenia. Chciałbym więc zrozumieć, jakie problemy można bardziej efektywnie rozwiązać za pomocą algorytmu kwantowego niż w przypadku klasycznego algorytmu. Naprawdę zakładam, że nie masz pełnej wiedzy na temat wszystkich możliwych klasycznych algorytmów, które mogłyby optymalnie rozwiązać ten sam problem!

Wiem, że kwantowe zoo wyraża całą kolekcję problemów, dla których istnieje algorytm kwantowy, który działa wydajniej niż klasyczny algorytm, ale nie udaje mi się połączyć tych algorytmów z rzeczywistymi problemami .

Rozumiem, że algorytm faktoringu Shora jest bardzo ważny w świecie kryptografii, ale celowo wykluczyłem kryptografię z zakresu tego pytania, ponieważ świat kryptografii jest bardzo specyficznym światem, który zasługuje na swoje własne pytania.

W wydajnych algorytmach kwantowych mam na myśli, że musi istnieć co najmniej jeden krok w algorytmie, który musi zostać przetłumaczony na obwód kwantowy na komputerze kwantowym n-qubit. Zasadniczo więc ten obwód kwantowy tworzy macierz x , a jego wykonanie da jedną z możliwości z pewną możliwością (więc różne przebiegi mogą dać różne wyniki - gdzie prawdopodobny kaptur każdego z możliwości określa skonstruowana macierz hermitowska x .)2n2n2n2n2n2n

Myślę więc, że aby odpowiedzieć na moje pytanie, musi istnieć jakiś aspekt / charakterystyka problemu świata rzeczywistego, który można odwzorować na macierz hermitowską . Więc jakie aspekty / cechy rzeczywistego problemu można zmapować na taką matrycę?2n×2n

Z problemem w świecie rzeczywistym mam na myśli faktyczny problem, który można rozwiązać za pomocą algorytmu kwantowego, nie mam na myśli dziedziny, w której może istnieć potencjalne zastosowanie algorytmu kwantowego.

JanVdA
źródło

Odpowiedzi:

7

Nie będę podawał żadnych precyzyjnych stwierdzeń, które problemy można rozwiązać bardziej efektywnie za pomocą algorytmów kwantowych (w porównaniu do istniejących algorytmów klasycznych), ale raczej kilka przykładów :

  • Dyskretna transformata Fouriera (DFT) jest stosowana w prawie wszystkich współczesnych systemach muzycznych, na przykład w iPodzie. Algorytm ten samodzielnie zmienił świat muzyki cyfrowej. Zobacz to dla podsumowania. Jednak kwantowa transformata Fouriera może dodatkowo poprawić złożoność DFT, tj. Od do . Tutaj napisałem odpowiedź na ten temat .O ( log 2 N )O(Nlog(N))O(log2N)

  • Algorytm kwantową systemów równań liniowych zapewnia wykładniczy przyrost prędkości w stosunku do klasycznej metody Gaussa eliminacji.

Algorytm kwantowy dla liniowych układów równań zaprojektowany przez Arama Harrowa, Avinatana Hassidima i Setha Lloyda jest algorytmem kwantowym sformułowanym w 2009 roku do rozwiązywania układów liniowych. Algorytm ocenia wynik pomiaru skalarnego wektora rozwiązania dla danego liniowego układu równań.

Algorytm jest jednym z głównych podstawowych algorytmów, które mają przyspieszyć ich klasyczne odpowiedniki, wraz z algorytmem faktoringu Shora, algorytmem wyszukiwania Grovera i symulacją kwantową. Pod warunkiem, że układ liniowy jest rzadki i ma niski numer warunku oraz że użytkownik jest zainteresowany wynikiem pomiaru skalarnego na wektorze rozwiązania, zamiast wartości samego wektora rozwiązania, a następnie algorytm ma czas działania , gdzie to liczba zmiennych w układzie liniowym. Zapewnia to wykładnicze przyspieszenie w stosunku do najszybszego klasycznego algorytmu, który działa w lub O(log(N) κ 2 ) N O ( N κ ) O(NκO(log(N)κ2)NO(Nκ)O(Nκ) dla dodatnich macierzy półfinałowych).

Jednym z pierwszych - i najważniejszych - zastosowań komputera kwantowego jest prawdopodobnie symulacja układów mechaniki kwantowej. Istnieją systemy kwantowe, dla których nie jest znana wydajna klasyczna symulacja, ale które możemy symulować na uniwersalnym komputerze kwantowym. Co to znaczy „symulować” system fizyczny? Według OED symulacja jest „techniką naśladowania zachowania jakiejś sytuacji lub procesu (ekonomicznego, wojskowego, mechanicznego itp.) Za pomocą odpowiednio analogicznej sytuacji lub aparatu”. To, co weźmiemy pod uwagę w symulacji, to przybliżenie dynamiki układu fizycznego. Zamiast dostosowywać nasz symulator do symulacji tylko jednego rodzaju układu fizycznego (który jest czasami nazywany symulacją analogową),

Szczegółowe informacje znajdują się w rozdziale 7 notatek z wykładów Ashleya Montaro.

Hybrydowe algorytmy kwantowe / klasyczne łączą przygotowanie i pomiar stanu kwantowego z klasyczną optymalizacją. Algorytmy te ogólnie mają na celu określenie wektora własnego stanu podstawowego i wartości własnej operatora pustelnika.

QAOA :

Algorytm optymalizacji kwantowej aproksymacji [1] jest zabawkowym modelem wyżarzania kwantowego, który można wykorzystać do rozwiązywania problemów w teorii grafów. Algorytm wykorzystuje klasyczną optymalizację operacji kwantowych w celu maksymalizacji funkcji celu.

Wariacyjny Eigensolver kwantowy

Algorytm VQE stosuje klasyczną optymalizację, aby zminimalizować oczekiwanie energetyczne stanu ansatz w celu znalezienia energii stanu podstawowego cząsteczki [2] . Można to również rozszerzyć, aby znaleźć wzbudzone energie cząsteczek. [3] .

Więcej takich przykładów można znaleźć na samej Wikipedii . Oprócz nich istnieje wiele najnowszych algorytmów, które można wykorzystać w uczeniu maszynowym i analizie danych. Ta odpowiedź będzie trochę za długa, jeśli dodam szczegóły tych wszystkich. Jednak zobacz to i tamto oraz odniesienia do nich.

[1]: A Quantum Approximate Optimization Algorytm Farhi i in. (2014)

[2]: Wariacyjny solver wartości własnych na procesorze kwantowym Peruzzo i in. (2013)

[3]: Wariacyjne obliczenia kwantowe stanów wzbudzonych Brierley i in. (2018)

Sanchayan Dutta
źródło
1
Dzięki za obszerną odpowiedź. Odpowiedź jest więc dla mnie wystarczająco jasna dla punktów symulacji Hamiltona i algorytmu kwantowego dla liniowych układów równań, ale dla innych punktów brakuje powiązania z problemem świata rzeczywistego. Dla mnie większość z tych algorytmów kwantowych jest bardzo teoretyczna i nie rozumiem, jak można je wykorzystać do rozwiązania rzeczywistego problemu. Powiązanie ich z rzeczywistym problemem w świecie rzeczywistym (nawet bardzo prostym) już uczyniłoby to o wiele jaśniejszym.
JanVdA,
1
@JanVdA Wspomniałem już o zastosowaniu dyskretnych transformacji Fouriera w świecie rzeczywistym. Przeczytaj to jeszcze raz. Problemy w teorii grafów są niezwykle istotne zarówno dla informatyki, jak i fizyki statystycznej (QAOA). VQE miałoby znaczenie dla chemii obliczeniowej. Jeśli to nie jest „prawdziwy świat”, nie wiem, co jest.
Sanchayan Dutta
Myślałem, że pierwszy punkt nie dotyczy DFT, ale QFT. Linki o QFT wyjaśniają, czym on nie jest, ale nie wyjaśniają, w jaki sposób można go wykorzystać w przypadku rzeczywistego problemu. VQE rzeczywiście rozwiązuje problem rzeczywistego świata, przepraszam, że nie wspomniałem o nim w moim komentarzu (sklasyfikowałem go jako Symulację Hamiltona). Wiem, że kilka problemów teorii grafów można poprawić za pomocą algorytmu kwantowego, ale wciąż szukam pierwszego problemu w świecie rzeczywistym, który można rozwiązać za pomocą takiego algorytmu.
JanVdA,
@JanVdA QFT można wykorzystać do tych samych celów, z których korzysta DFT. Byłby po prostu bardziej wydajny.
Sanchayan Dutta
@JanVdA Innym powszechnym zastosowaniem QFT jest estymacja fazy kwantowej, która jest szczególnie używana w algorytmie kwantowym „Układ równań liniowych”. Jestem teraz trochę zajęty, ale jeśli nalegacie na to, rozwinę nieco więcej odpowiedzi.
Sanchayan Dutta