Что делает квантовые вычисления такими сложными для объяснения?

Скотт Ааронсон

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

Вы, возможно, слышали, что квантовые компьютеры — это волшебные сверхмашины, которые скоро будут лечить рак и глобальное потепление, пытаясь найти все возможные ответы в разных параллельных вселенных. В течение 15 лет в своем блоге и в других местах я выступал против этого мультяшного видения, пытаясь объяснить то, что я вижу как более тонкую, но, по иронии судьбы, еще более захватывающую правду. Я отношусь к этому как к общественной службе и почти как к своему моральному долгу исследователя квантовых вычислений. Увы, работа кажется сизифовой: отвратительная шумиха вокруг квантовых компьютеров с годами только усилилась, поскольку корпорации и правительства вложили миллиарды, а технология продвинулась до программируемых 50-кубитных устройств, которые (при определенных выдуманных тестах) действительно могут дать самые большие в мире суперкомпьютеры. И так же, как в криптовалюте, машинном обучении и других модных областях, с деньгами пришли торгаши.

Хотя в моменты размышлений я это понимаю. Реальность такова, что даже если убрать все плохие стимулы и жадность, квантовые вычисления все равно будет трудно кратко и честно объяснить без математики. Как однажды сказал пионер квантовых вычислений Ричард Фейнман о работе в области квантовой электродинамики, которая принесла ему Нобелевскую премию, если бы ее можно было описать в нескольких предложениях, она не стоила бы Нобелевской премии.

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

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

Беда в том, что квантовые компьютеры не произведут революцию во всем.

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

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

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

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

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

На самом деле суперпозиция означает «сложную линейную комбинацию». Здесь мы подразумеваем «сложное» не в смысле «сложное», а в смысле действительного плюс мнимое число, а «линейная комбинация» означает, что мы складываем вместе различные кратные состояния. Таким образом, кубит — это бит, у которого есть комплексное число, называемое амплитудой, связанное с вероятностью того, что он равен 0, и другая амплитуда, связанная с возможностью того, что это 1. Эти амплитуды тесно связаны с вероятностями, в том смысле, что чем дальше амплитуда некоторого результата от нуля, тем больше шанс увидеть этот результат; точнее, вероятность равна квадрату расстояния.

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

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

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

Этот вопрос упускает из виду суть квантовых компьютеров, которая заключается в достижении лучшего «поведения при масштабировании» или времени работы как функции n, количества битов входных данных. Это может означать, что нужно взять задачу, в которой лучший классический алгоритм требует количества шагов, экспоненциально растущее с n, и решить ее, используя количество шагов, которое растет только как n2. В таких случаях при малых n решение задачи на квантовом компьютере будет фактически медленнее и дороже, чем ее решение классическим путем. Только по мере роста n квантовое ускорение сначала появляется, а затем становится доминирующим.

Но откуда нам знать, что не существует классического короткого пути — обычного алгоритма, который имел бы такое же поведение при масштабировании, как и квантовый алгоритм? Хотя этот вопрос обычно игнорируется в популярных источниках, этот вопрос занимает центральное место в исследованиях квантовых алгоритмов, где часто трудность заключается не столько в том, чтобы доказать, что квантовый компьютер может что-то делать быстро, сколько в том, чтобы убедительно доказать, что классический компьютер не может этого сделать. Увы, оказывается ошеломляюще трудно доказать, что проблемы сложны, как показано на знаменитой задаче P vs NP (которая, грубо говоря, спрашивает, можно ли быстро решить каждую проблему с быстро проверяемыми решениями). Это не просто академический вопрос, это вопрос расставления точек над i: за последние несколько десятилетий предполагаемые квантовые ускорения неоднократно исчезали, когда обнаруживались классические алгоритмы с аналогичной производительностью.

Заметьте, после объяснения всего этого я так и не сказал ни слова о практической сложности построения квантовых компьютеров. Одним словом, проблема заключается в декогеренции, что означает нежелательное взаимодействие между квантовым компьютером и его окружением — близлежащими электрическими полями, теплыми объектами и другими вещами, которые могут записывать информацию о кубитах. Это может привести к преждевременному «измерению» кубитов, которое сводит их к классическим битам, которые либо однозначно равны 0, либо определенно равны 1. Единственное известное решение этой проблемы — квантовая коррекция ошибок: схема, предложенная в середине 1990-х гг. который умело кодирует каждый кубит квантового вычисления в коллективное состояние десятков или даже тысяч физических кубитов. Но исследователи только сейчас начинают применять такое исправление ошибок в реальном мире, и на самом деле его использование займет гораздо больше времени. Когда вы читаете о последнем эксперименте с 50 или 60 физическими кубитами, важно понимать, что кубиты не исправлены. Пока это не так, мы не ожидаем, что сможем масштабироваться за пределы нескольких сотен кубитов.

Как только кто-то поймет эти концепции, я бы сказал, что они готовы начать читать — или, возможно, даже писать — статью о последнем заявленном прогрессе в области квантовых вычислений. Они будут знать, какие вопросы задавать в постоянной борьбе, чтобы отличить реальность от шумихи. Понять это действительно возможно — в конце концов, это не ракетостроение; это просто квантовые вычисления!

Источник: vk.com

Комментарии: