Класс BQP

В теории алгоритмов классом сложности BQP (от англ. bounded error quantum polynomial time) называется класс проблем разрешимости, которые могут быть решены квантовым компьютером за полиномиальное время (время работы над задачей полиномиально зависит от размера входных данных), обеспечив при этом вероятность получения верного ответа как минимум 2/3 для любого входа. Является квантовым аналогом класса BPP.

Другими словами, задача относится к классу BQP, если существует квантовый алгоритм (алгоритм для квантового компьютера), решающий данную проблему с высокой вероятностью и работающий гарантированно не более чем за полиномиальное время. Для произвольного запуска алгоритма вероятность получения неверного ответа должна быть не более 1/3.

Интерес к квантовым вычислениям и компьютерам вызван некоторыми задачами, находящимся в классе BQP, но принадлежность которых к классу P неизвестна:

• Факторизация чисел — алгоритм Шора^[1]
• Дискретный логарифм^[1]
• Моделирование квантовых систем с несколькими частицами (Задача Фейнмана, иногда также универсальный квантовый симулятор)

${\displaystyle {\mbox{P}}\subseteq {\mbox{BPP}}\subseteq {\mbox{BQP}}\subseteq {\mbox{AWPP}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}}$

• «Algorithms for quantum computation: discrete logarithms and factoring» P.W. Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

• А. Х. Шень, М. Н. Вялый, Курс лекций «Классические и квантовые вычисления». Лекция 8: Определение квантового вычисления. Примеры // Интуит.ру, 15.03.2007