Статья дня
https://arxiv.org/abs/2001.04383
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. MIP*=RE.
IP — это класс языков, которые распознаются эффективным алгоритмом проверки, который имеет доступ к доказывателям произвольной вычислительной мощности. Если разрешить доступ к нескольким доказывателям, у которых к тому же есть общее квантово запутанное состояние, получится класс MIP*. Оказывается, этот класс совпадает с классом всех рекурсивно перечислимых языков; в частности, он содержит проблему останова.
Доказательство основано на изучении «корреляционных множеств»: наборов вещественных чисел, описывающих некоторые вероятностные распределения, порождаемые квантовой механикой. Определение этих множеств довольно несложно и не использует ничего кроме определения гильбертова пространства. Оказывается, эти множества имеют очень сложную структуру с точки зрения теории вычислений: вопрос принадлежности точки не может быть определен машиной Тьюринга (что доказывается прямым сведением проблемы останова к этому вопросу).
Одним из следствий доказанного равенства классов является отрицательное решение проблемы Конна (Connes embedding problem) в теории алгебр фон Неймана.
https://arxiv.org/abs/2001.04383
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. MIP*=RE.
IP — это класс языков, которые распознаются эффективным алгоритмом проверки, который имеет доступ к доказывателям произвольной вычислительной мощности. Если разрешить доступ к нескольким доказывателям, у которых к тому же есть общее квантово запутанное состояние, получится класс MIP*. Оказывается, этот класс совпадает с классом всех рекурсивно перечислимых языков; в частности, он содержит проблему останова.
Доказательство основано на изучении «корреляционных множеств»: наборов вещественных чисел, описывающих некоторые вероятностные распределения, порождаемые квантовой механикой. Определение этих множеств довольно несложно и не использует ничего кроме определения гильбертова пространства. Оказывается, эти множества имеют очень сложную структуру с точки зрения теории вычислений: вопрос принадлежности точки не может быть определен машиной Тьюринга (что доказывается прямым сведением проблемы останова к этому вопросу).
Одним из следствий доказанного равенства классов является отрицательное решение проблемы Конна (Connes embedding problem) в теории алгебр фон Неймана.
Article of the day
https://arxiv.org/abs/2001.04383
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. MIP * = RE.
IP is a class of languages that are recognized by an efficient validation algorithm that has access to provers of arbitrary computing power. If you allow access to multiple provers who also have a common quantum entanglement state, you get the MIP * class. It turns out that this class is the same as the class of all recursively enumerated languages; in particular, it contains a halting problem.
The proof is based on the study of "correlation sets": sets of real numbers that describe some probability distributions generated by quantum mechanics. The definition of these sets is fairly straightforward and does not use anything other than the definition of a Hilbert space. It turns out that these sets have a very complex structure from the point of view of computational theory: the question of whether a point belongs to a point cannot be determined by a Turing machine (which is proved by directly reducing the halting problem to this question).
One of the consequences of the proved class equality is the negative solution of the Connes embedding problem in the theory of von Neumann algebras.
https://arxiv.org/abs/2001.04383
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. MIP * = RE.
IP is a class of languages that are recognized by an efficient validation algorithm that has access to provers of arbitrary computing power. If you allow access to multiple provers who also have a common quantum entanglement state, you get the MIP * class. It turns out that this class is the same as the class of all recursively enumerated languages; in particular, it contains a halting problem.
The proof is based on the study of "correlation sets": sets of real numbers that describe some probability distributions generated by quantum mechanics. The definition of these sets is fairly straightforward and does not use anything other than the definition of a Hilbert space. It turns out that these sets have a very complex structure from the point of view of computational theory: the question of whether a point belongs to a point cannot be determined by a Turing machine (which is proved by directly reducing the halting problem to this question).
One of the consequences of the proved class equality is the negative solution of the Connes embedding problem in the theory of von Neumann algebras.
У записи 5 лайков,
2 репостов,
587 просмотров.
2 репостов,
587 просмотров.
Эту запись оставил(а) на своей стене Александр Лузгарев
