Existem problemas nos quais os computadores quânticos são conhecidos por fornecer uma vantagem exponencial?

27

Geralmente, acredita-se e afirma-se que os computadores quânticos podem superar os dispositivos clássicos em pelo menos algumas tarefas.

Um dos exemplos mais citados de um problema no qual os computadores quânticos superariam os dispositivos clássicos é , mas também não se sabe se também é eficientemente solucionável com um computador clássico (que é ).Factoring Factoring PFactoringFactoringFactoringP

Para outros problemas comumente citados nos quais os computadores quânticos são conhecidos por oferecer uma vantagem, como a pesquisa em banco de dados, a aceleração é apenas polinomial.

Existem casos conhecidos de problemas nos quais pode ser demonstrado (provado ou comprovado sob fortes premissas de complexidade computacional) que os computadores quânticos forneceriam uma vantagem exponencial?

glS
fonte
Eu diria que a resposta é não, se você restringir os problemas a serem problemas de decisão , porque existem problemas de amostragem (por exemplo, BosonSampling e IQP) para os quais uma vantagem quântica exponencial foi demonstrada (ou melhor, comprovada sob fortes premissas). Pode haver outros que eu não conheço.
21818 glS
Observe que já existem muitos algoritmos clássicos de custo subexponencial para fatoração. (Existe um intervalo substancial entre os custos polinomiais e exponenciais.)
Delicado ossifrage
Como diz Heather, isso atualmente não é conhecido, uma vez que os limites dos computadores clássicos (e quânticos) não são conhecidos. Os critérios que você estabelece em sua pergunta exigem que o respondente vá além de provar o relacionamento além de P e NP. Eu sugiro que você reformule sua pergunta para pedir outros exemplos prováveis ​​(além de fatorar).
Toby Hawkins
2
As conseqüências práticas de uma aceleração quântica, por exemplo , para saber se o algoritmo de Shor pode realmente superar o GNFS clássico, também não são necessariamente implícitas por relações assintóticas das curvas de crescimento dos custos. Veja esta resposta para um pouco mais sobre a configuração assintótica versus concreta e por que as perguntas em torno de P = NP são um arenque vermelho para criptografia e comparações práticas de desempenho.
Delicado ossifrage
1
@SqueamishOssifrage Exactly. Eu gostaria de acrescentar que equiparar a associação de P a 'eficiente' é mais uma ilusão dos cientistas da computação do que a verdade absoluta. A idéia é que, uma vez que tenha demonstrado que um problema está em P , mesmo que seja algo horrivelmente parecido com , haverá melhorias que o reduzirão a algo semelhante a O ( n 3 ) , um pouco mais próximo do aconchegantes 'limites inferiores condicionais'. Para creditar, isso geralmente aconteceu no passado. Mas isso não é garantia e, quanto à praticidade, existem ainda algoritmos "lineares" que são considerados "não implementáveis". O(n1235436546)O(n3)
Lagarto discreto

Respostas:

9

Suponha que uma função tenha a seguinte propriedade curiosa: Existe s { 0 , 1 } n tal que f ( x ) = f ( y ) se e somente se x + y = s . Se s = 0 é a única solução, isso significa que f é 1 para 1; caso contrário, existe um diferente de zero s tal que f ( x )f:F2nF2ns{0 0,1}nf(x)=f(y)x+y=ss=0 0fs para todo x , o que, porque 2 = 0 , significa que f é 2-para-1.f(x)=f(x+s)x2=0f

Qual é o custo para qualquer probabilidade prescrita de sucesso, em um computador clássico ou quântico, de distinguir uma função aleatória uniforme 1 para 1 de uma função aleatória uniforme 2 para 1 que satisfaça essa propriedade, se cada opção (1 para -1 ou 2-para-1) tem igual probabilidade?

Ou seja, eu secretamente jogo uma moeda de forma justa; se eu tiver cabeças, entrego a você um circuito de caixa preta (clássica ou quântica, respectivamente) para uma função aleatória uniforme de 1 para 1 f , enquanto que, se obtiver coroa, entrego-lhe um circuito de caixa preta para uma distribuição aleatória uniforme -1 função . Quanto você tem que pagar para obter uma probabilidade prescrita de sucesso p de dizer se eu tenho cara ou coroa?fp

Este é o cenário do algoritmo de Simon . Tem aplicações esotéricas em criptoanálise sem sentido , * e foi um instrumento no início de estudar as classes de complexidade bqp e BPP e uma inspiração cedo para o algoritmo de Shor.

Simon apresentou um algoritmo quântico (§3.1, p. 7) que custa qubits e tempo esperado de O ( n T f ( n ) + G ( n ) ) para probabilidade próxima de 1 de sucesso, onde T f ( n ) é o tempo para calcular uma superposição de valores de f em uma entrada de tamanho n e onde G ( n ) é o tempo para resolver umaO(n+|f|)O(nTf(n)+G(n))Tf(n)fnG(n)n×n sistema de equações lineares em .F2

