Алгоритм Саймона в облачных NISQ системах

Основная информация

• ID статьи: 2406.11771
• Название: Simon's algorithm in the NISQ cloud
• Авторы: Reece Robertson, Emery Doucet, Ernest Spicer, Sebastian Deffner
• Классификация: quant-ph cs.ET
• Дата публикации: 18 июня 2024 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2406.11771

Аннотация

Алгоритм Саймона является одной из первых задач, демонстрирующих истинное квантовое преимущество. Однако алгоритм предполагает доступ к безошибочным квантовым битам. В данном исследовании алгоритм Саймона используется для тестирования коэффициентов ошибок устройств, доступных в текущих "квантовых облаках". Основные результаты включают объективное сравнение различных физических платформ, предоставляемых IBM и IonQ. Исследование подчёркивает важность понимания архитектуры устройства и топологии чипа при трансляции квантовых алгоритмов на аппаратное обеспечение. Например, показано, что следует избегать двухкубитных операций между пространственно разделёнными кубитами на сверхпроводящих чипах.

Предпосылки и мотивация исследования

Контекст проблемы

1. Разрыв между теорией и практикой квантового преимущества: Алгоритм Саймона теоретически обеспечивает экспоненциальное квантовое ускорение, но это основано на предположении об отсутствии шума в кубитах, тогда как современные устройства NISQ (Noisy Intermediate-Scale Quantum) содержат значительный шум.
2. Необходимость оценки производительности NISQ устройств: С ростом инвестиций в квантовые вычисления (прогнозируемый размер рынка 1,3 триллиона долларов к середине 2030-х годов) требуется объективная оценка фактической производительности современных облачных квантовых устройств.
3. Вызовы при переносе алгоритмов: Различные платформы квантового оборудования (сверхпроводящие vs ионные ловушки) имеют различные архитектурные особенности, требующие понимания влияния этих различий на производительность алгоритма.

Мотивация исследования

• Алгоритм Саймона высокочувствителен к шуму, что делает его идеальным инструментом для диагностики шума в NISQ устройствах
• Отсутствие систематических сравнительных исследований различных облачных квантовых платформ
• Необходимость понимания конкретного влияния топологии оборудования на производительность алгоритма

Основные вклады

1. Систематическое тестирование: Первое комплексное тестирование коэффициентов ошибок нескольких квантовых устройств IBM и IonQ с использованием алгоритма Саймона
2. Анализ сравнения платформ: Предоставление объективного сравнения производительности сверхпроводящих кубитов (IBM) и ионных ловушек (IonQ)
3. Обнаружение топологической зависимости: Доказательство значительного негативного влияния пространственного разделения кубитов на производительность сверхпроводящей платформы
4. Верификация модели шума: Обнаружение того, что существующие симуляторы шума не могут точно предсказать поведение реального оборудования
5. Анализ порога квантового преимущества: Определение конкретного разрыва между текущими NISQ устройствами и истинным квантовым преимуществом

Подробное описание методики

Определение задачи

Проблема Саймона: Дана функция f, необходимо определить, является ли она взаимно однозначной или двузначной периодической функцией с секретной строкой s, и если это так, найти s.

Математическое выражение: Для n-битных входных строк f либо взаимно однозначна, либо для любых двух входов x₁ и x₂, отображающихся на один и тот же выход, выполняется x₁ ⊕ x₂ = s.

Реализация алгоритма

Структура квантовой схемы

1. Инициализация: Два n-кубитных регистра, оба инициализированы в состояние |0⟩
2. Первое преобразование Адамара: Применение вентиля H к первому регистру, создание равномерного суперпозиционного состояния
3. Операция оракула: Применение Uₓ, реализующей Uₓ(|x⟩|y⟩) = |x⟩|f(x)⊕y⟩
4. Второе преобразование Адамара: Повторное применение вентиля H к первому регистру, создание интерференционной картины
5. Измерение: Измерение всех кубитов, извлечение результатов, ортогональных секретной строке s

Варианты реализации оракула

Сложный оракул: Использование максимального количества двухкубитных вентилей

• Содержит множество вентилей CNOT и однокубитные повороты
• Тестирование производительности оборудования при максимальных операциях запутывания

Простой оракул: Использование минимального количества двухкубитных вентилей

• Минимизация операций запутывания
• Служит базовой линией для сравнения производительности

Показатели оценки производительности

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

