Algoritmos de otimização quântica 📖 Wikipedia

Algoritmos de otimização quântica são algoritmos quânticos usados para resolver problemas de otimização.^[1] A otimização matemática lida com encontrar a melhor solução para um problema (de acordo com algum critério) a partir de um conjunto de soluções possíveis. Na maioria das vezes, o problema de otimização é formulado como um problema de minimização, onde se tenta minimizar um erro que depende da solução: a solução ótima tem o erro mínimo. Diferentes técnicas de otimização são aplicadas em vários campos, como mecânica, economia e engenharia, e à medida que a complexidade e a quantidade de dados envolvidos aumentam, são necessárias maneiras mais eficientes de resolver problemas de otimização. A computação quântica pode permitir que problemas que não são praticamente viáveis em computadores clássicos sejam resolvidos, ou sugerir uma aceleração considerável em relação ao melhor algoritmo clássico conhecido.

O ajuste de dados é um processo de construção de uma função matemática que melhor se ajusta a um conjunto de pontos de dados. A qualidade do ajuste é medida por alguns critérios, geralmente a distância entre a função e os pontos de dados.

Um dos tipos mais comuns de ajuste de dados é resolver o problema de mínimos quadrados, minimizando a soma dos quadrados das diferenças entre os pontos de dados e a função ajustada.

O algoritmo recebe ${\displaystyle N}$ pontos de dados de entrada ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$ e ${\displaystyle M}$ funções contínuas ${\displaystyle f_{1},f_{2},...,f_{M}}$. O algoritmo encontra e fornece como saída uma função contínua ${\displaystyle f_{\vec {\lambda }}}$ que é uma combinação linear de ${\displaystyle f_{j}}$:

${\displaystyle f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}}$

Em outras palavras, o algoritmo encontra os coeficientes complexos ${\displaystyle \lambda _{j}}$, e assim o vetor ${\displaystyle {\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})}$.

O algoritmo visa minimizar o erro, que é dado por:

${\displaystyle E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}}$

onde ${\displaystyle F}$ é definida como a seguinte matriz:

${\displaystyle {F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}}$

O algoritmo quântico de ajuste de mínimos quadrados^[2] faz uso de uma versão do algoritmo quântico para sistemas lineares de equações de Harrow, Hassidim e Lloyd (HHL), e produz os coeficientes ${\displaystyle \lambda _{j}}$ e a estimativa da qualidade do ajuste ${\displaystyle E}$. Ele consiste em três sub-rotinas: um algoritmo para realizar uma operação pseudo-inversa, uma rotina para a estimativa da qualidade do ajuste e um algoritmo para aprender os parâmetros do ajuste.

Como o algoritmo quântico é baseado principalmente no algoritmo HHL, ele sugere uma melhoria exponencial^[3] no caso em que ${\displaystyle F}$ é esparsa e o número de condição (isto é, a razão entre o maior e o menor autovalores) de ambos ${\displaystyle FF^{\dagger }}$ e ${\displaystyle F^{\dagger }F}$ é pequeno.

A programação semidefinida (SDP) é um subcampo da otimização que lida com a otimização de uma função objetivo linear (uma função especificada pelo usuário a ser minimizada ou maximizada), sobre a interseção do cone de matrizes semidefinidas positivas com um espaço afim. A função objetivo é um produto interno de uma matriz ${\displaystyle C}$ (dada como entrada) com a variável ${\displaystyle X}$. Denote por ${\displaystyle \mathbb {S} ^{n}}$ o espaço de todas as matrizes simétricas ${\displaystyle n\times n}$. A variável ${\displaystyle X}$ deve estar no cone (fechado convexo) de matrizes simétricas semidefinidas positivas ${\displaystyle \mathbb {S} _{+}^{n}}$. O produto interno de duas matrizes é definido como:

${\displaystyle \langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}$

