Когда мне было 9 лет, мы купили новый компьютер. Он был лучше старого во всем, кроме одного: на нем не шла моя любимая игра, гонки. На кой черт нужен этот навороченный компьютер, если он не тянет мою любимую игру, недоумевал я.
Похожая проблема и с квантовыми компьютерами. В теории они могут то же самое, что обычные. На практике, однако, эта самая квантовость не позволяет эффективно использовать важнейшие из классических алгоритмов.
Именно поэтому опубликованная 15 апреля научная работа несет радостные вести. В ней Крейг Гидни (Craig Gidney), программист из команды «Гугл АI квантум» (Google AI Quantum) в Санта-Барбаре, штат Калифорния, которая занимается разработкой искусственного интеллекта, описывает квантовую версию классического алгоритма быстрого умножения больших чисел. На обычных компьютерах он давно используется, однако до исследования Гидни оставалось неясным, можно ли его как-то подогнать под квантовые машины.
Еще важнее то, что целый класс алгоритмов умножения в информатике используется чуть ли не повсеместно. Гидни надеется, что его метод позволит запускать весь этот класс и на квантовых компьютерах тоже, хотя они прежде и считались слишком громоздкими.
Упомянутый алгоритм строится на первом за тысячи лет открытии в умножении. Традиционный метод умножения из начальной школы предполагает n2 шагов, где n — количество цифр в умножаемых числах. Тысячелетиями математики считали, что более эффективного метода нет и быть не может.
Но, как сообщал журнал «Кванта» в недавней статье «Математики открыли идеальный способ умножения», в 1960 году математик Анатолий Карацуба изобрел более быстрый способ. Его метод предполагает разбиение длинных чисел на более короткие. Например, чтобы умножить два восьмизначных числа, сначала нужно разбить каждое на два четырехзначных, а затем каждое из полученных — еще раз, уже на двузначные. Затем вы проделываете некоторые операции со всеми двузначными числами и получаете их произведение. При умножении больших чисел быстрый метод Карацубы требует гораздо меньше шагов, чем школьный метод «в столбик».
Но квантовые компьютеры сбрасывать информацию не умеют.
Квантовые компьютеры выполняют вычисления, используя системы квантовых битов, или «кубитов». Эти кубиты переплетены друг с другом в тесную сеть, можно даже сказать — перепутаны. Эта перепутанность и придает квантовым компьютерам их огромную мощь: вместо того, чтобы просто хранить информацию отдельными битами, квантовые компьютеры используют сложную систему отношений, которой охвачены все кубиты. И для определенных задач квантовые вычислительные машины в разы эффективнее традиционных.
Но эта же отличительная черта, которая придает квантовым компьютерам их мощь, делает их и более уязвимыми. Поскольку кубиты перепутаны, нельзя изменить отдельно взятые, не затронув остальных. Это не позволяет выборочно удалять информацию, как на обычном компьютере. Стирать кубиты — все равно, что обрезать нити в паутине. Одним надрезом можно разорвать всю сеть целиком.
Необходимость сохранения всей информации мешает созданию квантовых версий «рекурсивных» алгоритмов, — то есть замкнутых на себе. Рекурсивные алгоритмы в информатике широко используются, но для оптимальной работы они требуют, чтобы компьютер стирал информацию после каждого шага. Иначе вычисления быстро станут чересчур громоздкими. «Если при всякой операции вы будете хранить всю информацию, объем занятого пространства будет масштабироваться», — объясняет Эшли Монтанаро (Ashley Montanaro), специалист по квантовой информатике из Бристольского университета. И на практике на любой машине быстро закончится память.
В своей новой работе Гидни описывает квантовую версию алгоритма быстрого умножения Карацубы, которая не требует больших затрат памяти. Вместо того, чтобы создавать промежуточные значения до получения окончательного, в нем используется метод, который называется «оптимизация хвостового вызова», который позволяет преобразовывать ввод непосредственно в вывод. У этого алгоритма нет необходимости создавать промежуточные данные, которые квантовый компьютер все равно никогда не сможет удалить. «Ему не приходится иметь дела с лишними кубитами просто потому, что они не создаются в принципе», — объяснил Томас Вонг (Thomas Wong), специалист по квантовой информатике из Крейтонского университета.
Гидни рассчитывает, что его метод позволит адаптировать многие классические рекурсивные алгоритмы для работы на квантовых компьютерах. Пока что квантовые компьютеры еще находятся в зачаточном состоянии и едва способны перемножать даже одноразрядные числа. Но готовый алгоритм уже есть, поэтому, когда их начинка улучшится, они смогут выполнять гораздо больше операций.