В теории сложности вычислений EQP (иногда называемый QP) — класс задач разрешимости, решаемых квантовым компьютером, который выводит правильный ответ с вероятностью 1 и выполняется за полиномиальное время. Это — квантовый аналог класса сложности P.
Другими словами, существует алгоритм для квантового компьютера (квантовый алгоритм), который точно решает задачу и при этом гарантированно укладывается в полиномиальное время.
См. также
Ссылки
- Complexity Zoo: EQP Архивная копия от 27 августа 2016 на Wayback Machine
 |
|---|
| Считаются лёгкими | - DLOGTIME[англ.]
- AC0[англ.]
- ACC0[англ.]
- TC0[англ.]
- L
- SL[англ.]
- RL[англ.]
- NL
- NC
- SC[англ.]
- CC[англ.]
- P
- ZPP
- RP
- BPP
- BQP
- EQP
- APX
|
|---|
| Предполагаются сложными | |
|---|
| Считаются сложными | - EXPTIME
- NEXPTIME[англ.]
- EXPSPACE[англ.]
- 2-EXPTIME[англ.]
- ELEMENTARY[англ.]
- R
- PR[англ.]
- RE[англ.]
- Co-RE[англ.]
- ALL[англ.]
|
|---|
|
|---|
| Общие понятия | | |
|---|
| Квантовые коммуникации | |
|---|
| Квантовые алгоритмы | |
|---|
| Теория квантовой сложности | |
|---|
| Модели квантового компьютинга | |
|---|
| Предотвращение декогеренции | - Исправление квантовых ошибок
- Стабилизационные коды
- Стабилизационный формализм
- Квантовый свёрточный код
|
|---|
| Физические реализации | | Квантовая оптика | - Кавитационная квантовая электродинамика
- Контурная квантовая электродинамика
- Квантовые вычисления на основе линейной оптики
- Протокол KLM
- Бозонная выборка
|
|---|
| Суперхолодные атомы | |
|---|
| Основанные на спине | - Квантовый компьютер на основе ядерного магнитного резонанса
- Квантовый компьютер Кейна
- Квантовый компьютер Лосса — Ди Винченцо
- NV-центр
|
|---|
Сверхпроводниковые
квантовые компьютеры | - Зарядовый кубит
- Потоковый кубит
- Фазовый кубит
- Трансмон
|
|---|
|
|---|
