«Квантовые вычисления со времен Демокрита». Глава из книги

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

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

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

1. Работают на бумаге, но не на практике.
2. Нарушают расширенный тезис Чёрча — Тьюринга.
3. В них недостаточно «настоящей физики».
4. Малые амплитуды нефизичны.
5. Экспоненциально большие состояния нефизичны.
6. Квантовые компьютеры — это всего лишь форсированные аналоговые компьютеры.
7. Квантовые компьютеры не похожи ни на что виденное нами ранее.
8. Квантовая механика — всего лишь аппроксимация какой-то более глубокой теории.
9. Декогеренция всегда будет хуже, чем порог допустимой ошибки.
10. Классическим компьютерам не нужна толерантность к ошибкам.
11. Ошибки не являются независимыми.

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

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

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

Я с радостью обнаружил, что был не первым, кто указал на эту конкретную ошибку. Иммануил Кант написал целый трактат на эту тему под названием «О поговорке „Может, это и верно в теории, но не годится для практики“».

Второй аргумент состоит в том, что квантовые вычисления, должно быть, невозможны, потому что нарушают расширенный тезис Чёрча — Тьюринга: «Все, что эффективно вычислимо в физическом мире, вычислимо за полиномиальное время на стандартной машине Тьюринга». То есть мы знаем, что квантовые вычисления не могут оказаться возможными (считая, что BPP ≠ BQP), потому что мы знаем, что BPP определяет предел эффективной вычислимости.

Итак, у нас есть тезис и квантовые вычисления этот тезис нарушают, так что (если вы верите в этот тезис) они, следовательно, невозможны. С другой стороны, если заменить разложение на множители NP-полными задачами, то этот аргумент для меня лично станет более правдоподобным, потому что я бы сказал, что любой мир, в котором мы реально могли бы эффективно решать NP-полные задачи, не был бы слишком похож на наш мир. Для NP-промежуточных задач, таких как разложение на множители и изоморфизм графов, я не готов занять ту или иную априори теологическую позицию. Но диаграмма показывает, как, на мой взгляд, скорее всего обстоит дело.

Это был второй аргумент. Переходим к третьему: «Мне кажутся подозрительными все эти статьи о квантовых вычислениях, потому что в них недостаточно настоящей физики, которую я изучал в университете. Там слишком много унитарных матриц и недостает гамильтонианов. И еще всякая запутанность, но мой профессор запрещал мне даже думать о запутанности, потому что все это выглядит очень странно и попахивает философией, к тому же не имеет отношения к строению атома гелия». Что можно на это сказать? Конечно, это заявление четко показывает, что мы сегодня иначе думаем и говорим о квантовой механике, чем принято было в течение многих лет. Но те, кто выдвигает этот аргумент, утверждают также, что этот новый способ рассуждать о квантовой механике неверен. Это утверждение, разумеется, требует отдельного обсуждения. Не знаю, о чем тут еще говорить.

Четвертое возражение состоит в том, что «экспоненциально малые амплитуды откровенно нефизичны». Выдвинул этот аргумент Леонид Левин. Рассмотрим некоторое состояние 1000 кубитов, таких, что каждый их компонент имеет амплитуду 2⁻⁵⁰⁰. Нам неизвестен ни один физический закон, который выполнялся бы с большей точностью, чем до примерно дюжины десятичных знаков, а вы просите точности до сотен десятичных знаков? Как могло кому-то прийти в голову, что такое возможно в принципе?

Очевидный ответ на аргумент № 4 заключается в том, что я могу взять классическую монетку и бросить ее тысячу раз. Тогда вероятность любой конкретной последовательности составит 2⁻¹⁰⁰⁰, что намного меньше любой константы, которую мы могли бы измерить в природе. Означает ли это, что теория вероятностей — «всего лишь» аппроксимация какой-то другой, более глубокой теории или что она перестанет работать, если я кину монетку слишком много раз подряд?

Для меня ключевой момент здесь в том, что амплитуды развиваются линейно и в этом отношении схожи с вероятностями. Теперь у нас есть знак минус и интерференция, но очень может быть, что если бы мы взяли на себя труд как следует подумать о том, почему вероятности так хорошо работают, мы могли бы сказать, что дело не только в том, что мы всегда находимся в детерминистском состоянии и просто не знаем, что это такое; может быть, свойство линейности — это нечто более общее. Именно линейность не позволяет небольшим ошибкам вкрадываться в наши расчеты. Если у нас есть куча мелких ошибок, они скорее складываются, чем перемножаются. Это и есть линейность.

