Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории сложности вычислений класс QIP (который расшифровывается как Quantum Interactive Polynomial time ) является аналогом квантовых вычислений классического класса сложности IP , который представляет собой набор задач, решаемых с помощью интерактивной системы доказательства с полиномиальным верификатором и одной вычислительной неограниченный испытатель. Неформально IP - это набор языковдля которых вычислительно неограниченный доказывающий может убедить проверяющего с полиномиальным временем принять, когда ввод находится на языке (с высокой вероятностью), и не может убедить проверяющего принять, когда ввод не на языке (опять же, с высокой вероятностью). Другими словами, доказывающий и проверяющий могут взаимодействовать в течение полиномиально большого количества раундов, и если ввод на языке, проверяющий должен принять с вероятностью более 2/3, а если ввод не на языке, проверяющий должен быть отклонен. с вероятностью больше 2/3. В IP верификатор похож на машину BPP . В QIP связь между проверяющим и проверяющим является квантовым, и проверяющий может выполнять квантовые вычисления. В этом случае верификатор похож на машину BQP .

Ограничивая количество сообщений, используемых в протоколе, не более k , мы получаем класс сложности QIP (k). QIP и QIP (к) были введены Джоном Watrous , [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 легко показать, что он находится в QIP, используя результат IP = PSPACE .

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Зоопарк сложности : QIP