Resumo Técnico: Codificação Rotacional de Funções Objetivo para Otimização Quântica

Declaração do Problema

Algoritmos de busca quântica, como o algoritmo de Grover, oferecem vantagens computacionais para problemas de satisfação de restrições (CSPs) e otimização combinatória. No entanto, sua praticidade é fortemente limitada pelo custo de construção de oráculos específicos do problema. Nas abordagens tradicionais para otimização, os oráculos são baseados em Booleanos e dependem de registradores de múltiplos qubits para armazenar explicitamente os valores da função objetivo como números binários. Esses valores são então comparados contra um limiar (threshold) dinamicamente atualizado usando operadores aritméticos (por exemplo, incrementadores controlados) e comparadores.

Este método convencional incorre em um overhead significativo:

1. Intensidade de Recursos: Requer múltiplos registradores de múltiplos qubits (um para o valor do objetivo, outro para o limiar) e numerosos qubits auxiliares (ancilla).
2. Profundidade de Circuito e Custo: Os circuitos aritméticos e de comparação são construídos a partir de muitos gates reversíveis, levando a contagens de gates elevadas, circuitos profundos e maior suscetibilidade à decoerência.
3. Execução Iterativa: Como os oráculos Booleanos não podem inerentemente classificar soluções válidas por custo, a otimização requer a execução iterativa do algoritmo de busca com um limiar repetidamente atualizado, aumentando ainda mais o tempo de execução.

O artigo aborda a necessidade de uma representação alternativa que incorpore informações da função objetivo diretamente nas operações quânticas para reduzir esses custos.

Metodologia: Contador de Rotação Angular (ARC)

Os autores introduzem o Contador de Rotação Angular (Angular Rotational Counter - ARC), um design de circuito que codifica funções objetivo como uma soma acumulada de rotações quânticas em um registrador de um único qubit, em vez de um valor binário em um registrador de múltiplos qubits.

Mecanismo Central

O ARC é projetado para funções objetivo $C(x)$ que podem ser decompostas em uma soma ponderada de funções Booleanas:
$$C(x) = \sum_{i=1}^{m} w_i f_i(x)$$
onde $w_i \geq 0$ são pesos e $f_i(x)$ são funções Booleanas.

O circuito opera da seguinte forma:

1. Entrada: Uma solução candidata $x$ é processada.
2. Avaliação Booleana: Cada termo $f_i(x)$ é computado em um qubit de controle.
3. Codificação Rotacional: Se $f_i(x) = 1$, uma porta de rotação controlada (especificamente $RX$) aplica uma rotação de ângulo $\frac{\pi}{K} w_i$ a um qubit de saída. Se $f_i(x) = 0$, nenhuma rotação ocorre.
4. Acumulação: O ângulo de rotação total aplicado ao qubit de saída é proporcional ao valor do objetivo: $\theta = \frac{\pi}{K} C(x)$.

Propriedades Matemáticas

O artigo estabelece que a probabilidade de medição do qubit de saída é monotonicamente relacionada ao valor do objetivo $C(x)$:

• Maximização: Se o qubit de saída for inicializado em $|0\rangle$, a probabilidade de medir $|1\rangle$ aumenta conforme $C(x)$ aumenta (dentro do intervalo $(0, K)$).
• Minimização: Se inicializado em $|1\rangle$, a probabilidade de medir $|1\rangle$ diminui conforme $C(x)$ aumenta.
• Restrição: $K$ deve ser definido como maior ou igual ao valor máximo possível do objetivo para garantir a monotonicidade dentro do intervalo relevante.

Aplicação: Atribuição de Estados

Os autores aplicam o ARC ao problema de atribuição de estados para autômatos finitos, um problema fundamental na síntese estrutural de autômatos. O objetivo é atribuir codificações binárias distintas aos estados para minimizar uma função de custo.

