Existe uma prova formal de que a computação quântica é ou será mais rápida que a computação clássica?

15

Em vez de evidências empíricas, por quais princípios formais provamos que a computação quântica será mais rápida que a computação tradicional / clássica?

Alex Moore-Niemi
fonte
5
@ vzn: o modelo de circuito tem implementação em armadilhas de íons, que em breve deve ser capaz de lidar com cerca de 10 qubits. A máquina Dwave não implementa o modelo adiabático, mas algo chamado "recozimento quântico", que atualmente não é conhecido por produzir uma aceleração conjectural para qualquer problema.
precisa
4
@ vzn: Você sempre pode olhar para este artigo da wikipedia (vinculado ao artigo ao qual você vinculou). A computação adiabática quântica deve permanecer no estado fundamental. O recozimento quântico não precisa. Da wikipedia: "Se a taxa de mudança [em um processador quântico de recozimento] do campo transversal for lenta o suficiente, o sistema permanecerá próximo ao estado fundamental do Hamiltoniano instantâneo, isto é, computação quântica adiabática". A DWave recentemente parou de dizer que estava fazendo "computação adiabática quântica" e começou a dizer que estava fazendo "recozimento quântico".
Peter Shor
2
@hadsed: Estou bastante confiante de que a DWave implementará um Hamiltoniano mais versátil em breve, mas isso não resolverá o problema que eles têm de estar operando a uma temperatura acima da diferença de energia.
Peter Shor
5
@vzn poderia ou deveria? conjectura ou previsão? você pode se decidir sobre as palavras a usar?
precisa
5
@vzn: se você acha que Feynman não considera necessário / útil / bom fazer simulações, então você realmente não entende Richard Feynman. Não confunda a diferença de atitude da parte dele em relação ao que "conhecimento" consiste, com preguiça intelectual e uma propensão a construir castelos no céu. Essa era uma abordagem inquisitiva e exigente da ciência, que deve ser imitada; se ele não se preocupava muito com a prova matemática em particular, isso apenas indica que ele não era o principal matemático. (Nem, no entanto, você está abordando a questão como um matemático!)
Niel de Beaudrap

Respostas:

23

Essa é uma pergunta um pouco difícil de descompactar se você não estiver familiarizado com a complexidade computacional. Como a maior parte do campo da complexidade computacional, os principais resultados são amplamente considerados, mas conjecturais.

As classes de complexidade tipicamente associadas ao cálculo clássico eficiente são (para algoritmos determinísticos) e B P P (para randomização). A contrapartida quantum dessas classes é B Q P . Todas as três classes são subconjuntos de P S P A C E (uma classe muito poderosa). No entanto, os nossos métodos actuais de prova não são suficientemente fortes para mostrar definitivamente que P não é a mesma coisa que P S P A C E . Assim, não sabemos como separar formalmente P de B Q PPBPPBQPPSPUMACEPPSPUMACEPBQPou - uma vez que , que separa estas duas classes é mais difícil do que a tarefa de separar já formidável P de P S P A C E . (Se pudéssemos provar P B Q P , obteríamos imediatamente uma prova de que P P S P A C E , provando P B Q PPBQPPSPUMACEPPSPACEPBQPPPSPACEPBQPtem que ser pelo menos tão difícil quanto o problema já muito difícil de provar ). Por esse motivo, no atual estado da arte, é difícil obter uma prova matemática rigorosa que mostre que a computação quântica será mais rápida que a computação clássica.PPSPACE

Assim, geralmente confiamos em evidências circunstanciais para separações de classes de complexidade. Nossa evidência mais forte e mais famoso é o algoritmo de Shor que nos permite fator . Por outro lado, não conhecemos nenhum algoritmo que possa levar em consideração B P P - e a maioria das pessoas acredita que um não existe; isso é parte da razão pela qual usamos o RSA para criptografia, por exemplo. Grosso modo, isso implica que é possível que um computador quântico fatore com eficiência, mas sugere que pode não ser possível que um computador clássico fatore com eficiência. Por essas razões, o resultado de Shor sugeriu a muitos que B Q P é estritamente mais poderoso que B P PBQPBPPBQPBPP(e, portanto, também mais poderoso que ).P

Não conheço nenhum argumento sério de que , exceto daquelas pessoas que acreditam em um colapso muito maior da classe de complexidade (que é uma minoria da comunidade). Os argumentos mais sérios que ouvi contra a computação quântica vêm de posições mais próximas da física e argumentam que B Q P não captura corretamente a natureza da computação quântica. Esses argumentos geralmente dizem que estados coerentes macroscópicos são impossíveis de manter e controlar (por exemplo, porque há algum obstáculo físico fundamental ainda desconhecido) e, portanto, os operadores nos quais B Q P conta não podem ser realizados (mesmo em princípio) em nosso mundo. .BQP=PBQPBQP

