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.