Teses, Dissertações e Outros

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.