Класс BQP

Класс 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}

Примечания

  1. ↑ 1 2 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

Литература

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

Ссылки

Классы сложности алгоритмов
 
Cчитаются лёгкими P • L • NL • AC • NC • P-complete • BQP • BPP • RP • ZPP
Предпологаются сложными NP (co-NP • NP-complete • co-NP-complete ) • UP • #P (#P-complete ) • IP • PSPACE (PSPACE-complete) • R • PP • AM
Cчитаются сложными EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-complete • Co-RE-complete • PH
Список алгоритмов

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Класс BQP" в других словарях:

  • Класс BPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс NP — В теории алгоритмов классом NP (от англ. non deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за… …   Википедия

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс сложности — В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0… …   Википедия

  • Класс ВPP — В теории алгоритмов классом сложности BPP (от англ. bounded error, probabilistic, polynomial) называется класс предикатов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться …   Википедия

  • Класс P — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отр …   Википедия

  • Класс RP — Будем считать, что язык L принадлежит классу RP («randomized polynomial class»  случайный полиномиальный), если он допускается вероятностной машиной Тьюринга M, для которой выполнены следующие условия: Если w не принадлежит L, то вероятность …   Википедия

  • Класс co-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP,  класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, то есть множеств слов над конечным… …   Википедия

  • Класс сo-NP — В теории алгоритмов часто рассматривается класс, тесно связанный с P и NP, класс дополнений языков из NP, называемый co NP. Формальное определение Класс сложности co NP определяется для множества языков, т.е. множеств слов над конечным алфавитом… …   Википедия

  • Класс Sharp-P — Правильный заголовок этой статьи  Класс #P. Он показан некорректно из за технических ограничений. В теории сложности, #P является классом проблем, решением которых является количество успешных, т.е., завершающихся в допускающих состояниях,… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»