2025-11-23T15:19:16.484880

Quantum state preparation with optimal T-count

Gosset, Kothari, Wu
How many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $\varepsilon$? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is $Θ\left(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$ if we allow ancilla qubits. We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $\varepsilon$. We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.
academic

Подготовка квантового состояния с оптимальным T-счётом

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

  • ID статьи: 2411.04790
  • Название: Quantum state preparation with optimal T-count
  • Авторы: David Gosset, Robin Kothari, Kewen Wu
  • Классификация: quant-ph (квантовая физика)
  • Дата публикации: ноябрь 2024 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2411.04790

Аннотация

В данной работе исследуется фундаментальная проблема квантовых вычислений: сколько T-вентилей требуется для приближения произвольного n-кубитного квантового состояния с ошибкой ε? Развивая предыдущие работы Low, Kliuchnikov и Schaeffer, авторы доказывают, что при использовании вспомогательных кубитов оптимальная асимптотическая сложность составляет Θ(2nlog⁡(1/ε)+log⁡(1/ε))\Theta(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon)). Одновременно показано, что это также является оптимальным T-счётом для реализации произвольных диагональных n-кубитных унитарных матриц. В статье также описаны сценарии применения, где тензорные произведения нескольких однокубитных унитарных матриц могут синтезироваться параллельно.

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

Важность проблемы

  1. Центральная проблема отказоустойчивых квантовых вычислений: В отказоустойчивых квантовых вычислениях, основанных на двумерных кодах стабилизатора (например, поверхностном коде), стоимость реализации T-вентилей значительно превышает стоимость вентилей Клиффорда. T-вентили реализуются через дистилляцию магических состояний, тогда как вентили Клиффорда могут быть реализованы трансверсально.
  2. Количественная оценка квантовой магичности: Квантовая магичность является важным показателем способности квантовых вычислений превосходить классические вычисления. Понимание необходимых не-клиффордовских ресурсов для реализации квантовых состояний и операций критично для анализа квантового преимущества.
  3. Сложность классического моделирования: Расширения теоремы Готтесмана-Килла показывают, что стоимость классического моделирования квантовых вычислений полиномиальна по всем параметрам, кроме количества T-вентилей.

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

  1. Однокубитный случай: Алгоритм Росса-Селингера уже дал оптимальный T-счёт O(log⁡(1/ε))O(\log(1/\varepsilon)) для однокубитных унитарных матриц, соответствующий информационно-теоретической нижней границе.
  2. Сложность многокубитного случая: Прямое применение однокубитных методов к n-кубитному случаю даёт T-счёт O(2n(n+log⁡(1/ε)))O(2^n(n+\log(1/\varepsilon))).
  3. Пространство для улучшения метода LKS: Low-Kliuchnikov-Schaeffer (2024) улучшили T-счёт до O(2nnlog⁡(n/ε)+log⁡2(n/ε))O(\sqrt{2^n}n\log(n/\varepsilon)+\log^2(n/\varepsilon)), но остаётся место для оптимизации.

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

  1. Оптимальная подготовка квантового состояния: Доказано, что верхняя и нижняя границы T-счёта для произвольного n-кубитного квантового состояния составляют Θ(2nlog⁡(1/ε)+log⁡(1/ε))\Theta(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon))
  2. Оптимальный синтез диагональных унитарных матриц: Установлен одинаковый оптимальный T-счёт для реализации диагональных унитарных матриц
  3. Массовый синтез однокубитных унитарных матриц: Для m=O(log⁡log⁡(1/ε))m = O(\log\log(1/\varepsilon)) различных однокубитных унитарных матриц тензорное произведение может быть реализовано с O(log⁡(1/ε))O(\log(1/\varepsilon)) T-вентилями
  4. Массовое производство однокубитных унитарных матриц: Для m копий однокубитной унитарной матрицы T-счёт составляет O(m+log⁡(1/ε))O(m+\log(1/\varepsilon))
  5. Усиленное доказательство нижней границы: Нижняя граница справедлива в модели адаптивных схем Clifford+T, который сильнее модели, используемой для верхней границы

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

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

Задача подготовки квантового состояния: Дано n-кубитное целевое состояние ∣ψ⟩|\psi\rangle и параметр ошибки ε\varepsilon. Требуется спроектировать схему Clifford+T UU такую, что U∣0n⟩∣0a⟩=∣ψ~⟩∣0a⟩U|0^n\rangle|0^a\rangle = |\tilde{\psi}\rangle|0^a\rangle, где ∥∣ψ⟩−∣ψ~⟩∥≤ε\||\psi\rangle - |\tilde{\psi}\rangle\| \leq \varepsilon.

