Nonlinear Hamiltonians and Boolean satisfiability

Resumo Técnico: Hamiltonianos Não Lineares e Satisfatibilidade Booleana

Declaração do Problema
A computação quântica padrão é limitada pela linearidade da equação de Schrödinger, o que impõe limites fundamentais à distinguibilidade de estados. Especificamente, operações lineares não podem aumentar a distância de traço entre estados não ortogonais, tornando impossível a discriminação perfeita de estados quânticos sem recursos exponenciais. Essa limitação impede soluções eficientes para certos problemas computacionais difíceis, como determinar o número de atribuições satisfatórias para uma fórmula booleana. Este artigo investiga um modelo estendido de computação quântica onde um computador quântico escalável e tolerante a falhas é acoplado a um ou mais qubits ancila evoluindo sob uma equação de Schrödinger não linear. O objetivo é determinar se formas específicas de não linearidade de um único qubit podem contornar os limites de complexidade padrão para resolver eficientemente problemas de satisfatibilidade booleana, incluindo UNIQUE SAT, 3SAT e #SAT.

Metodologia
Os autores adotam uma abordagem de projeto inverso para construir Hamiltonianos não lineares. Em vez de começar com um sistema físico, eles começam definindo um retrato de fase desejado (campo de velocidade $\vec{v}$) na esfera de Bloch que atinja objetivos dinâmicos específicos, como separar estados ou criar pontos fixos. Em seguida, derivam o Hamiltoniano não linear $H$ associado usando a relação $\vec{v} = \vec{u} \times \vec{r}$, onde $\vec{u}$ é um campo dependente dos valores esperados do estado $\langle \vec{\sigma} \rangle$.

O protocolo computacional segue o método de codificação de amplitude de Abrams e Lloyd:

1. Codificação: Uma função booleana $f(x)$ na forma normal conjuntiva é avaliada em uma superposição de $n$ qubits. Através de portas Hadamard e pós-seleção no primeiro registro, o número de atribuições satisfatórias $s$ é codificado na amplitude de um único qubit ancila. O estado resultante é $|\psi_s\rangle = \cos(\theta_s/2)|0\rangle + \sin(\theta_s/2)|1\rangle$, onde $\theta_s$ depende de $s$.
2. Discriminação: Uma porta de discriminação de estado quântico não linear, gerada por um Hamiltoniano não linear específico, é aplicada ao ancila. Essa porta evolui o estado de modo que valores distintos de $s$ (ou propriedades de $s$) mapeiem para estados macroscopicamente distinguíveis (por exemplo, $|0\rangle$ vs. $|1\rangle$) em tempo polinomial.

O artigo analisa três modelos não lineares distintos:

1. O Modelo de Torção ($\langle \sigma_z \rangle \sigma_z$):

   • Hamiltoniano: $H = B\sigma_x + g\langle \sigma_z \rangle \sigma_z$.
   • Dinâmica: Este modelo gera uma frequência de rotação no eixo z proporcional à coordenada z do vetor de Bloch. Ao adicionar um termo de rotação linear no eixo x, os autores criam trajetórias que mapeiam estados no hemisfério superior para o polo norte e aqueles no hemisfério inferior para o polo sul.
   • Aplicação: Usado para resolver UNIQUE SAT (determinar se $s=0$ ou $s=1$ dada a promessa $0 \le s \le 1$). A porta separa eficientemente os estados exponencialmente próximos correspondentes a $s=0$ e $s=1$.

