![[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
вроде
Re: вроде
no subject
no subject
Что касается реальной осуществимости игры съ коробочками отъ RSA, то въ теоріи здѣсь всё очень красиво, удивительно и замѣчательно. Но на практикѣ возникаетъ проблема, которую я бы сформулировалъ наглядно какъ слѣдующее противорѣчіе: съ одной стороны, частица должна быть въ коробочкѣ хорошо изолирована, чтобы не разрушалось квантовое состояніе. А съ другой стороны, мы должны быть въ состояніи эту частицу перенести куда-то вмѣстѣ съ коробочкой, а значитъ, частица не можетъ быть тамъ вполнѣ изолирована, а должна быть привязана къ коробочкѣ. Можно ли это осуществить, чтобы состояніе не разрушалось за доли секунды - не знаю.
Мнѣ кажется, что такая же проблема - вообще съ квантовыми компьютерами. Съ одной стороны, нуженъ милліонъ кубитовъ, которые всѣ находятся въ сложномъ, сплетенномъ квантовомъ состояніи, которое не разрушается, значитъ надо, чтобы система кубитовъ была хорошо изолирована. Съ другой стороны, необходимо имѣть возможность производить макроскопическія операціи сразу со всѣми кубитами ("вычисленіе"), значитъ, надо имѣть физическое взаимодѣйствіе всѣхъ кубитовъ съ нѣкимъ внѣшнимъ макроскопическимъ объектомъ. Это противорѣчитъ требованію изолированности. На мой взглядъ (не спеціалиста), это противорѣчіе становится тѣмъ непреодолимѣе, чѣмъ больше кубитовъ мы хотимъ вложить въ одну систему. Поэтому я думаю, что квантовыхъ компьютеровъ никогда не будетъ, потому что созданіе квантоваго компьютера на N кубитовъ есть инженерная задача, становящаяся экспоненціально болѣе трудной съ растущимъ N, въ отличіе отъ классическихъ компьютеровъ, гдѣ ростъ трудности - линейный.
вроде
(no subject)
(no subject)
(Anonymous) - 2010-08-19 17:40 (UTC) - Expandmea
no subject
ну как сказать -
Re: ну как сказать -
я примерно
(no subject)
(no subject)
(no subject)
no subject
ну вроде
Re: ну вроде
ну да,
no subject
(Anonymous) 2010-08-15 11:21 am (UTC)(link)подозреваю, что нет,
no subject
(no subject)
(Anonymous) - 2010-08-15 15:18 (UTC) - Expandда, конечно,
Re: да, конечно,
то есть на
Re: то есть на
спасибо -
Re: спасибо -
no subject
а можно плз ссылки на этих computer scientists?
я сам видел только пересказ,
Re: я сам видел только пересказ,
специалисты
квантовые “уникальные игры”
Эксперимент по квантовой телепатии. Организаторы эксперимента пишут на доске систему линейных уравнений над конечным полем, в которой в каждое уравнение входят всего две переменные. В комнату приглашают двух участников, показывают им систему уравнений и дают договориться об общей стратегии. Затем участников разводят по разным комнатам. Организаторы тайно выбирают одно из уравнений в системе случайным образом, и просят одного из участников назвать значение одной переменной, входящей в уравнение, другого — другой. Эксперимент признаётся успешным если названные значения удовлетворяют уравнению.
Какова вероятность успеха 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: квантовые “уникальные игры”
Re: квантовые “уникальные игры”
Re: квантовые “уникальные игры”
Re: квантовые “уникальные игры”
no subject
(no subject)
фокус в том,
no subject
no subject
Если игроки и игра быстрые, то из имплементаций квантовой криптографии, вроде, следует, что это возможно:
http://en.wikipedia.org/wiki/Quantum_cryptography#Implementations
Что касается времени распада, то, вроде, люди говорят, что достигли времён порядка одной секунды:
http://www.nsf.gov/news/news_summ.jsp?cntn_id=112538&govDel=USNSF_51
(via http://en.wikipedia.org/wiki/Timeline_of_quantum_computing )
off topic
Рассмотрим алгоритм, берущий на входе некоторый набор аксиом арифметики, и производящий диофантовый полином, не имеющий целых корней, такой, что несуществование корней для этого полинома недоказуемо в той арифметике, которую подали на вход.
В построении такого алгоритма и доказательстве того, что он даёт именно такие полиномы, вроде бы, и состоит теорема Матиасевича.
Если бы это рассуждение, включая всё, что нужно для доказательства теоремы Матиасевича, можно было бы провести в рамках некоторой конкретной арифметики P, то, вроде бы, это даёт ещё и доказательство в рамках этой же самой арифметики, что "полином Матиасевича" не имеет корней, тем самым приводя к парадоксу (поскольку как раз это и должно быть недоказуемо в рамках арифметики P).
Поскольку мы не верим, что есть парадокс, значит что-то в этой цепочке не формализуется в рамках арифметики. Но что именно?
(Что-то похожее люди спрашивают и про теорему Гёделя, но про диофантовы полиномы проще думать.)
ну так
(no subject)
резульаты
Re: резульаты
Re: резульаты
Re: резульаты
Re: резульаты
(no subject)
утверждение
no subject
(no subject)