Квантовое ускорение для быстрого преобразования Фурье?
Быстрое преобразование Фурье с помощью квантового ускорения
Исследователи уже десятилетия изучают теоретический потенциал квантовых компьютеров. Только в последние годы реальные системы начали достигать точности и масштаба, которые делают их будущее вполне возможным.
Ключевым стимулом для внимания и инвестиций стало революционное введение методов Питера Шора, теперь работающего в Массачусетском технологическом институте, которые могут позволить квантовым компьютерам взламывать существующие схемы шифрования с открытым ключом. Ресурсы, такие как время, требуемые классическими методами для факторизации чисел, растут экспоненциально с числом разрядов ввода. Требования к квантовым алгоритмам Шора возрастают только как полиномиальная функция, что потенциально делает зашифрованные данные уязвимыми для будущих квантовых компьютеров.
Главным ингредиентом этого метода является квантовая реализация преобразования Фурье для быстрого определения основной повторяющейся частоты в последовательности данных, что указывает на простые множители большого числа. Действительно, квантовое преобразование Фурье, или QFT, является ключевым элементом многих экспоненциально мощных квантовых алгоритмов, предложенных на сегодняшний день. (Другой класс алгоритмов, разработанных Ловом Гровером, ускоряет неструктурированный квантовый поиск, но только в степени размера проблемы.)
Преобразования Фурье уже широко используются для задач, таких как обработка изображений, но QFT не непосредственно обращается к этим важным приложениям. Исследователи, стремящиеся исправить эту ситуацию, разработали очень отличный квантовый подход, который может стать частью инструментария для более широкого использования квантовых вычислений. Однако пока что квантовое преимущество кажется менее убедительным.
- Amazon тестирует доставку лекарств с помощью дронов
- Вглядывание внутрь квантового компьютера создает новые фазы информации
- Nvidia и производитель iPhone Foxconn собираются строить ‘фабрики искусственного интеллекта
БПФ: Быстрое преобразование Фурье
Преобразования Фурье преобразуют входные данные, такие как последовательность значений во времени, в амплитуды (комплексные числа) частотного спектра. В большинстве цифровых приложений вход состоит из некоторого числа N дискретных выборок, и выходной спектр содержит N пространственных или временных частот. Спектр полностью эквивалентен исходным данным, которые можно восстановить с использованием аналогичного процесса.
Преобразование также предоставляет простой способ сжатия данных, например, путем представления амплитуд с меньшим разрешением или отбрасывания высокочастотных компонентов. Форматы JPEG (Joint Photographic Experts Group), например, позволяют уменьшить размер файла, сохраняя наиболее важные особенности. Вариант преобразования Фурье, “дискретное косинусное преобразование”, вычисляет пространственные частотные компоненты из двумерных пиксельных данных.
Математически, амплитуда каждой частоты вычисляется путем сложения всех входных значений после “поворота”, умножая значение каждой входной точки на коэффициент, зависящий от произведения частоты и индекса точки. N точек и N частот поэтому, кажется, требуют N 2 произведений. Однако, как было популяризировано Джеймсом Кули и Джоном Тьюки в 1965 году, вычисление может быть значительно ускорено с помощью стратегии “разделяй и властвуй”, называемой быстрым преобразованием Фурье, или БПФ. Например, если N является степенью двойки, полное преобразование может быть вычислено путем повторного разделения матрицы на четыре подматрицы. Ресурсы, необходимые для этого алгоритма, растут слегка быстрее, чем линейно относительно N (как N log N), а не пропорционально N 2 .
Квантовое преобразование Фурье
Полная мощность квантовых вычислений была продемонстрирована еще более мощным ускорением преобразования Фурье, но его выход ограниченее, чем у БПФ. Факторизационный алгоритм Шора, например, определяет доминирующий период (или частоту) последовательности, но не амплитуды других частот.
Преобразование Фурье является естественным способом извлечения относительной информации из амплитуд, сказал Аббот, но “в конце концов, вам нужно найти способ извлечь нужную информацию.”
Для определения периода состояния кубитов, или квантовых битов, преобразуются так же, как в случае преобразования Фурье. После этого преобразования кубиты по-прежнему содержат всю входную информацию. Однако, как предупреждает Аластер Абботт из центра Инриа (Французский институт исследования в компьютерной науке и автоматизации) во Франции Университета Гренобль Альпы, такие манипуляции включают “крошечные, крошечные вращения, которые могут очень быстро запутаться из-за шума.” “Найти способ делать это надежно довольно сложно.”
Важно отметить, что извлечение этой информации приводит только к одному ответу. При измерении ее значения каждый кубит должен принимать значение 0 или 1, точно так же, как классический бит. Более тонкая “квантовая информация”, например, представление нескольких возможных результатов, исчезает при измерении.
Преобразование Фурье – это естественный способ исследования относительной информации в амплитудах, сказал Аббот, но “В конце концов, вам нужно найти способ извлечь нужную вам информацию, а это непростая часть”. Изобретательность QFT заключается в создании состояния, измерение которого почти наверняка приведет к получению 1 для кубита, представляющего целевую периодичность, в то время как остальные измеряются как 0.
QFFT: Квантовое быстрое преобразование Фурье
Несмотря на свою несомненную важность, QFT не предоставляет доступа ко всей спектральной информации, широко используемой в алгоритме Фурье. Чтобы решить эту проблему, физики из Токийского университета науки (TUS) в Японии предлагают использовать квантовую схему для выполнения Фурье-преобразования, которую они называют QFFT (хотя это название может вызвать путаницу с QFT).
Ожидается, что предложенная схема не даст квантового ускорения по сравнению с классическим FFT, по крайней мере, для одного входа (например, изображения). Однако исследователи утверждают, что их схема может выполнять вычисления для множества изображений параллельно без необходимости дополнительных ресурсов.
Для реализации преобразования Фурье команда TUS использует стратегию, называемую кодированием базисов, которая, как они говорят, является “сущностно отличной” от эффективно аналоговых манипуляций перед измерением в QFT. Вместо прямого представления каждого входного значения в виде амплитуды кубита, данные вводятся в двоичное представление. Затем двоичное представление передается состоянию нескольких кубитов.
Квантовая схема разработана так, чтобы выполнять вычисления над этими битами, похожие на вычисления классических схем. Отличие состоит в том, что дополнительные входные потоки могут быть одновременно встроены в конфигурацию в виде квантового “суперпозиционного” состояния, и вычисление FFT может быть выполнено над всеми ними одновременно.
“Некоторые задачи могут быть немного проще, (в то время как) другие задачи, без безошибочных вычислений, вам действительно нечего надеяться выполнить.”
В конце концов, измерение преобразованного выхода даст только один результат. Однако, если измерение откладывается, данную схему можно включить как подпрограмму в другое квантовое вычисление, которое может использовать полное преобразование Фурье. “Арифметические операции, такие как сложение и вычитание, могут быть применены к выходу QFFT, [но] не к QFT”, – сказал студент-выпускник TUS Рё Асака. “Это одно из преимуществ QFFT”. Однако для большинства текущих приложений нет необходимости в сравнении между несколькими изображениями, что, предположительно, является наиболее мощным способом сохранения нескольких квантовых представлений преобразования Фурье.
Важно отметить, что ресурсы, необходимые для подготовки входных данных для вычислений, должны включать в себя те, которые иногда пренебрегаются. “Если время подготовки входных данных возрастает пропорционально количеству [входов], преимущество QFFT исчезает”, – отметил Асака. Чтобы избежать такого исхода, он предвидит разработку сложной квантовой конфигурации кубитов и их сохранение в квантовой оперативной памяти с произвольным доступом. Такая “qRAM” была предложена в 2000-х годах, но пока не стала практической.
Поиск квантового преимущества
Другие исследователи также пытаются представить способы использования квантовых компьютеров для повседневных задач. Однако, несмотря на огромные инвестиции, кубиты в существующих системах квантовых компьютеров слишком шумные и быстро теряют свое деликатное квантовое состояние, а их количество недостаточно, хотя системы становятся все более крупными и лучше. В 2019 году команда из Google объявила о том, что их система выполнила задачу, которая для классической системы заняла бы порядки больше времени, и позже исследователи в Китае описали аналогичные демонстрации. Однако выбранные задачи не демонстрируют практически важную возможность.
В долгосрочной перспективе большинство наблюдателей ожидает, что большинство интересных практических задач будут зависеть от квантовой коррекции ошибок, сложной техники, которая может потребовать гораздо большего количества кубитов. “Некоторые задачи могут быть немного проще”, – сказал Аббот, но “многие другие задачи без должных вычислений безошибочных вычислений трудно выполнимы. Большинство алгоритмов квантового преобразования Фурье относятся к последней категории.” Он добавил: “На данный момент даже плохо выполнить это невозможно.”
Исследователи уже изучают квантовые алгоритмы с использованием систем, доступных в текущей эпохе “Noisy Intermediate-Scale Quantum” (NISQ). Некоторые из самых многообещающих проблем-кандидатов включают в себя квантовые симуляции молекул и материалов. Маленькие квантовые системы также могут быть воссозданы с помощью небольшого числа кубитов, например, недавно было заявлено о эмуляции передачи информации через червоточину пространства-времени с использованием всего семи кубитов.
Другой класс проблем, который привлекает внимание даже низкотехнологичных предприятий, – это повсеместная задача оптимизации сложной системы, такой как распределение производственных ресурсов или финансов. Найти лучшее решение может быть возможным, несмотря на значительный шум, например, с помощью гибридных классически-квантовых алгоритмов. (Компания D-Wave Systems также продает машины, которые решают такие задачи с гораздо большим числом кубитов, но многие исследователи сомневаются в том, является ли его работа действительно квантово-механической, в отличие от более распространенных архитектур на основе гейтов.)
Компании и правительства по всему миру продолжают исследовать возможные алгоритмы, архитектуры и физическую реализацию квантового компьютера. Однако надежные системы из тысяч кубитов для надежных, масштабных устойчивых к ошибкам вычислений возможно появятся только через несколько лет, если вообще.
Дальнейшее чтение
Asaka, R., Sakai, K., and Yahagi, R. “Квантовая схема для быстрого преобразования Фурье,” Quantum Information Processing 19 , 277 (2020). DOI: https://doi.org/10.1007/s11128-020-02776-5
Arute, F. et al. “Квантовое превосходство с использованием программируемого сверхпроводящего процессора,” Nature 574 , 505 (2019) DOI: https://doi.org/10.1038/s41586-019-1666-5
Hoefler, T., Thomas Häner, T, and Matthias Troyer, M. “Разделение помпы от практичности: о реалистичном достижении квантовой преимущественности,” Communications 66 , 82 (2023). DOI: https://doi.org/10.1145/3571725
Автор
Дон Монро – писатель по науке и технологиям, живущий в Миддлбери, штат Вермонт, США.
©2023 ACM 0001-0782/23/11
Разрешается создание цифровых или бумажных копий части или всего этой работы для личного использования или использования в классе без оплаты, при условии, что копии не делаются или не распространяются с целью получения прибыли или коммерческой выгоды, и что на копиях есть эта заметка и полная ссылка на первую страницу. Авторские права на компоненты этой работы, принадлежащие другим лицам, чем ACM, должны быть сохранены. Разрешается использование с указанием авторства. Для копирования в другие цели, повторной публикации, размещения на серверах или распространения по спискам требуется предварительное специальное разрешение и/или оплата. Запрос разрешения на публикацию отправляйте по адресу permissions@acm.org или по факсу (212) 869-0481.
Цифровая библиотека издается Association for Computing Machinery. Авторские права © 2023 ACM, Inc.
