![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
квантовая механика и телепатия
Рассмотрим такую странную игру для команды из двух человек. Их разводят по разным комнатам и сообщают каждому случайный бит q_1, q_2 (все четыре комбинации равновероятны). Они, не сговариваясь, должны в ответ сказать по биту (a_1,a_2). Если оказалось, что a_1 + a_2 по модулю 2 равно q_1 AND q_2, то они выиграли.
Как им заранее договориться, чтобы увеличить вероятность выигрыша? Видя 0, каждый знает, что ответ нуль, и хочет сделать так, чтобы назвать то же число, что и партнёр - но не знает, какой бит тот видит. Простая стратегия - называть обоим всегда нуль, тогда в трёх случаях из четырёх они выиграют (кроме q_1=q_2=1).
Оказывается, что это оптимальная стратегия.
Почему? в самом деле, поскольку всего 4 варианта, каждый из которых имеет вероятность $1/4$, то лучше может быть только стратегия, всегда гарантирующая выигрыш. А такой не существует - можно перебрать или заметить, что любая функция a_1(q_1) и a_2(q_2) одной переменной линейна, поэтому и сумма a_1(q_1)+a_2(q_2) будет линейной функцией над полем из двух элементов, и потому не может совпадать с (нелинейной) функцией AND
В принципе, игроки могут использовать вероятностные стратегии (то есть до игры сначала бросить монеты, и действовать в зависимости от них). Но это не позволит увеличить вероятность (если биты q_1 и q_2 организаторы игры выбирают независимо от случайных битов игроков). В самом деле, такая вероятностная стратегия есть комбинация некоторых детерминированных (каждая выбирается с какой-то частотой), и если каждая из детерминированных даёт не более 75% попаданий, то и комбинация даст не больше.
Представьте себе, что к вам приходят два человека и говорят, что могут выиграть не в трёх случаях из четырёх, а в 4 из 5 - и действительно демонстрируют это в большой серии игр. Доказывает ли это существование телепатии?
Оговорка: игры происходят последовательно - если игроки паралелльно получают много битов из разных игр (независимых) и после этого посылают ответные биты, то рассуждение про 75% уже не проходит. (Не знаю, что конкретно для этой игры, но в общем случае бывают ситуации, когда параллельные игры проще - см. parallel repetition conjecture/theorem)
Оказывается, что квантовая механика говорит, что можно выигрывать более чем в 75% случаев. Для этого игроки заранее приготавливают два кубита в смешанном состоянии. Каждый приносит свой кубит в свою комнату. Получив вопрос, он проводит над этим кубитом некоторое измерение (зависящее от вопроса) и посылает ответ, зависящий от результата измерения. При таких действиях рассуждение о 75% теряет силу и действительно можно придумать способ, дающий большую вероятность.
Говорят, можно достичь вероятности 1/2+1/2\sqrt(2), что примерно 85%, но я не знаю как. Но небольшое увеличение вероятности (до 80%) можно получить так: готовится пара кубитов в состоянии (1/sqrt(2)) (0x0 + 1x1). Видя нуль, игрок выполняет измерение в обычном базисе 0,1 (и сообщает один бит - исход). Видя единицу, игрок выполняет изменение в повёрнутом на угол \alpha базисе : (cos(alpha) 0 + sin(alpha)1, -sin(alpha)0+cos(alpha)1) и тоже сообщает один бит - исход. Другой игрок делает то же самое, но базис повёрнут в другую сторону. Если я ничего не путаю (квантовая механика - наука непростая), то при двух нулевых вопросах ответы будут гарантированно одинаковые. Если один вопрос 0, а другой 1, то ответы одинаковые с вероятностью cos^2(alpha) и разные с вероятностью sin^2(alpha). А если оба вопроса 1, то относительный угол 2alpha и ответы одинаковые с вероятностью cos^2(2alpha) и разные с вероятностью sin^2(2alpha). Видно, что по крайней мере при малых alpha выигрыш больше (sin^2 (2\alpha) примерно в четыре раза больше sin^2(alpha), а достаточно в два).
Вроде это всё давно и хорошо известно специалистам. Изначально это называлось "парадокс Эйнштейна-Подольского-Розена" (можно создать два объекта в смешанном состоянии на большом удалении, и тогда измерение одного объекта вроде как нелокально действует на второй), потом были какие-то "неравенства Белла", показывающие (для специалистов - я не знаю подробностей), что "квантовая механика не сводится к классической" и "нет объяснений со скрытыми параметрами", потом был предложен "CHSH-эксперимент", а недавно специалисты по computer science заинтересовались этим, то есть квантовыми обобщениями multi-prover interactive games, и интерпретировали CHSH-эксперимент в терминах описанной игры. Заодно доходчиво объяснили, в каком смысле и почему квантовая механика принципиально не сводится к классической - я прочёл это (пересказанное выше) у Julia Kempe.
Чего я не знаю (и если кто знает - скажите), насколько современная технология квантовых компьютеров позволяет такие кубиты создать в каких-то (наверно, криогенных) коробочках и сохранить на время. достаточное, чтобы разнести их по комнатам и принять участие в игре. Но если это действительно возможно, по-моему, это замечательное достижение квантовой механики (даже если бы она не сделала ничего другого:-)
UPD: исправлена опечатка, должно быть 1/2 + 1/2sqrt{2}
Как им заранее договориться, чтобы увеличить вероятность выигрыша? Видя 0, каждый знает, что ответ нуль, и хочет сделать так, чтобы назвать то же число, что и партнёр - но не знает, какой бит тот видит. Простая стратегия - называть обоим всегда нуль, тогда в трёх случаях из четырёх они выиграют (кроме q_1=q_2=1).
Оказывается, что это оптимальная стратегия.
Почему? в самом деле, поскольку всего 4 варианта, каждый из которых имеет вероятность $1/4$, то лучше может быть только стратегия, всегда гарантирующая выигрыш. А такой не существует - можно перебрать или заметить, что любая функция a_1(q_1) и a_2(q_2) одной переменной линейна, поэтому и сумма a_1(q_1)+a_2(q_2) будет линейной функцией над полем из двух элементов, и потому не может совпадать с (нелинейной) функцией AND
В принципе, игроки могут использовать вероятностные стратегии (то есть до игры сначала бросить монеты, и действовать в зависимости от них). Но это не позволит увеличить вероятность (если биты q_1 и q_2 организаторы игры выбирают независимо от случайных битов игроков). В самом деле, такая вероятностная стратегия есть комбинация некоторых детерминированных (каждая выбирается с какой-то частотой), и если каждая из детерминированных даёт не более 75% попаданий, то и комбинация даст не больше.
Представьте себе, что к вам приходят два человека и говорят, что могут выиграть не в трёх случаях из четырёх, а в 4 из 5 - и действительно демонстрируют это в большой серии игр. Доказывает ли это существование телепатии?
Оговорка: игры происходят последовательно - если игроки паралелльно получают много битов из разных игр (независимых) и после этого посылают ответные биты, то рассуждение про 75% уже не проходит. (Не знаю, что конкретно для этой игры, но в общем случае бывают ситуации, когда параллельные игры проще - см. parallel repetition conjecture/theorem)
Оказывается, что квантовая механика говорит, что можно выигрывать более чем в 75% случаев. Для этого игроки заранее приготавливают два кубита в смешанном состоянии. Каждый приносит свой кубит в свою комнату. Получив вопрос, он проводит над этим кубитом некоторое измерение (зависящее от вопроса) и посылает ответ, зависящий от результата измерения. При таких действиях рассуждение о 75% теряет силу и действительно можно придумать способ, дающий большую вероятность.
Говорят, можно достичь вероятности 1/2+1/2\sqrt(2), что примерно 85%, но я не знаю как. Но небольшое увеличение вероятности (до 80%) можно получить так: готовится пара кубитов в состоянии (1/sqrt(2)) (0x0 + 1x1). Видя нуль, игрок выполняет измерение в обычном базисе 0,1 (и сообщает один бит - исход). Видя единицу, игрок выполняет изменение в повёрнутом на угол \alpha базисе : (cos(alpha) 0 + sin(alpha)1, -sin(alpha)0+cos(alpha)1) и тоже сообщает один бит - исход. Другой игрок делает то же самое, но базис повёрнут в другую сторону. Если я ничего не путаю (квантовая механика - наука непростая), то при двух нулевых вопросах ответы будут гарантированно одинаковые. Если один вопрос 0, а другой 1, то ответы одинаковые с вероятностью cos^2(alpha) и разные с вероятностью sin^2(alpha). А если оба вопроса 1, то относительный угол 2alpha и ответы одинаковые с вероятностью cos^2(2alpha) и разные с вероятностью sin^2(2alpha). Видно, что по крайней мере при малых alpha выигрыш больше (sin^2 (2\alpha) примерно в четыре раза больше sin^2(alpha), а достаточно в два).
Вроде это всё давно и хорошо известно специалистам. Изначально это называлось "парадокс Эйнштейна-Подольского-Розена" (можно создать два объекта в смешанном состоянии на большом удалении, и тогда измерение одного объекта вроде как нелокально действует на второй), потом были какие-то "неравенства Белла", показывающие (для специалистов - я не знаю подробностей), что "квантовая механика не сводится к классической" и "нет объяснений со скрытыми параметрами", потом был предложен "CHSH-эксперимент", а недавно специалисты по computer science заинтересовались этим, то есть квантовыми обобщениями multi-prover interactive games, и интерпретировали CHSH-эксперимент в терминах описанной игры. Заодно доходчиво объяснили, в каком смысле и почему квантовая механика принципиально не сводится к классической - я прочёл это (пересказанное выше) у Julia Kempe.
Чего я не знаю (и если кто знает - скажите), насколько современная технология квантовых компьютеров позволяет такие кубиты создать в каких-то (наверно, криогенных) коробочках и сохранить на время. достаточное, чтобы разнести их по комнатам и принять участие в игре. Но если это действительно возможно, по-моему, это замечательное достижение квантовой механики (даже если бы она не сделала ничего другого:-)
UPD: исправлена опечатка, должно быть 1/2 + 1/2sqrt{2}
квантовые “уникальные игры”
Эксперимент по квантовой телепатии. Организаторы эксперимента пишут на доске систему линейных уравнений над конечным полем, в которой в каждое уравнение входят всего две переменные. В комнату приглашают двух участников, показывают им систему уравнений и дают договориться об общей стратегии. Затем участников разводят по разным комнатам. Организаторы тайно выбирают одно из уравнений в системе случайным образом, и просят одного из участников назвать значение одной переменной, входящей в уравнение, другого — другой. Эксперимент признаётся успешным если названные значения удовлетворяют уравнению.
Какова вероятность успеха p? Во-первых, если система совместна, то участники могут просто выбрать одно из решений, затем назвать значения переменных в этом решении. Вероятность успеха равна единице, p=1. Аналогично, если существует решение такое, что 99% всех уравнений выполнены, то p ≥ 99%. Таким образом:
Факт 1. Рассмотрим решение, которое удовлетворяет максимальному числу уравнений в системе. Обозначим через v долю удовлетворённых уравнений. Тогда p ≥ v.
Более того, несложно проверить, что, в “классическом” мире p = v. Однако в квантовом мире p может быть гораздо больше чем v:
Факт 2. Для любого ε>0 существует система с p > 1 - ε и v < ε (размер конечного поля зависит от ε).
Комбинаторная оптимизация. Теперь давайте посмотрим на задачу с точки зрения комбинаторной оптимизации. Нам дана система и мы хотим найти оптимальное решение (в котором выполняется наибольшее число уравнений), т.е. найти v. Эта задача NP-сложная: мы не можем найти точное решение за полиномиальное время (если P≠NP). Можем ли мы хотя бы как-то оценить v? Да, мы знаем, что v ≤ p (Факт 1). Эта оценка на v конструктивна — оказывается, что значение p можно приближенно вычислить с помощью “semi-definite programming” за полиномиальное время.
Правда, как мы знаем (Факт 2), в некоторых случаях p очень плохо приближает v. Самое удивительное, что тем не менее, если так называемая Unique Games Conjecture верна, эта оценка для v через вероятность успеха квантового эксперимента оптимальна! (Грубо говоря, не существует эффективно вычислимой более сильной оценки сверху.)
Re: квантовые “уникальные игры”
Re: квантовые “уникальные игры”
Re: квантовые “уникальные игры”
поскольку (пока?) не разобрался с этим, я опирался только на эту фраз и ничего более (но я кажется понимаю о чем Вы).
но в любом случае похоже что "пациент больше мертв чем жив"? или это только так на глаз игнорамуса?
Re: квантовые “уникальные игры”
>> "пациент больше мертв чем жив"
Я бы так не сказал... Я думаю, что большинство специалистов скорее считает, что Unique Games Conjecture верна.
Re: квантовые “уникальные игры”
this is interesting - even despite your results and those of Barak et al?
Re: квантовые “уникальные игры”
Re: квантовые “уникальные игры”