$100000 или «Каковой будет цена открытия?»

Один из моих коллег, криптоаналитик, постоянно задает мне один и тот же вопрос: «Когда, по-вашему, будет сделан квантовый компьютер — завтра, через 10 лет, или никогда?» Я обычно оптимистично и радостно рассказываю о самых последних достижениях в этой области — вот, соединили два кубита, и это прорыв, вот, соединили кубит с резонатором-памятью, и это означает, что успех близок и т.п. Однако, недавно вспыхнувшая на просторах Интернета (в блоге Потерянное письмо Геделя, Gödel’s Lost Letter) дискуссия о возможности создания квантового компьютера заставила меня отнестись к вопросу коллеги по-другому.

Но сначала о последних событиях. В начале февраля этого года исследователь из MIT Скот Ааронсон (Scott Aaronson) в своем блоге предложил приз в $100 тыс. тому, кто докажет, исходя из законов Природы, принципиальную невозможность создания масштабируемого квантового компьютера. Скот Ааронсон вовсе не миллионер, а простой физик, преподаватель вуза, и $100 тыс. для него — немалая сумма. Мотивом столь неординарного поступка явилось непреодолимое желание, живущее в каждом настоящем исследователе, увидеть фундаментальные ограничения, устанавливаемые Природой, в данном случае, на скорость обработки информации. Побудительной силой для заявления Ааронсона стала упомянутая выше дискуссия между пессимистом Жилем Калайи (Gil Kalai) и оптимистом Арамом Херроу (Aram Harrow) в области квантовых методов обработки информации.

Gil Kalai

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

Быстродействие квантового компьютера опирается на законы квантовой физики и первоначальную идею (Р. Фейнман, 1983 г.), легшую в основу квантовой информатики, можно сформулировать так: Квантовый мир настолько сложен, что мы не можем описать его с помощью классических машин. Так давайте используем то, что обуславливает эту сложность, для ускорения и увеличения эффективности обработки информации.

Aram Harrow

На проблему квантового компьютера можно посмотреть и с другой, несколько философской точки зрения. В Природе, в её процессах заложена определенная сложность (Природа искусна и хитроумна). В попытке описать Природу и предсказать ее шаги (в чем, собственно, и заключается цель любых вычислений, любой обработки информации) мы создаем вычислительные машины, способность которых решать все более и более сложные задачи увеличивается. Есть ли какой-то предел у этого процесса? Ситуация очень похожа на ситуацию, сложившуюся в конце XVIII — начале XIX века в термодинамике. Люди пытались создать машины, которые бы производили как можно больше полезной работы, потребляя как можно меньше тепла (т.е. горючего) и обнаружили некий предел, устанавливаемый вторым началом термодинамики — КПД тепловой машины не просто должен быть меньше 1, а всегда есть «бесполезная» теплота (которую физики связывают с энтропией), которую принципиально невозможно превратить в полезную работу (в замкнутом процессе, т.е., при работе теплового двигателя). Гипотетическую машину, которая превращает «бесполезную» теплоту в работу назвали «вечным двигателем» 2-го рода и приняли как закон Природы, что такой двигатель невозможен.

Компьютер, который превращает сложную для человека задачу в простую, тоже является своего рода информационным двигателем. Так же, как и тепловая машина, компьютер может иметь свой, информационный, КПД, связанный со степенью понижения сложности задачи и степенью сложности самого компьютера. Существуют ли фундаментальные ограничения на информационный КПД компьютеров? Ответ на этот вопрос мог бы стать первым постулатом квантовой информатики. Собственно этого ответа и ждет Скот Ааронсон.

Чтобы разобраться в смысле спора между двумя ведущими специалистами в области математических методов обработки квантовой информации, начнем с истории квантовой информатики. В 1983 году Ричард Фейнман высказал идею о принципиальной возможности описания (на языке математики) процессов любой сложности, встречающихся в Природе путем использования для вычислений (обработки информации) процессов такой же сложности, какими, например, являются процессы, происходящие в квантовом мире. После этого долгое время усилия исследователей в области квантовой информатики разделились, грубо говоря, на два направления. С одной стороны, активно создавались физические устройства (кубиты), способные удерживать и обрабатывать квантовую информацию, но при этом все эксперименты, в конечном счете, сводились к испытанию небольшого количества кубитов (до 10), ставя перед собой цель «продемонстрировать принципиальную возможность», а не создать реальный компьютер. С другой стороны, не бездельничали и прикладные математики, которые разрабатывали квантовые алгоритмы, позволяющие существенно уменьшить количество выполняемых операций (именно это количество в зависимости от длины входного числа и определяет сложность алгоритма) для решения задач, практически «нерешаемых» классическими (неквантовыми) методами. Однако, все предложенные алгоритмы предполагали существование «сферического коня в вакууме», иными словами, идеальных кубитов и идеально выполняемых над ними логических операций.

