Класс BQP

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Примерное положение BQP на карте классов NP, P, PSPACE.

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

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

Важные представители[править | править вики-текст]

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

Взаимоотношения с другими классами[править | править вики-текст]

\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

Ссылки[править | править вики-текст]