Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/85547
Título: | Quantum reinforcement learning: a heuristic approach to solve deterministic MDPs |
Autor(es): | Brito, Renato Alberto Soares de |
Orientador(es): | Santos, Luís Paulo |
Palavras-chave: | Amplitude amplification Heuristic Model-free Maximum finding Query complexity Amplificação de amplitude Complexidade de query Heurística Modelo livre Procura pelo máximo |
Data: | 13-Fev-2022 |
Resumo(s): | 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. |
Tipo: | Dissertação de mestrado |
Descrição: | Dissertação de mestrado integrado em Physics Engineering |
URI: | https://hdl.handle.net/1822/85547 |
Acesso: | Acesso aberto |
Aparece nas coleções: | BUM - Dissertações de Mestrado DI - Dissertações de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Renato Alberto Soares de Brito.pdf | Dissertação de Mestrado | 554,03 kB | Adobe PDF | Ver/Abrir |
Este trabalho está licenciado sob uma Licença Creative Commons