Аргумент 5 возвращает нас к тому, о чем говорилось в предыдущей главе: «Очевидно, что квантовые состояния — весьма экстравагантные объекты; невозможно просто взять 2ⁿ битов и упаковать их в n кубитов». Как-то в споре со мной Пол Дэвис выдвинул этот аргумент, апеллируя к голографическому принципу и говоря, что существует конечная верхняя оценка числа битов, которые можно втиснуть в конечную область пространства-времени. Если у вас есть квантовое состояние на 1000 кубитов, то требуется 2¹⁰⁰⁰ бит, и, по Дэвису, мы только что нарушили голографическую границу².

Как на это реагировать? Во-первых, эту информацию — вне зависимости от того, считаем ли мы, что она «там» имеется, — как правило, невозможно прочитать. Об этом говорят такие результаты, как теорема Холево. В определенном смысле вы, может быть, и сможете запихнуть в некоторое состояние 2ⁿ битов, но число битов, которые вы сможете уверенно считать оттуда, не превысит n.

Голографическая граница означает, неформально говоря, что максимальное число битов, которое можно упаковать в произвольную конечную область, пропорционально площади поверхности этой области с коэффициентом примерно один бит на планковскую площадь, или 1,4 × 10⁶⁹ битов на квадратный метр. Почему максимальное число битов растет как площадь поверхности, а не как объем? Это очень глубокий вопрос, который, вероятно, не дает спать спокойно таким людям, как Эд Виттен и Хуан Малдасена. Дурацкий ответ: если попытаться взять много-много битов и запихнуть их все в некоторый объем (к примеру, в кубический жесткий диск), то в какой-то момент этот кубический накопитель схлопнется и образует черную дыру. Плоский накопитель тоже схлопнется, а вот одномерный накопитель этого не сделает.

Вот в чем дело: все эти биты, кажется, скапливаются возле горизонта событий черной дыры. Почему возле горизонта событий? Потому что если вы стоите вне черной дыры, то вы никогда не увидите, как что-то падает внутрь сквозь горизонт событий. Вместо этого из-за замедления времени все падающие внутрь объекты будут, на взгляд внешнего наблюдателя, зависать непонятным образом над самым горизонтом событий, все время приближаясь к нему, как у Зенона, но никогда не достигая.

Затем, если вы хотите сохранить унитарность и не дать чистым состояниям превратиться в смешанные, когда что-то падает в черную дыру, вы говорите, что при испарении черной дыры через излучение Хокинга все эти биты отшелушиваются с ее поверхности, как чешуйки, и улетают в пространство. Опять же никто этого по-настоящему не понимает. Многие рассматривают (справедливо) голографическую границу как один из немногих намеков на квантовую теорию гравитации, но пока проработанной теории, где применялась бы эта граница, не существует; речь может идти разве что о нескольких специальных модельных системах.

Здесь есть еще один забавный момент: в классической общей теории относительности горизонт событий не играет особо важной роли. Сквозь него можно пролететь и даже не заметить этого. Конечно, со временем ты поймешь, что миновал горизонт событий, поскольку тебя затянет в сингулярность, но в момент прохода сквозь него ты ничего особенного не ощутишь. С другой стороны, с информационной точки зрения можно сказать, что при проходе сквозь горизонт событий ты минуешь множество битов, сосредоточенных возле него. Что же выделяет горизонт событий и ставит его в особое положение с точки зрения хранения информации? Это очень странно и мне бы хотелось понять, в чем тут дело (дальнейшее обсуждение этого вопроса см. в главе 22).

Здесь на самом деле есть интересный вопрос. Голографический принцип гласит, что вы можете заложить на хранение в пределах какой-то области пространства лишь ограниченное количество информации, но что значит заложить эту информацию на хранение? Обязательно ли иметь произвольный доступ к этой информации? Обязательно ли иметь возможность вытащить их хранилища произвольный бит по желанию и при этом получить ответ за разумное время? Если же эти биты хранятся в черной дыре и на поверхности имеется n бит, то, очевидно, потребуется порядка n^3/2 времени, чтобы эти биты испарились в виде излучения Хокинга. Так что время извлечения информации по порядку величины полиномиально по числу битов, но этот процесс не особенно эффективен. Не следует сразу же выбирать черную дыру как материал для жесткого диска.

Аргумент 6: «Квантовый компьютер был бы просто форсированной версией аналогового компьютера». Это мне приходится слышать снова и снова от таких людей, как нобелевский лауреат Роберт Лафлин, изложивший этот довод в своей популярной книге «Другая Вселенная»³. Эта точка зрения популярна среди физиков. Мы знаем, что аналоговые компьютеры не так уж надежны и могут буквально свихнуться от мелких ошибок. На следующем шаге задается вопрос, почему квантовый компьютер должен быть каким-то иным, если он оперирует амплитудами — постоянно меняющимися величинами.

