Новая теория намекает на более эффективный способ разработки квантовых алгоритмов

В 2019 году Google заявила, что впервые продемонстрировала квантовый компьютер, выполняющий вычисления, превосходящие возможности самых мощных современных суперкомпьютеров.

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

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

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

Алгоритм — это последовательность шагов для выполнения вычисления. Алгоритм обычно реализуется на схеме.

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

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

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

«Например, даже небольшая молекула белка может содержать сотни электронов. Если каждый электрон может принимать только две формы, то для моделирования 300 электронов потребуется 2 ³⁰⁰ классических состояний, что больше, чем число всех атомов во Вселенной «, — сказала Сабер Кейс, профессор химического факультета Пердью и член Института квантовой науки и инженерии Пердью.

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

У исследователей до сих пор не было хорошего способа определить, какие квантовые состояния могут удовлетворять этому условию полиномиальной сложности.

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

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

«Учитывая любое квантовое состояние, теперь мы можем разработать эффективную процедуру выборки коэффициентов, чтобы определить, принадлежит ли оно к классу или нет», — сказал Ху.

Эта работа поддержана Министерством энергетики США (Управление фундаментальных энергетических наук) в рамках награды № DE-SC0019215. Институт квантовой науки и инженерии Purdue является частью парка открытий Purdue.