Квантовые вычисления со времен Демокрита - Скотт Ааронсон

описал это доказательство. Он сказал: если у нас есть квантовый совет, а мы хотим имитировать его при помощи классического совета посредством постселекции, мы используем «дарвинову обучающую последовательность» входных сигналов. Пусть у нас есть машина, способная принять классический совет, а мы хотим рассказать этой машине про некоторый набор квантовых советов при помощи только классических советов. Для этого мы рассматриваем некоторые тестовые входы X1, X2, …, XT. Заметьте, кстати, что наша машина с классическим советом не знает истинного состояния квантового совета |ψ〉. Машина с классическим советом начинает с предположения о том, что квантовый совет — это максимально смешанное состояние, поскольку без априорного знания любое квантовое состояние имеет равную вероятность оказаться состоянием совета. Далее, X1 — это входная строка к алгоритму, такая, что если максимально смешанное состояние используется вместо квантового совета, то алгоритм выдает неверный ответ с вероятностью выше одной трети. Если же алгоритм все же угадывает верный ответ, то проведенное измерение изменит состояние совета в некоторое новое состояние ρ1. Почему же этот процесс описывается как «дарвинов»? Следующая часть классического совета, X2, описывает некоторый входной сигнал к алгоритму, такой, что неверный ответ будет дан с вероятностью, большей одной трети, если использовать ρ1 вместо настоящего квантового совета. Если, несмотря на высокую вероятность получения неверного ответа, алгоритм, получив на вход X1 и X2, все же даст два верных ответа, то мы используем полученную в результате оценку состояния совета ρ2, чтобы получить следующую часть классического совета X3. По существу, мы пытаемся научить нашу машину для классического совета работе с квантовым советом, раз за разом повторяя: «Предположим, ты все предыдущие уроки усвоила успешно, вот тебе новый тест, который ты наверняка провалишь. Иди учись, дитя мое».

Суть в том, что если мы признаем |ψn〉 истинным квантовым советом, то, поскольку мы можем разложить максимально смешанное состояние в любом базисе, в каком захотим, мы можем считать его результатом смешения состояния истинного совета, которое мы пытаемся узнать, и кучи других вещей, ортогональных ему. Всякий раз, когда мы даем неверный ответ с вероятностью, большей одной трети, мы как бы отсекаем от этого пространства еще треть. После этого мы делаем постселекцию из того, что получилось. Мы знаем также, что если бы мы начали с истинного состояния совета, мы выдали бы верный ответ, так что этот процесс должен где-то завершиться; постепенно мы отсеем весь мусор, и примеры, на которых алгоритм ошибается, у нас закончатся.

Итак, в этой ситуации квантовые состояния работают не как экспоненциально длинные векторы. Они работают как если бы в них был закодирован лишь полиномиальный объем информации, хотя извлечение того, что вы хотите узнать, может оказаться экспоненциально более эффективным, чем если бы та же информация была представлена классически. Опять же мы получаем неоднозначные ответы, но мы этого и ожидали. Мы знали, что именно квантовые состояния населяют это странное срединное царство между распределениями вероятности и экспоненциально длинными строками. Тем не менее приятно точно знать, как играет интуитивное понимание в каждом из этих конкретных сценариев. Мне кажется, что именно это привлекает меня в квантовой теории сложности. В каком-то смысле это то самое, о чем спорили Бор и Гейзенберг, но мы сегодня можем задавать вопросы намного конкретнее — и иногда даже отвечать на них.

15. Скептики о квантовых вычислениях

В предыдущей главе мы говорили о том, следует ли рассматривать квантовые состояния как экспоненциально длинные векторы, и я ввел класс BQP/qpoly и кое-какие концепции, вроде квантового совета. На самом деле я бы сказал, что главная причина моего интереса так и не была названа; она связана с вопросом о том, следует ли нам в принципе считать квантовые вычисления фундаментально возможными или нет. Есть люди, такие как Леонид Левин и Одед Голдрейх, для которых очевидно, что квантовые вычисления просто должны оказаться невозможными[116]. Отчасти их аргументы сводятся к тому, что мир, в котором для описания состояния 200 частиц требуется больше битов, чем существует частиц во Вселенной, представляется очень уж экстравагантным. Для этих людей такая экстравагантность — четкое указание на то, что что-то здесь не так. Поэтому причина, по которой мне нравится исследовать мощность квантовых доказательств и квантового совета, отчасти состоит в том, что это помогает нам ответить на вопрос, действительно ли квантовое состояние кодирует экспоненциальное количество информации.

Итак, переходим к Одиннадцати возражениям против квантовых вычислений.

1. Работают на бумаге, но не на практике.

2. Нарушают расширенный тезис Чёрча — Тьюринга.

3. В них недостаточно «настоящей физики».

4. Малые амплитуды нефизичны.

5. Экспоненциально большие состояния нефизичны.

6. Квантовые компьютеры — это всего лишь форсированные аналоговые компьютеры.

7. Квантовые компьютеры не похожи ни на что виденное нами ранее.

8. Квантовая механика — всего лишь аппроксимация какой-то более глубокой теории.

9. Декогеренция всегда будет хуже, чем порог допустимой ошибки.

10. Классическим компьютерам не нужна толерантность к ошибкам.

11. Ошибки не являются независимыми.

Что я сделал? Записал все аргументы скептиков против возможности квантовых вычислений, какие только сумел вспомнить. Теперь я просто пройдусь по ним и откомментирую. Позвольте для начала сказать, что моя точка зрения всегда была довольно простой: вполне может быть, что квантовые вычисления окажутся невозможными по какой-то фундаментальной причине. Если вдруг обнаружится, что это действительно так, тут-то и начнется самое увлекательное. Вообще, это было бы намного интереснее, чем если квантовые вычисления возможны, — ведь такое открытие изменит наши представления о физике. Получить квантовый компьютер, способный раскладывать на простые множители 10 000-значные целые числа, — относительно скучный результат, полностью соответствующий уже имеющимся у нас теориям.

Я люблю спорить со скептиками по нескольким причинам. Во-первых, потому что я вообще люблю спорить. Во-вторых, я часто обнаруживаю, что лучший способ получить какие-то новые результаты — найти человека, который говорит что-то, что мне кажется ясно и откровенно неверным, и попробовать придумать для него контраргументы. Ошибочные утверждения — благодатный источник исследовательских идей.

Итак, как выглядят некоторые скептические аргументы, которые мне приходилось слышать? Чаще всего я слышу что-то вроде: «Ну хорошо, это работает формально, на бумаге, но это не будет работать в реальном мире». Нет, правда, люди действительно говорят такое и при этом считают свои слова серьезным аргументом. Для меня ошибочность этого заявления не в том, что у людей могут возникать идеи, не работающие в реальном мире, а в том, что эти идеи, не работая в реальном мире, способны «работать на бумаге». Разумеется, могут