в теории квантовых вычислений: Джайн с соавторами доказал, что QIP = PSPACE (см. главу 17); это означает, что квантовые интерактивные системы доказательства не мощнее классических. В этом случае я по крайней мере угадал правильный ответ!
(На самом деле был еще один прорыв в исследовании квантовых интерактивных систем доказательства, о котором я не буду рассказывать в этой книге. Недавно мой постдок Томас Видик вместе с Цуёси Ито[8] показал, что NEXP ⊆ MIP*; это означает, что любую интерактивную систему доказательства с многими доказателями можно «привить» против того, чтобы эти доказатели втайне скоординировали свои отклики посредством квантовой запутанности.)
В главе 20 этой книги обсуждается предложенная Дэвидом Дойчем модель квантовой механики в присутствии замкнутых времениподобных траекторий, а также мой и Джона Ватруса новый (на тот момент) вывод о том, что модель Дойча обеспечивает в точности вычислительную мощность PSPACE. (Отсюда, в частности, следует, что путешествующие во времени квантовые компьютеры оказались бы не более мощными, чем классические компьютеры того же назначения, если вас почему-то интересовал этот вопрос.) Однако после 2006 г. вышли новые важные статьи, в которых подвергаются сомнению предположения, положенные в основу модели Дойча, и предложены альтернативные модели, что, как правило, ведет к вычислительной мощности меньшей, чем PSPACE. К примеру, одна из моделей, предложенная Ллойдом с соавторами, «всего лишь» позволит путешественнику во времени решить все задачи класса PP! Об этих достижениях речь пойдет в главе 20.
А что с нижними оценками сложности схемы (для специалистов по теоретической информатике это, по существу, кодовое слово, обозначающее «попытку доказать P ≠ NP», точно так же как для физиков «замкнутые времени подобные траектории» – кодовое слово для обозначения путешествий во времени)? Рад сообщить, что и здесь после 2006 г. имеются интересные подвижки – безусловно, более серьезные, чем можно было тогда ожидать. В качестве примера скажу, что Рахул Сантханам при помощи интерактивных методик доказательства получил нерелятивизирующий результат, согласно которому класс PromiseMA не имеет схем какого бы то ни было фиксированного полиномиального размера (см. главу 17). Результат Сантханама, в частности, побудил меня и Ави Вигдерсона в 2007 г. сформулировать теорему о барьере алгебраизации (см. там же) – обобщение теоремы о барьере релятивизации Бейкера, Гилла и Соловея, сформулированной еще в 1970-е гг. (см. так же главу 17). Алгебраизация объясняет, почему методики интерактивного доказательства в попытке доказать P ≠ NP позволяют нам лишь дойти до определенного предела и не более того – к примеру, почему эти методики привели к сверхлинейной нижней оценке сложности схемы для класса PromiseMA, но не для класса NP, который всего лишь «чуть ниже его». Мы поставили задачу разработки новых методик поиска нижней оценки сложности схемы, которые позволяли бы убедительно обойти
T. Ito and T. Vidick, A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. In
