Caminhadas Quânticas em Complexos Simpliciais e Homologia Harmônica: Aplicação à Análise de Dados Topológicos com Acelerações Superpolinomiais

Incorporar interações de ordem superior no processamento de informações nos permite construir modelos mais precisos, obter insights mais profundos sobre sistemas complexos e lidar com desafios do mundo real de maneira mais eficaz. No entanto, os métodos existentes, como caminhadas aleatórias em simplices orientados e homologia, que capturam essas interações, não são conhecidos por sua eficiência. Este trabalho investiga se caminhadas quânticas em complexos simpliciais apresentam vantagens quânticas. Introduzimos uma nova caminhada quântica que codifica o laplaciano combinatório, um objeto matemático chave cujas propriedades espectrais refletem a topologia do complexo simplicial subjacente. Além disso, construímos uma codificação unitária que projeta sobre o núcleo do laplaciano, representando o espaço de ciclos harmônicos na homologia do complexo. Combinado com a construção eficiente de unitários de caminhada quântica para complexos de clique que apresentamos, isso abre caminho para utilizar caminhadas quânticas para explorar interações de ordem superior dentro de estruturas topológicas. Nossos resultados alcançam aceleração quântica superpolinomial com caminhadas quânticas sem depender de óraculos quânticos para grandes conjuntos de dados. Crucialmente, a caminhada opera em um espaço de estados que abrange simplices orientados positiva e negativamente, efetivamente dobrando seu tamanho em comparação a abordagens não orientadas. Através da interferência coerente desses simplices emparelhados, conseguimos codificar com sucesso o laplaciano combinatório, o que de outra forma seria impossível. Esta observação constitui nossa principal contribuição técnica. Também expandimos a estrutura construindo variantes de caminhadas quânticas. Essas variantes nos permitem: (1) estimar os números de Betti persistentes normalizados, capturando informações topológicas ao longo de um processo de deformação, e (2) verificar um problema específico QMA₁-difícil, mostrando aplicações potenciais na teoria da complexidade computacional.