• В идеальном случае должен быть 0%
• 50% коэффициент ошибок эквивалентен случайному угадыванию, указывая на полный отказ алгоритма

Экспериментальная установка

Тестируемые платформы

Сверхпроводящая платформа IBM

• Устройства: Brisbane, Osaka, Kyoto (все 127-кубитные чипы Eagle)
• Особенности: Фиксированная топология соединений, требующая вентилей SWAP для дальних операций
• Модель шума: Локальный симулятор IBM AER, включающий ошибки однокубитных и двухкубитных вентилей и ошибки считывания

Платформа ионных ловушек IonQ

• Устройства: Harmony (11 кубитов), Aria (25 кубитов), Forte (32 кубита)
• Особенности: Полносвязная топология, прямые операции между любыми кубитами
• Преимущества: Более высокая точность, предсказуемость и время когерентности

Экспериментальные параметры

• Размер задачи: n ∈ 2, 12 (соответствует 4-24 кубитам)
• Количество повторений: 3 эксперимента для каждой конфигурации, 30 для симулятора
• Распределение кубитов: Разрешена динамическая оптимизация выбора физических кубитов для систем IBM
• Обновление калибровки: Получение последних характеристик шума перед каждым экспериментом

Результаты экспериментов

Основные находки

1. Общие тенденции производительности

• Все NISQ устройства демонстрируют рост коэффициента ошибок с увеличением размера задачи
• Критический порог: При примерно 12 кубитах коэффициент ошибок сложного оракула приближается к 50%
• Прогноз квантового преимущества: При экстраполяции на 53 кубита все устройства достигнут коэффициента ошибок 50%

2. Различия между платформами

Сверхпроводящая платформа IBM:

• Сложный оракул: Нелинейный рост ошибок, резкое ухудшение при n>8
• Простой оракул: Хорошая производительность, низкие коэффициенты ошибок
• Влияние пространственного разделения: Коэффициент ошибок вентиля CNOT значительно увеличивается с расстоянием между кубитами

Платформа ионных ловушек IonQ:

• Коэффициент ошибок демонстрирует последовательный линейный рост
• Полносвязная топология исключает проблемы пространственного разделения
• Более предсказуемая общая производительность

3. Симулятор vs реальное оборудование

• IBM: Симулятор шума значительно недооценивает коэффициент ошибок сложного оракула
• IonQ: Симулятор правильно предсказывает тенденцию, но недооценивает ошибки примерно в 2 раза
• Ключевая проблема: Существующие модели шума недостаточно учитывают коррелированные ошибки

Количественные результаты

Сравнение физических параметров

Влияние пространственного разделения

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

Связанные работы

Тестирование квантовых алгоритмов

• Исторические исследования: Ранние маломасштабные реализации алгоритма Шора, выборка случайных схем, поиск Гровера и др.
• Оценка NISQ: Предыдущие исследования показали, что устройства IBM, Rigetti, IonQ и DWave не достигают справедливой выборки

Проблема скрытой подгруппы

• Теоретическая база: Алгоритм Саймона как представитель проблемы скрытой подгруппы, наряду с алгоритмом Шора, алгоритмом Дойча-Йозсы и др.
• Квантовое преимущество: Один из первых алгоритмов, доказывающих, что квантовая машина Тьюринга может нарушить тезис Чёрча-Тьюринга

Характеристики NISQ устройств

• Моделирование шума: Предыдущие исследования в основном сосредоточены на случайном шуме Паули, данная работа раскрывает сложность реального оборудования
• Сравнение устройств: Отсутствие систематических сравнительных исследований различных физических платформ

Выводы и обсуждение

Основные выводы

1. Ограничения NISQ: Современные облачные квантовые устройства слишком шумны для поддержки истинного квантового преимущества
2. Важность архитектуры: Понимание архитектуры устройства и топологии чипа критично для трансляции алгоритмов
3. Пространственные эффекты: На сверхпроводящих чипах следует избегать двухкубитных операций между пространственно разделёнными кубитами
4. Недостаточность симуляторов: Существующие симуляторы шума не могут точно предсказать поведение реального оборудования

Технические рекомендации

Стратегии оптимизации для сверхпроводящих платформ

• Учёт топологии соединений кубитов при разработке алгоритмов
• Минимизация дальних операций, требующих вентилей SWAP
• Динамическое распределение кубитов может частично смягчить топологические ограничения

Преимущества платформ ионных ловушек

