Por que o recozimento quântico não pode ser descrito por um modelo de portão?

Essa é uma pergunta que fui inspirada a fazer com base nessa pergunta , que observa que o recozimento quântico é um modelo de computação totalmente diferente do modelo de circuito usual. Já ouvi isso antes, e entendo que o modelo de porta não se aplica ao recozimento quântico, mas nunca entendi bem por que isso é ou como analisar os cálculos que um recozedor pode fazer. Pelo que entendi em várias palestras (algumas delas da D-wave!), O fato de os recozedores estarem confinados a um hamiltoniano específico é parte disso.

d-wave models annealing Emily Tyhurst
fonte

Respostas:

Um recozedor quântico, como uma máquina de onda D, é uma representação física do modelo de Ising e, como tal, tem um Hamiltoniano de 'problema' da forma

H_{P} = \sum_{J = 1}^{n} h_{j} σ_{j}^{z} + \sum_{i, j} J_{i j} σ_{i}^{z} σ_{j}^{z} .

$H_P = \sum_{J=1}^nh_j\sigma_j^z + \sum_{i, j}J_{ij}\sigma_i^z\sigma_j^z.$

Essencialmente, o problema a ser resolvido é mapeado para o Hamiltoniano acima. O sistema começa com o hamiltoniano e o parâmetro de recozimento, é utilizado para mapear a inicial Hamiltoniano para o problema hamiltoniano usando $H_I = \sum_{J=1}^nh'_j\sigma_j^x$ $s$ $H_I$ $H_P$ $H\left(s\right) = \left(1-s\right)H_I + sH_P$ .

Como se trata de um recozimento, o processo é feito devagar o suficiente para permanecer próximo ao estado fundamental do sistema, enquanto o hamiltoniano varia com o do problema, usando o tunelamento para permanecer próximo ao estado fundamental, conforme descrito na resposta de Nat .

Agora, por que isso não pode ser usado para descrever um modelo de portão QC? O exemplo acima é um problema de otimização binária sem restrições (QUBO) da Quadratic , que é difícil para NP ... De fato, aqui está um artigo que mapeia vários problemas de NP para o modelo de Ising . Qualquer problema no NP pode ser mapeado para qualquer problema difícil do NP no tempo polinomial e a fatoração de número inteiro é realmente um problema do NP.

Bem, a temperatura é diferente de zero, portanto não estará no estado fundamental durante todo o recozimento e, como resultado, a solução ainda será apenas aproximada. Ou, em termos diferentes, a probabilidade de falha é maior que a metade (não está nem perto de ter uma probabilidade decente de sucesso em comparação com o que um CQ universal considera 'decente' - a julgar pelos gráficos que eu já vi, a probabilidade de sucesso do máquina atual é de cerca de $0.2\%$ e isso só piora com o aumento do tamanho), e o algoritmo de recozimento não é um erro limitado. Em absoluto. Como tal, não há como saber se você tem ou não a solução correta com algo como fatoração de número inteiro.

O que ele (em princípio) faz é chegar muito perto do resultado exato, muito rapidamente, mas isso não ajuda em nada em que o resultado exato seja necessário, pois passar de 'quase correto' para 'correto' ainda é extremamente difícil ( ou seja, presumivelmente ainda o NP em geral, quando o problema original está no NP), neste caso, pois os parâmetros que são / dão uma solução 'quase correta' não necessariamente serão distribuídos em qualquer lugar perto dos parâmetros que são / fornecem o solução correta.

Editar para esclarecimento: o que isso significa é que um recozedor quântico (QA) ainda leva tempo exponencial (embora potencialmente um tempo exponencial mais rápido) para resolver problemas de NP, como fatoração de número inteiro, onde um CQ universal fornece uma velocidade exponencial e pode resolver o mesmo problema no tempo poli. Isso é o que implica que um controle de qualidade não pode simular um controle de qualidade universal no tempo poli (caso contrário, poderia resolver problemas no tempo poli que não pode). Conforme apontado nos comentários, não é o mesmo que dizer que um controle de qualidade não pode dar a mesma aceleração em outros problemas, como a pesquisa no banco de dados.

Mithrandir24601
fonte

Se bem entendi, você está basicamente dizendo que um recozedor quântico não pode descrever um circuito quântico porque o problema de encontrar o mínimo de um hamiltoniano arbitrário é difícil para o NP. Eu não entendo essa implicação. A simulação de circuitos quânticos também é geralmente difícil de simular classicamente (consulte, por exemplo, 1610.01808 )

glS 15/03

