Класс BQP (Tlgvv BQP)

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

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

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

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

[править | править код]

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

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

[править | править код]
Положение класса BQP в иерархии классов сложности.

Примечания

[править | править код]
  1. 1 2 arXiv: quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor. Дата обращения: 4 ноября 2010. Архивировано 4 декабря 2014 года.

Литература

[править | править код]
  • «Algorithms for quantum computation: discrete logarithms and factoring» P.W. Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700