• Função de Custo: Uma distância de Hamming ponderada heurística entre as codificações de estado, um caso especial do problema de atribuição quadrática.
• Construção do Oráculo: O oráculo inclui um verificador de codificação (para garantir estados distintos) e o calculador de custo baseado em ARC. O ARC substitui o contador aritmético e o comparador tradicionais.
• Algoritmo: O oráculo é integrado ao algoritmo de Grover. O algoritmo executa a busca de Grover uma única vez com o oráculo construído. Os qubits de entrada são então medidos, e $r \geq 1$ soluções são escolhidas com base nas maiores probabilidades de medição. Crucialmente, essas soluções selecionadas ainda devem ser verificadas para confirmar validade e otimalidade, pois as probabilidades de medição indicam tendências de custo, mas não garantem uma solução válida em uma única tentativa sem verificação pós-processamento.

Principais Contribuições

1. Estrutura de Codificação Rotacional: Introdução do ARC como um método para representar funções objetivo decomponíveis via rotações quânticas acumuladas em um único qubit, contrastando com a codificação binária explícita.
2. Formalização Matemática: Prova de que o ARC codifica rotacionalmente a função objetivo e que a probabilidade de medição do qubit de saída é monotonicamente dependente do valor do objetivo, permitindo a otimização direta sem atualizações iterativas de limiar.
3. Design de Oráculo para Atribuição de Estados: Construção de um oráculo específico para o problema de atribuição de estados usando uma função de custo de distância de Hamming ponderada, demonstrando a aplicabilidade do ARC a problemas importantes de otimização combinatória.
4. Avaliação Abrangente: Uma análise comparativa dos oráculos baseados em ARC contra oráculos baseados em Booleanos em 26 benchmarks.

Resultados Experimentais

Os autores avaliaram o oráculo ARC contra os correspondentes oráculos baseados em Booleanos em 26 benchmarks de máquinas de estados finitos da biblioteca LGSynth'91. Os circuitos foram transpilados usando Qiskit (otimização de nível 3) para gates nativos (CZ, RX, RZ, $\sqrt{X}$, X).

Métricas de Desempenho (Reduções Médias Aritméticas):

• Contagem de Qubits: Reduzida em 20,8% (variando de 3,9% a 45,2%). Isso é atribuído à substituição de registradores de múltiplos qubits para custo e limiar por um único registrador de um qubit.
• Contagem de Gates: Reduzida em 89,3% (variando de 63,8% a 9gg.5%).
• Profundidade de Circuito: Reduzida em 92,4% (variando de 72,8% a 99,7%).
• Custo Quântico de Transpilação (TQC): Reduzido em 90,6% (variando de 67,4% a 99,6%).

As reduções significativas na contagem de gates e profundidade devem-se principalmente à eliminação de gates de incremento controlado caros e comparadores, que são substituídos por gates de rotação controlada no design do ARC.

Significância e Alegações

O artigo afirma que o ARC oferece uma redução substancial no custo do circuito para os benchmarks avaliados, estabelecendo a codificação rotacional como uma alternativa promissora para a codificação binária explícita de funções objetivo.

• Eficiência de Recursos: A abordagem reduz significativamente os requisitos de qubits, gates e profundidade, o que é crítico para dispositivos quânticos de curto prazo (near-term) com conectividade e coerência limitadas.
• Estrutura Algorítmica: Permite a otimização dentro de uma única execução de um algoritmo de busca quântica ao codificar o custo diretamente nas amplitudes de probabilidade, removendo a necessidade de atualizações iterativas de limiar exigidas pelos oráculos Booleanos. O algoritmo seleciona soluções candidatas com base nas probabilidades de medição, seguidas por uma etapa de verificação para confirmar a validade.
• Escalabilidade: A análise teórica sugere que o calculador de custo ARC tem uma complexidade de tempo de $O(n^2 \log n)$, que é significativamente menor do que o escalonamento exponencial observado nos métodos baseados em Booleanos anteriores para atribuição de estados.

Limitações e Modéstia:
Os autores afirmam explicitamente que, embora os resultados demonstrem melhorias significativas na eficiência de recursos do circuito, eles não estabelecem por si só uma redução no tempo de execução física ou um speedup quântico assintótico. Os benefícios são atualmente enquadrados em termos de custos de síntese de circuito (qubits, gates, profundidade) em vez de vantagens de tempo de execução garantidas em hardware físico, que também dependeriam de ruído e correção de erros. A aplicabilidade é demonstrada atualmente para funções objetivo decomponíveis (somas ponderadas de funções Booleanas), embora os autores sugiram que este framework possa se estender a outras classes de problemas.