BQP

BQP (ang. bounded-error quantum polynomial time, dosł. „kwantowy czas wielomianowy z ograniczonym błędem”) – klasa złożoności w teorii złożoności obliczeniowej obejmująca problemy decyzyjne, które mogą być rozwiązywane przez komputer kwantowy w czasie wielomianowym z prawdopodobieństwem błędu ograniczonym stałą mniejszą niż 1/2. W standardowej definicji przyjmuje się próg błędu co najwyżej 1/3 dla każdej instancji, czyli prawdopodobieństwo poprawnej odpowiedzi co najmniej 2/3. BQP jest kwantowym odpowiednikiem klasy BPP(inne języki), zdefiniowanej dla klasycznych obliczeń probabilistycznych. Do najważniejszych problemów należących do BQP zalicza się rozkład liczb całkowitych na czynniki i logarytm dyskretny, rozwiązywane algorytmem Shora. Zachodzą zawierania 𝖯⊆𝖡𝖯𝖯⊆𝖡𝖰𝖯⊆𝖠𝖶𝖯𝖯⊆𝖯𝖯⊆𝖯𝖲𝖯𝖠𝖢𝖤, natomiast relacja BQP z klasą NP pozostaje otwarta.

Klasa BQP służy do formalnego opisu tego, co uważa się za efektywnie rozwiązywalne w modelu obliczeń kwantowych z niewielkim, kontrolowanym prawdopodobieństwem pomyłki. Podobnie jak w definicjach klas P czy NP, chodzi o asymptotyczny czas działania względem długości wejścia.

Definicja

Sfera Blocha – geometryczna reprezentacja stanu kubitu, podstawowej jednostki informacji w obliczeniach kwantowych
Algorytm BQP (1 przebieg)
Poprawna odpowiedź / uzyskanataknie
tak ≥ 2/3≤ 1/3
nie ≤ 1/3≥ 2/3
Algorytm BQP (k przebiegów)
Poprawna odpowiedź / uzyskanataknie
tak >1−2−ck<2−ck
nie <2−ck>1−2−ck
dla pewnej stałej c > 0

Formalnie BQP można definiować jako klasę języków L⊆{0,1}∗, dla których istnieje wielomianowo jednolita rodzina obwodów kwantowych {Qn}n∈ℕ działających na wejściach długości n, taka że obwód kończy się pomiarem dającym jeden bit odpowiedzi. Jednolitość oznacza tu, że jeden klasyczny algorytm w czasie wielomianowym generuje opis obwodu dla zadanej długości wejścia. Jeżeli x∈L, to Q|x| akceptuje x z prawdopodobieństwem co najmniej 2/3. Jeżeli x∉L, to odrzuca x z prawdopodobieństwem co najmniej 2/3.

Równoważnie można używać modelu kwantowej maszyny Turinga działającej w czasie wielomianowym. Pomysł, że mechanika kwantowa mogłaby dać maszynom obliczeniowym moc przewyższającą klasyczne maszyny Turinga, wysunął w 1982 Richard Feynman. Zwrócił on też uwagę, że mechaniki kwantowej nie da się, jak się zdaje, wydajnie symulować na klasycznych maszynach Turinga, i zasugerował, że takie symulacje mogłyby umożliwić komputery kwantowe. W 1985 David Deutsch formalnie zdefiniował kwantową maszynę Turinga, choć z perspektywy czasu jego definicja okazała się niezadowalająca, a lepsze definicje podali następnie Deutsch wspólnie z Richardem Jozsą oraz Bernstein i Vazirani. Bernstein i Vazirani wykazali m.in. istnienie wydajnej uniwersalnej kwantowej maszyny Turinga, a Andrew Yao wielomianową równoważność tego modelu z obwodami kwantowymi. W praktyce współczesne sformułowania BQP najczęściej używają obwodów kwantowych, bo dobrze odpowiadają one opisowi algorytmów przez kubity, bramki kwantowe i pomiar.

Zestaw bramek kwantowych nazywa się uniwersalnym, gdy złożonymi z nich obwodami można z dowolną dokładnością przybliżyć każde przekształcenie unitarne. W literaturze używa się na przykład zestawu bramki Hadamarda, bramki CNOT i bramki T. Uniwersalny obliczeniowo jest również zestaw złożony z bramki Hadamarda i bramki Toffoliego, mimo że wszystkie generowane przez niego amplitudy są liczbami rzeczywistymi. Z argumentu zliczającego wynika zarazem, że istnieją przekształcenia unitarne wymagające do realizacji wykładniczo wielu bramek elementarnych.

Stała 1/3 w definicji nie ma szczególnego znaczenia. Jeżeli algorytm ma prawdopodobieństwo sukcesu oddzielone od 1/2 niezerową stałą, można uruchomić go wielokrotnie niezależnie i przyjąć odpowiedź większościową, zmniejszając błąd wykładniczo względem liczby powtórzeń. Dlatego ta sama klasa powstaje przy wielu innych stałych progach błędu, o ile są one odseparowane od losowego zgadywania.

Relacje z innymi klasami

