Quantum reinforcement learning: a heuristic approach to solve deterministic MDPs

Abstract

This thesis works on Reinforcement Learning tree search and attempts to find the best possible sequence of actions the agent needs to execute to get the most reward while using less computational effort than by just applying a quantum maximum finding algorithm. To achieve this we will use the property that makes it possible to limit our search space to the elements that were marked by the oracle in Grover’s Algorithm, by marking a fourth of the search space and following it with a quantum maximum finding subroutine. From this, one of the marked elements is obtained and the information encoded in it is used to update a probabilistic distribution stored in a classical memory. The goal is to encounter the minimum amount of iterations of this process and compare the results, i.e., percentage of success which is measured as the number of times the algorithm produces a solution (element with maximum reward) and the number of queries used - with a traditional quantum maximum finding procedure. If this is observed, it is also hypothe sized that the algorithm could be used to observe a step further into the future compared to the traditional procedure, i.e., use the same or fewer queries to evaluate a larger number of sequences fruit of increasing the horizon of the episodes. The last hypothesis tests the depth of the circuits, more specifically the number of gates used. If the algorithm evaluates shallower circuits than the quantum maximum finding, the approach can be applied on the current quantum machines (NISQ) because the shallower circuits produces more error-proof measurements. The results show that the proposed algorithm has no advantages compared to a traditional quantum maximum finding procedure due to using more queries to achieve the same rate of success which, consequently, invalidates the first and second hypothesis. For the third hypothesis, the gate complexity was not directly measured. Instead, was opted to measure the number of queries used by circuit which might not be sufficient to conclude that the algorithm uses shallower circuits.

Esta tese trabalha com a busca em árvores utilizando a Aprendizagem por Reforço para encontrar a melhor sequência possível de ações que o agente terá de executar de forma a obter o maior prémio possível, isto enquanto usa menos esforço computacional em comparação com utilizar apenas um algoritmo de procura quântica pelo máximo. Para atingir estes objectivos, usaremos a propriedade que possibilita limitar o espaço de procura para os elementos marcados pelo oráclo no Algoritmo de Grover, marcando exatamente um quarto do espaço de procura, procedendo com uma procura quântica. Disto resulta um dos elementos marcado e a informação codificada nele será usada para atualizar uma distribuição probabilística guardada em memoria clássica. O objectivo é encontrar o mínimo de iterações deste processo necessário para obter uma percentagem de sucesso - número de vezes que o algoritmo retornou um elemento que é solução do problema e o número de queries usado - e comparar estes resultados com um procedimento tradicional de procura quântica. Caso isto se observe, é colocada a hipótese de se usar este algoritmo como forma de observar ações futuras em comparação com os algoritmos tradicionais, isto é, usar o mesmo ou menos queries para avaliar um maior número de sequências fruto do aumento do horizonte dos episódios a avaliar. A última hipótese testa se a profundidade dos circuitos, mais concretamente o número de gates usadas. Caso o algoritmo proposto utilize circuitos menos profundos que o algoritmo quantum maximum finding, este poderá ser utilizado nas máquinas quânticas atuais pois estes circuitos produzem medições mais resistentes a erros. Os resultados mostraram que o algoritmo proposto não possui qualquer vantagem comparado ao quantum maximum finding por usar mais queries para atingir a mesma percentagem de sucesso o que, consequentemente, invalida a primeira e segunda hipótese. Quanto à terceira hipótese, o número de gates usadas por circuito não foi medido diretamente. Em vez disso, optou-se por medir o número de queris por circuito o que poderá não ser suficiente para obter conclusões quanto à profundidade dos circuitos medidos.