A Statistical Approach to Analyzing the Quantum Alternating Operator Ansatz with Grover Mixer
Autores
|
7435 |
2733,3229
|
|
|
7436 |
2733,3229
|
Informações:
Publicações do PESC
O operador Grover mixer é uma versão variacional do operador difusão de Grover, introduzido como um operador mixing para o Quantum Alternating Operator Ansatz (QAOA) e usado em duas variantes, conhecidas como Grover Mixer QAOA (GM-QAOA) e Grover Mixer Threshold QAOA (GM-Th-QAOA). Uma propriedade importante dessas variantes é que o valor esperado é invariante para qualquer permutação de estados. Como consequência, o algoritmo é independente da estrutura do problema. Se, por um lado, esta característica levanta sérias dúvidas sobre a capacidade do algoritmo de superar o bound do problema de busca não estruturada, por outro lado, pode abrir caminho para o seu estudo analítico. Neste sentido, este trabalho considera uma abordagem estatística para analisar tanto o GM-QAOA quanto o GM-Th-QAOA que resulta em expressões analíticas para o valor esperado que dependem da distribuição de probabilidade associada ao espectro do hamiltoniano do problema. Embora no caso do GM-QAOA a expressão dependa exponencialmente do número de camadas, o caso mais simples do GM-Th-QAOA resulta em uma expressão independente desse parâmetro e, com ela, fornecemos limites para diferentes métricas de desempenho. Posteriormente, estendemos a análise do GM-Th-QAOA para um contexto mais geral para o QAOA com o Grover mixer que chamamos de Grover-based QAOA. Nessa estrutura, que permite ao operador separador de fase codificar qualquer compilação da função de custos, generalizamos todos os bounds utilizando um argumento de contradição com a otimalidade do algoritmo de Grover no problema de busca não estruturada. Como resultado, obtemos a principal contribuição deste trabalho, formalizando a noção de que o Grover mixer reflete, no máximo, uma aceleração quadrática ao estilo do algoritmo de Grover sobre a força bruta clássica.
The Grover mixer operator is a variational version of Grover's diffusion operator, introduced as a mixing operator for the Quantum Alternating Operator Ansatz (QAOA) and used in two variants known as Grover Mixer QAOA (GM-QAOA) and Grover Mixer Threshold QAOA (GM-Th-QAOA). An important property of these variants is that the expectation value is invariant over any permutation of states. As a consequence, the algorithm is independent of the structure of the problem. If, on the one hand, this characteristic raises serious doubts about the capacity of the algorithm to overcome the bound of the unstructured search problem, on the other hand, it can pave the way to its analytical study. In this sense, this work considers a statistical approach to analyze both GM-QAOA and GM-Th-QAOA that results in analytical expressions for the expectation value depending on the probability distribution associated with the problem Hamiltonian spectrum. Although in the case of GM-QAOA, the expression depends exponentially on the number of layers, the more simple case of GM-Th-QAOA results in an expression with complexity independent of that parameter, and, with it, we provide bounds for different performance metrics. Subsequently, we extend the analysis of GM-Th-QAOA to a more general context for QAOA with the Grover mixer we called Grover-based QAOA. In that framework, which allows the phase separation operator to encode any compilation of the cost function, we generalize all the bounds by using a contradiction argument with the optimality of Grover's algorithm on the unstructured search problem. As a result, we get the main contribution of this work, formalizing the notion that the Grover mixer, at most, reflects a quadratic Grover-style speed-up over classical brute force.