Além disso, sabe-se que alguns problemas solucionáveis por algoritmos expressos em circuitos quânticos também são solucionáveis por meio de recozimento quântico. Um exemplo notável é a pesquisa no banco de dados (consulte, por exemplo, a seção II de 1006.1696 ). Isso significa que, em certo sentido, é possível, em algumas circunstâncias, mapear um circuito aq em um problema de recozimento q. Isso também não invalida seu terceiro parágrafo (especificamente, a alegação de que isso [não] pode ser usado para descrever um modelo de portão QC )?

glS 15/03

@glS não, de jeito nenhum - ainda é preciso um tempo exponencial para encontrar o mínimo (conforme o artigo em seu segundo comentário) de um problema NP-difícil, portanto, enquanto houver problemas em P (por exemplo, pesquisa no banco de dados) em que a aceleração pode ser capaz de corresponder ao do CQ universal, resolver um problema de NP ainda leva tempo exponencial para estar dentro de um erro limitado, onde um CQ universal pode ser capaz de resolver o mesmo problema no tempo poli, por exemplo, fatoração inteira. Como o controle de qualidade não pode fazer isso, um controle de qualidade não pode simular um controle de qualidade universal no tempo poli

Mithrandir24601

Ok, mas não é isso que você está dizendo na resposta (ou pelo menos não explicitamente). A partir da resposta, parece que você está dizendo que o controle de qualidade nunca pode ser usado para resolver um problema resolvido via modelo de portão QC. Isso é muito diferente de dizer que o controle de qualidade não pode resolver com eficiência um problema difícil de NP (que às vezes pode ser resolvido por um circuito quântico ... embora eu não pense que isso tenha sido comprovado, pois não sabemos se o fatoramento é realmente NP-hard, e a maioria dos outros problemas em que uma vantagem quântica foi demonstrada não são problemas de decisão, que eu saiba).

18718 glS

Eu fiz uma edição que espero esclarecer as coisas. Não se sabe se P = NP ou não, com certeza, mas ainda é um exemplo específico de QC ser exponencialmente mais rápido, de acordo com o conhecimento atual

Mithrandir24601

O recozimento é mais uma tática analógica.

A essência é que você tem alguma função estranha que deseja otimizar. Então, você pula em torno dele. A princípio, a " temperatura " é muito alta, de modo que o ponto selecionado pode saltar bastante. Então, como o algoritmo " esfria ", a temperatura diminui e o salto se torna menos agressivo.

Por fim, estabelece-se como uma ótima local que, idealmente, é favorável como a ótima global.

Aqui está uma animação para recozimento simulado (não quântico):

Mas, é praticamente o mesmo conceito para o recozimento quântico :

Por outro lado, a lógica da porta é muito mais digital do que analógica. Ele se preocupa com qubits e operações lógicas, em vez de apenas encontrar um resultado após um caótico caos.

Nat
fonte

Obrigado, isso esclarece certas limitações para mim. Você conhece algum problema que não é possível reformular como um problema de recozimento (eu sei que a Wikipedia afirmou que o algoritmo de Shor não era possível porque é um problema de "escalada", mas se você souber mais sobre os detalhes disso, eu adoraria ouvi-los :)

Emily Tyhurst

@EmilyTyhurst Tecnicamente, qualquer problema pode ser descrito em termos de escalada. É muito mais uma questão de quão bem o comportamento parece quando descrito no formato de escalada. Problemas que não se encaixam bem podem ser incrivelmente feios. Para problemas inteiramente não convexos, a escalada seria, na melhor das hipóteses, basicamente uma busca por força bruta.

Nat

@EmilyTyhurst Hah opps, interpretou mal o seu comentário na direção oposta. xD Mas, sim, você pode fazer um recozimento simulado em um computador quântico, assim como em um computador clássico. Então, suponho que chamemos ou não de " recozimento quântico " se torne mais uma questão de semântica.

Nat

@EmilyTyhurst Sim, são definitivamente todos inter-conversíveis. Quero dizer, é como o conceito de completeza de Turing - se tivermos algum tipo de lógica completa, podemos construir praticamente qualquer outra coisa com ela.

Nat

Um ponto importante do recozimento quântico é o de alterar adiabaticamente o hamiltoniano para que o estado permaneça sempre um estado fundamental do hamiltoniano (em mudança), e você acaba com os gs do hamiltoniano final, que é o objetivo do protocolo . Como isso se relaciona com o "salto" que você está descrevendo aqui? Este artigo ( 1006.1696 ) pode ser interessante a esse respeito (especificamente, a última parte da segunda coluna da primeira página).

18718 glS