Задача синтеза диагональной унитарной матрицы: Дана n-кубитная диагональная унитарная матрица DD и ошибка ε\varepsilon. Требуется спроектировать схему Clifford+T для приближённой реализации DD.

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

1. Оптимальный синтез диагональных унитарных матриц (теорема 1.2)

Ключевая идея: Рассматривать n-кубитную диагональную унитарную матрицу DD как однокубитную унитарную матрицу, действующую на n-й кубит и управляемую первыми n-1 кубитами.

Шаги алгоритма:

  1. Для каждого управляющего состояния ∣y⟩|y\rangle однокубитная унитарная матрица GyG_y может быть приближена с использованием O(log⁡(1/ε))O(\log(1/\varepsilon)) вентилей H и T
  2. Использовать булев оракул B:∣y⟩∣z⟩∣0⟩→∣y⟩∣z⟩∣sy⟩B: |y\rangle|z\rangle|0\rangle \to |y\rangle|z\rangle|s_y\rangle, где sys_y — двоичная строка, описывающая последовательность вентилей GyG_y
  3. T-счёт булева оракула составляет O(2nlog⁡(1/ε))O(\sqrt{2^n\log(1/\varepsilon)})
  4. Применить управляемые вентили H и управляемые вентили T с T-счётом O(log⁡(1/ε))O(\log(1/\varepsilon))
  5. Обратить вычисление булева оракула

2. Оптимальный метод подготовки квантового состояния (теорема 1.1)

Двухэтапная стратегия:

Этап первый: грубое приближение (лемма 3.2)

  • Использовать неравенство Хинчина для доказательства существования булевых фазовых оракулов B1,B2B_1, B_2 таких, что ∣ϕ⟩=B2H⊗nB1H⊗n∣0n⟩|\phi\rangle = B_2H^{\otimes n}B_1H^{\otimes n}|0^n\rangle имеет постоянное перекрытие с целевым состоянием ∣ψ⟩|\psi\rangle, не менее 1/21/\sqrt{2}

Этап второй: снижение ошибки (лемма 3.4)

  • Итеративно применить метод грубого приближения к разностному состоянию ∣ψ⟩−∣ϕ⟩|\psi\rangle - |\phi\rangle
  • Построить разложение в ряд: ∣ψ⟩≈ζ⋅∑k=0O(log⁡(1/ε))2−k/2∣ψk⟩|\psi\rangle \approx \zeta \cdot \sum_{k=0}^{O(\log(1/\varepsilon))} 2^{-k/2}|\psi_k\rangle
  • Реализовать с использованием линейной комбинации унитарных матриц (LCU) и точного усиления амплитуды

Технические инновации

  1. Избежание затрат Гровера-Рудольфа: Традиционные методы требуют n многоуправляемых однокубитных унитарных матриц, данный метод требует только O(1) диагональных унитарных матриц
  2. Оптимальный синтез диагональных унитарных матриц: Инновационное разложение многокубитной диагональной унитарной матрицы на однокубитную задачу и задачу булева оракула
  3. Точное усиление амплитуды: Умный выбор амплитуды sin⁡(π/10)\sin(\pi/10) позволяет после двух раундов усиления амплитуды точно получить целевое состояние

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

Теоретическая аналитическая схема

Работа в основном проводит теоретический анализ, используя следующие инструменты:

  1. Неравенство Хинчина: Для доказательства эффекта выравнивания амплитуд
  2. Границы сферической упаковки: Для установления нижних границ в комбинаторных аргументах
  3. Теория нормальных форм: Для преобразования схем Clifford+T в нормальную форму для анализа

Сравнительные эталоны

  1. Алгоритм Росса-Селингера: Оптимальный синтез однокубитных унитарных матриц
  2. Алгоритм LKS: Текущий лучший метод подготовки многокубитных состояний
  3. Информационно-теоретическая нижняя граница: Нижняя граница Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)), установленная Beverland и др.

Параметры модели

  • Адаптивные схемы Clifford+T: Самая сильная модель, допускающая промежуточные измерения и адаптивное управление
  • Унитарные схемы Clifford+T: Традиционная модель унитарных схем
  • Метрика ошибки: Для подготовки состояний используется норма ℓ2\ell_2, для унитарных матриц — операторная норма

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

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

Теорема 1.1 (оптимальная подготовка состояния)

Произвольное n-кубитное квантовое состояние может быть подготовлено с использованием O(2nlog⁡(1/ε)+log⁡(1/ε))O(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon)) T-вентилей, и эта граница является точной.

