Оптимальное обучение квантовых гамильтонианов из гиббсовых состояний высокой температуры

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

• ID статьи: 2108.04842
• Название: Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• Авторы: Jeongwan Haah (Microsoft Quantum), Robin Kothari (Microsoft Quantum), Ewin Tang (University of Washington)
• Классификация: quant-ph cs.DS cs.LG
• Дата публикации: 17 марта 2023 г. (версия arXiv)
• Ссылка на статью: https://arxiv.org/abs/2108.04842

Аннотация

В данной работе исследуется задача обучения гамильтониана H до точности ε по копиям гиббсова состояния ρ=exp(-βH)/Tr(exp(-βH)) с известной обратной температурой β. В области высоких температур (низких β) авторы предлагают алгоритм обучения для класса гамильтонианов с низким пересечением, достигающий сложности по выборкам S=O(logN/(βε)²) и временной сложности O(SN), и доказывают соответствующие нижние границы, демонстрирующие оптимальность алгоритма как по сложности выборок, так и по временной сложности.

Исследовательский контекст и мотивация

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

Задача обучения гамильтониана является важной проблемой на пересечении квантовой многотельной физики и машинного обучения. Дано несколько копий теплового равновесного состояния (гиббсова состояния) неизвестного гамильтониана H; целью является обучение коэффициентов гамильтониана. Эта задача имеет прямую физическую мотивацию: гамильтониан описывает взаимодействия и временную эволюцию квантовой системы, а гиббсово состояние представляет состояние системы в тепловом равновесии с окружением при заданной температуре.

Научная значимость

1. Физическое значение: Понимание фундаментальных свойств квантовых систем и предсказание их поведения
2. Вычислительное значение: Это квантовое обобщение классической задачи обучения марковских случайных полей
3. Теоретическое значение: Связывает квантовую теорию информации и статистическую теорию обучения

Ограничения существующих методов

• Работа Anshu и соавторов (AAKS21) для геометрически локальных гамильтонианов имеет сложность по выборкам O(2^{poly(β)}N²logN/(β^c ε²)), что неоптимально по зависимости от β и N
• Отсутствует явный анализ и оптимизация временной сложности
• Применимо только к геометрически локальному классу гамильтонианов

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

1. Оптимальный алгоритм: Предложен оптимальный алгоритм обучения гамильтонианов с низким пересечением в области высоких температур со сложностью по выборкам O(logN/(βε)²) и временной сложностью O(N logN/(βε)²)
2. Соответствующие нижние границы: Доказаны соответствующие нижние границы сложности по выборкам Ω(exp(β)logN/(β²ε²)), достигающие оптимальности в области высоких температур
3. Более широкий класс гамильтонианов: Расширение на гамильтонианы с низким пересечением, которые более общие, чем геометрически локальные гамильтонианы
4. Теоретический анализ: Улучшена анализ сильной выпуклости логарифма статистической суммы, параметр сильной выпуклости улучшен до β²/2
5. Расширение на реальную временную эволюцию: Доказано, что тот же алгоритм может использоваться для обучения гамильтониана из унитарных операторов реальной временной эволюции e^{-itH}

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

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

Рассмотрим гамильтониан N-кубитной системы H = Σ_^M λ_a E_a, где:

• E_a — известные различные неединичные операторы Паули
• λ_a ∈ -1,1 — коэффициенты, подлежащие обучению
• Гамильтониан имеет низкое пересечение: каждый оператор действует на постоянное число кубитов, и каждый оператор имеет нетривиальное пересечение поддержки только с постоянным числом других операторов

Цель: обучить коэффициенты {λ_a} до аддитивной ошибки ε по копиям гиббсова состояния ρ = exp(-βH)/Tr(exp(-βH)).

Основная техническая схема

1. Кластерное разложение (Cluster Expansion)

Использование техники кластерного разложения из статистической механики для разложения математического ожидания ⟨E_a⟩ в ряд Тейлора по β:

⟨E_a⟩(x) = β p₁^{(a)}(x) + β² p₂^{(a)}(x) + β³ p₃^{(a)}(x) + ...

где p_m^{(a)} — однородные многочлены степени m, и p₁^{(a)}(x) = -x_a.

2. Алгоритмическая процедура

Шаг 1: Оценка математических ожиданий

• Для каждого оператора Паули E_a оценить ⟨E_a⟩ до точности βε
• Использование раскраски двойственного графа взаимодействия для параллельного измерения непересекающихся операторов
• Сложность по выборкам: O(d/(β²ε²)log(M/δ))

Шаг 2: Метод Ньютона-Рафсона Определить функцию F_a(x) = Σ_^m β^k p_k^{(a)}(x) - Ê_a, целью является нахождение x такого, что F(x) достаточно мала.

Использование модифицированной итерации Ньютона-Рафсона:

x^{(t+1)} = Proj_{[-1,1]^M}[x^{(t)} + β^{-1} Σ_{k=0}^{K-1} (I + β^{-1}J(x^{(t)}))^k F(x^{(t)})]