• Полносвязность упрощает реализацию алгоритмов
• Лучшая предсказуемость ошибок
• Текущее ограничение по количеству кубитов остаётся основным узким местом

Ограничения

1. Специфичность алгоритма: Выводы основаны в основном на алгоритме Саймона, другие алгоритмы могут показать иные результаты
2. Временная зависимость: Производительность квантовых устройств постоянно улучшается, выводы имеют временную привязку
3. Ограничение масштаба: Из-за ограничений возможностей устройств не удалось протестировать задачи большего масштаба
4. Бюджетные ограничения: Тестирование IonQ Forte ограничено бюджетом, количество точек данных меньше

Направления будущих исследований

1. Расширение диапазона алгоритмов: Тестирование алгоритмов Дойча-Йозсы, Бернштейна-Вазирани, Шора и др.
2. Устойчивость к шуму: Исследование порогов устойчивости алгоритма Саймона к шуму при сохранении квантового преимущества
3. Булевы линейные системы: Разработка эффективных алгоритмов решения шумных булевых линейных уравнений
4. Улучшение оборудования: Отслеживание влияния улучшений производительности устройств на производительность алгоритмов

Глубокая оценка

Сильные стороны

1. Высокая систематичность: Первое комплексное тестирование алгоритма Саймона на нескольких облачных квантовых платформах
2. Высокая практическая ценность: Предоставление важных рекомендаций разработчикам квантовых алгоритмов при выборе подходящей платформы
3. Важные открытия: Раскрытие значительного влияния пространственного разделения на производительность сверхпроводящих платформ
4. Научная методология: Эффективное разделение влияния различных факторов через сравнение сложного и простого оракулов
5. Открытость данных: Предоставление полного кода и данных, поддерживающих воспроизводимость результатов

Недостатки

1. Ограничение алгоритма: Тестирование только алгоритма Саймона, универсальность выводов требует проверки
2. Ограничение масштаба: Максимальный размер тестирования (24 кубита) всё ещё далёк от порога квантового преимущества
3. Временная актуальность: Быстрое развитие NISQ устройств может быстро устаревить выводы
4. Недостаток теоретического анализа: Отсутствие глубокого теоретического объяснения наблюдаемых явлений
5. Бюджетные ограничения: Некоторые эксперименты ограничены бюджетом, полнота данных требует улучшения

Влияние

Научный вклад:

• Предоставление новой методики тестирования производительности NISQ устройств
• Раскрытие важного влияния топологии оборудования на производительность алгоритмов
• Предоставление данных для прогнозирования сроков реализации квантового преимущества

Практическая ценность:

• Руководство разработчикам квантовых алгоритмов при выборе подходящей аппаратной платформы
• Указание направлений улучшения для поставщиков облачных квантовых услуг
• Справочная информация для инвесторов при оценке этапа развития квантовых вычислений

Воспроизводимость:

• Предоставление полного репозитория GitHub с кодом
• Подробное описание экспериментальной установки и параметров
• Использование общедоступных облачных квантовых платформ

Области применения

1. Разработка NISQ алгоритмов: Предоставление рекомендаций разработчикам при выборе оборудования
2. Оценка облачных квантовых сервисов: Помощь пользователям в выборе подходящей платформы квантовых вычислений
3. Руководство по улучшению оборудования: Предоставление направлений оптимизации производителям квантовых устройств
4. Образовательные исследования: Использование в качестве практического примера в курсах квантовых вычислений
5. Инвестиционные решения: Предоставление справочной информации о текущем состоянии технологии для инвестиций в квантовые вычисления

Библиография

Данная работа цитирует 47 важных источников, включая:

• Simon, D.R. (1997): Оригинальная статья об алгоритме Саймона
• Nielsen & Chuang (2010): Классический учебник по квантовым вычислениям и квантовой информации
• Preskill, J. (2018): Основополагающая статья об эпохе NISQ
• Техническая документация и API IBM и IonQ
• Связанные работы по недавним экспериментам квантового преимущества

Резюме: Данная работа проводит систематическое тестирование основных облачных квантовых платформ с использованием алгоритма Саймона, раскрывая ограничения производительности NISQ устройств и особенности различных архитектур оборудования. Результаты исследования имеют важную практическую ценность для области квантовых вычислений, но также показывают, что до реализации истинного квантового преимущества остаётся значительное расстояние. С быстрым развитием квантового оборудования непрерывный мониторинг и оценка производительности будут важным направлением исследований в этой области.