Estudo Inicial do Problema do Caixeiro Viajante utilizando Computação Quântica
Resumo
Este artigo apresenta um estudo inicial sobre o uso de computação quântica para o Problema do Caixeiro Viajante (TSP), explorando sua modelagem por grafos e sua relação com formulações QUBO, QAOA e Quantum Annealing. A partir de uma implementação preliminar em Qiskit, o trabalho organiza abordagens relacionadas e define critérios para comparar algoritmos clássicos, híbridos e quânticos em instâncias controladas, considerando desempenho, qualidade das rotas e limitações de dispositivos NISQ.
Referências
Blekos, K. et al. (2024). A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66.
Goswami, K. et al. (2025). Solving the travelling salesman problem using bloch sphere encoding. Quantum Science and Technology, 11(1):015007.
Klug, F. (2024). Quantum algorithms for solving the traveling salesman problem. Available at SSRN. DOI: 10.2139/ssrn.4836033.
Le, T. V. et al. (2023). Quantum annealing approach for selective traveling salesman problem. In ICC 2023 – IEEE International Conference on Communications, pages 2686–2691. [link].
Martoň’ak, R. et al. (2004). Quantum annealing of the traveling-salesman problem. Physical Review E, 70(5):057701.
Papalitsas, C. et al. (2019). A qubo model for the traveling salesman problem with time windows. Algorithms, 12(11):224. [link].
Preskill, J. (2018). Quantum computing in the nisq era and beyond. Quantum, 2:79.
Qian, W. et al. (2023). Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem. Entropy, 25(8):1238. [link].
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3 edition.
Warren, R. H. (2019). Solving the traveling salesman problem on a quantum annealer. SN Applied Sciences, 2(1):75.
Goswami, K. et al. (2025). Solving the travelling salesman problem using bloch sphere encoding. Quantum Science and Technology, 11(1):015007.
Klug, F. (2024). Quantum algorithms for solving the traveling salesman problem. Available at SSRN. DOI: 10.2139/ssrn.4836033.
Le, T. V. et al. (2023). Quantum annealing approach for selective traveling salesman problem. In ICC 2023 – IEEE International Conference on Communications, pages 2686–2691. [link].
Martoň’ak, R. et al. (2004). Quantum annealing of the traveling-salesman problem. Physical Review E, 70(5):057701.
Papalitsas, C. et al. (2019). A qubo model for the traveling salesman problem with time windows. Algorithms, 12(11):224. [link].
Preskill, J. (2018). Quantum computing in the nisq era and beyond. Quantum, 2:79.
Qian, W. et al. (2023). Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem. Entropy, 25(8):1238. [link].
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3 edition.
Warren, R. H. (2019). Solving the traveling salesman problem on a quantum annealer. SN Applied Sciences, 2(1):75.
Publicado
02/09/2026
Como Citar
LIAO, Luíza; ZANAGA, Pietro; BIANCHINI, Calebe P..
Estudo Inicial do Problema do Caixeiro Viajante utilizando Computação Quântica. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DE SÃO PAULO (ERAD-SP), 17. , 2026, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 77-80.
DOI: https://doi.org/10.5753/eradsp.2026.30770.
