Consequências de$MIP^\ast=RE$Sobre algoritmos quânticos
A prova (pendente de revisão por pares) de$MIP^\ast=RE$nesta pré-impressão foi saudado como um avanço significativo. A importância desse resultado é abordada por Henry Yuen (um dos autores) nesta postagem do blog . Scott Aaronson também lista algumas das principais implicações neste post de blog .
Para um jogo não local ($G$), defina o máximo de probabilidades de sucesso para estratégias de produtos de tensores não relativísticos como$\omega^\ast(G)$, e o máximo de probabilidades de sucesso para uma estratégia de operador de comutação relativística (QFT) como$\omega^{co}(G)$. Como o QM não relativístico é um caso especial de QFT, fica claro que uma estratégia ótima baseada em operador de comutação é pelo menos tão boa quanto uma estratégia ótima baseada em produto tensorial,$\omega^\ast(G) \le \omega^{co}(G)$.
Meu entendimento da postagem de Yuen é que uma consequência de$MIP^\ast=RE$é que existem jogos não locais para os quais$\omega^\ast(G) < \omega^{co}(G)$. Especificamente, ele diz
Deve haver um jogo$G$, então, para o qual o valor quântico é diferente do valor do operador de comutação. Mas isso implica que o problema de Tsirelson tem uma resposta negativa e, portanto, a conjectura de imersão de Connes é falsa.
Entendo que isso significa que existe uma classe de problemas para os quais os algoritmos que usam técnicas de QFT (operadores de comutação) têm probabilidades de sucesso mais altas do que os algoritmos que usam técnicas de QM não relativístico (produtos de tensores, formalismo de circuito quântico).
A primeira parte da minha pergunta é, supondo que esta prova seja válida :
- Faz$MIP^\ast=RE$implica que existe um conjunto de problemas que podem ser resolvidos de forma mais eficiente empregando o formalismo matemático de QFT (operadores de comutação) em vez do formalismo QM não relativístico (circuitos quânticos convencionais)?
A menos que eu esteja interpretando mal, isso parece decorrer diretamente das declarações de Yuen. Se for assim, é possível que exista um conjunto de jogos não locais para os quais$\omega^\ast(G) < 0.5$e$\omega^{co}(G) > 0.5$? Especificamente, a segunda parte da minha pergunta é:
- Faz$MIP^\ast=RE$implica que existe (ou pode haver) um conjunto de problemas que podem ser resolvidos usando operadores de comutação que não podem ser resolvidos usando circuitos quânticos, ou essa possibilidade é descartada pela universalidade do modelo de circuito quântico?
EDIT: Henry Yuen criou um MIP* Wiki para os interessados em entender melhor esta classe de complexidade ou o$MIP^\ast = RE$resultado.
Respostas
Não sei se o resultado MIP* = RE, e em particular a alegação de que existe um jogo não local$G$Onde$\omega^*(G) \neq \omega^{co}(G)$, tem implicações algorítmicas para computadores quânticos. Há algumas coisas a dizer aqui.
O resultado MIP* = RE é sobre quais problemas computacionais podem ser verificados usando jogos não locais, em oposição ao que pode ser resolvido por jogos não locais (não tenho certeza do que isso significaria, de qualquer maneira!). A distinção entre verificar e resolver se deve ao seguinte: em um jogo não local, supomos que Alice e Bob saibam magicamente a resposta para o problema (portanto, supomos que eles podem resolver qualquer problema computacional instantaneamente). Seu desafio não é resolvê-lo, mas provarpara um verificador clássico de tempo polinomial, eles sabem a resposta. Apenas saber a resposta para algo não significa que você é capaz de convencer outra pessoa da resposta. Se Alice e Bob podem usar correlações da estrutura do produto tensor ou da estrutura do operador de comutação afeta o que eles podem provar ao verificador. MIP* = RE mostra que, com correlações de produto tensorial, Alice e Bob podem provar que sabem que uma Máquina de Turing eventualmente para. Isso é algo que não pode ser feito se Alice e Bob compartilham correlações de operador de comutação; portanto, o modelo do operador de comutação difere do modelo do produto tensorial.
A segunda coisa que gostaria de mencionar é, separadamente, que é uma questão interessante se alguém pode definir um modelo de computação quântica que fale sobre operadores de comutação e sistemas de dimensão infinita. Parece que Cleve e outros tentaram criar um modelo para isso, algo que eles chamam de modelo de circuito C*:https://arxiv.org/pdf/1811.12575.pdf. Você pode achar isto interessante.