Класс EQP
В теории сложности вычислений EQP (иногда называемый QP) — класс задач разрешимости, решаемых квантовым компьютером, который выводит правильный ответ с вероятностью 1 и выполняется за полиномиальное время. Это — квантовый аналог класса сложности P.
Другими словами, существует алгоритм для квантового компьютера (квантовый алгоритм), который точно решает задачу и при этом гарантированно укладывается в полиномиальное время.
См. также
[править | править код]Ссылки
[править | править код]- Complexity Zoo: EQP Архивная копия от 27 августа 2016 на Wayback Machine
| Считаются лёгкими | |
|---|---|
| Предполагаются сложными | |
| Считаются сложными | |
| Общие понятия |  | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Квантовые коммуникации | |||||||||
| Квантовые алгоритмы |
| ||||||||
| Теория квантовой сложности | |||||||||
| Модели квантового компьютинга | |||||||||
| Предотвращение декогеренции | |||||||||
| Физические реализации |
| ||||||||