A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

Resumo Técnico: Um Algoritmo de Busca Quântica Não Estruturada para Otimização Discreta

Enunciado do Problema
O artigo aborda o desafio de resolver problemas de otimização discreta, especificamente a otimização combinatória, onde as variáveis são binárias e as derivadas não podem ser definidas. Embora os métodos baseados em gradiente sejam eficazes para variáveis contínuas, eles falham em espaços discretos, que são frequentemente NP-difíceis. As abordagens quânticas existentes, como o framework de Otimização Binária Não Restrita Quadrática (QUBO), são limitadas a funções objetivo que contêm apenas termos de primeira e segunda ordem. Além disso, muitos algoritmos de otimização quântica atuais (por exemplo, Algoritmos Quânticos Variacionais) dependem de loops híbridos clássico-quânticos que podem sofrer com ruído ou exigir circuitos profundos. Os autores propõem um método para encontrar os extremos ou raízes de funções discretas gerais, $f(x)$, que podem conter termos de ordem superior além do limite quadrático do QUBO.

Metodologia: O Algoritmo QSERA
Os autores introduzem o Algoritmo de Busca Quântica para Extremos e Raízes (QSERA), um membro da família de Algoritmos de Busca Quântica (QSA) baseados no algoritmo de Grover. A metodologia procede em duas etapas primárias:

1. Construção do Oráculo ($f(x) \to u(z)$):
   A primeira etapa envolve o mapeamento da condição de encontrar um extremo (ou raiz) $f(x^*) \approx f^*$ para um problema de busca não estruturada por uma string binária $z^*$.

   • Redimensionamento (Rescaling): A função objetivo $f(x)$ é redimensionada para uma função $g(x) \in [0, 1]$. Para maximização, $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$; para minimização, $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$; e para busca de raízes, uma transformação específica é aplicada. Isso requer conhecimento a priori ou estimativas do mínimo global ($f_{min}$) e máximo global ($f_{max}$).
   • Amplificação: Para criar um oráculo binário $u(z)$ onde $u(z^*) = 1$ e $u(z \neq z^*) = 0$, a função $g(x)$ é elevada a uma potência alta $n$ (ou seja, $u_n(z) \equiv g(x)^n$). À medida que $n \to \infty$, $u_n(z)$ aproxima-se do oráculo ideal.
   • Generalização: O artigo observa que $f(x)$ pode ser um polinômio geral com termos até ordem $K$ (Eq. 10), permitindo funções objetivo mais complexas do que a forma padrão de QUBO.
   • Implementação de Portas: Os autores derivam o circuito quântico para o oráculo. Eles definem operadores autoadjuntos $B_k$ correspondentes a variáveis binárias e constroem um operador unitário $G$ tal que $G|z\rangle = g(x)|z\rangle$. O operador oráculo $Q^*$ é então definido como $e^{i\pi G^n}$. Este é decomposto em um produto de operadores unitários $Q^*_j$ para cada ordem de termos (ordem zero, primeira, segunda, etc.), implementados usando qubits auxiliares (ancilla) e portas de deslocamento de fase (phase shift).

2. Execução da Busca:
   Uma vez construído o oráculo $Q^*$, o algoritmo emprega o operador de difusão de Grover ($Q_+$) e o oráculo ($Q^*$) em um loop iterativo. O estado é inicializado em uma superposição uniforme, e o operador $(Q_+ Q^*)$ é aplicado $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ vezes para amplificar a amplitude do estado alvo $|z^*\rangle$.

Principais Contribuições

• Generalização além do QUBO: Ao contrário de muitos métodos de otimização quântica restritos a formas quadráticas, o QSERA pode lidar com funções objetivo com termos de ordem superior (cúbicos, quárticos, etc.), tornando-o aplicável a uma classe mais ampla de problemas combinatórios.
• Construção Explícita de Circuito: O artigo fornece uma derivação matemática detalhada para a construção de portas de oráculo quântico para ordens polinomiais arbitrárias, incluindo o cálculo recursivo dos coeficientes necessários para os parâmetros do circuito.
• Lidando com Limites Aproximados: Os autores analisam o cenário em que $f_{min}$ e $f_{max}$ não são conhecidos exatamente. Eles demonstram que, embora o algoritmo ainda possa funcionar com estimativas, a probabilidade de encontrar o ótimo exato depende da escolha do parâmetro de potência $n$. Se $n$ for muito grande, o sinal do oráculo pode desaparecer; se for muito pequeno, o sinal não será distinto o suficiente. Existe um $n$ ótimo para equilibrar esses fatores.

Resultados: Estudo de Caso de Otimização de Portfólio
Os autores validam o QSERA usando um problema de otimização de portfólio com $N_a = 4$ ativos, resultando em $N=16$ portfólios possíveis.

• Configuração: O objetivo era encontrar um portfólio de 2 ativos que minimizasse a distância em relação a um retorno de referência e volatilidade. A função objetivo incluiu termos até a quarta ordem.
• Implementação: Um circuito quântico foi montado usando 4 qubits para os estados do portfólio, 2 qubits auxiliares para operações AND e 1 auxiliar para rastreamento de fase.
• Desempenho:
  • Com o número ótimo de iterações de Grover ($m_{opt} = 2$) e um valor de $n \approx 24$ cuidadosamente escolhido, o algoritmo identificou com sucesso o portfólio ideal (estado $|1001\rangle$) com a maior probabilidade.
  • O segundo melhor portfólio ($|0101\rangle$) também mostrou uma probabilidade relativamente alta, refletindo o fato de que o algoritmo encontrou a solução mais próxima dos limites estimados.
  • O estudo confirmou que, se $f_{min}$ e $f_{max}$ forem estimados em vez de exatos, a probabilidade de medir o verdadeiro ótimo é inferior a 1, necessitando de múltiplas "shots" (execuções repetidas) para distinguir o verdadeiro ótimo das soluções quase ótimas.
  • A relação entre a potência $n$ e a probabilidade de sucesso foi visualizada, mostrando um pico de probabilidade para valores intermediários de $n$, com o desempenho degradando se $n$ for muito grande (supressão de sinal) ou muito pequeno (discriminação insuficiente).

Significância e Alegações
O artigo afirma que o QSERA oferece uma aceleração quadrática ($O(\sqrt{N})$) sobre a busca bruta clássica para encontrar extremos ou raízes de funções discretas. Sua principal significância reside na sua capacidade de:

1. Resolver problemas de otimização com funções objetivo de ordem superior que são incompatíveis com as formulações padrão de QUBO.
2. Operar sem a necessidade de loops de otimização de parâmetros híbridos clássico-quânticos (ao contrário dos VQAs), baseando-se, em vez disso, em uma execução quântica de disparo único (embora múltiplas execuções possam ser necessárias para confiança estatística se os limites forem aproximados).
3. Potencialmente abordar funções contínuas "ruidosas" ou de gradiente íngreme (após a discretização) onde métodos baseados em gradiente podem falhar, embora os autores observem que a busca estruturada é geralmente mais eficiente para variáveis contínuas.

Os autores concluem que, embora o algoritmo exija o conhecimento dos limites da função para garantir o sucesso, ele permanece uma ferramenta robusta para otimização discreta, particularmente quando a estrutura da função objetivo excede as capacidades das abordagens baseadas em QUBO atuais.