O problema pode ter restrições adicionais (dadas como entradas), também geralmente formuladas como produtos internos. Cada restrição força o produto interno das matrizes ${\displaystyle A_{k}}$ (dadas como entrada) com a variável de otimização ${\displaystyle X}$ a ser menor que um valor especificado ${\displaystyle b_{k}}$ (dado como entrada). Finalmente, o problema de SDP pode ser escrito como:

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{sujeito a}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}}$

O melhor algoritmo clássico não é conhecido por rodar incondicionalmente em tempo polinomial. Sabe-se que o problema de viabilidade correspondente está ou fora da união das classes de complexidade NP e co-NP, ou na interseção de NP e co-NP.^[4]

As entradas do algoritmo são ${\displaystyle A_{1}...A_{m},C,b_{1}...b_{m}}$ e parâmetros relacionados ao traço da solução, precisão e valor ótimo (o valor da função objetivo no ponto ótimo).

O algoritmo quântico^[5] consiste em várias iterações. Em cada iteração, ele resolve um problema de viabilidade, ou seja, encontra qualquer solução satisfazendo as seguintes condições (dado um limiar ${\displaystyle t}$):

${\displaystyle {\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}}$

Em cada iteração, um limiar diferente ${\displaystyle t}$ é escolhido, e o algoritmo produz como saída uma solução ${\displaystyle X}$ tal que ${\displaystyle \langle C,X\rangle _{\mathbb {S} ^{n}}\leq t}$ (e as outras restrições também são satisfeitas) ou uma indicação de que nenhuma solução existe. O algoritmo realiza uma busca binária para encontrar o limiar mínimo ${\displaystyle t}$ para o qual uma solução ${\displaystyle X}$ ainda existe: isso dá a solução mínima para o problema de SDP.

O algoritmo quântico fornece uma melhoria quadrática em relação ao melhor algoritmo clássico no caso geral, e uma melhoria exponencial quando as matrizes de entrada são de baixo rank.

O problema de otimização combinatória visa encontrar um objeto ótimo a partir de um conjunto finito de objetos. O problema pode ser formulado como uma maximização de uma função objetivo que é uma soma de funções booleanas. Cada função booleana ${\displaystyle \,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\rightarrow \lbrace {0,1}\rbrace }$ recebe como entrada a string de ${\displaystyle n}$ bits ${\displaystyle z=z_{1}z_{2}\ldots z_{n}}$ e produz como saída um bit (0 ou 1). O problema de otimização combinatória de ${\displaystyle n}$ bits e ${\displaystyle m}$ cláusulas é encontrar uma string de ${\displaystyle n}$ bits ${\displaystyle z}$ que maximize a função

${\displaystyle C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)}$

A otimização aproximada é uma maneira de encontrar uma solução aproximada para um problema de otimização, que é frequentemente NP-difícil. A solução aproximada do problema de otimização combinatória é uma string ${\displaystyle z}$ que está próxima de maximizar ${\displaystyle C(z)}$.

Para otimização combinatória, o algoritmo de otimização aproximada quântica (QAOA)^[6] teve brevemente uma razão de aproximação melhor do que qualquer algoritmo clássico de tempo polinomial conhecido (para um certo problema),^[7] até que um algoritmo clássico mais eficaz fosse proposto.^[8] A aceleração relativa do algoritmo quântico é uma questão de pesquisa em aberto.

O QAOA consiste nas seguintes etapas:

