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, 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 ${\mathsf {P}}\subseteq {\mathsf {BPP}}\subseteq {\mathsf {BQP}}\subseteq {\mathsf {AWPP}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}$, 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. Nie jest to klasa „wszystkich problemów, które komputer kwantowy rozwiązuje szybko” w sensie praktycznym. Podobnie jak w definicjach klas P czy NP, chodzi o asymptotyczny czas działania względem długości wejścia. Definicja nie uwzględnia konkretnych kosztów sprzętowych, liczby odpornych na błędy kubitów ani stałych ukrytych w notacji asymptotycznej.

Definicja

Sfera Blocha – geometryczna reprezentacja stanu kubitu, podstawowej jednostki informacji w obliczeniach kwantowych

Algorytm BQP (1 przebieg)
Poprawna odpowiedź / uzyskana	tak	nie
tak	≥ 2/3	≤ 1/3
nie	≤ 1/3	≥ 2/3
Algorytm BQP (k przebiegów)
Poprawna odpowiedź / uzyskana	tak	nie
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\subseteq \{0,1\}^{*}$, dla których istnieje wielomianowo jednolita rodzina obwodów kwantowych $\{Q_{n}\}_{n\in \mathbb {N} }$ działających na wejściach długości $n$, taka że obwód kończy się pomiarem dającym jeden bit odpowiedzi. Jeżeli $x\in L$, to $Q_{|x|}$ akceptuje $x$ z prawdopodobieństwem co najmniej $2/3$. Jeżeli $x\notin 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. Jego pierwotną motywacją była wydajna symulacja układów kwantowych, a pierwszą definicję kwantowej maszyny Turinga podał w 1985 David Deutsch. Dopracowane sformułowania, dzięki którym obliczenia kwantowe ugruntowały się jako dziedzina teorii złożoności, podali następnie Andrew Yao oraz Bernstein i Vazirani. Ci dwaj ostatni wprowadzili ten model w teorii złożoności kwantowej i wykazali jego podstawowe własności, w tym związek z obliczeniami przez jednolite rodziny obwodów kwantowych. 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.

Definicja klasy nie zależy przy tym od wyboru skończonego uniwersalnego zestawu elementarnych bramek kwantowych. 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: ${\mathsf {P}}\subseteq {\mathsf {ZPP}}\subseteq {\mathsf {BPP}}\subseteq {\mathsf {BQP}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}$. 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 ${\mathsf {P}}\subseteq {\mathsf {BQP}}$. Także klasyczne obliczenia probabilistyczne z ograniczonym błędem mieszczą się w modelu kwantowym, dlatego zwykle zapisuje się ${\mathsf {P}}\subseteq {\mathsf {BPP}}\subseteq {\mathsf {BQP}}$. 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 ${\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}$, a późniejsze prace dały silniejsze relacje z klasami probabilistycznymi: ${\mathsf {BQP}}$ jest zawarta w AWPP, a tym samym w PP. 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. 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ż ${\mathsf {PP}}^{\mathsf {BQP}}={\mathsf {PP}}$. Poprawia to wcześniejsze oszacowanie ${\mathsf {BQP}}\subseteq {\mathsf {PP}}$ 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) 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 ${\mathsf {NP}}\subseteq {\mathsf {BQP}}$, czy ${\mathsf {BQP}}\subseteq {\mathsf {NP}}$, ani czy klasy te są nieporównywalne. Choć formalnie kwestia ta pozostaje nierozstrzygnięta, powszechnie przypuszcza się, że ${\mathsf {NP}}\not \subseteq {\mathsf {BQP}}$, 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ł problemy typu Forrelation/Fourier Checking jako kandydatów do separacji decyzyjnej. Raz i Tal później udowodnili separację wyroczniową BQP od PH. Takie separacje nie są dowodem bezwarunkowym, ale pokazują ograniczenia wielu klasycznych metod porównywania klas złożoności.

BQP jest też zamknięta na użycie własnych podprocedur jako wyroczni w czasie wielomianowym. Zapisuje się to jako ${\mathsf {BQP}}^{\mathsf {BQP}}={\mathsf {BQP}}$. 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 $2^{n/2}$ zapytań. Uogólnienie problemu Simona stało się punktem wyjścia 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. Ujęcie to wyjaśnia, dlaczego BQP jest centralną klasą kwantowej teorii złożoności: opisuje nie tylko konkretne algorytmy, lecz także granicę tego, co da się efektywnie oszacować poprzez kontrolowaną ewolucję amplitud i pomiar.

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 $\alpha$, czy co najwyżej $\beta$, przy obietnicy luki $\alpha -\beta >0$.

Typowym problemem zupełnym dla Promise-BQP jest wariant przybliżonego problemu obwodu kwantowego: mając opis obwodu kwantowego i dwa progi $\alpha >\beta$, należy rozstrzygnąć, czy pomiar wskazanego kubitu daje wynik $1$ z prawdopodobieństwem co najmniej $\alpha$, czy co najwyżej $\beta$. 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 $(A^{m})_{jj}$ potęgi rzadkiej symetrycznej macierzy rzeczywistej $A$ z dokładnością do $\varepsilon b^{m}$, 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 ${\mathsf {P}}$, ${\mathsf {BPP}}$ i ${\mathsf {BQP}}$.

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ż

• Problem P vs NP
• PSPACE
• informatyka kwantowa

Bibliografia

• SanjeevS. Arora SanjeevS., BoazB. Barak BoazB., Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4  (ang.).
• Michael A.M.A. Nielsen Michael A.M.A., Isaac L.I.L. Chuang Isaac L.I.L., Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2010, ISBN 978-1-107-00217-3  (ang.).

Linki zewnętrzne

• BQP [online], Complexity Zoo [dostęp 2026-05-18] [zarchiwizowane z adresu 2026-04-08]  (ang.).