Existe alguma declaração geral sobre que tipos de problemas podem ser resolvidos com mais eficiência usando um computador quântico?

Existe uma declaração geral sobre que tipos de problemas podem ser resolvidos com mais eficiência usando computadores quânticos (somente modelo quântico de portas)? Os problemas pelos quais um algoritmo é conhecido hoje têm uma propriedade comum?

Tanto quanto eu entendo, a computação quântica ajuda no problema de subgrupos ocultos (Shor); O algoritmo de Grover ajuda a acelerar os problemas de pesquisa. Li que algoritmos quânticos podem acelerar, se você procurar uma 'propriedade global' de uma função (Grover / Deutsch).

1. Existe uma declaração mais concisa e correta sobre onde a computação quântica pode ajudar?
2. É possível dar uma explicação por que a física quântica pode ajudar lá (de preferência algo mais profundo que 'a interferência possa ser explorada')? E por que isso possivelmente não ajudará em outros problemas (por exemplo, problemas NP-completos)?

Existem documentos relevantes que discutem exatamente isso?

Eu já fiz essa pergunta antes em cstheory.stackexchange.com, mas pode ser mais adequada aqui.

Sobre a utilidade computacional em geral

Sem talvez perceber, você está fazendo uma versão de uma das perguntas mais difíceis que você pode fazer sobre a ciência da computação teórica. Você pode fazer a mesma pergunta sobre computadores clássicos; apenas, em vez de perguntar se a adição de 'quantumness' é útil, você pode perguntar:

• Existe uma declaração concisa sobre onde aleatoriamente algoritmos podem ajudar?

  É possível dizer algo muito vago aqui - se você acha que as soluções são abundantes (ou que o número de soluções para um subproblema é abundante), mas que pode ser difícil construir sistematicamente uma, é útil poder fazer isso escolhas aleatórias para superar o problema da construção sistemática. Mas tenha cuidado, às vezes a razão pela qual você sabe que existem soluções abundantes para um subproblema é porque há uma prova usando o método probabilístico . Nesse caso, você sabe que o número de soluções é abundante por redução ao que é, na verdade, um algoritmo aleatório útil!

  A menos que você tenha outra maneira de justificar o fato de que o número de soluções é abundante para esses casos, não há uma descrição simples de quando um algoritmo aleatório pode ajudar. E se você tem demandas suficientemente altas de 'utilidade' (uma vantagem super-polinomial), então o que você está perguntando é se , que é um problema não resolvido na teoria da complexidade. $\mathsf P \ne \mathsf{BPP}$
  
  

• Existe uma declaração concisa sobre onde os algoritmos paralelizados podem ajudar?

  Aqui as coisas podem ser um pouco melhores. Se um problema parece que pode ser dividido em muitos subproblemas independentes, ele pode ser paralelizado - embora esse seja um critério vago, "você saberá quando vir". A principal questão é: você saberá quando vir ? Você imaginaria que testar a viabilidade de sistemas de equações lineares sobre os racionais não é apenas paralelizável, mas pode ser resolvido usando circuitos profundidade [cf  Comput. Complexo. 8 (pp. 99-126), 1999 ]?$O(\log^2 n)$

  Uma maneira pela qual as pessoas tentam pintar uma intuição geral para isso é abordar a questão na direção oposta e dizer quando se sabe que um algoritmo paralelo não ajudará. Especificamente, não ajudará se o problema tiver um aspecto inerentemente sequencial. Mas isso é circular, porque 'sequencial' significa apenas que a estrutura que você pode ver para o problema é uma estrutura que não é paralela.

  Novamente, não há uma descrição simples e abrangente de quando um algoritmo paralelo pode ajudar. E se você tiver demandas suficientemente altas de 'utilidade' (um limite superior poliolarítmico na quantidade de tempo, assumindo paralelização polinomial), o que você está perguntando é se$\mathsf P \ne \mathsf{NC}$
  
  

As perspectivas de "descrições concisas e corretas de quando [X] é útil" não parecem muito boas nesse ponto. Embora você possa protestar que estamos sendo muito rigorosos aqui: com o objetivo de exigir mais do que uma vantagem polinomial, não podemos sequer afirmar que as máquinas de Turing não determinísticas foram 'úteis' (o que é claramente absurdo). Não devemos exigir uma barra tão alta - na ausência de técnicas para resolver com eficiência a satisfação, deveríamos pelo menos aceitar que, se de alguma forma pudéssemos obter uma máquina de Turing não determinística, realmente a acharíamos muito útil . Mas isso é diferente de ser capaz de caracterizar com precisão para quais problemas achamos útil.

