Что такое Quantum XOR Games?

Я провел некоторые исследования и нашел несколько разных работ, в которых обсуждаются игры XOR (классические и квантовые). Мне любопытно, если бы кто-то мог дать краткое вводное объяснение относительно того, что такое игры XOR и как они используются или могут быть использованы / полезны в квантовых вычислениях.

Квантовые игры xor - это метод значительного упрощения идей, лежащих в основе теоремы Белла , который утверждает, что никакая физическая теория локальных скрытых переменных никогда не сможет воспроизвести все предсказания квантовой механики.

В основном, когда два кубита запутаны, измерения на них кажутся коррелированными, даже если они очень далеко друг от друга. Тогда возникает вопрос: решили ли кубиты, как они будут разрушаться во время запутывания (таким образом, неся с собой «локальные скрытые переменные»), или решили, как они разрушатся во время измерения (таким образом, требуя какое-то мгновенное «жуткое действие на расстоянии»)? «). Теорема Белла и xor игры твердо идут на сторону последнего.

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

Например, в оригинальной игре xor, игре CHSH , Алиса получает случайный бит$X$ и Боб случайный бит $Y$, Алиса затем выводит выбранный бит$a$ и Боб выводит выбранный бит $b$, Они хотят удовлетворить уравнение$X \cdot Y = a \oplus b$, Конечно, поскольку они не могут общаться, они могут выиграть только время от времени; они хотят выбрать стратегию, чтобы максимизировать вероятность выигрыша. Лучшая классическая стратегия для Алисы и Боба - всегда выводить$0$, что приведет к победе в 75% случаев. Однако, если Алиса и Боб разделяют запутанную пару кубитов, они могут придумать стратегию, чтобы выиграть 85% времени! Вывод состоит в том, что это опровергает существование локальных скрытых переменных, потому что если бы кубиты содержали локальную скрытую переменную (некоторую строку битов), то Алиса и Боб могли бы предварительно разделить эту же строку битов для использования в их классической стратегии, чтобы также получить вероятность выигрыша 85%; поскольку никакая цепочка битов не позволяет им делать это, это означает, что запутанные кубиты не могут полагаться на общую цепочку битов (локальная скрытая переменная), и происходит что-то более пугающее. Вы можете увидеть реализацию игры CHSH в примерах Microsoft Q # (с расширенным объяснением) здесь .

Лучшее объяснение игры CHSH от профессора Вазирани в этом видео . Он утверждает что-то интересное (возможно, риторическое), что если бы Эйнштейн имел доступ к упрощенной презентации игр xor, он бы не стал тратить последние три десятилетия своей жизни на поиск скрытой теории квантовой механики на основе переменных!

Я также написал сообщение в блоге, детализирующее игру CHSH здесь .

One application of xor games is self-testing: when running algorithms on an untrusted quantum computer, you can use xor games to verify that the computer isn't corrupted by an adversary trying to steal your secrets! This is useful in device-independent quantum cryptography.