Consecuencias de$MIP^\ast=RE$Acerca de los algoritmos cuánticos
La prueba (pendiente de revisión por pares) de$MIP^\ast=RE$en esta preimpresión ha sido aclamado como un avance significativo. Henry Yuen (uno de los autores) aborda la importancia de este resultado en esta publicación de blog . Scott Aaronson también enumera algunas de las principales implicaciones en esta publicación de blog .
Para un juego no local ($G$), define el supremo de las probabilidades de éxito para las estrategias de productos tensoriales no relativistas como$\omega^\ast(G)$, y el supremo de probabilidades de éxito para una estrategia de operador de conmutación relativista (QFT) como$\omega^{co}(G)$. Dado que QM no relativista es un caso especial de QFT, está claro que una estrategia óptima basada en operadores de conmutación es al menos tan buena como una estrategia óptima basada en productos tensoriales,$\omega^\ast(G) \le \omega^{co}(G)$.
Mi entendimiento de la publicación de Yuen es que una consecuencia de$MIP^\ast=RE$es que existen juegos no locales para los cuales$\omega^\ast(G) < \omega^{co}(G)$. En concreto, dice
debe haber un juego$G$, entonces, para el cual el valor cuántico es diferente del valor del operador de conmutación. Pero esto implica que el problema de Tsirelson tiene una respuesta negativa y, por lo tanto, la conjetura de incrustación de Connes es falsa.
Entiendo que esto significa que hay una clase de problemas para los cuales los algoritmos que usan técnicas de QFT (operadores de conmutación) tienen mayores probabilidades de éxito que los algoritmos que usan técnicas de QM no relativista (productos tensoriales, formalismo de circuito cuántico).
La primera parte de mi pregunta es, suponiendo que esta prueba sea válida :
- Lo hace$MIP^\ast=RE$implica que hay un conjunto de problemas que se pueden resolver de manera más eficiente empleando el formalismo matemático de QFT (operadores de conmutación) en lugar del formalismo QM no relativista (circuitos cuánticos convencionales)?
A menos que lo esté malinterpretando, esto parece seguirse directamente de las declaraciones de Yuen. Si es así, ¿es posible que exista un conjunto de juegos no locales para los cuales$\omega^\ast(G) < 0.5$y$\omega^{co}(G) > 0.5$? Específicamente, la segunda parte de mi pregunta es:
- Lo hace$MIP^\ast=RE$¿Implica que hay (o podría haber) un conjunto de problemas que pueden resolverse usando operadores de conmutación que no pueden resolverse usando circuitos cuánticos, o esta posibilidad está cerrada por la universalidad del modelo de circuito cuántico?
EDITAR: Henry Yuen ha creado un MIP* Wiki para aquellos interesados en comprender mejor esta clase de complejidad o el$MIP^\ast = RE$resultado.
Respuestas
No sé si el resultado MIP* = RE, y en particular la afirmación de que existe un juego no local$G$dónde$\omega^*(G) \neq \omega^{co}(G)$, tiene implicaciones algorítmicas para las computadoras cuánticas. Hay un par de cosas que decir aquí.
El resultado MIP* = RE se trata de qué problemas computacionales se pueden verificar usando juegos no locales, a diferencia de lo que se puede resolver con juegos no locales (¡no estoy seguro de lo que eso significaría, de todos modos!). La distinción entre verificar y resolver se debe a lo siguiente: en un juego no local, asumimos que Alice y Bob saben mágicamente la respuesta al problema (así que asumimos que pueden resolver cualquier problema computacional instantáneamente). Su desafío no es resolverlo, sino probara un verificador clásico de tiempo polinomial saben la respuesta. El simple hecho de saber la respuesta a algo no significa que puedas convencer a otra persona de la respuesta. El hecho de que Alice y Bob puedan usar correlaciones del marco del producto tensorial o del marco del operador de conmutación afecta lo que pueden demostrar al verificador. MIP* = RE muestra que, con las correlaciones del producto tensorial, Alice y Bob pueden demostrar que saben que una máquina de Turing finalmente se detiene. Esto es algo que no se puede hacer si Alice y Bob comparten correlaciones de operadores de conmutación; por lo tanto, el modelo de operador de conmutación difiere del modelo de producto tensorial.
Lo segundo que quería mencionar es que, por separado, es una pregunta interesante si se puede definir un modelo de computación cuántica que hable de operadores conmutados y sistemas de dimensión infinita. Parece que Cleve, et al han tratado de encontrar un modelo para esto, algo que ellos llaman el modelo de circuito C*:https://arxiv.org/pdf/1811.12575.pdf. Podrias encontrar esto interesante.