Теорема 1.2 (оптимальная диагональная унитарная матрица)

Произвольная n-кубитная диагональная унитарная матрица может быть реализована с использованием O(2nlog⁡(1/ε)+log⁡(1/ε))O(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon)) T-вентилей, и эта граница является точной.

Результаты применения

Теорема 1.3 (массовый синтез)

Для тензорного произведения m=O(log⁡log⁡(1/ε))m = O(\log\log(1/\varepsilon)) различных однокубитных унитарных матриц T-счёт составляет O(log⁡(1/ε))O(\log(1/\varepsilon)).

Теорема 1.4 (массовое производство)

Для m копий однокубитной унитарной матрицы UU, то есть U⊗mU^{\otimes m}, T-счёт составляет O(m+log⁡(1/ε))O(m+\log(1/\varepsilon)).

Анализ улучшений

По сравнению с методом LKS O(2nnlog⁡(n/ε)+log⁡2(n/ε))O(\sqrt{2^n}n\log(n/\varepsilon)+\log^2(n/\varepsilon)):

  1. Исключен множитель n в члене 2n\sqrt{2^n}
  2. Улучшен член log⁡2(n/ε)\log^2(n/\varepsilon) до log⁡(1/ε)\log(1/\varepsilon)
  3. Достигнута асимптотическая оптимальность

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

Синтез квантовых схем

  1. Синтез однокубитных матриц: Kliuchnikov-Maslov-Mosca (2013) установили теоретико-групповые основы, Ross-Selinger (2016) дали оптимальный алгоритм
  2. Синтез многокубитных матриц: Grover-Rudolph (2002) предложили иерархический метод, LKS (2024) достигли значительного улучшения
  3. Синтез унитарных матриц: Остаётся значительный разрыв между Ω~(2n)\tilde{\Omega}(2^n) и O~(21.5n)\tilde{O}(2^{1.5n})

Теория квантовой магичности

  1. Ранг стабилизатора: Bravyi и др. (2019) установили теорию разложения стабилизатора
  2. Дистилляция магических состояний: Bravyi-Kitaev (2005) заложили основы отказоустойчивых квантовых вычислений
  3. Классическое моделирование: Многочисленные работы исследуют связь между T-счётом и сложностью классического моделирования

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

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

  1. Полное решение задачи подготовки квантового состояния: Даны точные верхняя и нижняя границы Θ(2nlog⁡(1/ε)+log⁡(1/ε))\Theta(\sqrt{2^n\log(1/\varepsilon)}+\log(1/\varepsilon))
  2. Установлен оптимальный синтез диагональных унитарных матриц: Одинаковая граница сложности
  3. Предоставлены практические методы массового синтеза: Значительная экономия ресурсов в определённых диапазонах параметров

Ограничения

  1. Разрыв для общих унитарных матриц: Для общих n-кубитных унитарных матриц остаётся разрыв между Ω~(2n)\tilde{\Omega}(2^n) и O~(21.5n)\tilde{O}(2^{1.5n})
  2. T-счёт вентилей Клиффорда: Хотя T-счёт оптимален, счёт вентилей Клиффорда составляет O(2nlog⁡(1/ε))O(2^n\log(1/\varepsilon)), близко, но не совсем оптимален
  3. Практическая реализация: Теоретические результаты требуют преобразования в практически осуществимые квантовые алгоритмы

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

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

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

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

  1. Теоретическая полнота: Полностью решена проблема T-счёта сложности подготовки квантового состояния с точными верхней и нижней границами
  2. Технические инновации: Умелое сочетание различных методов (неравенство Хинчина, LCU, усиление амплитуды и т.д.)
  3. Практическая ценность: Результаты массового синтеза имеют важное применение в практических квантовых алгоритмах
  4. Строгое доказательство нижней границы: Установление нижней границы в самой сильной адаптивной модели повышает надёжность результатов

Недостатки

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

Влияние

  1. Теоретическое значение: Предоставляет важные границы сложности для теории сложности квантовых вычислений
  2. Практическая ценность: Предоставляет точную теоретическую основу для оценки ресурсов отказоустойчивых квантовых вычислений
  3. Методологический вклад: Предоставленные методы могут быть применимы к другим проблемам квантовых алгоритмов

Сценарии применения

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

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

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

  • Gottesman (1998): Теория представления Гейзенберга
  • Ross & Selinger (2016): Оптимальный синтез однокубитных матриц
  • Low, Kliuchnikov & Schaeffer (2024): Улучшение подготовки многокубитных состояний
  • Beverland et al. (2020): Теория нижних границ T-счёта