Sobre a utilidade dos computadores quânticos

Tomando um passo para trás, há alguma coisa que podemos dizer sobre onde computadores quânticos são úteis?

Podemos dizer o seguinte: um computador quântico só pode fazer algo interessante se estiver aproveitando a estrutura de um problema, que não está disponível para um computador clássico. (Isso é sugerido pelas observações sobre uma "propriedade global" de um problema, como você mencionou). Mas podemos dizer mais do que isso: os problemas resolvidos por computadores quânticos no modelo de circuito unitário instanciarão alguns recursos desse problema como operadores unitários . Os recursos do problema que não estão disponíveis para os computadores clássicos serão todos aqueles que não tiverem uma relação (comprovadamente) estatisticamente significativa com a base padrão.

• No caso do algoritmo de Shor, essa propriedade são os autovalores de um operador de permutação, definidos em termos de multiplicação sobre um anel.
• $\pm 1$

Não é de surpreender que, em ambos os casos, as informações estejam relacionadas a autovalores e autovetores. Este é um excelente exemplo de propriedade de um operador que não precisa ter nenhum relacionamento significativo com a base padrão. Mas não há nenhuma razão específica para que a informação tenha que ser um autovalor. Tudo o que é necessário é ser capaz de descrever um operador unitário, codificando alguma característica relevante do problema que não é óbvia na inspeção da base padrão, mas que pode ser acessada de alguma outra maneira facilmente descrita.

No final, tudo isso diz que um computador quântico é útil quando você pode encontrar um algoritmo quântico para resolver um problema. Mas pelo menos é um esboço amplo de uma estratégia para encontrar algoritmos quânticos, o que não é pior do que os esboços gerais de estratégias que descrevi acima para algoritmos aleatórios ou paralelizados.

Comentários sobre quando um computador quântico é 'útil'

Como outras pessoas observaram aqui, "onde a computação quântica pode ajudar" depende do que você quer dizer com 'ajuda'.

• O algoritmo de Shor é frequentemente descrito em tais discussões, e de vez em quando as pessoas apontam que não sabemos que a fatoração não é solucionável em tempo polinomial. Então, sabemos realmente que "a computação quântica seria útil para fatorar números"?

  Além da dificuldade em realizar computadores quânticos, acho que aqui a resposta razoável é "sim"; não porque sabemos que você não pode fatorar eficientemente usando computadores convencionais, mas porque não sabemos como você faria isso usando computadores convencionais. Se os computadores quânticos o ajudarem a fazer algo que você não tem uma abordagem melhor para fazer, parece-me que isso está 'ajudando'.

• $O(2^{0.386\,n})$

  Talvez o algoritmo de Grover, como tal, não seja especialmente útil. No entanto, pode ser útil se você o usar para elaborar estratégias clássicas mais inteligentes além da busca por força bruta: usando a amplificação de amplitude , a generalização natural do algoritmo de Grover para configurações mais gerais, podemos melhorar o desempenho de muitos algoritmos não triviais para SAT (ver, por exemplo, [ACM SIGACT News  36 (pp.103-108), 2005 - link em PDF gratuito ]; dica de Martin Schwarz, que me indicou essa referência nos comentários).

  Como no algoritmo de Grover, a amplificação de amplitude produz apenas acelerações polinomiais: mas falando na prática, mesmo uma aceleração polinomial pode ser interessante se não for eliminada pela sobrecarga associada à proteção de informações quânticas contra ruídos.

TL; DR: Não, não temos nenhuma declaração "geral" precisa sobre exatamente que tipo de problemas os computadores quânticos podem resolver , em termos da teoria da complexidade. No entanto, temos uma ideia aproximada.

De acordo com o sub-artigo da Wikipedia sobre Relação com a teoria da complexidade computacional

A classe de problemas que podem ser resolvidos com eficiência por computadores quânticos é chamada de BQP , para "erro limitado, tempo quântico e polinomial". Os computadores quânticos executam apenas algoritmos probabilísticos ; portanto, o BQP em computadores quânticos é a contrapartida do BPP ("erro limitado, tempo probabilístico e polinomial") em computadores clássicos. É definido como o conjunto de problemas solucionáveis ​​com um algoritmo de tempo polinomial, cuja probabilidade de erro é limitada pela metade . Diz-se que um computador quântico "resolve" um problema se, para todos os casos, sua resposta estiver correta com alta probabilidade. Se essa solução for executada em tempo polinomial, esse problema estará no BQP.

O BQP está contido na classe de complexidade #P (ou mais precisamente na classe associada de problemas de decisão P ^#P ), que é uma subclasse de PSPACE .

