Точное квантовое полиномиальное время
 | Эта статья может содержать неправомерные ссылки на пользовательский контент . ( февраль 2023 г. ) |
В сложности вычислений теории точное квантовое полиномиальное время ( EQP или иногда QP ) — это класс задач принятия решений , которые могут быть решены квантовым компьютером с нулевой вероятностью ошибки и с гарантированным полиномиальным временем в худшем случае. квантовый аналог класса сложности P. Это В этом отличие от квантовых вычислений с ограниченной ошибкой , где квантовые алгоритмы ожидается, что будут работать за полиномиальное время, но не всегда могут это делать.
В исходном определении EQP каждый язык вычислялся с помощью одной квантовой машины Тьюринга (QTM) с использованием конечного набора вентилей, амплитуды которого могли быть вычислены за полиномиальное время. Однако некоторые результаты потребовали использования бесконечного набора вентилей. Амплитуды в наборе вентилей обычно представляют собой алгебраические числа.
