Aplicação de Algoritmos Quânticos Variacionais para Fatoração de Inteiros
Autores
|
7426 |
3226,2733
|
|
|
7427 |
3226,2733
|
Informações:
Publicações do PESC
O algoritmo VQF (Variational Quantum Factoring), que consiste em uma abordagem híbrida de pré-processamento clássico seguido da aplicação do QAOA (Quantum Approximate Optimization Algorithm), foi proposto de modo a verificar o problema de fatoração de inteiros no cenário de dispositivos quânticos atuais. Foi então testada, neste trabalho, a performance desse algoritmo e de uma variação proposta baseada no algoritmo QWOA (Quantum walk-assisted Optimization Algorithm), uma generalização do QAOA assistido por CTQW (continuous-time quantum walk ). Foram realizadas simulações em ambientes ideal e ruidoso, identificando o impacto altamente negativo do ruído na probabilidade de se medir os fatores corretos. Foram comparados diferentes otimizadores clássicos, BFGS e L-BFGS-B, e dois métodos de inicialização de parâmetros distintos, o original de busca em grade e um segundo baseado na superfície de custo da função objetivo. Foi identificada ainda a possibilidade de desenvolvimento de heurísticas de inicialização de parâmetros maiseficientes. Foi verificado, a partir da análise de relações numéricas, que propriedades como simetria p ? q e presença de bits de transporte, nos fatores primos, tendem a promover um aumento da taxa de sucesso do algoritmo. Foi analisado ainda o efeito do processo de transpilação sobre as propriedades dos circuitos lógicos dos algoritmos, tendo sido constatado que a restrição imposta pelo mapa de conectividade do processador quântico supercondutor ocasiona um aumento expressivo de portas CN OT e profundidade do circuito e, portanto, de ruído. Por fim, verificou-se que a variação testada (com quantum-walk mixer) apresentou resultados melhores para determinados conjuntos de instâncias (de tamanho até 6 qubits), embora tenha escalado de forma pior que a versão original (com transverse-field mixer) para outros conjuntos de instâncias (tamanho de 8 qubits).
The VQF algorithm (Variational Quantum Factoring), which consists of a hybrid approach of classical preprocessing followed by the application of QAOA (Quantum Approximate Optimization Algorithm), was proposed in order to verify the integer factoring problem in today’s quantum device scenario. This work then tested the performance of this algorithm and a proposed variation based on the QWOA algorithm (Quantum walk-assisted Optimization Algorithm), a generalization of QAOA assisted by CTQW (continuous-time quantum walk ). Simulations were carried out in ideal and noisy environments, identifying the highly negative impact of noise on the probability of measuring the correct factors. Different classical optimizers were compared, BFGS and L-BFGS-B, and two different parameter initialization methods, the original grid search and a second based on the cost surface of the objective function. The possibility of developing more efficient parameter initialization heuristics was also identified. It was verified, from the analysis of numerical relationships, that properties such as symmetry p ? q and the presence of carry-bits in the prime factors tend to promote an increase in the algorithm’s success rate. The effect of the transpilation process on the properties of the algorithms’ logic circuits was also analyzed, and it was found that the restriction imposed by the connectivity map of the superconducting quantum processor causes a significant increase in CN OT gates and circuit depth, and therefore in noise. Finally, it was found that the variation tested (with quantum-walk mixer) showed better results for certain groups of instances (up to 6 qubits), although it scaled worse than the original version (with transverse-field mixer) for other sets of instances (8 qubits in size).