квантовая механика и телепатия
Aug. 15th, 2010 08:42 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
a_shenРассмотрим такую странную игру для команды из двух человек. Их разводят по разным комнатам и сообщают каждому случайный бит 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}
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
резульаты
Date: 2010-08-20 08:51 pm (UTC)Re: резульаты
Date: 2010-08-20 09:31 pm (UTC)Да, конечно.
Я не вполне понимаю, почему это не преобразуется в формальное доказательство отсутствия корней в рамках данной арифметики (и, тем самым, в доказательство противоречивости данной арифметики) следующим способом: рассмотрим арифметику P; из утверждения "неверно, что данный полином не имеет корней" следует, что из P выводим "false"; тем самым из P следует, что из утверждения "неверно, что данный полином не имеет корней" следует "false"; тем самым из P следует, что "данный полином не имеет корней".
Re: резульаты
Date: 2010-08-20 10:47 pm (UTC)"многочлен имеет корни <-> P противоречива"
"доказуемо, что многочлен не имеет корней <-> доказуема непротиворечивость <-> теория P противоречива"
но не более
Re: резульаты
Date: 2010-08-20 11:23 pm (UTC)1) в P выводимо: "если доказуемо, что P непротиворечива, то P противоречива"
2) в P выводимо: "многочлен имеет корни <-> P противоречива"
и
3) в P выводимо: "доказуемо, что многочлен не имеет корней <-> доказуема непротиворечивость <-> теория P противоречива"
?
Я пытаюсь дополнить это до утверждения, что в P выводимо "теория P противоречива", и не вижу, где дырка. Примерно следующим образом:
4) если в P выводимо, что "многочлен имеет корни <-> P противоречива", то в P выводимо, что "многочлен имеет корни -> false". (Используя то обстоятельство, что противоречивая P должна позволить вывести false.)
5) Если в P выводимо, что "многочлен имеет корни -> false",
то в P выводимо, что многочлен не имеет корней. (Используя то обстоятельство, что P имеет правила вывода классической логики.)
6) Сочетая 3) и 5), получаем, что (в P выводимо, что) P противоречива.
Re: резульаты
Date: 2010-08-20 11:29 pm (UTC)no subject
Date: 2010-08-21 01:03 am (UTC)На самом деле, это верно для A, выводимых в P, но вовсе не для всех A. В частности, теорема Гёделя как раз говорит, что если A=false, то утверждение "в P выводимо false -> false", может быть выводимо в P если и только если в P выводимо false.
Ошибка в этой схеме как раз в использовании "в P выводимо false -> false".
утверждение
Date: 2010-08-21 05:35 am (UTC)