Квантовые границы для скомпилированных XOR-игр и d-исходных CHSH-игр

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

• ID статьи: 2403.05502
• Название: Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• Авторы: Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, Ivan Šupić
• Классификация: quant-ph (квантовая физика)
• Время публикации/конференция: Принято в Quantum 2025-08-08
• Ссылка на статью: https://arxiv.org/abs/2403.05502

Аннотация

Нелокальные игры играют ключевую роль в квантовой теории информации и имеют многочисленные приложения в протоколах аутентификации и криптографии. Kalai и соавторы (STOC 2023) представили процедуру компиляции нелокальных игр в интерактивные доказательства с одним доказывающим, используя схему квантового гомоморфного шифрования, и доказали, что их метод компиляции сохраняет классические границы игры. Natarajan и Zhang (FOCS 2023) впоследствии доказали, что для частного случая CHSH-игр квантовые границы сохраняются. В данной работе расширены методы доказательства Natarajan и Zhang, доказано, что процедура компиляции Kalai и соавторов сохраняет квантовые границы для двух классов игр: XOR-игр и d-исходных CHSH-игр. Мы также устанавливаем, что для любой пары измерений кубитов существует XOR-игра, оптимальная вероятность выигрыша которой может служить самотестированием этой конкретной пары измерений.

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

Основная проблема

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

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

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

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

1. Требование пространственного разделения: Традиционная нелокальность Белла требует физического пространственного разделения, что ограничивает сценарии применения
2. Ограниченные теоретические результаты: Метод компиляции Kalai и соавторов доказывает только сохранение классических границ, отсутствуют верхние границы квантовых границ
3. Ограничение конкретными играми: Результаты Natarajan и Zhang применимы только к CHSH-играм, что недостаточно универсально

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

Использование квантового гомоморфного шифрования (QHE) для имитации пространственного разделения путём скрытия полной информации о входных данных, таким образом компилируя нелокальные игры в интерактивные доказательства с одним доказывающим и доказывая, что такая компиляция сохраняет квантовые границы.

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

1. Расширение теоремы о сохранении квантовых границ: Доказано, что процедура компиляции Kalai и соавторов сохраняет квантовые границы для XOR-игр и d-исходных CHSH-игр с ошибкой, являющейся пренебрежимо малой функцией параметра безопасности
2. Установление криптографической структуры SOS-разложения: На основе методов Natarajan и Zhang разработан метод криптографического разложения в сумму квадратов (SOS), применимый к более широкому классу игр
3. Реализация вычислительного самотестирования:
   • Самотестирование для произвольной пары измерений кубитов
   • Самотестирование трёх антикоммутирующих квантовых наблюдаемых
4. Предоставление новых теоретических инструментов: Введено отображение псевдоожидания (pseudo-expectation map), которое отображает полиномы нелокальных наблюдаемых в корреляции, наблюдаемые в скомпилированной игре

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

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

Входные данные: Нелокальная игра G, схема квантового гомоморфного шифрования QHE Выходные данные: Скомпилированная интерактивная игра с одним доказывающим G' Ограничения: Сохранение квантовых границ исходной игры с ошибкой, являющейся пренебрежимо малой функцией параметра безопасности κ

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

1. Протокол компиляции (компиляция KLVY)

Для двусторонней нелокальной игры:

• Первый раунд: Верификатор отправляет зашифрованный вопрос $\bar{x} = \text{Enc}(x)$ доказывающему, получает зашифрованный ответ $\bar{a} = \text{Enc}(a)$
• Второй раунд: Верификатор отправляет открытый вопрос $y$ доказывающему, получает открытый ответ $b$
• Определение: Использует предикат $V(\text{Dec}(\bar{a}), b|\text{Dec}(\bar{x}), y)$ для определения выигрыша

2. Отображение псевдоожидания

Определяется линейный оператор $\tilde{E}$, отображающий однородные полиномы второй степени измеряемых наблюдаемых в корреляции в скомпилированной игре:

$\tilde{E}[A_x B_y] = C_{x,y}, \quad \tilde{E}[B_y A_x] = C^T_{y,x}$