Se começarmos a mudar para outros modelos de computação, um modelo particularmente fácil de trabalhar é a complexidade da consulta quântica (a versão clássica que corresponde a ela é a complexidade da árvore de decisão). Neste modelo, para funções totais, podemos provar que (para alguns problemas) os algoritmos quânticos podem atingir uma aceleração quadrática, embora também possamos mostrar que, para funções totais, não podemos fazer melhor do que uma potência-6 acelerar e acreditar que quadrático é o Melhor possível. Para funções parciais, é uma história totalmente diferente e podemos provar que são possíveis acelerações exponenciais. Novamente, esses argumentos se baseiam na crença de que temos uma compreensão decente da mecânica quântica e que não existe uma barreira teórica mágica desconhecida para impedir que estados quânticos macroscópicos sejam controlados.

Artem Kaznatcheev
fonte
boa resposta, como e B Q P estão relacionados, presumo (a partir da resposta) que B P P B Q P , ainda assim, limites ou conjecturas para isso? BPPBQPBPPBQP
Nikos M.
1
"porque há algum obstáculo fundamental física ainda desconhecido ..." na verdade, existem muitos físicos conhecidos obstáculos documentados copiosamente por experimentalistas, se eles ou outros desconhecidos são sérios obstáculos é uma questão em aberto ....
vzn
4
@ Nikos: é uma contenção simplesmente provada de classes. Para esboçar: podemos caracterizar B P P por cálculos determinísticos (e reversíveis) atuando na entrada, alguns bits de trabalho preparados como 0s e alguns bits aleatórios que são 0 ou 1 uniformemente aleatoriamente. Na computação quântica, a preparação dos bits aleatórios pode ser simulada por transformações unitárias de bit único adequadas (embora as chamemos de 'qubits' quando permitimos tais transformações). Assim, podemos mostrar facilmente que B P P B Q P , embora não saibamos se essa contenção é rigorosa. BPPBQPBPPBPPBQP
Niel de Beaudrap
@NieldeBeaudrap, obrigado, por que eles não são equivalentes? significando ? Estou faltando sth aqui, não é (também?) B P P uma classe para todos os cálculos aleatórios? BQPBPPBPP
Nikos M.
1
@ Nikos: não, não é uma classe para todos os cálculos aleatórios. Ele tem uma definição matemática específica que determina quais problemas ele contém e não é conhecido por conter B Q P ou algo parecido. Por outro exemplo, P P também é uma classe aleatória (onde a resposta deve ser correta apenas com probabilidade> 1/2, embora não por uma margem significativa) que contenha P B P P B Q P P P e N P P P , onde se espera que todas as contenções sejam rigorosas.BPPBQPPPPBPPBQPPPNPPP
Niel de Beaudrap
7

