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