КИП (сложность)
В теории сложности вычислений класс QIP (который обозначает квантовое интерактивное полиномиальное время ) является квантовым вычислительным аналогом классического класса сложности IP , который представляет собой набор задач, решаемых интерактивной системой доказательства с верификатором с полиномиальным временем и одним вычислительным устройством. неограниченное доказательство. Неформально, IP - это набор языков , для которых неограниченный в вычислительном отношении проверяющий может убедить проверяющего с полиномиальным временем принять, когда входные данные находятся на языке (с высокой вероятностью), и не может убедить проверяющего принять, когда входные данные не на этом языке. (опять же с большой вероятностью). Другими словами, доказывающий и верификатор могут взаимодействовать в течение полиномиального числа раундов, и если входные данные представлены на языке, верификатор должен принять с вероятностью, большей 2/3, а если входные данные не на данном языке, верификатор должен быть отклонен. с вероятностью больше 2/3. В IP верификатор подобен машине BPP . В QIP связь между доказывающим и проверяющим является квантовой, и проверяющий может выполнять квантовые вычисления. В этом случае верификатор подобен БКП Машина .
Ограничив количество сообщений, используемых в протоколе, не более k , мы получим класс сложности QIP(k). QIP и QIP(k) были представлены Джоном Уотрусом , [1] который вместе с Китаевым в более поздней работе доказал [2] что QIP = QIP(3), что показывает, что 3 сообщений достаточно для моделирования квантового интерактивного протокола с полиномиальным раундом. Поскольку QIP(3) уже является QIP, остается 4 возможных разных класса: QIP(0), который является BQP , QIP(1), который является QMA , QIP(2) и QIP.
Китаев и Уотрус также показали, что QIP содержится в EXP , классе задач, решаемых детерминированной машиной Тьюринга за экспоненциальное время. [2] Затем было показано, что QIP(2) содержится в PSPACE — наборе задач, решаемых детерминированной машиной Тьюринга в полиномиальном пространстве. [3] Оба результата были включены в результат 2009 года, согласно которому QIP содержится в PSPACE. [4] что также доказывает, что QIP = IP = PSPACE, поскольку PSPACE легко показать, что PSPACE находится в QIP, используя результат IP = PSPACE .
Ссылки [ править ]
- ^ Уотрус, Джон (2003), «PSPACE имеет квантовые интерактивные системы доказательств с постоянным циклом», Theor. Вычислить. наук. , 292 (3), Эссекс, Великобритания: Elsevier Science Publishers Ltd.: 575–588, номер номера : 10.1016/S0304-3975(01)00375-9 , ISSN 0304-3975.
- ↑ Перейти обратно: Перейти обратно: а б Китаев, Алексей; Уотроус, Джон (2000), «Распараллеливание, усиление и экспоненциальное моделирование во времени квантовых интерактивных систем доказательства», STOC '00: Материалы тридцать второго ежегодного симпозиума ACM по теории вычислений , ACM, стр. 608–617, ISBN 978-1-58113-184-0
- ^ Джайн, Рахул; Упадхьяй, Сарвагья; Уотрус, Джон (2009), «Квантовые интерактивные доказательства с двумя сообщениями в PSPACE», FOCS '09: Материалы 50-го ежегодного симпозиума IEEE по основам компьютерных наук 2009 г. , Компьютерное общество IEEE, стр. 534–543, ISBN 978-0-7695-3850-1
- ^ Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотроус, Джон (2010), «QIP = PSPACE», STOC '10: Материалы 42-го симпозиума ACM по теории вычислений , ACM, стр. 573–582, ISBN 978-1-4503-0050-6
