Consequências do

33

Como amador do TCS, estou lendo algum material popular e muito introdutório sobre computação quântica. Aqui estão alguns bits elementares de informações que aprendi até agora:

  1. Os computadores quânticos não são conhecidos por resolver problemas de NP-completos em tempo polinomial.
  2. "A magia quântica não será suficiente" (Bennett et al. 1997): se você jogar fora a estrutura do problema e considerar apenas o espaço de soluções possíveis, mesmo um computador quântico precisará de cerca de etapas para encontrar a correta (usando o algoritmo de Grover)2n2n
  3. Se um algoritmo de tempo polinomial quântico para um problema completo de NP for encontrado, ele deve explorar a estrutura do problema de alguma maneira (caso contrário, o marcador 2 seria contraditado).

Eu tenho algumas perguntas (básicas) que ninguém parece ter feito até agora neste site (talvez porque sejam básicas). Suponha que alguém encontre um algoritmo de tempo polinomial quântico de erro limitado para (ou qualquer outro problema completo do NP), colocando no e implicando .SUMATSUMATBQPNPBQP

Questões

  1. Quais seriam as consequências teóricas dessa descoberta? Como o quadro geral das classes de complexidade seria afetado? Quais classes se tornariam iguais a quais outras?
  2. Um resultado como esse parece sugerir que os computadores quânticos têm um poder inerentemente superior aos computadores clássicos. Quais seriam as consequências de um resultado como esse na física? Emanaria alguma luz sobre qualquer problema em aberto na física? A física seria alterada após um resultado semelhante? A lei da física como a conhecemos seria afetada?
  3. A possibilidade (ou não) de explorar a estrutura do problema de uma maneira bastante geral (ou seja, independente de instância específica) parece ser o cerne da questão P = NP. Agora, se for encontrado um algoritmo quântico de tempo polinomial de erro limitado para , e ele deve explorar a estrutura do problema, sua estratégia de exploração da estrutura não seria utilizável também no cenário clássico? Existe alguma evidência indicando que tal exploração de estrutura possa ser possível para computadores quânticos, permanecendo impossível para computadores clássicos?SUMAT
Giorgio Camerani
fonte
11
@ Walther: Notei que você atualizou a pergunta para adicionar um pouco sobre uma aceleração exponencial, mas, francamente, a distinção entre acelerações polinomiais e exponenciais é um tanto artificial, e por isso não vejo isso afetando a física de maneira alguma.
21811 Joe Fitzsimons
@ Joe: Eu adicionei isso apenas para esclarecer o que eu tinha em mente quando fiz a pergunta (ou seja, que o quantum pareceria mais poderoso do que o clássico no sentido de que o primeiro resolveria problemas completos de NP em tempo polinomial, enquanto o ainda não ou nunca). Mas agora vejo que se alguém lê a versão atual da pergunta e depois lê a sua resposta, ele pode estar errado e pensar que uma frase da sua resposta está errada: é por isso que vou remover essa parte.
Giorgio camerani
Desculpe, não pretendi sugerir que você o reformule.
21811 Joe Fitzsimons
@ Joe: Não, não se preocupe! ;-) Realmente, não quero que a pergunta e suas respostas estejam desalinhadas: seria confuso para os leitores e injusto para as pessoas que responderam.
Giorgio camerani
11
Artigo SEP .
Kaveh

Respostas:

18

Não vou tentar responder à primeira pergunta, pois alguém como Scott Aaronson, Peter Shor ou John Watrous pode, sem dúvida, fornecer uma resposta muito mais abrangente nesse aspecto.

Com relação à pergunta 2, é importante observar que os computadores quânticos são de fato mais poderosos que os computadores clássicos em muitos casos:

  1. Existe uma aceleração polinomial bastante genérica obtida por computadores quânticos em relação a computadores clássicos em vários problemas. Do ponto de vista da complexidade, isso talvez seja um pouco menos interessante que uma aceleração exponencial, mas é algo que podemos realmente provar.
  2. A complexidade da comunicação quântica geralmente pode variar drasticamente da complexidade da comunicação clássica para o mesmo problema. Novamente, isso é algo que pode ser provado (veja, por exemplo, o jogo Mermin-GHZ).
  3. Consultas quânticas para oráculos são frequentemente muito mais poderosas do que consultas clássicas para o mesmo oráculo (veja, por exemplo, o algoritmo Deutsch-Josza).

Com isso em mente, já se sabe que os computadores quânticos são fundamentalmente mais poderosos que os computadores clássicos. Eu acho que estaria correto ao dizer que a maioria dos físicos que trabalham com essas coisas já presumiria que não é possível encontrar um algoritmo clássico para simular com eficiência todos os sistemas quânticos, e, enquanto isso, um resultado mostrando que NP estava contido no BQP certamente seria surpreendente, não seria particularmente provável fornecer uma inovação na compreensão de qualquer fenômeno físico em particular. Em vez disso, forneceria evidências um pouco mais fortes de que a física quântica é difícil de simular.

Não existe uma física fundamental que dependa da complexidade computacional da simulação, portanto, encontrar um algoritmo quântico eficiente para um problema completo de NP não teria consequências fundamentais para a correção de nossa compreensão atual de como o universo funciona (embora eu esteja inclinado concordar com a sugestão de Scott Aaronson de que é interessante ver se você poderia ter leis físicas emergindo de suposições computacionais).

