A computação quântica adiabática pode ser mais rápida que o algoritmo de Grover?

Foi provado que a computação quântica adiabática é equivalente a "padrão", ou computação quântica de modelo de porta. A computação adiabática, no entanto, mostra promessas para problemas de otimização, onde o objetivo é minimizar (ou maximizar) uma função que está de alguma forma relacionada ao problema - ou seja, encontrar a instância que minimiza (ou maximiza) essa função resolve imediatamente o problema. problema.

Agora, parece-me que o algoritmo de Grover pode essencialmente fazer o mesmo: pesquisando no espaço da solução, ele encontrará uma solução (possivelmente dentre muitas soluções) que satisfaz o critério do oracle, que nesse caso equivale à condição de otimização, no tempo $O(\sqrt N)$, onde$N$é o tamanho do espaço da solução.

Este algoritmo demonstrou ser ótimo: como Bennett et al. (1997) colocam que "a classe não pode ser resolvida em uma máquina quântica de Turing no tempo o ( 2 n / 2 ) ". No meu entendimento, isso significa que não há como construir qualquer algoritmo quântico que encontre uma solução pesquisando no espaço mais rapidamente que O ( $\rm NP$$o(2^{n/2})$, ondeN éescalonado com o tamanho do problema.$O(\sqrt N)$$N$

Portanto, minha pergunta é: embora a computação quântica adiabática seja frequentemente apresentada como superior quando se trata de problemas de otimização, ela pode ser realmente mais rápida que ? Se sim, isso parece contradizer a otimidade do algoritmo de Grover, já que qualquer algoritmo adiabático pode ser simulado por um circuito quântico. Caso contrário, qual é o sentido de desenvolver algoritmos adiabáticos, se eles nunca serão mais rápidos do que algo que podemos construir sistematicamente com circuitos? Ou há algo errado com meu entendimento?$O(\sqrt N)$

Boa pergunta. Para pesquisa não estruturada, o cálculo quântico adiabático realmente fornece exatamente o mesmo aceleração que o algoritmo de Grover padrão baseado em porta faz, como comprovadoneste$\sqrt{N}$ importante artigo de Roland e Cerf. Isso concorda com a equivalência entre o cálculo quântico adiabático e baseado em portas que você mencionou.

(Uma pequena correção na sua pergunta: você está certo de que, na configuração do problema de pesquisa do oracle, é necessário enquadrar sua consulta de pesquisa como uma pergunta sim / não que o oracle possa responder. Mas a pergunta não é realmente feita para ser " extremiza a função f ( x ) ?", como você propôs. Em vez disso, é "é f ( x ) menor ou igual a M ?" Veja os slides 9 e 10 aqui . Isso ocorre porque um oráculo para este A questão é considerada um modelo mais realista para uma configuração física, onde é concebível que alguém possa computar ou medir diretamente f ( x $x$$f(x)$$f(x)$$M$$f(x)$ para um dado $x$, mas .)$f(x) - f_\text{min}$

No entanto, existem duas vantagens em potencial no controle de qualidade adiabático, as quais são difíceis de estudar teoricamente. O primeiro é prático: na verdade, construir grandes circuitos quânticos coerentes é muito mais difícil do que apenas desenhá-los em um artigo de jornal. Embora o CQ adiabático não tenha nenhuma vantagem fundamental sobre a configuração tradicional, pode ser muito mais fácil de implementar experimentalmente.

Em segundo lugar, a mesma ressalva aplica-se ao AQC e ao algoritmo padrão de Grover: aplica-se apenas a estruturas não estruturadas ou "caixa preta", na qual ignoramos todas as correlações entre as respostas que o oráculo dá quando alimentado em "semelhante" ou " consultas "relacionadas". Qualquer problema de pesquisa real com o qual nos preocupamos terá, por definição, alguma estrutura, embora essa estrutura possa ser muito complicada para ser analisada. Por exemplo, se pensarmos que a função é extremizada como um cenário energético, parece razoável que o sistema possa túnel mais facilmente entre mínimos locais "próximos" do que entre "distantes".

$\subset$

A computação quântica adiabática não pode fazer nada mais rápido que a computação quântica baseada em circuito de uma perspectiva de complexidade computacional. Isso ocorre porque há uma prova matemática de que a computação quântica baseada em circuito pode simular eficientemente a computação quântica adiabática [consulte a seção 5 deste artigo ].

$\mathcal{O}(\sqrt{N})$

A resposta é não. Isso ocorre porque se o AQC puder fazê-lo em, digamos, , o QC baseado em circuito também poderá fazê-lo em $\mathcal{O}(\log{N})$$\mathcal{O}(\log{N})$$\mathcal{O}(\sqrt{N})$