3. Ключевые технические инновации

Вычисление кластерных производных:

• Разработан алгоритм точного вычисления кластерных производных D_W L
• Временная сложность: (8m + L)poly(m)
• Использование целочисленных свойств матриц Паули для точной арифметики

Анализ матрицы Якобиана:

• Доказано, что матрица Якобиана J обладает свойством "ленточной диагональности"
• Если расстояние между b и a равно k, то J_ имеет порядок β^{k+1}
• Это делает J близкой к -βI, что позволяет легко аппроксимировать J^{-1}

Анализ сходимости

Условие критической температуры

Алгоритм работает при β < β_c, где β_c = (25e^6(d+1)^{10})^{-1} зависит только от степени двойственного графа взаимодействия d.

Распространение ошибки

Анализ распространения ошибки через многомерную теорему о среднем значении:

|x_a - λ_a| ≤ ||J^{-1}||_{∞→∞}(||F(x)||_∞ + ||F(λ)||_∞) ≤ 4ε

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

Теоретическая верификация

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

Анализ сложности

• Сложность по выборкам: O(logN/(βε)²) (ошибка ℓ_∞), O(N/(βε)²) (ошибка ℓ_2)
• Временная сложность: O(N logN/(βε)²) (ℓ_∞), O(N²/(βε)²) (ℓ_2)
• Время предварительной обработки: O(LMd log d) для построения двойственного графа взаимодействия

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

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

Теорема верхней границы (Theorem 1.1)

Для гамильтонианов с низким пересечением при условии β < β_c:

• Ошибка ℓ_∞ ε: сложность по выборкам O(1/(β²ε²) log(N/δ))
• Ошибка ℓ_2 ε: сложность по выборкам O(N/(β²ε²) log(N/δ))
• Временная сложность равна сложности по выборкам, умноженной на N

Теорема нижней границы (Theorem 1.2)

Существуют 2-локальные гамильтонианы такие, что:

• Ошибка ℓ_∞: сложность по выборкам Ω(exp(β)/(β²ε²) log(N/δ))
• Ошибка ℓ_2: сложность по выборкам Ω(exp(β)N/(β²ε²))

Сравнение с предыдущими работами

Улучшение сильной выпуклости

Улучшен параметр сильной выпуклости логарифма статистической суммы с Ω(β^c/N) до Ω(β²), что соответствует улучшению нижней границы дисперсии макроскопических наблюдаемых.

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

Обучение квантовых гамильтонианов

• Bairey и соавторы (2019): Первое предложение обучения гамильтониана из стационарного состояния, но без анализа наихудшего случая
• AAKS21: Установлены строгие верхние границы сложности по выборкам, но неоптимальны по нескольким параметрам
• Классический случай: Уже существуют почти оптимальные алгоритмы для обучения параметров марковских случайных полей

Технические связи

• Кластерное разложение: Заимствование техники высокотемпературного разложения из статистической механики
• Метод Ньютона: Применение классического метода оптимизации в квантовой постановке
• Информационно-теоретические нижние границы: Использование леммы Фано для установления информационно-теоретических нижних границ

Заключение и обсуждение

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

1. В области высоких температур обучение квантовых гамильтонианов может достичь той же оптимальной сложности, что и в классическом случае
2. Предложенный алгоритм оптимален как по сложности выборок, так и по временной сложности
3. Класс гамильтонианов с низким пересечением более общий, чем геометрически локальные, но все еще может быть эффективно обучен

Ограничения

1. Ограничение температуры: Алгоритм работает только в области высоких температур, критическая температура зависит от степени двойственного графа
2. Зависимость от степени: Хотя оптимален для фиксированной степени, критическая температура быстро снижается с увеличением степени
3. Область низких температур: Задача обучения в области низких температур остается открытой

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

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

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

Преимущества

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

Недостатки

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

Влияние

1. Теоретический вклад: Установление эталона для обучения квантовых гамильтонианов
2. Методологическая ценность: Демонстрация эффективного применения классических техник в квантовой постановке
3. Основание для дальнейших исследований: Подготовка основы для исследований в области низких температур и более общих постановок
4. Практический потенциал: Предоставление теоретического руководства для экспериментальной характеризации квантовых систем

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

1. Квантовое моделирование: Верификация точности квантовых симуляторов
2. Материаловедение: Обучение эффективных гамильтонианов конденсированного состояния
3. Квантовые вычисления: Калибровка и верификация квантовых процессоров
4. Фундаментальные исследования: Понимание свойств квантовых многотельных систем

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

1. Anshu, A., Arunachalam, S., Kuwahara, T., & Soleimanifar, M. (2021). Sample-efficient learning of interacting quantum systems. Nature Physics.
2. Kuwahara, T., Kato, K., & Brandão, F. G. (2020). Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. Physical Review Letters.
3. Bresler, G. (2015). Efficiently learning Ising models on arbitrary graphs. STOC.
4. Klivans, A., & Meka, R. (2017). Learning graphical models using multiplicative weights. FOCS.