$\tilde{E}[A_x A_{x'}] = \delta_{x,x'}, \quad \tilde{E}[B_y B_{y'}] = S_{y,y'}$

где матрица корреляций определяется как: $C = \sum_{x,y} \langle A_x, B_y \rangle |x\rangle\langle y|$

3. Криптографическое SOS-разложение

Для XOR-игр, используя SOS-разложение из Теоремы 1:

$\xi_q 1 - B_g = \sum_x \frac{\lambda_x}{2}\left(A_x - \sum_y F_{xy}B_y\right)^2 + P(\{B_y\}_y)$

Применяя отображение псевдоожидания: $\tilde{E}[\xi_q 1 - B_g] = \sum_x \frac{\lambda_x}{2}\tilde{E}\left[\left(A_x - \sum_y F_{xy}B_y\right)^2\right] + \tilde{E}[P(\{B_y\}_y)]$

Ключевые леммы

Лемма 8: Для полиномов вида $P_x = A_x - \sum_y F_{xy}B_y$ существует пренебрежимо малая функция $\delta_{\text{QHE}}(\cdot)$ такая, что: $\tilde{E}[P_x^\dagger P_x] \geq -\delta_{\text{QHE}}(\kappa)$

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

1. Специальная форма SOS-разложения: Доказано, что SOS-разложение XOR-игр может быть записано так, чтобы каждый член содержал только одну наблюдаемую Алисы
2. Использование криптографической безопасности: Искусное использование IND-CPA безопасности QHE для ограничения значений псевдоожидания
3. Обобщение на высокие размерности: Расширение метода на SATWAP неравенства для d-исходных измерений

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

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

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

1. Класс XOR-игр: Верификация свойства сохранения квантовых границ для всех XOR-игр
2. d-CHSH игры: Верификация сохранения квантовых границ неравенства SATWAP
3. Протоколы самотестирования: Построение конкретных скомпилированных игр, реализующих самотестирование измерений

Критерии оценки

1. Сохранение квантовых границ: Разница между оптимальной вероятностью выигрыша скомпилированной игры и исходной игры составляет только $\text{negl}(\kappa)$
2. Робастность самотестирования: Границы ошибок самотестирования при шуме и конечном параметре безопасности
3. Вычислительная эффективность: Полиномиальная временная реализуемость стратегии доказывающего

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

1. Сохранение квантовых границ для XOR-игр (Теорема 3)

Результат: Для XOR-игры с оптимальным квантовым смещением $\xi_q$, оптимальное квантовое смещение скомпилированной XOR-игры составляет $\xi_q + \delta_{\text{QHE}}(\kappa)$, где $\delta_{\text{QHE}}(\cdot)$ является пренебрежимо малой функцией.

2. d-мерное неравенство SATWAP (Теорема 4)

Результат: Для d-мерного неравенства SATWAP Белла, если d полиномиально зависит от параметра безопасности κ, то квантовая граница скомпилированного неравенства SATWAP составляет $(\beta^{\text{SATWAP}}_d)_q + \theta(\kappa)$, где $\theta(\cdot)$ является пренебрежимо малой функцией.

3. Самотестирование произвольных двухкубитных измерений

Результат: Для каждой пары наблюдаемых кубитов существует XOR-игра G такая, что в скомпилированном протоколе G' любой полиномиальный доказывающий, выигрывающий с вероятностью по крайней мере $\omega_q(G) - \epsilon$, должен реализовать операторы измерения в пределах $O(\sqrt{\epsilon}, \text{negl}(\kappa))$ с точностью до локальной изометрии.

4. Самотестирование трёх антикоммутирующих наблюдаемых Паули

Результат: Скомпилированный протокол, основанный на элегантном неравенстве Белла, может самотестировать три антикоммутирующих измерения Паули $\sigma_x, \sigma_y, \sigma_z$ с ошибкой $O(\delta, \text{negl}(\kappa))$.

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

Компиляция нелокальных игр

1. Kalai и соавторы (2023): Первое предложение компиляции нелокальных игр с использованием QHE, доказательство сохранения классических границ
2. Natarajan и Zhang (2023): Доказательство сохранения квантовых границ для CHSH-игр
3. Brakerski и соавторы (2023): Анализ квантовых границ для конкретных CHSH-игр

Приложения нелокальности Белла

1. Распределение квантовых ключей без устройств: Распределение безопасных ключей на основе нарушения неравенств Белла
2. Аутентификация случайности: Аутентификация истинной случайности с использованием нелокальности Белла
3. Самотестирование: Аутентификация квантовых устройств через нарушение неравенств Белла

Квантовое гомоморфное шифрование

1. Mahadev (2018): Первое введение концепции квантового гомоморфного шифрования
2. Brakerski (2018): Улучшенная схема QHE с повышенной устойчивостью к шуму

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

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

1. Расширение универсальности: Успешное расширение результатов сохранения квантовых границ от единственной CHSH-игры на весь класс XOR-игр и d-исходные CHSH-игры
2. Реализация самотестирования: Первая реализация вычислительного самотестирования произвольных пар измерений кубитов в однопроцессорной установке
3. Теоретические инструменты: Установление универсальной математической структуры для анализа квантовых границ скомпилированных игр

Ограничения

1. Ограничения формы SOS-разложения: Метод применим только к играм со специальной формой SOS-разложения (каждый член содержит только одну наблюдаемую Алисы)
2. Зависимость от параметра безопасности: Точность результатов зависит от параметра безопасности схемы QHE
3. Многосторонние игры: Расширение на нелокальные игры более чем двух сторон ещё не выполнено

Будущие направления

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

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

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

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

Недостатки

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

Влияние

1. Теоретический вклад: Предоставление новых инструментов для пересечения квантовой криптографии и теории сложности
2. Перспективы приложений: Открытие новых путей для аутентификации устройств на практических платформах квантовых вычислений
3. Направления исследований: Продвижение теоретических исследований скомпилированных квантовых протоколов

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

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

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

1. Kalai et al. "Quantum advantage from any non-local game." STOC 2023
2. Natarajan and Zhang. "Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification." FOCS 2023
3. Mahadev. "Classical homomorphic encryption for quantum circuits." FOCS 2018
4. Brakerski. "Quantum FHE (almost) as secure as classical." CRYPTO 2018

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