В конце 90-х прошлого столетия стало ясно, что успех квантовой информатики зависит от «несферичности коня» и наличия «атмосферы», т.е., от возможности реализовать квантовые алгоритмы в реальных условиях, при наличии шумов. Шум мешает любым вычислениям, и квантовым, и классическим, поскольку вносит ошибку во все элементы вычислительного процесса (начальные данные, логические операции, считывание данных и т.д.). Ошибки, возникающие при классических вычислениях, научились исправлять еще во времена Шеннона. С квантовыми системами все гораздо сложнее — они более чувствительны к внешним шумам, и классические методы коррекции ошибок для них неприменимы в силу фундаментальных свойств Природы (измерение-считывание разрушает состояние квантового бита). Скептики полагали, что вся эффективность идеальных квантовых алгоритмов будет сведена на «нет» при попытке извлечь информацию из квантовой системы.

Однако, в 1997 г. Питер Шор (Peter Shor — автор наиболее известного квантового алгоритма), Джон Прескилл (John Preskill) и ряд других исследователей разработали такие методы коррекции ошибок в квантовых системах, которые не приводят к существенному удлинению самого алгоритма (точнее, требуют выполнения полиномиального количества операций коррекции). Кроме того, были предложены схемы кодирования квантовой информации, позволяющие производить устойчивые к ошибкам вычисления. После этого все немного успокоились, скептики приутихли, а оптимисты начали с еще большим усердием создавать новые физические реализации кубитов, новые (нецифровые) концепции квантовых вычислений и пытаться построить квантовое вычислительное устройство, содержащее более двух кубитов. Тем не менее, за более чем 10 лет текущего столетия преодолеть т.н. «квантовую пропасть» (т.е. удержать в состоянии суперпозиции более 10 кубитов) так и не удалось (канадская компания D-Wave утверждает, что ей удалось создать квантовый компьютер с количеством кубитов порядка 1000, однако опубликованные в открытой печати результаты исследований сотрудников этой компании не позволяют безоговорочно поверить в это утверждение). Скептики и пессимисты опять оживились и поставили вопрос ребром — а может, квантовый компьютер и вовсе невозможен? Возможно, что Природа никогда не позволит нам познать ее (читай: описать математически) до конца? Основания у них были — и Шор, и Прескилл, и их коллеги при создании помехоустойчивых квантовых кодов и алгоритмов опирались на некоторую, определенную модель шума. А именно, предполагалось, что шум (т.е. неконтролируемое вмешательство окружающей среды) влияет на состояние каждого кубита в отдельности, независимо от других кубитов. А что, если есть и другой шум, например такой, который затрагивает состояния нескольких кубитов одновременно? Сможем ли мы эффективно (за разумное время) исправлять ошибки в такой ситуации? И существует ли какой-то баланс между скоростью образования ошибок в квантовых системах и скоростью их коррекции? И, самое главное, возможно ли ограничить рост ошибок при увеличении количества кубитов?

Скептик Жиль Калайи считает, что увеличение числа кубитов приведет к катастрофическому росту ошибок, исправление которых займет столько же времени, как и решение задачи на классическом компьютере. Его главный аргумент — возможность порождения шумом «неправильных» квантовых корреляций, которые в большой системе будут распространяться по принципу домино и охватывать все кубиты. Иными словами, то, что делает квантовый компьютер столь мощным и привлекательным вычислительным средством, а именно, квантовые корреляции, приводит к столь же мощному и быстрому увеличению и распространению шума.

Оптимист Арам Харроу, который, как мне кажется, в большей мере является физиком, нежели Ж. Калайи, полагает, вслед за Эйнштейном, что Природа хитроумна, но не злокозненна («God is subtle but not malicious»). Харроу считает, что в тех конкретных системах, которые на сегодняшний день удалось создать, коррелированные шумы либо маловероятны, либо могут быть учтены и устранены как систематическая ошибка. Учитывая линейность уравнений квантовой механики, Харроу не видит причины катастрофического распространения шума (при условии регулярного применения процедуры коррекции ошибок).

Спор ещё не окончен — в дискуссию активно включаются другие ученые. Веские аргументы сторон пока ещё недостаточны для раскрытия тайн Природы, но спорщики не теряют надежды на победу в споре, подыскивая новые доводы.