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

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 ∈ $\text{Factoring}$$\text{Factoring}$$\text{Factoring}\in \text{P}$

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?

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\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$$s \in \{0,1\}^n$$f(x) = f(y)$$x + y = s$$s = 0$$f$$s$ para todo x , o que, porque 2 = 0 , significa que f é 2-para-1.$f(x) = f(x + s)$$x$$2 = 0$$f$

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?$f$$p$

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 uma$O(n + |f|)$$O(n \cdot T_f(n) + G(n))$$T_f(n)$$f$$n$$G(n)$$n \times n$ sistema de equações lineares em .$\mathbb F_2$

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 $f$$2^{n/4}$ relação a uma suposição aleatória uniforme.$2^{-n/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.}

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\times N$$A$$b$$q$

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.$\log{N}$$>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.

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 $\neq$ 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).

$\textbf{BPP}^O \neq \textbf{BQP}^O$ $\neq$

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.