Algoritmos de otimização quântica são algoritmos quânticos usados para resolver problemas de otimização. 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.
Ajuste de dados quântico 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.
Ajuste de mínimos quadrados quântico 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 pontos de dados de entrada e funções contínuas . O algoritmo encontra e fornece como saída uma função contínua que é uma combinação linear de :
Em outras palavras, o algoritmo encontra os coeficientes complexos , e assim o vetor .
O algoritmo visa minimizar o erro, que é dado por:
onde é definida como a seguinte matriz:
O algoritmo quântico de ajuste de mínimos quadrados 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 e a estimativa da qualidade do ajuste . 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 no caso em que é esparsa e o número de condição (isto é, a razão entre o maior e o menor autovalores) de ambos e é pequeno.
Programação semidefinida quântica 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 (dada como entrada) com a variável . Denote por o espaço de todas as matrizes simétricas . A variável deve estar no cone (fechado convexo) de matrizes simétricas semidefinidas positivas . O produto interno de duas matrizes é definido como:
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 (dadas como entrada) com a variável de otimização a ser menor que um valor especificado (dado como entrada). Finalmente, o problema de SDP pode ser escrito como:
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.
O algoritmo quântico As entradas do algoritmo são 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 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 ):
Em cada iteração, um limiar diferente é escolhido, e o algoritmo produz como saída uma solução tal que (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 para o qual uma solução 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.
Otimização combinatória quântica 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 recebe como entrada a string de bits e produz como saída um bit (0 ou 1). O problema de otimização combinatória de bits e cláusulas é encontrar uma string de bits que maximize a função
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 que está próxima de maximizar .
Algoritmo de otimização aproximada quântica Para otimização combinatória, o algoritmo de otimização aproximada quântica (QAOA) teve brevemente uma razão de aproximação melhor do que qualquer algoritmo clássico de tempo polinomial conhecido (para um certo problema), até que um algoritmo clássico mais eficaz fosse proposto. A aceleração relativa do algoritmo quântico é uma questão de pesquisa em aberto.
O QAOA consiste nas seguintes etapas:
Definir um Hamiltoniano de custo tal que seu estado fundamental codifique a solução para o problema de otimização. Definir um Hamiltoniano de mistura . Definir os oráculos e , com parâmetros e α. Aplicação repetida dos oráculos e , na ordem: Preparar um estado inicial, que é uma superposição de todos os estados possíveis e aplicar ao estado. Usar métodos clássicos para otimizar os parâmetros 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 . thumb|457x457px|Exemplo de ansatz QAOA para um circuito de três qubits 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 e o Hamiltoniano final com , 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 ângulos (parâmetros), onde é um inteiro de entrada, que pode ser identificado como o número de camadas do oráculo . 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 é estimada. Os ângulos são então atualizados classicamente para aumentar . Após este procedimento ser repetido um número suficiente de vezes, o valor de é 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.
QAOA para encontrar a cobertura mínima de vértices de um grafo 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. thumb|220x220px|Grafo de exemplo para ilustrar o problema da cobertura mínima de 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:
thumb|Saída da implementação do QAOA em Qiskit para o problema da cobertura mínima de vértices. Observe que a string de bits |1010> é invertida como |0101> pois o Qiskit usa ordenação reversa de bits. thumb|Implementação em Qiskit do QAOA para o problema da cobertura mínima de vértices. 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.
Generalização do QAOA para otimização combinatória com restrições Em princípio, o valor ótimo de pode ser alcançado com precisão arbitrária, isso é garantido pelo teorema adiabático ou alternativamente pela universalidade dos unitários do QAOA. 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.
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).
No artigo How many qubits are needed for quantum computational supremacy submetido ao arXiv, 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 e o número de qubits necessários para a vantagem quântica. Um estudo do QAOA e do algoritmo MaxCut mostra que é necessário para uma vantagem escalável.
Variações do QAOA