Defesa de Dissertação de Mestrado de Lucas Amaral dos Santos Barroso Leite, 11/03/26, 10h, na sala 310 do Instituto de Computção e por videoconferência
Link para defesa: https://meet.google.com/mar-rqbe-fwa
Simulação Eficiente de Hamiltonianos Esparsos e Aplicação na Resolução Quântica de Sistemas Lineares
Resumo:
Esta dissertação investiga a implementação de algoritmos de simulação quântica de Hamiltonianos representados por matrizes esparsas, com foco na aplicação do algoritmo de Harrow–Hassidim–Lloyd (HHL) para a resolução de sistemas lineares. O objetivo central do trabalho é analisar a viabilidade prática do algoritmo HHL em cenários nos quais o Hamiltoniano é esparso, hermitiano e computável por linha (row-computable), características frequentemente encontradas em modelos físicos e químicos.
Para esse fim, foi implementado um método de simulação Hamiltoniana de matrizes esparsas proposto por Berry et al. (2007), o qual explora a estrutura esparsa do Hamiltoniano para evitar custos que escalam polinomialmente com a dimensão do sistema. A implementação foi realizada em simuladores quânticos, permitindo a avaliação integrada da simulação Hamiltoniana como subrotina do algoritmo HHL.
Os resultados obtidos indicam que a simulação Hamiltoniana aproximada não se configura como um gargalo dominante para o desempenho do HHL nos regimes analisados, preservando o ganho assintótico de complexidade esperado para sistemas esparsos. Dessa forma, o trabalho valida a aplicabilidade do método de Berry et al. na integração com o algoritmo HHL e contribui para uma compreensão mais realista das condições sob as quais algoritmos quânticos para resolução de sistemas lineares podem ser implementados de maneira eficiente.
Abstract:
This dissertation investigates the implementation of quantum simulation algorithms for Hamiltonians represented by sparse matrices, with a focus on the application of the Harrow–Hassidim–Lloyd (HHL) algorithm for solving linear systems. The main objective of this work is to analyze the practical viability of the HHL algorithm in scenarios where the Hamiltonian is sparse, Hermitian, and row computable, properties commonly found in physical and chemical models.
To this end, a sparse Hamiltonian simulation method proposed by Berry et al. (2007) was implemented. This approach exploits the sparsity structure of the Hamiltonian to avoid costs that scale polynomially with the system dimension. The implementation was carried out using quantum simulators, enabling an integrated evaluation of Hamiltonian simulation as a subroutine of the HHL algorithm.
The results indicate that the approximate Hamiltonian simulation does not constitute a dominant bottleneck for the performance of the HHL algorithm in the regimes analyzed, preserving the expected asymptotic complexity advantage for sparse systems. In this way, the present work validates the applicability of the method proposed by Berry et al. when integrated with the HHL algorithm and contributes to a more realistic understanding of the conditions under which quantum algorithms for solving linear systems can be efficiently implemented.
Banca examinadora:
Prof. Luis Antonio Brasil Kowada, UFF
Prof. Fábio Protti, UFF
Prof. Renato Portugal, LNCC