1. Definir um Hamiltoniano de custo ${\displaystyle H_{C}}$ tal que seu estado fundamental codifique a solução para o problema de otimização.
2. Definir um Hamiltoniano de mistura ${\displaystyle H_{M}}$.
3. Definir os oráculos ${\displaystyle U_{C}(\gamma )=\exp(-\imath \gamma H_{C})}$ e ${\displaystyle U_{M}(\alpha )=\exp(-\imath \alpha H_{M})}$, com parâmetros ${\displaystyle \gamma }$ e α.
4. Aplicação repetida dos oráculos ${\displaystyle U_{C}}$ e ${\displaystyle U_{M}}$, na ordem: ${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})=\coprod _{i=1}^{N}(U_{C}(\gamma _{i})U_{M}(\alpha _{i}))}$
5. Preparar um estado inicial, que é uma superposição de todos os estados possíveis e aplicar ${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$ ao estado.
6. Usar métodos clássicos para otimizar os parâmetros ${\displaystyle {\boldsymbol {\gamma }},{\boldsymbol {\alpha }}}$ e medir o estado de saída do circuito otimizado para obter a solução ótima aproximada para o Hamiltoniano de custo. Uma solução ótima será aquela que maximiza o valor esperado do Hamiltoniano de custo ${\displaystyle H_{C}}$.

A estrutura do algoritmo, isto é, o uso de Hamiltonianos de custo e mistura, é inspirada no teorema adiabático quântico, que afirma que começando em um estado fundamental de um Hamiltoniano dependente do tempo, se o Hamiltoniano evoluir lentamente o suficiente, o estado final será um estado fundamental do Hamiltoniano final. Além disso, o teorema adiabático pode ser generalizado para qualquer outro autoestado, desde que não haja sobreposição (degenerescência) entre diferentes autoestados durante a evolução. Identificando o Hamiltoniano inicial com ${\displaystyle H_{M}}$ e o Hamiltoniano final com ${\displaystyle H_{C}}$, cujos estados fundamentais codificam a solução para o problema de otimização de interesse, pode-se aproximar o problema de otimização como a evolução adiabática do Hamiltoniano de um inicial para um final, cujo estado (auto)fundamental dá a solução ótima. Em geral, o QAOA depende do uso de operadores unitários dependentes de ${\displaystyle 2p}$ ângulos (parâmetros), onde ${\displaystyle p>1}$ é um inteiro de entrada, que pode ser identificado como o número de camadas do oráculo ${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$. Esses operadores são aplicados iterativamente em um estado que é uma superposição quântica de igual peso de todos os estados possíveis na base computacional. Em cada iteração, o estado é medido na base computacional e a função booleana ${\displaystyle C(z)}$ é estimada. Os ângulos são então atualizados classicamente para aumentar ${\displaystyle C(z)}$. Após este procedimento ser repetido um número suficiente de vezes, o valor de ${\displaystyle C(z)}$ é quase ótimo, e o estado sendo medido também está próximo de ser ótimo. Um circuito de exemplo que implementa QAOA em um computador quântico é dado na figura. Este procedimento é destacado usando o seguinte exemplo de encontrar a cobertura mínima de vértices de um grafo.^[9]

O objetivo aqui é encontrar uma cobertura mínima de vértices de um grafo: uma coleção de vértices tal que cada aresta no grafo contenha pelo menos um dos vértices na cobertura. Assim, esses vértices "cobrem" todas as arestas. Desejamos encontrar uma cobertura de vértices que tenha o menor número possível de vértices. Coberturas de vértices podem ser representadas por uma string de bits onde cada bit denota se o vértice correspondente está presente na cobertura. Por exemplo, a string de bits 0101 representa uma cobertura consistindo do segundo e quarto vértices em um grafo com quatro vértices.

Considere o grafo dado na figura. Ele tem quatro vértices e há duas coberturas mínimas de vértices para este grafo: vértices 0 e 2, e os vértices 1 e 2. Estes podem ser respectivamente representados pelas strings de bits 1010 e 0110. O objetivo do algoritmo é amostrar essas strings de bits com alta probabilidade. Neste caso, o Hamiltoniano de custo tem dois estados fundamentais, |1010⟩ e |0110⟩, coincidindo com as soluções do problema. O Hamiltoniano de mistura é a simples soma não comutante de operações Pauli-X em cada nó do grafo e eles são dados por:

${\displaystyle H_{C}=-0.25Z_{3}+0.5Z_{0}+0.5Z_{1}+1.25Z_{2}+0.75(Z_{0}Z_{1}+Z_{0}Z_{2}+Z_{2}Z_{3}+Z_{1}Z_{2})}$

${\displaystyle H_{M}=X_{0}+X_{1}+X_{2}+X_{3}}$

Implementar o algoritmo QAOA para este circuito de quatro qubits com duas camadas do ansatz em qiskit (veja figura) e otimizar leva a uma distribuição de probabilidade para os estados dada na figura. Isso mostra que os estados |0110⟩ e |1010⟩ têm as maiores probabilidades de serem medidos, exatamente como esperado.

Em princípio, o valor ótimo de ${\displaystyle C(z)}$ pode ser alcançado com precisão arbitrária, isso é garantido pelo teorema adiabático^[10][11] ou alternativamente pela universalidade dos unitários do QAOA.^[12] No entanto, é uma questão em aberto se isso pode ser feito de maneira viável. Por exemplo, foi mostrado que o QAOA exibe uma forte dependência na razão entre a restrição de um problema e as variáveis (densidade do problema), colocando uma restrição limitadora na capacidade do algoritmo de minimizar uma função objetivo correspondente.^[13]

Logo foi reconhecido que uma generalização do processo QAOA é essencialmente uma aplicação alternada de um passeio quântico de tempo contínuo em um grafo subjacente seguido por um deslocamento de fase dependente da qualidade aplicado a cada estado solução. Este QAOA generalizado foi denominado QWOA (Quantum Walk-based Optimisation Algorithm).^[14]

No artigo How many qubits are needed for quantum computational supremacy submetido ao arXiv,^[15] os autores concluem que um circuito QAOA com 420 qubits e 500 restrições exigiria pelo menos um século para ser simulado usando um algoritmo de simulação clássico rodando em supercomputadores de estado da arte, de modo que isso seria suficiente para a supremacia computacional quântica.

Uma comparação rigorosa do QAOA com algoritmos clássicos pode dar estimativas sobre a profundidade ${\displaystyle p}$ e o número de qubits necessários para a vantagem quântica. Um estudo do QAOA e do algoritmo MaxCut mostra que ${\displaystyle p>11}$ é necessário para uma vantagem escalável.^[16]

Várias variações da estrutura básica do QAOA foram propostas,^[17] que incluem variações no ansatz do algoritmo básico. A escolha do ansatz tipicamente depende do tipo de problema, como problemas combinatórios representados como grafos, ou problemas fortemente influenciados pelo design do hardware. No entanto, o design do ansatz deve equilibrar especificidade e generalidade para evitar sobreajuste e manter a aplicabilidade a uma ampla gama de problemas. Por esta razão, projetar ansatze ótimos para QAOA é um tópico extensivamente pesquisado e amplamente investigado. Algumas das variantes propostas são:

1. QAOA multi-ângulo^[18]
2. QAOA expressivo (XQAOA)^[19]
3. QAOA+^[20]
4. QAOA contra-adiabático digitalizado^[21]
5. Ansatz de operador alternante quântico^[22], que permite restrições no problema de otimização, etc.

Outra variação do QAOA foca em técnicas para otimização de parâmetros, que visa selecionar o conjunto ótimo de parâmetros iniciais para um determinado problema e evitar platôs estéreis, que representam parâmetros que levam a autoestados que correspondem a platôs na paisagem energética do Hamiltoniano de custo.

Finalmente, houve um interesse significativo de pesquisa em alavancar hardware específico para melhorar o desempenho do QAOA em várias plataformas, como íons presos, átomos neutros, qubits supercondutores e computadores quânticos fotônicos. Os objetivos dessas abordagens incluem superar limitações de conectividade de hardware e mitigar problemas relacionados a ruídos para ampliar a aplicabilidade do QAOA a uma ampla gama de problemas de otimização combinatória.

O circuito quântico mostrado aqui é de um exemplo simples de como o algoritmo QAOA pode ser implementado em Python^[23] usando Qiskit, uma estrutura de desenvolvimento de software de computação quântica de código aberto da IBM.

• Computação quântica adiabática
• Recozimento quântico

• Implementação do algoritmo QAOA para o problema da mochila com Classiq^{[ligação inativa]}