![[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}
no subject
Что касается реальной осуществимости игры съ коробочками отъ RSA, то въ теоріи здѣсь всё очень красиво, удивительно и замѣчательно. Но на практикѣ возникаетъ проблема, которую я бы сформулировалъ наглядно какъ слѣдующее противорѣчіе: съ одной стороны, частица должна быть въ коробочкѣ хорошо изолирована, чтобы не разрушалось квантовое состояніе. А съ другой стороны, мы должны быть въ состояніи эту частицу перенести куда-то вмѣстѣ съ коробочкой, а значитъ, частица не можетъ быть тамъ вполнѣ изолирована, а должна быть привязана къ коробочкѣ. Можно ли это осуществить, чтобы состояніе не разрушалось за доли секунды - не знаю.
Мнѣ кажется, что такая же проблема - вообще съ квантовыми компьютерами. Съ одной стороны, нуженъ милліонъ кубитовъ, которые всѣ находятся въ сложномъ, сплетенномъ квантовомъ состояніи, которое не разрушается, значитъ надо, чтобы система кубитовъ была хорошо изолирована. Съ другой стороны, необходимо имѣть возможность производить макроскопическія операціи сразу со всѣми кубитами ("вычисленіе"), значитъ, надо имѣть физическое взаимодѣйствіе всѣхъ кубитовъ съ нѣкимъ внѣшнимъ макроскопическимъ объектомъ. Это противорѣчитъ требованію изолированности. На мой взглядъ (не спеціалиста), это противорѣчіе становится тѣмъ непреодолимѣе, чѣмъ больше кубитовъ мы хотимъ вложить въ одну систему. Поэтому я думаю, что квантовыхъ компьютеровъ никогда не будетъ, потому что созданіе квантоваго компьютера на N кубитовъ есть инженерная задача, становящаяся экспоненціально болѣе трудной съ растущимъ N, въ отличіе отъ классическихъ компьютеровъ, гдѣ ростъ трудности - линейный.
вроде
вообще-то само это открытие - возможность превзойти классически оптимальную стратегию - замечательно независимо от всяких квантовых компьютеров
no subject
no subject
(Anonymous) 2010-08-19 05:40 pm (UTC)(link)mea