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

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

Важные представители

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

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

Взаимоотношения с другими классами

${\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

Ссылки

• А. Х. Шень, М. Н. Вялый, // Интуит.ру, 15.03.2007