Suspeita-se que o BQP seja separado do NP-completo e um superconjunto estrito de P, mas isso não é conhecido. A fatoração inteira e o log discreto estão no BQP. Esses dois problemas são NP suspeitos de estarem fora da BPP e, portanto, fora de P. Ambos são suspeitos de não estarem completos em NP. Existe um equívoco comum de que computadores quânticos podem resolver problemas de NP-completos em tempo polinomial. Não se sabe que isso é verdade e geralmente se suspeita que seja falso.

A capacidade de um computador quântico acelerar os algoritmos clássicos tem limites rígidos - limites superiores da complexidade da computação quântica. A parte esmagadora dos cálculos clássicos não pode ser acelerada em um computador quântico. Um fato semelhante ocorre para tarefas computacionais específicas, como o problema de pesquisa, para as quais o algoritmo de Grover é ideal.

${\displaystyle O({\sqrt[{3}]{N}})}$$\displaystyle O({\sqrt {N}})$

Embora os computadores quânticos possam ser mais rápidos que os clássicos para alguns tipos de problemas, os descritos acima não podem resolver nenhum problema que os computadores clássicos já não possam resolver. Uma máquina de Turing pode simular esses computadores quânticos, para que um computador quântico nunca possa resolver um problema indecidível como o problema da parada. A existência de computadores quânticos "padrão" não desmente a tese de Church-Turing. Especula-se que teorias da gravidade quântica, como a teoria M ou a gravidade quântica em loop, podem permitir a construção de computadores ainda mais rápidos. Atualmente, definir a computação em tais teorias é um problema aberto devido ao problema do tempo, ou seja, atualmente não existe uma maneira óbvia de descrever o que significa para um observador enviar entrada para um computador e receber saída posteriormente.

Quanto ao motivo pelo qual os computadores quânticos podem resolver com eficiência os problemas de BQP:

1. $n$$2n$

2. Geralmente, a computação em um computador quântico termina com uma medição. Isso leva a um colapso do estado quântico em um dos estados base. Pode-se dizer que o estado quântico é medido para estar no estado correto com alta probabilidade.

Curiosamente, se teoricamente permitirmos a pós-seleção (que não possui nenhuma implementação prática escalável), obteremos a classe de complexidade pós-BQP :

Na teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste em todos os problemas computacionais solucionáveis ​​em tempo polinomial em uma máquina quântica de Turing com pós-seleção e erro limitado (no sentido de que o algoritmo está correto pelo menos 2/3 do tempo em todos os entradas). No entanto, a pós-seleção não é considerada um recurso que um computador realista (mesmo um quântico) possuiria, mas, no entanto, as máquinas pós-seleção são interessantes do ponto de vista teórico.

Gostaria de adicionar o que o lagarto @Discrete mencionou na seção de comentários. Você não definiu explicitamente o que você quer dizer com "pode ​​ajudar", no entanto, a regra básica na teoria da complexidade é que, se um computador quântico "puder ajudar" em termos de resolução em tempo polinomial (com um erro vinculado) se a classe de problema que pode resolver está no BQP, mas não no P ou BPP. Suspeita -se que a relação geral entre as classes de complexidade discutidas acima seja:

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

No entanto, P = PSPACE, é um problema aberto em Ciência da Computação . Além disso, a relação entre P e NP ainda não é conhecida.

Não existe essa afirmação geral e é improvável que haja uma em breve. Vou explicar por que esse é o caso. Para uma resposta parcial à sua pergunta, analisar os problemas nas duas classes de complexidade BQP e PostBQP pode ajudar.

As classes de complexidade que mais se aproximam dos problemas que podem ser resolvidos com eficiência por computadores quânticos do modelo de portas quânticas são:

1. BQP ; e
2. PostBQP

O BQP consiste nos problemas que podem ser resolvidos em tempo polinomial em um circuito quântico. Os algoritmos quânticos mais importantes, como o algoritmo de Shor, resolvem problemas no BQP.

$=$

No entanto, atualmente não existem métodos para implementar praticamente a seleção de posts, portanto o PostBQP é mais de interesse teórico.

A relação entre P, NP e BQP é atualmente desconhecida; e um problema em aberto da ordem de P vs. NP. Como uma declaração geral sobre que tipos de problemas podem ser resolvidos com mais eficiência usando computadores quânticos, é necessário responder à pergunta BQP vs. P (se BQP = P, os computadores quânticos aparentemente não são mais eficientes (pelo menos para os teóricos da complexidade))

Semelhante à imagem de Blue, eu gosto mais desta da Quanta Magazine , pois parece resumir visualmente o que estamos falando.