Чтобы понять, на что способны квантовые компьютеры, а на что — нет, избегайте слишком простых объяснений. Комментарий Сохранить статью Прочитать позже
Нажимая кнопку просмотра этого видео, вы соглашаетесь с нашей политикой конфиденциальности.Видео : Квантовые компьютеры — это не новое поколение суперкомпьютеров, а нечто совершенно иное. Прежде чем мы начнём говорить об их потенциальных применениях, нам необходимо понять фундаментальные физические принципы, лежащие в основе теории квантовых вычислений.
Введение
Квантовые компьютеры, как вы, возможно, слышали, — это волшебные сверхмашины, которые скоро вылечат рак и глобальное потепление, перепробовав все возможные ответы в разных параллельных вселенных. В течение 15 лет в своем блоге и в других местах я выступал против этого карикатурного видения, пытаясь объяснить то, что я считаю более тонкой, но, по иронии судьбы, еще более захватывающей правдой. Я подхожу к этому как к общественному служению и почти как к своему моральному долгу исследователя квантовых вычислений. Увы, работа кажется сизифовым трудом: отвратительная шумиха вокруг квантовых компьютеров только усилилась с годами, поскольку корпорации и правительства инвестировали миллиарды, и по мере того, как технология развивалась до программируемых 50-кубитных устройств, которые (на некоторых надуманных тестах) действительно могут составить конкуренцию крупнейшим в мире суперкомпьютерам. И, как и в криптовалюте, машинном обучении и других модных областях, с деньгами пришли и спекулянты.
Но в моменты раздумий я это понимаю. Реальность такова, что даже если убрать все дурные мотивы и жадность, квантовые вычисления всё равно было бы сложно объяснить кратко и честно без математики. Как сказал однажды пионер квантовых вычислений Ричард Фейнман о работе по квантовой электродинамике, которая принесла ему Нобелевскую премию, если бы её можно было описать в нескольких предложениях, она не стоила бы и Нобелевской премии.
Но это не останавливало людей от попыток. С тех пор, как в 1994 году Питер Шор обнаружил, что квантовый компьютер может взломать большую часть шифрования, защищающего транзакции в интернете, интерес к этой технологии был обусловлен не только интеллектуальным любопытством. Действительно, разработки в этой области обычно освещаются скорее в рамках бизнес- или технологических, чем научных публикаций.
Было бы прекрасно, если бы журналист, пишущий о бизнесе или технологиях, мог честно сказать читателям: «Послушайте, под капотом скрывается вся эта глубокая квантовая механика, но вам нужно понять лишь одно: физики находятся на пороге создания более быстрых компьютеров, которые произведут революцию во всем».
Проблема в том, что квантовые компьютеры не произведут революцию во всем.
Да, когда-нибудь они смогут решить несколько конкретных задач за считанные минуты, что (мы думаем) заняло бы больше времени, чем возраст Вселенной на классических компьютерах. Но есть и множество других важных задач, в решении которых, по мнению большинства экспертов, квантовые компьютеры помогут лишь в незначительной степени, если вообще помогут. Кроме того, хотя Google и другие компании недавно сделали убедительные заявления о достижении квантового ускорения, это было сделано лишь для конкретных, эзотерических тестов (в разработке которых я принимал участие). Квантовый компьютер, достаточно большой и надёжный, чтобы превзойти классические компьютеры в практических приложениях, таких как взлом криптографических кодов и моделирование химических процессов, вероятно, ещё очень далек от реальности.
Но как программируемый компьютер может быть быстрее только для некоторых задач? Знаем ли мы, для каких именно? И что вообще означает «большой и надёжный» квантовый компьютер в данном контексте? Чтобы ответить на эти вопросы, нам придётся разобраться в сути.
Начнём с квантовой механики. (Что может быть глубже?) Понятие суперпозиции, как известно, трудно передать обычными словами. Поэтому неудивительно, что многие авторы выбирают лёгкий путь: они утверждают, что суперпозиция означает «оба сразу», то есть квантовый бит, или кубит, — это просто бит, который может быть «и 0, и 1 одновременно», в то время как классический бит может быть только одним из этих значений. Далее они говорят, что квантовый компьютер достигнет своей скорости, используя кубиты для перебора всех возможных решений в суперпозиции, то есть одновременно или параллельно.
Именно это я считаю фундаментальной ошибкой популяризации квантовых вычислений, которая ведёт ко всем остальным. Отсюда всего один шаг до квантовых компьютеров, способных быстро решить, например, задачу коммивояжёра, перебирая все возможные варианты сразу — то, что, по мнению большинства экспертов, им не под силу.
Дело в том, что для того, чтобы компьютер был полезен, в какой-то момент нужно посмотреть на него и прочитать вывод. Но если вы посмотрите на равную суперпозицию всех возможных ответов, правила квантовой механики гласят, что вы увидите и прочтете лишь случайный ответ. И если бы вам это было нужно, вы могли бы выбрать его сами.
На самом деле суперпозиция означает «комплексную линейную комбинацию». Здесь мы подразумеваем «комплексный» не в смысле «сложный», а в смысле действительного и мнимого числа, в то время как «линейная комбинация» означает, что мы складываем различные кратные состояния. Таким образом, кубит — это бит, имеющий комплексное число, называемое амплитудой, связанное с возможностью того, что он равен 0, и другую амплитуду, связанную с возможностью того, что он равен 1. Эти амплитуды тесно связаны с вероятностями, поскольку чем дальше амплитуда некоторого результата от нуля, тем больше вероятность увидеть этот результат; точнее, вероятность равна квадрату расстояния.
Но амплитуды не являются вероятностями. Они подчиняются разным правилам. Например, если некоторые вклады в амплитуду положительны, а другие отрицательны, то вклады могут интерферировать деструктивно и компенсировать друг друга, так что амплитуда будет равна нулю, а соответствующий результат никогда не будет наблюдаться; аналогично, они могут интерферировать конструктивно и увеличивать вероятность заданного результата. Цель разработки алгоритма для квантового компьютера — организовать схему конструктивной и деструктивной интерференции таким образом, чтобы для каждого неверного ответа вклады в его амплитуду компенсировали друг друга, тогда как для правильного ответа вклады усиливали друг друга. Если, и только если, вы сможете это организовать, вы увидите правильный ответ с большой вероятностью, когда посмотрите. Сложность в том, чтобы сделать это, не зная ответа заранее, и быстрее, чем вы могли бы сделать это с классическим компьютером.
Двадцать семь лет назад Шор показал, как это сделать для задачи факторизации целых чисел, которая позволяет взломать широко используемые криптографические коды, лежащие в основе значительной части онлайн-торговли. Теперь мы знаем, как это сделать и для некоторых других задач, но только используя специальные математические структуры, используемые в этих задачах. Дело не только в том, чтобы перебрать все возможные ответы сразу.
Проблема усугубляется тем, что, если вы хотите честно говорить о квантовых вычислениях, вам также необходим понятийный словарь теоретической информатики. Меня часто спрашивают, во сколько раз квантовый компьютер будет быстрее современных. В миллион раз? В миллиард?
Этот вопрос не учитывает суть квантовых компьютеров, заключающуюся в достижении лучшего «масштабируемого поведения», то есть времени выполнения как функции от n, количества бит входных данных. Это может означать, что нужно взять задачу, для которой наилучший классический алгоритм требует количества шагов, растущие экспоненциально с n, и решить её, используя количество шагов, растущие лишь как n². В таких случаях при малых n решение задачи на квантовом компьютере будет фактически медленнее и дороже, чем решение её классическим способом. Квантовое ускорение впервые проявляется только с ростом n, а затем в конечном итоге становится доминирующим.
Но как мы можем знать, что не существует классического сокращения — обычного алгоритма, который имел бы поведение масштабирования, похожее на поведение квантового алгоритма? Хотя этот вопрос обычно игнорируется в популярных работах, он является центральным для исследований квантовых алгоритмов, где часто сложность заключается не столько в доказательстве того, что квантовый компьютер может делать что-то быстро, сколько в убедительном аргументе против классического компьютера. Увы, оказывается поразительно сложно доказать, что проблемы сложны, как показано на знаменитой задаче P против NP (которая, грубо говоря, спрашивает, может ли каждая задача с быстро проверяемыми решениями быть также быстро решена). Это не просто академический вопрос, вопрос расстановки точек над i: за последние несколько десятилетий предполагаемые квантовые ускорения неоднократно исчезали, когда находили классические алгоритмы с аналогичной производительностью.
Обратите внимание, что, объяснив всё это, я так и не сказал ни слова о практических сложностях создания квантовых компьютеров. Проблема, если коротко, заключается в декогеренции, то есть нежелательном взаимодействии квантового компьютера с окружающей средой — ближайшими электрическими полями, тёплыми объектами и другими вещами, способными записывать информацию о кубитах. Это может привести к преждевременному «измерению» кубитов, что приведёт к их коллапсу до классических битов, которые либо определённо равны 0, либо определённо равны 1. Единственное известное решение этой проблемы — квантовая коррекция ошибок: схема, предложенная в середине 1990-х годов, которая хитроумно кодирует каждый кубит квантового вычисления в коллективное состояние десятков или даже тысяч физических кубитов. Но исследователи только сейчас начинают применять такую коррекцию ошибок в реальном мире, и её реальное применение займёт гораздо больше времени. Читая о последнем эксперименте с 50 или 60 физическими кубитами, важно понимать, что кубиты не имеют функции коррекции ошибок. Пока это не так, мы не рассчитываем на возможность масштабирования за пределы нескольких сотен кубитов.
Как только кто-то поймёт эти концепции, я бы сказал, что он готов начать читать — или, возможно, даже писать — статью о последнем заявленном достижении в области квантовых вычислений. Он будет знать, какие вопросы задавать в постоянной борьбе за то, чтобы отличить реальность от шумихи. Понять это действительно возможно — в конце концов, это не высшая математика, это просто квантовые вычисления!
Источник: www.quantamagazine.org