Para a complexidade computacional, não há provas de que os computadores quânticos sejam melhores que os computadores clássicos devido à dificuldade em obter limites mais baixos da dureza dos problemas. No entanto, existem configurações nas quais um computador quântico prova-se melhor do que um computador clássico. O mais famoso desses exemplos está no modelo de caixa preta no qual você tem acesso via caixa preta a uma função e deseja encontrar o x exclusivo para o qual f é avaliado como 1. A medida de complexidade, neste caso, é o número de chamadas para ff:{0 0,1}n{0 0,1}xff. Clássico, você não pode fazer melhor do que adivinhar aleatoriamente, o que leva em média Ω ( 2 n ) consultas a f . No entanto, usando o algoritmo de Grover, você pode realizar a mesma tarefa em O ( xΩ(2n)f.O(2n)

Para separações mais prováveis, você pode analisar a complexidade da comunicação, onde sabemos como provar limites mais baixos. Existem tarefas que dois computadores quânticos que se comunicam através de um canal quântico podem realizar com menos comunicação do que dois computadores clássicos. Por exemplo, a computação do produto interno de duas cadeias, um dos problemas mais difíceis na complexidade da comunicação, acelera o uso de computadores quânticos.

Philippe Lamontagne
fonte
4

Artem Kaznatcheev fornece um resumo excelente de algumas das principais razões pelas quais esperamos que os computadores quânticos sejam fundamentalmente mais rápidos que os computadores clássicos para algumas tarefas.

Se você quiser uma leitura adicional, pode ler as notas da aula de Scott Aaronson sobre computação quântica , que discutem o algoritmo Shor e outros algoritmos que admitem algoritmos quânticos eficientes, mas não parecem admitir nenhum algoritmo clássico eficiente.

Não é lá é BQP um modelo preciso da realidade, ou é algo que pode nos impedir de construir um computador quântico, quer por razões de engenharia ou por causa de barreiras físicas fundamentais: um debate sobre se os computadores quânticos podem ser construídas na prática? Você pode ler as notas da aula de Scott Aaronson resumindo os argumentos que outros levantaram e também ler sua postagem no blog com sua opinião sobre esse debate , mas provavelmente não teremos uma resposta definitiva até que alguém realmente construa um computador quântico que possa executar tarefas não triviais (como fator de números grandes).

DW
fonte
"mas provavelmente não teremos uma resposta definitiva até que alguém realmente construa um computador quântico que possa executar tarefas não triviais (como fator de números grandes)". isso é algo de pensamento positivo (que permeia o campo) que limita uma frase anterior não sequiturt , "o debate sobre se os computadores QM podem ser construídos na prática, ou existem barreiras etc." é possível que computadores QM escaláveis ​​possam não ser fisicamente realizáveis ​​e nenhuma prova teórica ou experimental estará disponível, apenas relatórios de obstáculos formidáveis ​​(isto é, quase o status atual do campo experimental).
vzn
-2

O edifício básico da computação quântica é a transformação unitária, esta é a principal ferramenta para acelerar em muitos algoritmos da literatura. Algoritmos que usam Unitaries usam propriedades teóricas de número / gráfico de problemas em mãos - descoberta de períodos, acelerações em caminhadas quânticas, etc. Acelerações em problemas naturais ainda são ilusórias - como apontado. Se fatorar grandes números é o fim em si para a computação quântica, ainda é uma questão em aberto. Outras questões em aberto, como a QNC, sua separação da NC ainda poderiam fornecer pistas ilusórias sobre o que os computadores quânticos podem fazer. Mas, se o objetivo do computador quântico é fatorar grandes números - ainda pode ser viável, em si mesmo em algum futuro, com implicações assustadoras (é claro, para a privacidade pessoal)!

user3046538
fonte
1
na verdade, o aumento de velocidade (por exemplo, o algoritmo de Shor) é baseado no princípio da superposição de QM (que é ligeiramente relacionada ao unitarity)
Nikos M.
O "princípio de superposição" é matematicamente equivalente à afirmação de que as distribuições quânticas se transformam linearmente. Os vetores de probabilidade também se transformam linearmente. Seria necessário mais do que o "princípio da superposição" para explicar qualquer separação quântica / clássica.
Niel de Beaudrap
Aliás: embora eu pessoalmente concorde que a unitariedade (em oposição a, digamos, estocástica ) desempenha um papel importante na computação quântica, não está claro que se possa dizer que é "o edifício básico" do sujeito. A Computação Quântica Baseada em Medidas e a Computação Quântica Adiabática como exemplos de modelos de CQ em que a unitariedade é muito colocada no banco de trás e onde seria necessário um argumento não trivial para, de alguma forma, reprimir a unitariedade, exceto se inclinarmos a campo de atuação descrevendo o "CQ universal" em termos do modelo de circuito unitário.
Niel de Beaudrap
@NieldeBeaudrap, na verdade, a superposição decorre da linearidade. contagem pessoalmente não em unitarity tanto (mas vamos ver)
Nikos M.
1
@ Nikos: de fato, você pode obter muito mais poder (suspeito) se considerar operações lineares invertíveis arbitrárias . Estou apenas apontando que superstições / linearidade em si não são poderosas, porque as transformações estocásticas também são lineares e também agem sobre superposições - mas muitos pesquisadores suspeitamBPP=PApesar disso.
Niel de Beaudrap
-2

Eu queria responder aos comentários de Niel de Beaudrap sobre a fonte de acelerações quânticas, mas não posso comentar. Não sei se posso postar uma resposta.

Na minha opinião, todas as acelerações quânticas são devidas a emaranhados. O único algoritmo em que podemos fazer algo mais rápido que os computadores clássicos sem usar estados emaranhados é o Deutsch-Jozsa para calcular a paridade de dois bits. Se discutirmos sobre acelerações assintóticas, é necessário o emaranhamento e, de fato, muito disso. Se um algoritmo quântico precisa de uma pequena quantidade de emaranhamento, ele pode ser simulado de forma eficiente e classicamente. Eu posso apontar o artigo http://arxiv.org/abs/quant-ph/0201143 , que discute especificamente o algoritmo de fatoração e quanto emaranhamento ele requer.

costelus
fonte
2
"Na minha opinião, todas as acelerações quânticas são devidas a emaranhados". Sua reivindicação está realmente aberta ao debate. O papel do emaranhamento nos algoritmos quânticos não é totalmente bem compreendido. Sabemos que o emaranhamento não é um recurso suficiente para obter uma aceleração quântica exponencial (existem circuitos quânticos de emaranhamento máximo, chamados circuitos de Clifford , que são classicamente simuláveis), mostrando que esses não são conceitos equivalentes.
Juan Bermejo Vega
2
Além disso, você pode querer olhar para este artigo , que mostra que pouco emaranhamento é suficiente para fazer computação quântica universal (para medidas contínuas de emaranhamento).
Juan Bermejo Vega
Eu só queria dizer que os algoritmos quânticos mais interessantes usam emaranhamento. Quanto isso depende da medida de emaranhamento, e há artigos que argumentam que muito emaranhamento é inútil. E, sim, o emaranhamento por si só não é suficiente.
costelus
-4

essa é quase a mesma questão central que está impulsionando algo como centenas de milhões, ou possivelmente bilhões de dólares em iniciativas de pesquisa em QM de computação, tanto públicas quanto privadas em todo o mundo. a questão está sendo atacada ao mesmo tempo, experimental e teoricamente, e os avanços de cada lado são transferidos para o outro lado.

a questão tenta separar claramente os aspectos teóricos e pragmáticos / experimentais dessa questão, mas um experimentalista ou engenheiro argumentaria que eles são fortemente acoplados, inseparáveis, e que o progresso histórico até agora no desafio é evidência / prova disso.

o ponto a seguir certamente não ganhará nenhum concurso de popularidade (possivelmente devido ao viés bem conhecido / observado de que resultados negativos raramente são relatados cientificamente), mas vale a pena notar que há uma opinião minoritária / contrária promovida por vários grupos credíveis , até pesquisadores de elite que a computação em QM pode ou nunca se materializará fisicamente devido a desafios de implementação intransponíveis, e há ainda algumas justificativas / análises teóricas para isso (mas talvez mais na física teórica do que no TCS). (e observe que alguns podem ter dúvidas, mas não estão dispostos a continuar registrando o questionamento do "paradigma dominante".) os principais argumentos são baseados no ruído inerente à GQ, no princípio da incerteza de Heisenberg e na confusão experimental fundamental das configurações de GQ, etc.

agora existem duas décadas bastante sólidas de pesquisas teóricas e experimentais e a facção minoritária argumentaria que os resultados até agora não são animadores, sem brilho ou até agora estão chegando a uma resposta negativa definitiva.

um dos mais sinceros defensores da visão negativa (na fronteira com o extremo / feroz!) é Dyakonov, mas, no entanto, argumenta apaixonadamente o caso com base em todos os ângulos:

pode-se acusar Dyakonov de quase polemismo, mas serve como um contraponto quase simétrico a alguns proponentes da computação de QM que acreditam fervorosamente na posição oposta (que não há quase absolutamente nenhuma questão de sua viabilidade futura / eventual / inevitável). outro grande teórico que defende as limitações inerentes à computação em QM (com base no ruído) é Kalai. aqui está um longo debate entre ele e Harrow sobre o assunto.

também é natural traçar alguma analogia, pelo menos frouxa, de outro projeto de física massivo / complexo que até agora não alcançou seu objetivo final após décadas de tentativas e previsões iniciais otimistas, o de experimentos de fusão geradores de energia .

vzn
fonte
4
Isso não responde à pergunta conforme solicitado.
DW
em suma, a premissa implícita de que é uma questão puramente teórica está empurrando os limites da aplicabilidade da teoria contra a realidade a ponto de ser falha ... ou seja, há uma questão de modelagem no coração dela ... os formalismos existentes (cruzando as duas TCS e física!) Realmente / capturar com precisão a realidade? Dyakonov para um pode responder a nenhuma ... e novos formalismos estão ativamente sendo proposto pela facção minoritária ...
vzn
2
@vzn: com o entendimento de que isso nunca poderia produzir uma prova formal de uma maneira ou de outra, você poderia pelo menos elaborar como o componente teórico das "duas décadas bastante sólidas de pesquisa teórica e experimental" está apontando para resultados que são "não é encorajador, sem brilho, ou agora está chegando a uma resposta negativa definitiva" no que diz respeito à viabilidade da computação quântica?
Niel de Beaudrap
3
Em vista do axioma de Dyanokov sobre precisão e valores exatos, não está claro que sou eu quem estou mergulhando no filosófico! Dyanokov parece ser um anti-realistaista incondicional, um cético em mecânica quântica ou ambos. E não está claro como esses argumentos re: cálculo quântico de erro delimitado por endereço de precisão, onde o teorema do limite também se aplica ao cálculo quântico de precisão delimitada. Em suma, ele não parece atualizado sobre o estado da arte da computação quântica, a partir de 1997 em diante. Não há muita necessidade de interação em tempo real, para lidar com o ceticismo que não está atualizado.
Niel de Beaudrap
1
Partindo de seu resumo e de uma breve leitura de seu artigo, o argumento de Dyakonov parece ser: como as suposições usadas na prova do fracasso do teorema da tolerância a falhas não são satisfeitas no mundo real, não há garantia de que a computação quântica realmente funcione. Se usássemos esse critério em geral, quase nenhum resultado teórico seria aplicável na prática.
Peter Shor