Но ответ на этот аргумент известен примерно с 1996 г. и называется теоремой о пороговом значении⁴. Если опустить формальности, то теорема о пороге гласит, что если можно сделать вероятность ошибки на кубит на шаг по времени достаточно малой — меньше некоторой константы, которую традиционно оценивали в 10⁻⁶, но которая может быть и намного больше, до 0,1 или 0,2, — то можно добиться так называемой квантовой устойчивости к ошибкам, которая не дает им накапливаться и портить расчет. Аналогичную теорему об устойчивости к ошибкам для классических вычислений доказал Джон фон Нейман в 1950-е гг., однако в конце концов она оказалась практически не востребованной: вошедшие в обиход транзисторы были настолько надежны, что людям почти никогда не приходилось беспокоиться об отказах. В середине 1990-х гг. некоторые физики предположили, что «аналоговая» природа квантовых компьютеров исключает квантовую устойчивость к ошибкам. Если говорить подробнее, интуиция подсказывала, что поскольку измерение в квантовой механике — деструктивный процесс, то сам факт измерения с целью обнаружения ошибки или копирования квантовой информации ради ее защиты от будущих ошибок привел бы к разрушению той самой информации, о защите которой шла речь. Но интуиция здесь, как оказалось, ошиблась: существуют хитроумные методы измерения только «синдрома ошибки», при которых вы узнаёте, произошла ли ошибка и как можно ее исправить, но не измеряете и, соответственно, не разрушаете «законную» квантовую информацию. Возможность таких измерений, по существу, обеспечивается линейностью квантовой механики — оружием, насмерть поразившим множество неверных интуитивных представлений о том, как работает квантовая механика!

Существует ли похожая теорема о пороговом значении для аналоговых компьютеров? Нет, ее просто не может быть. Суть в том, что есть одно критически важное свойство, общее для дискретных, вероятностных и квантовых теорий, но не имеющее отношения к аналоговым или непрерывным теориям. Это свойство — нечувствительность к малым ошибкам. Это опять же следствие линейности.

Обратите внимание: если бы нам нужна была более слабая теорема о пороговом значении, мы могли бы рассмотреть некое вычисление, занимающее t шагов по времени, в котором количество ошибок на один шаг составляло бы 1/t. Тогда теорема о пороговом значении доказывалась бы тривиально. Если бы у нас было произведение унитарных матриц U₁U₁ ... U₁₀₀ и каждая из них искажалась бы на величину 1/t (1/100 в данном случае), то мы бы получили примерно такое произведение:

Произведение всех этих ошибок все же будет невелико, опять благодаря линейности. Бернштейн и Вазирани⁵ отметили, что квантовые вычисления в каком-то смысле естественно устойчивы к обратно-полиномиальным ошибкам. «В принципе» это уже можно рассматривать как ответ на вопрос; остается «всего лишь» показать, как проявлять терпимость к более крупным и более реалистичным количествам ошибок, а не только к обратно-полиномиальным.

Переходим к аргументу 7. Его выдвигает, к примеру, Михаил Дьяконов⁶. Аргумент состоит в том, что все системы, с какими нам приходилось сталкиваться, испытывают очень быструю декогеренцию, поэтому не слишком реально ожидать, что мы могли бы «просто» соорудить некую систему, не похожую ни на одну из природных систем, с которыми нам случалось иметь дело.

Да, но ядерный реактор тоже во многих отношениях не похож ни на одну из природных систем. А космический аппарат? В природе никто и ничто не пользуется реактивной силой, чтобы убежать от Земли. Мы ничего такого никогда не видели. Или, наконец, классический компьютер.

Далее, есть люди, убежденные в том, что квантовая механика — приближенная теория, работающая лишь для небольшого числа частиц. При переходе к значительному числу частиц на сцене должно появиться что-то другое. Проблема в том, что проводились эксперименты, в которых квантовая механика испытывалась на довольно большом числе частиц; в качестве примера можно назвать эксперимент группы Цайлингера с фуллеренами. Были также эксперименты SQUID со сверхпроводящим квантовым интерферометром, в которых было подготовлено «состояние кота Шрёдингера» \( \left | 0...0 \right \rangle + \left | 1...1 \right \rangle \) на n кубитах, где в зависимости от того, что вам угодно считать степенью свободы, n может доходить до нескольких миллиардов.

Хотя опять же главное здесь то, что открытие нарушения квантовой механики стало бы самым интересным из всех возможных результатом попыток создания квантового компьютера. И как еще можно это обнаружить, кроме как путем экспериментальных исследований? Поразительно, но я встречаю людей (в первую очередь компьютерщиков), спрашивающих у меня: «Как, вы ожидаете получить Нобелевскую премию, если ваш квантовый компьютер не заработает?» Для них так очевидно, что квантовый компьютер работать не будет, что это даже неинтересно.