Simon esboçou ainda uma prova (Teorema 3.1, p. 9) de que um algoritmo clássico que avalia em não mais que 2 n / 4 valores distintos distintos não pode adivinhar a moeda com vantagem melhor que 2f2n/4 relação a uma suposição aleatória uniforme.2n/2

Em certo sentido, isso responde positivamente à sua pergunta: um cálculo quântico que requer um número linear de avaliações da função aleatória em uma superposição quântica de entradas pode atingir uma probabilidade de sucesso muito melhor do que um cálculo clássico que requer um número exponencial de avaliações de uma função aleatória em funções discretas. entradas , no tamanho das entradas. Mas em outro sentido que não responder à sua pergunta em tudo, porque pode ser que para cada detalhe função existe uma maneira mais rápida para calcular a pesquisa.f

O algoritmo Deutsch – Jozsa serve como ilustração semelhante para um problema artificial ligeiramente diferente para estudar diferentes classes de complexidade, P e EQP, descobrindo os detalhes que são deixados como um exercício para o leitor.


* Simon's não faz sentido para a análise criptográfica, porque apenas um idiota inconcebivelmente confuso alimentaria sua chave secreta no circuito quântico do adversário para usar em uma superposição quântica de entradas, mas por algum motivo, ele estraga toda vez que alguém publica um novo artigo sobre o uso do algoritmo de Simon quebrar as chaves dos idiotas com hardware imaginário, e é assim que todos esses ataques funcionam. Exceção: É possível que isso possa quebrar a criptografia de caixa branca , mas a história de segurança da criptografia de caixa branca, mesmo contra adversários clássicos, não é promissora.

Ossifrage Squeamish
fonte
1
interessante, obrigado pela resposta. Você pode explicar por que isso não prova que ? Acho que a resposta é algo nesse sentido, mostrando uma separação oracular , como oposta a uma "regular", mas não sou versado o suficiente nesses tópicos para realmente dizer. Eu acho que uma breve discussão sobre isso melhoraria a resposta. BQPBPP
glS 21/03
@glS Adicionei uma frase que acho que deve ser o ponto crucial da diferença. Isso ajuda?
Delicado ossifrage
12

Não tenho certeza se isso é estritamente o que você está procurando; e não sei se qualificaria isso como "exponencial" (também não sou cientista da computação, portanto minha capacidade de fazer análises de algoritmos é mais ou menos inexistente ...), mas um resultado recente de Bravyi et. Todos apresentaram uma classe de 'problemas da função linear oculta 2D' que comprovadamente usam menos recursos em um dispositivo paralelo quântico.

O artigo está no arxiv aqui , mas aqui está um breve resumo. A vantagem quântica está na profundidade do circuito paralelo, portanto, o número de threads em que se pode dividir o problema em uma fan-in limitada. O problema é dada uma matriz A e um vector de entrada b , pode-se definir uma forma quadrática q e um subespaço especial para essa forma. O objetivo do "problema da função linear oculta" é encontrar uma linearização para essa função quadrática em um subespaço especial.N×NUMAbq

Um circuito probablistic clássica é constrangido a ~ profundidade, se você quiser que o seu cálculo para ter sucesso com probabilidade > 7 / 8 (você provavelmente quer ter sucesso com, pelo menos, essa probabilidade). Um circuito quântico pode fazê-lo com profundidade constante, o que é uma grande melhoria.registroN>7/8

A prova equivale essencialmente a um estado gráfico específico, sendo difícil para um circuito clássico simular, esse sub-resultado foi comprovado um pouco antes . Em seguida, o restante do artigo mostra que a maior classe de problemas contém esse problema difícil.

Emily Tyhurst
fonte
5

A classe de complexidade dos problemas de decisão solucionáveis ​​com eficiência em um computador clássico é chamada BPP (ou P , se você não permitir aleatoriedade, mas suspeita-se que seja igual de qualquer maneira). A classe de problemas solucionáveis ​​com eficiência em um computador quântico é chamada BQP . Se existir um problema para o qual um computador quântico forneça uma aceleração exponencial, isso implicaria que BPP BQP . No entanto, a questão BQP versus BPP é uma questão importante em aberto na ciência da computação teórica; portanto, esse problema não foi comprovado (e, se você encontrar um, certamente ganhará todos os tipos de prêmios).

BPPOBQPO

tparker
fonte
2
2

Embora eu não possa fornecer uma prova formal, acredita-se que a simulação de (a evolução temporal) de um sistema quântico seja: Não existe melhor maneira conhecida de fazer isso em um computador clássico do que no tempo exponencial, mas um computador quântico pode trivialmente fazê-lo em tempo polinomial.

A idéia de um simulador quântico (ver também artigo da Wikipedia ) é de fato como os computadores quânticos foram propostos pela primeira vez.

pirâmides
fonte