Znane zawierania klas probabilistycznych i kwantowych: 𝖯⊆𝖹𝖯𝖯⊆𝖡𝖯𝖯⊆𝖡𝖰𝖯⊆𝖯𝖯⊆𝖯𝖲𝖯𝖠𝖢𝖤. Nie wiadomo, czy większość z tych zawierań jest właściwa (ścisła). Dla czytelności pominięto część klas pośrednich, m.in. AWPP.

Każdy klasyczny algorytm deterministyczny czasu wielomianowego można zasymulować jako obliczenie kwantowe, więc 𝖯⊆𝖡𝖰𝖯. Także klasyczne obliczenia probabilistyczne z ograniczonym błędem mieszczą się w modelu kwantowym, dlatego zwykle zapisuje się 𝖯⊆𝖡𝖯𝖯⊆𝖡𝖰𝖯. Nie wiadomo jednak, czy którekolwiek z tych zawierań jest właściwe. W szczególności nie udowodniono, że BQP zawiera problem niewykonalny w klasycznym czasie wielomianowym.

Znane są natomiast klasyczne górne ograniczenia na moc BQP. Bernstein i Vazirani pokazali zawieranie 𝖡𝖰𝖯⊆𝖯𝖲𝖯𝖠𝖢𝖤, a późniejsze prace dały silniejsze relacje z klasami probabilistycznymi: 𝖡𝖰𝖯 jest zawarta w AWPP(inne języki), a tym samym w PP(inne języki). W szczególności wyniki te nie mówią, że komputery kwantowe mogłyby rozwiązywać dowolne problemy z PSPACE. Wskazują jedynie znane ograniczenia górne wynikające z klasycznej symulacji amplitud kwantowych.

Zawieranie BQP w PSPACE można uzasadnić, obliczając amplitudy końcowe jako sumy wkładów poszczególnych ciągów stanów pośrednich obwodu. Choć liczba składników jest wykładnicza, każdy z nich można wyznaczyć w pamięci wielomianowej i usunąć po dodaniu do sumy. Czas takiej klasycznej symulacji może więc być wykładniczy, mimo że zużycie pamięci pozostaje wielomianowe.

Oszacowanie to można dodatkowo wzmocnić: klasa BQP jest „niska” względem PP, to znaczy użycie jej jako wyroczni nie zwiększa mocy obliczeniowej PP, gdyż 𝖯𝖯𝖡𝖰𝖯=𝖯𝖯. Poprawia to wcześniejsze oszacowanie 𝖡𝖰𝖯⊆𝖯𝖯 uzyskane przez Leonarda Adlemana i współpracowników. Szczególnie ścisły związek BQP z klasą PP ujawnia się przy dopuszczeniu postselekcji: Scott Aaronson pokazał, że rozszerzenie BQP o warunkowanie wyniku na zajściu zdarzenia o niezerowym prawdopodobieństwie (klasa PostBQP(inne języki)) daje dokładnie klasę PP. Charakteryzacja ta dostarczyła m.in. prostszego dowodu, że PP jest zamknięta ze względu na przecięcie języków.

Relacja między BQP a NP pozostaje otwarta. Nie wiadomo, czy 𝖭𝖯⊆𝖡𝖰𝖯, czy 𝖡𝖰𝖯⊆𝖭𝖯, ani czy klasy te są nieporównywalne. Choć formalnie kwestia ta pozostaje nierozstrzygnięta, powszechnie przypuszcza się, że 𝖭𝖯⊈𝖡𝖰𝖯, ponieważ na problemach NP-zupełnych komputery kwantowe zdają się dawać jedynie kwadratowe przyspieszenie (poprzez algorytm Grovera), a nie wykładnicze. Wyniki relatywizowane dają przesłanki, że BQP może zachowywać się inaczej niż klasyczne hierarchie niedeterministyczne. Aaronson uzyskał separację dla problemu relacyjnego i wskazał problem Fourier Checking jako kandydata do separacji decyzyjnej. Raz i Tal później udowodnili separację wyroczniową BQP od PH(inne języki). Takie separacje można traktować jako dolne ograniczenia w modelu złożoności zapytań, mierzącym liczbę odwołań do danych wejściowych.

BQP jest też zamknięta na użycie własnych podprocedur jako wyroczni w czasie wielomianowym. Zapisuje się to jako 𝖡𝖰𝖯𝖡𝖰𝖯=𝖡𝖰𝖯. Intuicyjnie wynika to z faktu, że wielomianowo wiele wywołań algorytmów działających w czasie wielomianowym nadal daje czas wielomianowy, a błędy można obniżyć tak, aby całe obliczenie zachowało ograniczone prawdopodobieństwo pomyłki.

Przykłady problemów i algorytmów

