Quantum computers promise to solve computational problems significantly faster than classical computers. These 'speed-ups' are achieved by utilizing a resource known as magic. Measuring the amount of magic used by a device allows us to quantify its potential computational power. Without this property, quantum computers are no faster than classical computers. Whether magic can be accurately measured on large-scale quantum computers has remained an open problem. To address this question, we introduce Pauli instability as a measure of magic and experimentally measure it on the IBM Eagle quantum processor. We prove that measuring large (i.e., extensive) quantities of magic is intractable. Our results suggest that one may only measure magic when a quantum computer does not provide a speed-up. We support our conclusions with both theoretical and experimental evidence. Our work illustrates the capabilities and limitations of quantum technology in measuring one of the most important resources in quantum computation.
- ID статьи: 2408.01663
- Название: On the Hardness of Measuring Magic
- Авторы: Roy J. Garcia, Gaurav Bhole, Kaifeng Bu, Liyuan Chen, Haribabu Arthanari, Arthur Jaffe
- Учреждения: Гарвардский университет, Онкологический институт Dana-Farber, Медицинская школа Гарварда
- Классификация: quant-ph (квантовая физика)
- Дата публикации: 6 августа 2024 г.
- Ссылка на статью: https://arxiv.org/abs/2408.01663
Квантовые компьютеры обещают решать вычислительные задачи быстрее классических компьютеров благодаря использованию ресурса, называемого "магией" (magic). Количество магии, используемой устройством, может количественно определить его потенциальную вычислительную мощность. Без этого свойства квантовые компьютеры не будут быстрее классических. В данной работе вводится нестабильность Паули (Pauli instability) как мера магии и проводятся экспериментальные измерения на квантовом процессоре IBM Eagle. Исследование доказывает, что измерение большого количества (то есть экстенсивного) магии невозможно. Результаты показывают, что магия может быть измерена только когда квантовый компьютер не обеспечивает ускорение. Исследование подтверждается теоретическими и экспериментальными доказательствами, демонстрируя возможности и ограничения квантовых технологий при измерении одного из наиболее важных ресурсов квантовых вычислений.
Центральный вопрос, который решает данная работа: Возможно ли точно измерить магию на крупномасштабных квантовых компьютерах?
Магия является ключевым ресурсом в квантовых вычислениях, количественно определяя способность квантового компьютера превосходить классические компьютеры. Без магии вычислительная мощность квантового компьютера не превышает возможности классических суперкомпьютеров.
- Основа квантового преимущества: Магия является необходимым условием для достижения квантового преимущества. Квантовые компьютеры могут превосходить классические компьютеры в скорости вычислений только благодаря использованию магии
- Практическая ценность: Измерение магии позволяет оценить возможности реальных квантовых компьютеров, что имеет критическое значение для применения квантовых вычислений в биологии, химии, физике, криптографии, машинном обучении и финансах
- Отказоустойчивые квантовые вычисления: Стоимость генерации магических состояний напрямую влияет на реализацию отказоустойчивых универсальных квантовых вычислений
- Границы классического моделирования: Монотонные функции магии используются для доказательства границ времени, необходимого для классического моделирования вычислений
- Экспоненциальная сложность: Существующие монотонные функции магии (такие как robustness of magic, stabilizer rank, mana и др.) обычно определяются как суммы или оптимизация экспоненциального числа переменных, что затрудняет их измерение
- Экспериментальные ограничения: Измерение монотонных функций магии Google в 2022 году на квантовом процессоре IBM требовало экспоненциального числа физических измерений, что невозможно для крупномасштабных систем
- Открытые вопросы: Additive Bell magic, измеренная в 2023 году на квантовом компьютере IonQ, считалась осуществимой в крупном масштабе, но авторы считают необходимой дальнейшую проверку
Данная работа направлена на систематическое исследование границ осуществимости измерения магии с теоретической и экспериментальной точек зрения, в частности:
- Введение новой измеримой меры магии
- Установление количественного соотношения между сложностью измерения и количеством магии
- Исследование внутреннего противоречия между квантовым преимуществом и измеримостью магии
- Введение нестабильности Паули (Pauli Instability): Предложена новая монотонная функция магии, основанная на out-of-time-ordered correlator (OTOC), обладающая свойствами верности (faithfulness), инвариантности (invariance), аддитивности (additivity) и хорошей масштабируемостью с числом T-вентилей
- Установление теории сложности: Доказана Теорема 1, показывающая, что сложность выборки Паули для измерения магии растет экспоненциально с количеством магии: N = e^{2I(U)}f(η,δ)
- Определение границ осуществимости:
- Когда I(U) = log(n), магия может быть эффективно и точно измерена (полиномиальная сложность)
- Когда I(U) = linear(n), точное измерение невозможно (экспоненциальная сложность)
- Предложение важной гипотезы (Conjecture 1): Для любой надежной монотонной функции магии M, когда M = linear(n), эффективное точное измерение невозможно
- Экспериментальная верификация: Экспериментальное измерение нестабильности Паули на квантовом процессоре IBM Eagle подтверждает теоретические предсказания и демонстрирует влияние шума на измерения
- Теоретические прозрения: Раскрыто внутреннее противоречие в измерении магии — магия может быть измерена только когда квантовый компьютер не демонстрирует квантовое преимущество, связывая проблему измерения магии с теорией хаоса и проблемой barren plateau
Вход: n-кубитный унитарный оператор U (обычно квантовая схема)
Выход: Приблизительное значение I_N(U) количества магии I(U) оператора U
Ограничения:
- Граница ошибки: |I_N(U) - I(U)| < η с вероятностью не менее 1-δ
- Требование эффективности: сложность выборки N = poly(n)
Определение 1: Нестабильность Паули унитарного оператора U определяется как:
I(U)=−log[EP1,P2∈Q⊗n∣OTOC(U,P1,P2)∣]
где:
- OTOC(U,P1,P2)=2n1Tr{U†P1UP2U†P1UP2}
- Q⊗n={⊗i=1nP(i):P(i)∈{I,X,Y,Z}} — множество n-кубитных строк Паули
- E обозначает равномерное математическое ожидание на Q⊗n
- Верность (Faithfulness):
- I(U) ≥ 0 для всех унитарных операторов
- I(U) = 0 тогда и только тогда, когда U является унитарным оператором Клиффорда
- Инвариантность (Invariance):
- I(V₁UV₂) = I(U) для любых унитарных операторов Клиффорда V₁ и V₂
- Аддитивность (Additivity):
- I(U₁ ⊗ U₂) = I(U₁) + I(U₂)
- Масштабирование с T-вентилями (Scaling with T gates):
- I(T^⊗k ⊗ I^⊗(n-k)) = k log(4/3)
- Независимо от позиции T-вентилей
Поскольку точное вычисление требует 16^n членов, на практике используется метод выборки:
- Выборка Паули: Равномерная выборка N пар строк Паули {(P1(i),P2(i))}i=1N из Q⊗n
- Построение аппроксиматора:
IN(U)=−log[N1∑i=1N∣OTOC(U,P1(i),P2(i))∣]
- Измерение OTOC: Использование квантовой схемы (показано на рис. 2) для измерения OTOC
- Требует n кубитов-ссылок, n системных кубитов и 1 управляющего кубита
- Получение значения OTOC через измерение ожидаемого значения X-базиса управляющего кубита ⟨X_C⟩
- Связь между хаосом и магией:
- Связывание OTOC (традиционно используемого для измерения scrambling в хаотических системах) с измерением магии
- Унитарные операторы Клиффорда отображают строки Паули в отдельные строки Паули: U†PU = e^{-iφ}P'
- Неклиффордовы унитарные операторы отображают строки Паули в суперпозиции нескольких строк Паули: U†PU = ΣᵢcᵢPᵢ ("делокализация" в пространстве Паули)
- Эта характеристика scrambling приводит к |OTOC| близкому к 0, откуда I(U) > 0
- Масштабируемый дизайн:
- Использование выборки вместо точного вычисления делает метод принципиально масштабируемым для крупномасштабных систем
- Явная формула для сложности выборки облегчает анализ границ осуществимости
- Связь с классическим моделированием:
- Эффективно измеримое количество магии (log(n)) соответствует классически моделируемым схемам
- Неэффективно измеримое количество магии (linear(n)) соответствует схемам, которые могут демонстрировать квантовое преимущество
- Квантовый процессор: IBM Eagle
- Масштаб системы: 4-5 кубитов (небольшой масштаб для уменьшения влияния шума)
- Простая архитектура Uₖ (рис. 1c сверху):
- Один слой k T-вентилей: T^⊗k
- Для проверки основных соотношений масштабирования
- Сложная архитектура Vₖ (рис. 1c снизу):
- k-слойная структура, каждый слой содержит:
- Слой вентилей H
- Два чередующихся слоя вентилей CNOT
- Слой вентилей S
- Один T-вентиль (применяется к i-му кубиту)
- Моделирование сложных структур схем в реальных квантовых вычислениях
- Сложность выборки Паули N: 500 (значительно меньше, чем требуется для точного вычисления 16^n)
- Сложность выборки OTOC M: 500
- Количество повторений: Каждая точка данных измеряется независимо 5 раз и усредняется
- Численное моделирование: n=10 кубитов (рис. 1a)
- Экспериментальные измерения: n=4-5 кубитов (рис. 1b,d)
- Точное значение: I(Uₖ) = k log(4/3) (черные точки)
- Численное моделирование: I_N(Uₖ) в среде без шума (синие точки)
- Экспериментальные измерения: I_N(Uₖ) в среде с шумом (красные точки)
- Масштаб системы: n=10 кубитов
- Наблюдения:
- Когда количество T-вентилей невелико (k < 5), смоделированные значения (синие точки) хорошо согласуются с точными значениями (черные точки), демонстрируя линейную зависимость
- Когда количество T-вентилей сравнимо с масштабом системы (k ≥ 5), точность приближения значительно снижается
- Смоделированные значения начинают недооценивать истинное значение магии
- Верификация: Подтверждает предсказание Теоремы 1 — с увеличением магии требуется больше образцов для сохранения точности измерения
- Масштаб системы: n=5 кубитов
- Наблюдения:
- Начальный этап (k=1,2): экспериментальные значения (красные точки) переоценивают истинные значения из-за внутреннего шума квантового процессора
- Промежуточный этап: экспериментальные значения постепенно приближаются к точным значениям
- Поздний этап (k≥5): как экспериментальные, так и смоделированные значения недооценивают точные значения
- Анализ влияния шума:
- Предположим, что Uₖ подвергается деполяризационному шуму с интенсивностью λ
- Нестабильность Паули преобразуется в: I(Uₖ) → I(Uₖ) - log(1-λ)
- Шум увеличивает значение монотонной функции, создавая ложный сигнал магии
- Это согласуется с первыми двумя красными точками экспериментальных данных
- Масштаб системы: n=4 кубита
- Структура схемы: Vₖ содержит несколько слоев вентилей Клиффорда и запутывающих вентилей
- Наблюдения:
- Экспериментально измеренные значения примерно линейно зависят от количества T-вентилей
- Подтверждает надежность монотонной функции для сложных архитектур схем
- С увеличением глубины схемы эффект шума становится более выраженным, приводя к смещению экспериментальных значений выше смоделированных
При заданных δ, η > 0, когда сложность выборки Паули составляет:
N=e2I(U)f(η,δ)
вероятность того, что |I_N(U) - I(U)| < η, составляет не менее 1-δ
где: f(η,δ)=2(1−egη)2ln(1/δ), g=sign(I(U)−IN(U))
Ключевое значение: Измерение большего количества магии требует экспоненциально больше образцов
- Осуществимый случай: Когда I(U) = log(n), магия может быть эффективно и точно аппроксимирована (N = poly(n))
- Неосуществимый случай: Когда I(U) = linear(n), точная аппроксимация невозможна (N = exp(n))
Конкретный пример: Для Uₖ = T^⊗k ⊗ I^⊗(n-k)
- N = e^{8k/3}f(η,δ)
- Когда k = log(n), измерение эффективно
- Когда k = linear(n), измерение невозможно
С вероятностью не менее 1-δ, количество образцов, необходимых для измерения OTOC(U,P₁,P₂) с ошибкой γOTOC(U,P₁,P₂) (0<γ<1), составляет:
M=γ2OTOC(U,P1,P2)2ln(1/δ)
- Осуществимо: Когда OTOC(U) = 1/poly(n)
- Неосуществимо: Когда OTOC(U) = exp(-n)
Ключевое прозрение: Для случайных унитарных операторов Хаара значения OTOC обычно составляют exp(-n), что делает измерение невозможным
- Экспоненциальный рост сложности выборки: Как экспериментальные, так и смоделированные данные подтверждают, что с увеличением магии точность измерения снижается, требуя экспоненциально больше образцов
- Двойственное влияние шума:
- При низкой магии: шум приводит к переоценке
- При высокой магии: недостаточность выборки приводит к недооценке
- Измеримость сложных схем: Даже для сложных схем с несколькими слоями вентилей нестабильность Паули все еще может захватить рост магии с количеством T-вентилей
- Порог осуществимости: Когда количество T-вентилей достигает порядка масштаба системы, точность измерения значительно снижается
- Robustness of magic 22: Мера, основанная на робастности
- Stabilizer rank 24: Ранг стабилизатора
- Mana и relative entropy of magic 21: Меры, основанные на относительной энтропии
- Magic entropy 54: Энтропия магии
- Stabilizer Rényi entropy 55: Энтропия Рени стабилизатора
- Additive Bell magic 43: Аддитивная магия Белла
- Эксперимент Google 2021 42: Обнаружение характеристик магии на квантовом процессоре Sycamore
- Эксперимент IBM 2022 23: Измерение новых монотонных функций магии, но требующее экспоненциального числа физических измерений
- Эксперимент IonQ 2023 43: Измерение additive Bell magic, считающееся осуществимым в крупном масштабе
- Логический квантовый процессор 2024 46: Измерение additive Bell magic на логическом квантовом процессоре
- Метод интерферометрии 56: Предложен Swingle и др., используется в данной работе
- Набор инструментов случайного измерения 57,58: На основе случайного измерения
- Техника квантовой телепортации 59,60: На основе квантовой телепортации
- Формализм классической тени 61,62: Использование структуры классической тени
- Теоретическая полнота: Впервые устанавливаются строгие теоретические границы сложности измерения магии
- Масштабируемость: Предложенный метод совместим с квантовыми платформами с однокубитным считыванием
- Экспериментальная верификация: Проверка теоретических предсказаний на реальном квантовом процессоре
- Универсальное прозрение: Предложена гипотеза, применимая к любой надежной мере магии
- Установление границ осуществимости:
- Малое количество магии (I(U) = log(n)) может быть эффективно и точно измерено на крупномасштабных квантовых компьютерах
- Большое количество магии (I(U) = linear(n)) невозможно эффективно измерить
- Парадокс квантового преимущества:
- Магия может быть измерена только когда квантовый компьютер не демонстрирует квантовое преимущество
- Схемы, демонстрирующие квантовое преимущество (содержащие linear(n) T-вентилей), имеют магию, которая не может быть эффективно измерена
- Это раскрывает внутреннее противоречие в измерении магии
- Универсальная гипотеза (Conjecture 1):
- Для любой надежной монотонной функции магии M, когда M = linear(n), эффективное точное измерение невозможно
- Это связано с тем, что многие монотонные функции магии имеют форму M = -log(exp(-N_T)), и точное извлечение exp(-N_T) требует ошибку экспоненциально меньше N_T
- Связь между хаосом и магией:
- Нестабильность Паули связывает измерение магии с квантовым хаосом (scrambling)
- Характеристика scrambling неклиффордовых унитарных операторов является источником их магии
- Ограничения экспериментального масштаба:
- Из-за влияния шума эксперименты проводились только на 4-5 кубитах
- Невозможно прямо проверить поведение крупномасштабных систем
- Чувствительность к шуму:
- Экспериментальные результаты показывают, что шум создает ложные сигналы магии
- Необходимо разработать протоколы измерения, устойчивые к шуму
- Теоретическая полнота:
- Гипотеза 1 еще не строго доказана
- Требуется дальнейшая теоретическая работа по немеримости для общих монотонных функций магии
- Эффективность выборки:
- Текущий метод требует значительное количество образцов при среднем количестве магии
- Могут существовать более эффективные стратегии выборки
- Зависимость от архитектуры схемы:
- Хотя протестированы две архитектуры схем, применимость к более широким типам схем требует дальнейшего исследования
- Открытые проблемы:
- Строгое доказательство Гипотезы 1
- Доказательство того, что магия не может быть измерена, когда квантовый компьютер демонстрирует квантовое преимущество
- Робастность к шуму:
- Разработка протоколов измерения магии, устойчивых к шуму
- Заимствование успешных техник обработки шума из измерений хаоса 59
- Связь с квантовым машинным обучением:
- Исследование возможности обучения магии с помощью квантового машинного обучения
- Предположение о столкновении с проблемами, подобными barren plateau
- Это соответствует явлению в квантовом машинном обучении, когда только модели, не обеспечивающие квантовое преимущество, поддаются обучению 69-71
- Глубокое понимание проблемы точности:
- Установление более глубокой связи между проблемой точности измерения магии и проблемой barren plateau
- Понимание того, почему большее количество магии требует сверхточного измерения
- Практические приложения:
- Разработка практических инструментов для оценки возможностей реальных квантовых компьютеров
- Предоставление руководства для генерации магических состояний в отказоустойчивых квантовых вычислениях
- Значительный теоретический вклад:
- Впервые устанавливаются строгие математические границы сложности измерения магии
- Теорема 1 предоставляет явное количественное соотношение между сложностью выборки и количеством магии
- Раскрывается глубокое противоречие между квантовым преимуществом и измеримостью магии
- Сильная методологическая инновация:
- Творческое применение OTOC (инструмента теории хаоса) к измерению магии
- Нестабильность Паули удовлетворяет всем идеальным свойствам монотонной функции
- Предоставляет масштабируемую схему измерения
- Интеграция теории и эксперимента:
- Не только строгие теоретические доказательства, но и экспериментальная верификация на квантовом процессоре IBM
- Численное моделирование, теоретические предсказания и экспериментальные результаты взаимно подтверждают друг друга
- Анализ конкретного влияния шума на измерения
- Глубокие прозрения:
- Связывание проблемы измерения магии с хаосом, barren plateau и квантовым преимуществом
- Предложенная Гипотеза 1 имеет универсальный характер, применяясь ко всем надежным мерам магии
- Раскрытие сущности измерения как проблемы точности
- Ясное изложение:
- Логичная структура статьи, последовательно переходящая от определений к теории и затем к экспериментам
- Строгие математические формулировки с четкими физическими объяснениями
- Интуитивные диаграммы, эффективно поддерживающие аргументацию
- Ограниченный экспериментальный масштаб:
- Из-за шума эксперименты ограничены 4-5 кубитами
- Невозможно прямо проверить поведение крупномасштабных систем (например, n=50-100 кубитов)
- Это общее ограничение современного квантового оборудования, но все же влияет на прямую применимость выводов
- Неполнота теории:
- Гипотеза 1, хотя и хорошо аргументирована, не имеет строгого доказательства
- Доказательство немеримости для общих монотонных функций магии остается открытой проблемой
- Возможно существование специальных мер магии, избегающих препятствий сложности
- Недостаточная обработка шума:
- Хотя влияние шума проанализировано, не предложены устойчивые к шуму протоколы измерения
- Экспериментальные результаты показывают, что шум создает ложные сигналы магии
- Для практического применения требуются более эффективные стратегии смягчения шума
- Оптимизация стратегии выборки:
- Текущий метод использует равномерную выборку, которая может быть неоптимальной
- Не исследуется, существуют ли методы важности выборки или другие техники для снижения сложности выборки
- Для среднего количества магии требуемое количество образцов остается значительным
- Охват типов схем:
- Эксперименты тестируют только две относительно простые архитектуры схем
- Применимость к более сложным реальным квантовым алгоритмам (например, VQE, QAOA) требует верификации
- Различные топологии схем могут влиять на эффективность измерения
- Вклад в теорию квантовых вычислений:
- Предоставляет важные границы измеримости для теории магии
- Раскрывает фундаментальное ограничение в теории квантовых ресурсов
- Может влиять на будущее направление разработки монотонных функций магии
- Руководство для экспериментальных квантовых вычислений:
- Предоставляет теоретическую основу для оценки возможностей квантовых процессоров
- Помогает понять, какие меры магии практически осуществимы
- Имеет важное значение для экспериментов по верификации квантового преимущества
- Междисциплинарные связи:
- Устанавливает новую связь между квантовыми вычислениями и теорией хаоса
- Соответствует проблеме barren plateau в квантовом машинном обучении
- Может вдохновить исследования измеримости других квантовых ресурсов
- Практическая ценность:
- Нестабильность Паули может служить практическим инструментом для оценки квантовых схем
- Помогает идентифицировать классически моделируемые схемы (I(U) = log(n))
- Предоставляет справочные данные для оценки ресурсов отказоустойчивых квантовых вычислений
- Воспроизводимость:
- Методология четко описана и легко воспроизводима
- Эксперименты проводятся на общедоступном квантовом процессоре IBM
- Теоретические доказательства строги и легко проверяются
- Анализ квантовых схем:
- Оценка неклассичности квантовых схем
- Идентификация классически моделируемых схем (I(U) = log(n))
- Оценка вычислительной сложности схем
- Оценка квантовых процессоров:
- Измерение способности квантовых процессоров генерировать магию
- Сравнение производительности различных квантовых платформ
- Верификация качества операций квантовых вентилей
- Разработка квантовых алгоритмов:
- Руководство по разработке алгоритмов для балансирования использования магии и измеримости
- Оптимизация использования T-вентилей для повышения эффективности классического моделирования
- Анализ сложности для вариационных квантовых алгоритмов
- Отказоустойчивые квантовые вычисления:
- Оценка требований к ресурсам дистилляции магических состояний
- Оценка затрат магии для различных схем кодирования
- Оптимизация разработки отказоустойчивых протоколов
- Исследование квантового преимущества:
- Понимание требований к ресурсам для квантового преимущества
- Верификация достоверности заявлений о квантовом преимуществе
- Разработка проверяемых демонстраций квантового преимущества
Неприменимые сценарии:
- Точное измерение магии для крупномасштабных квантовых схем (>50 кубитов, содержащих linear(n) T-вентилей)
- Приложения, требующие мониторинга магии в реальном времени
- Точное измерение в высокошумных окружениях
- Gottesman (1998): Основополагающая работа по группе Клиффорда и формализму стабилизатора
- Bravyi & Kitaev (2005): Universal quantum computation with ideal Clifford gates and noisy ancillas — роль магических состояний в отказоустойчивых квантовых вычислениях
- Veitch et al. (2014): Исходное определение relative entropy of magic
- Howard & Campbell (2017): Введение robustness of magic
- Mi et al. (2021): Эксперимент Google по измерению OTOC и магии на процессоре Sycamore
- Haug & Kim (2023): Измерение additive Bell magic
Общая оценка: Это статья с важным вкладом в область теории ресурсов квантовых вычислений, которая посредством строгого теоретического анализа и экспериментальной верификации раскрывает фундаментальные ограничения измерения магии, предлагая глубокий парадокс квантового преимущества. Основная ценность статьи заключается в установлении количественных границ измеримости и связывании магии с хаосом, квантовым преимуществом и другими ключевыми концепциями. Несмотря на ограничения экспериментального масштаба и неполноту некоторых теоретических результатов, ее новаторские прозрения и строгая методология делают ее важным справочным материалом в этой области.