2. O Modelo Morse–Smale ($\langle \sigma_x \rangle \sigma_y - \langle \sigma_y \rangle \sigma_x$):

   • Hamiltoniano: $H = g(\langle \sigma_x \rangle \sigma_y - \langle \sigma_y \rangle \sigma_x)$.
   • Dinâmica: Este modelo cria um fluxo com um ponto fixo instável (fonte) no polo norte ($|0\rangle$) e um ponto fixo estável (sumidouro) no polo sul ($|1\rangle$). Todos os estados além de $|0\rangle$ fluem em direção a $|1\rangle$.
   • Aplicação: Usado para resolver 3SAT (determinar se $s=0$ ou $s>0$ para $s$ irrestrito). A porta mapeia qualquer instância satisfatória ($s>0$) para $|1\rangle$ e a instância insatisfatória ($s=0$) para $|0\rangle$ em tempo polinomial.

3. O Modelo de Garfo Supercrítico ($\langle \sigma_y \rangle \langle \sigma_z \rangle \sigma_x - \langle \sigma_x \rangle \langle \sigma_z \rangle \sigma_y$):

   • Hamiltoniano: $H = g(\langle \sigma_y \rangle \langle \sigma_z \rangle \sigma_x - \langle \sigma_x \rangle \langle \sigma_z \rangle \sigma_y)$.
   • Dinâmica: Este modelo apresenta dois pontos fixos atrativos nos polos ($|0\rangle$ e $|1\rangle$) e um ponto fixo repulsivo no equador. Ele cria um fluxo bistável onde o equador atua como uma separatriz.
   • Aplicação: Usado para resolver #SAT (contar o valor exato de $s$). Ao combinar essa porta com um algoritmo de busca binária (método de Aaronson), os autores demonstram que o valor preciso de $s$ pode ser determinado bit a bit em tempo polinomial.

Resultados Principais

• UNIQUE SAT: O modelo de torção permite a discriminação eficiente entre $s=0$ e $s=1$. O tempo da porta escala como $O(n)$, que é polinomial no número de bits. Como UNIQUE SAT é NP-difícil sob redução polinomial aleatorizada, isso implica que tal modelo não linear poderia resolver problemas NP-difíceis eficientemente.
• 3SAT: O modelo Morse–Smale distingue eficientemente entre $s=0$ e $s>0$. O tempo da porta escala como $O(n)$, permitindo a solução eficiente de 3SAT, um problema NP-completo.
• #SAT: O modelo de garfo supercrítico, utilizado dentro de uma estrutura de busca binária, permite a medição eficiente do inteiro exato $s$. A complexidade de tempo total é $O(n \log(2^n \epsilon^{-1}))$, fornecendo uma solução eficiente para #SAT, um problema #P-completo.
• Implicações de Complexidade: O artigo demonstra que, no limite livre de ruído, a inclusão de não linearidades específicas de um único qubit eleva o poder computacional de um computador quântico de BQP para classes capazes de resolver problemas NP-difíceis e #P-completos em tempo polinomial.

Significado e Alegações
O artigo afirma explorar a interação entre formas distintas de não linearidade e seu poder computacional resultante. Estabelece que:

1. Hamiltonianos não lineares do tipo campo médio podem teoricamente contornar as limitações da mecânica quântica linear regarding a distinguibilidade de estados.
2. Retratos de fase projetados especificamente (torção, fluxo Morse–Smale e fluxo bistável) podem ser mapeados para Hamiltonianos não lineares específicos que resolvem problemas de satisfatibilidade cada vez mais complexos.
3. Embora os modelos sejam hipotéticos, eles oferecem uma estrutura teórica para entender as consequências computacionais da não linearidade.

Os autores permanecem modestos quanto à realização física. Eles observam que os resultados assumem uma implementação escalável e tolerante a falhas, o que não é abordado. Eles sugerem que a não linearidade $\langle \sigma_z \rangle \sigma_z$ pode ser simulada com átomos ultrafrios, mas caracterizam os modelos Morse–Smale e de garfo supercrítico como "algo exóticos" e provavelmente fenômenos emergentes (por exemplo, Hamiltonianos efetivos de Floquet) em vez de interações fundamentais. O artigo conclui que esses modelos servem como uma ferramenta teórica para sondar os limites da complexidade computacional na presença de não linearidade.