Najbardziej znanym przykładem problemów mieszczących się w BQP są zadania rozkładu liczb całkowitych na czynniki oraz obliczania logarytmu dyskretnego, dla których Peter Shor podał algorytmy kwantowe działające w czasie wielomianowym. Wyniki te są ważne dla kryptografii, ponieważ wiele klasycznych systemów opiera bezpieczeństwo na założeniu praktycznej trudności takich zadań. Nie dowodzą one jednak, że faktoryzacja lub logarytm dyskretny leżą poza klasą P deterministycznych obliczeń wielomianowych. Algorytm faktoryzacji pozostaje zarazem najsilniejszą przesłanką, że klasa BQP wykracza poza BPP: rozkład na czynniki to jeden z najstarszych i najlepiej zbadanych problemów obliczeniowych, dla którego mimo to nie jest znany wydajny algorytm klasyczny. Innym często przywoływanym przykładem jest algorytm Grovera dla przeszukiwania nieuporządkowanej przestrzeni, dający kwadratowe przyspieszenie względem klasycznego przeszukiwania. Algorytm Simona pokazuje z kolei przyspieszenie wykładnicze, a nie tylko kwadratowe. Rozwiązuje on w czasie wielomianowym problem, dla którego wszystkie znane algorytmy klasyczne wymagają czasu wykładniczego, a w modelu wyroczni (czarnej skrzynki) każdy algorytm klasyczny potrzebuje rzędu 2n/2 zapytań. Uogólnienie problemu Simona okazało się kluczowe dla kwantowego algorytmu faktoryzacji Shora.

Do BQP należą również inne problemy naturalnie wynikające z obliczeń kwantowych, zwłaszcza zadania związane z symulacją ewolucji układów kwantowych oraz problemami z obietnicą formułowanymi przez obwody kwantowe.

Nie każdy problem, dla którego znany jest szybki algorytm kwantowy, musi być problemem decyzyjnym wprost. W teorii złożoności wersje decyzyjne, zadania z obietnicą albo problemy estymacji przekłada się na języki i progi akceptacji, aby porównywać je z klasami takimi jak BQP. Z tego powodu hasło „problem w BQP” często oznacza precyzyjnie dobraną wersję decyzyjną lub obietnicową szerszego zadania obliczeniowego.

Problemy z obietnicą

Wiele technicznych wyników o zupełności formułuje się nie dla samej klasy BQP języków całkowitych, lecz dla wersji obietnicowej, zwykle oznaczanej Promise-BQP. Problem z obietnicą określa zachowanie algorytmu tylko na wejściach spełniających jeden z dwóch rozłącznych warunków, pozostawiając wejścia pośrednie poza zakresem problemu. Jest to naturalne w obliczeniach kwantowych, gdzie często trzeba rozróżnić, czy prawdopodobieństwo pomiaru jest co najmniej α, czy co najwyżej β, przy obietnicy luki α−β>0.

Typowym problemem zupełnym dla Promise-BQP jest wariant przybliżonego problemu obwodu kwantowego: mając opis obwodu kwantowego i dwa progi α>β, należy rozstrzygnąć, czy pomiar wskazanego kubitu daje wynik 1 z prawdopodobieństwem co najmniej α, czy co najwyżej β. Każde obliczenie z BQP można sprowadzić do takiego testu przez zakodowanie algorytmu jako obwodu i ustawienie progów, np. 2/3 oraz 1/3.

Znane są też problemy zupełne dla Promise-BQP o charakterze czysto algebraicznym, niewymagające wprost języka obwodów kwantowych. Janzing i Wocjan wykazali, że zupełne dla tej klasy jest oszacowanie wybranego elementu diagonalnego (Am)jj potęgi rzadkiej symetrycznej macierzy rzeczywistej A z dokładnością do εbm, gdzie b ogranicza normę macierzy. Problem pozostaje trudny dla Promise-BQP nawet wtedy, gdy macierz ma wyłącznie wyrazy −1, 0 i 1. Wynik ten daje algebraiczną charakteryzację Promise-BQP, niewyrażoną bezpośrednio językiem obwodów kwantowych.

Znaczenie

Procesor komputera kwantowego (Chalmers, 2017); BQP opisuje abstrakcyjny model efektywnego obliczania kwantowego, a nie konkretną architekturę sprzętową

BQP jest jednym z podstawowych punktów odniesienia w ocenie potencjalnej przewagi obliczeń kwantowych nad klasycznymi. Jeżeli dla pewnego naturalnego problemu uda się pokazać, że należy do BQP i jednocześnie nie należy do odpowiednich klas klasycznych, byłby to formalny dowód separacji modeli obliczeń. Na razie najważniejsze separacje mają charakter relatywizowany albo dotyczą szczególnych modeli i zadań, dlatego ostrożnie odróżnia się dowody przewagi w modelach ograniczonych od pełnego rozdzielenia klas 𝖯, 𝖡𝖯𝖯 i 𝖡𝖰𝖯.

Znaczenie BQP nie zależy wyłącznie od przyszłej budowy dużych komputerów kwantowych odpornych na błędy. Klasa ta porządkuje pytania o algorytmy kwantowe, symulację układów fizycznych, wpływ kwantowości na kryptografię oraz granice klasycznej symulacji procesów kwantowych. Dzięki temu stanowi wspólny język dla teorii złożoności, informatyki kwantowej i części fizyki obliczeniowej.

Zobacz też