É extremamente tentador dizer que isso teria consequências para a evolução adiabática dos sistemas quânticos (e acho que você pode obter uma resposta ou duas sugerindo isso), etc., mas isso seria incorreto, pois eles são governados por um processo físico específico , e mostrar que, em princípio, é possível resolver o SAT em tempo polinomial em um computador quântico, não diria nada sobre sua evolução específica.

Com relação à sua última pergunta, já temos exemplos em que a estrutura do problema é explorada para gerar um algoritmo quântico polinomial, mas que não leva a um algoritmo clássico (fatoração, por exemplo). Portanto, no que diz respeito a nosso entendimento atual, um problema com uma estrutura explorável para produzir um algoritmo quântico de tempo polinomial não implica que a estrutura seja explorável para produzir um algoritmo clássico de tempo polinomial.

Joe Fitzsimons
fonte
16

Scott Aaronson costumava gostar de apontar (e provavelmente ainda gosta de apontar, assumindo que não se cansou de fazê-lo) que os processos físicos nem sempre encontram o mínimo global de um cenário energético . Em particular, se você formular uma instância de um problema de otimização completo de NP como um problema de minimização de energia para um sistema físico, não há razão - teórica ou empírica - para acreditar que esse sistema físico "relaxará" após algum tempo para uma solução do problema ( ou seja,  uma configuração de energia que seja um mínimo global). É mais provável que relaxe para um mínimo local: um para o qual configurações ligeiramente diferentes requerem mais energia, mas onde uma configuração substancialmente diferente pode ter menos energia.

Portanto, ao provar o NP  ⊆  BQP seria um triunfo de primeira ordem - para todos os teóricos da complexidade, não apenas para os teóricos da computação quântica -, sugeriria que há toda uma nova teoria dos modelos "físicos" de computação esperando para serem descobertos. Por quê? Bem, modelos de computação podem ser interpretados como modelos de física (embora altamente especializados): a saber, quais recursos computacionais são fisicamente razoáveis. Um dos 'slogans' da computação quântica é que Nature isn't classical, [darn] it - a menos que você pode simular a mecânica quântica em um computador clássico, o que você pode fisicamente calcular de forma eficiente é quase certamente mais poderoso do que P . E, no entanto, temos evidências de que é menos poderoso que o NP; então teria que ser menos poderoso que o BQP também, se isso acontecesse com o NP  ⊆  BQP .

Portanto, uma prova de NP  ⊆  BQP nos apresentaria um trilema:

  1. os circuitos quânticos podem ser simulados eficientemente em um computador clássico, provando NP  ⊆  BQP  ⊆  P , superando assim os sonhos ou pesadelos mais loucos de todos os teóricos;
  2. os circuitos quânticos não podem ser simulados em um computador clássico, mas os computadores quânticos escalonáveis ​​podem ser construídos para resolver problemas no NP , dando origem a um interesse verdadeiramente explosivo na computação quântica e garantindo que os físicos experimentais tenham segurança na carreira no futuro previsível;
  3. existe outro modelo de computação esperando para ser descoberto, intermediário entre P e BQP em potência, que descreve (ou melhor, aproxima-se melhor ) o que é eficientemente computável fisicamente.

Suspeito que o dinheiro inteligente esteja no terceiro lugar, tão divertido quanto o primeiro ou o segundo seria do ponto de vista acadêmico.

 Com desculpas a Feynman, que eu suspeito que nem sempre poupou suas maldições.

Niel de Beaudrap
fonte
11
Certamente, a possibilidade 2 não é uma possibilidade risível (mesmo, devo enfatizar, na situação hipotética que NP P BQP ). Mas seu argumento também pode ser usado para argumentar a favor do número 1. Dada a escolha entre as três possibilidades, escolho a terceira, porque é a possibilidade mais conservadora; mas também porque acho importante enfatizar que existem, em princípio, boas razões físicas e empíricas para fazer conjecturas teóricas da complexidade.
Niel de Beaudrap
3
@ Neil: Eu realmente discordo. Não considero conservador (ao contrário) afirmar que a mecânica quântica provavelmente está errada porque os computadores quânticos seriam poderosos. Simplesmente não há evidência para 1, razão pela qual o argumento não se aplicaria. Há uma enorme evidência de que a computação quântica é, pelo menos em princípio, possível.
21811 Joe Fitzsimons
11
@ Joe: Claro, nossos modelos de CQ são excelentes abstrações de QM (que por si só é uma teoria muito boa), tanto quanto podemos dizer. Ele também admite limites razoáveis ​​de erro, em princípio, e espera por uma correção de erro compostável. Mas é difícil o suficiente colocar todas as peças no lugar para obter operações silenciosas, não é? De qualquer forma, estamos falando de contrafactuais aqui, e a condição aqui é uma confusão - você pode me dizer que um resultado como NPBQP não daria a você um momento para pensar que, talvez, haja um grande problema esperando para QC em algum lugar?
Niel de Beaudrap
2
3
@ Neil: Na verdade, 2 parece ser o caso agora. Eu realmente duvido que BQP = P , então os circuitos quânticos provavelmente não podem ser simulados de forma eficiente classicamente. No entanto, há todas as indicações de que podemos de fato construir computadores quânticos (embora seja complicado!).
18711 Joe Fitzsimons