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

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 .)$2^n$$2^n$$2^n$$2^n$$2^n$$2^n$

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ę?$2^n \times 2^n$

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.

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 $\mathcal{O}(N\log(N))$$\mathcal{O}(\log^2 N)$

• 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${\displaystyle \kappa }$$O(\log(N)\kappa ^{2})$${\displaystyle N}$${\displaystyle O(N\kappa )}$$O(N{\sqrt {\kappa }})$ dla dodatnich macierzy półfinałowych).

• Symulacja Hamiltona :

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 :

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)