Identificação de números primos com computadores quânticos

• Ano de defesa: 2024
• Autor(a) principal: Santos, Victor Ferreira dos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Santa Maria; Brasil; Física; UFSM; Programa de Pós-Graduação em Física; Centro de Ciências Naturais e Exatas
• Palavras-chave em Português: Identificação de números primos; Computação quântica; Dinâmica de emaranhamento; Algoritmo quântico; Custo computacional; Identification of prime numbers; Quantum computing; Entanglement dynamics; Quantum algorithm; Computational cost; CNPQ::CIENCIAS EXATAS E DA TERRA::FISICA
• Link de acesso: http://repositorio.ufsm.br/handle/1/33301

The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.