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 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.