QIP (сложность)
-
Определение и аналогия с классическим IP
- QIP — это квантовый аналог IP, который решает задачи с помощью квантовых вычислений и полиномиального времени.
- IP — это набор языков, где верификатор может убедить верификатора в правильности ввода с высокой вероятностью.
-
Взаимодействие между проверяющим и верификатором
- В IP верификатор похож на машину BPP, а в QIP связь между ними квантовая.
- В QIP верификатор может выполнять квантовые вычисления, что делает его похожим на машину BQP.
-
Классы сложности QIP и QIP(k)
- QIP(k) — это класс сложности, ограничивающий количество сообщений в протоколе до k.
- Джон Уотроус и Китай доказали, что QIP = QIP(3), что означает, что достаточно трех сообщений для моделирования полиномиального квантового протокола.
-
Содержательность QIP в других классах сложности
- QIP(2) содержится в PSPACE, а QIP в EXP, что доказывает их принадлежность к разным классам сложности.
- QIP = IP = PSPACE, так как PSPACE содержится в QIP.
-
Рекомендации и внешние ссылки
- Статья содержит ссылки на «Зоопарк сложностей: QIP» для дополнительной информации.