Класс BQP

Примерное положение BQP на карте классов NP, P, PSPACE.

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

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

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

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

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

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

Положение класса BQP в иерархии классов сложности.

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