Кто-то скажет: «Нет-нет, я хочу высказать отдельное возражение. Я не считаю, что квантовая механика где-то перестанет работать, но даже если этого не произойдет, квантовые вычисления могут все же оказаться фундаментально невозможными, просто потому, что в мире слишком много декогеренции». Эти люди утверждают, что декогеренция — фундаментальная проблема. То есть что ошибка всегда будет выше, чем порог устойчивости, или что какая-то нехорошая маленькая частица непременно пролетит и декогерирует ваш квантовый компьютер.

Следующий аргумент немного тоньше: для классического компьютера нам не приходится прикладывать подобные усилия. Устойчивость к ошибке в нем получается естественным образом. У вас есть некоторое напряжение, которое либо ниже нижнего порога, либо выше верхнего, и это дает нам два легко различимых состояния, которые мы можем обозначить как 0 и 1. Нам не приходится много работать, чтобы обеспечить устойчивость к ошибке. В современных микропроцессорах, к примеру, никто даже не старается ввести существенную избыточность и обеспечить особую устойчивость к ошибке, поскольку компоненты настолько надежны, что в подобных предосторожностях нет нужды. Далее говорится, что вы можете в принципе производить универсальные квантовые вычисления при помощи специальных устройств, обеспечивающих устойчивость к ошибке, но что сама необходимость таких устройств должна вызывать тревогу: почему необходима сложная система коррекции ошибок? Разве это не должно вызывать подозрения?

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

Мы уже видим намеки на то, как все может в конце концов обернуться. Есть, к примеру, такие темы, как неабелевы энионы, где квантовые вычисления становятся «естественно устойчивыми к ошибкам», поскольку единственные процессы, способные породить ошибки, должны обходить квантовый компьютер с нетривиальной топологией. Эти предложения показывают, что когда-нибудь мы, возможно, научимся создавать квантовые компьютеры с такой же «естественной» коррекцией ошибок, какую мы имеем сегодня в классических компьютерах.

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

Мой любимый ответ на этот аргумент принадлежит Дэниелу Готтесману, высказавшему его в споре с Левиным; тот убежден, что ошибки непременно вступят в какой-то заговор за пределами воображения. Готтесман сказал: если предположить, что ошибки коррелируют таким дьявольским способом, а Природа готова прилагать так много усилий, чтобы уничтожить квантовые вычисления, то почему вы не можете вывернуть ситуацию наизнанку и использовать дьявольские ухищрения Природы для получения еще большей вычислительной мощности? Может быть, вам удалось бы даже решить NP-полные задачи. Создается впечатление, что Природе пришлось бы тратить громадные усилия только ради того, чтобы нужным образом скоррелировать кубиты и убить тем самым квантовые вычисления.

Иными словами, ваши ошибки должны будут коррелировать не просто каким-то дьявольским способом, а непредсказуемым дьявольским способом. В противном случае с проблемой можно было бы разобраться в общем и целом.

Подведем итог. Я уверен, что споры со скептиками не только забавны, но и чрезвычайно полезны. Квантовые вычисления вполне могут оказаться невозможными по какой-то фундаментальной причине. Но я до сих пор жду от скептиков аргумент, который на самом деле нетривиально задел бы мое воображение. Есть возражения на то и на это, но нет полностью проработанной альтернативной картины мира, в которой квантовые вычисления не были бы возможны. Вот чего мне не хватает, чего я всегда ищу и пока не нахожу⁷.

Я завершу этот разговор вопросом, который вам следует обдумать до начала следующей главы. Если мы видим 500 воронов, и все они черные, следует ли нам ожидать, что и 501-й ворон тоже окажется черным? Если да, почему? Почему созерцание пятисот черных воронов дает нам хоть какие-то основания для такого вывода?

¹ См., например, «Polynomial Time and Extravagant Models» и «On Quantum Computing».

² Впоследствии Дэвис опубликовал этот довод; см. «The Implications of a Cosmological Information Bound for Complexity, Quantum Information and the Nature of Physical Law».

³ Англоязычное издание выпущено Basic Books в 2006 г.

⁴ Мягкое введение в теорему о пороговом значении можно найти, например, в работе Джона Прескилла «Reliable Quantum Computers» или Дорит Ааронов «Quantum Computation».

⁵ «Quantum complexity theory».

⁶ См. «Is Fault-Tolerant Quantum Computation Really Possible?» или более свежую «State of the art and prospects for quantum computing».

⁷ См. в блоге Скотта Ааронсона недавнюю дискуссию о скептицизме в отношении квантовых вычислений.