Саша, интересно, что “квантовая телепатия”, о которой ты пишешь, тесно связана с комбинаторной оптимизацией.
Эксперимент по квантовой телепатии. Организаторы эксперимента пишут на доске систему линейных уравнений над конечным полем, в которой в каждое уравнение входят всего две переменные. В комнату приглашают двух участников, показывают им систему уравнений и дают договориться об общей стратегии. Затем участников разводят по разным комнатам. Организаторы тайно выбирают одно из уравнений в системе случайным образом, и просят одного из участников назвать значение одной переменной, входящей в уравнение, другого — другой. Эксперимент признаётся успешным если названные значения удовлетворяют уравнению.
Какова вероятность успеха 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 через вероятность успеха квантового эксперимента оптимальна! (Грубо говоря, не существует эффективно вычислимой более сильной оценки сверху.)
квантовые “уникальные игры”
Эксперимент по квантовой телепатии. Организаторы эксперимента пишут на доске систему линейных уравнений над конечным полем, в которой в каждое уравнение входят всего две переменные. В комнату приглашают двух участников, показывают им систему уравнений и дают договориться об общей стратегии. Затем участников разводят по разным комнатам. Организаторы тайно выбирают одно из уравнений в системе случайным образом, и просят одного из участников назвать значение одной переменной, входящей в уравнение, другого — другой. Эксперимент признаётся успешным если названные значения удовлетворяют уравнению.
Какова вероятность успеха 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 через вероятность успеха квантового эксперимента оптимальна! (Грубо говоря, не существует эффективно вычислимой более сильной оценки сверху.)