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

Классические биты – чёрно-белые, а квантовые немного сложнее

Когда мне было 9, родители купили новый компьютер. Он практически по всем статьям был лучше старого, кроме одного: на нём не запускались мои любимые гонки. Помню, как я думал – зачем нужен новомодный компьютер, если он не запускает мою самую любимую программу?

Та же проблема есть и у квантовых компьютеров. В теории они способны на всё, на что способен классический. На практике их квантовость делает практически невозможным запуск некоторых наиболее важных классических алгоритмов.

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

Что важнее, алгоритм умножения принадлежит к классу повсеместно используемых алгоритмов информатики. Гидни считает, что его новая техника позволит квантовым компьютерам реализовать весь класс этих алгоритмов, которые пока считались слишком громоздкими для использования в квантовой машине.

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

Но, как мы недавно разъяснили в статье "Математики обнаружили идеальный способ перемножения чисел", в 1960 советский математик Анатолий Карацуба обнаружил более быстрый способ. Его метод заключался в разбитии длинных чисел на более короткие. Для умножения двух восьмизначных чисел, к примеру, нужно сначала разбить их на два четырёхзначных, затем разбить каждое из них на два двузначных числа. Затем нужно провести несколько операций с двузначными числами и восстановить результат итогового умножения. Для умножения очень больших чисел метод Карацубы отнимает гораздо меньше шагов, чем школьный.

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

Но квантовые компьютеры не могут отбрасывать информацию.

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

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

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

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

Гидни считает, что его метод сработает для адаптации многих классических рекурсивных алгоритмов для квантовых компьютеров. Пока что квантовые компьютеры находятся в настолько зачаточном состоянии, что едва могут справляться с умножением однозначных чисел. Однако алгоритм готов, и когда их схемы будут улучшены, они станут способными на гораздо большее.