Оскільки квантові комп'ютери працюють лише за імовірнісними алгоритмами, то клас BQP є квантовим аналогом класу BPP — усі задачі, які можна розв'язати на класичному комп'ютері за поліноміальний час за певної дозволеної обеженої імовірності помилки (). Кажуть, що квантовий комп'ютер може «розв'язати» задачу, якщо в результаті з високою ймовірністю отримується правильна відповідь. Якщо при цьому квантовий комп'ютер розв'язує задачу за поліноміальний час, то така задача належить класу BQP.