Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

A Quantum-inspired Approach to Estimate Optimum-Path Forest Prototypes based on the Traveling Salesman Problem

Maria Angélica Krüger Miranda, F. F. Fanchini, Leandro Aparecido Passos Júnior, Douglas Rodrigues, Kelton Augusto Pontara da Costa, Rafał Scherer, João Paulo Papa

Published Dec 3, 2024• 0 citations
Publisher
DOI
10.1007/978-3-031-78183-4_6

Related papers

A Magnetism-Inspired Quantum Algorithm to Solve the Traveling Salesman Problem

Luke Ellert-Beck, Michael J. Lawler, Samuel Gosin

Bulletin of the American Physical Society•Mar 19, 2021•0 citations

Quantum Algorithms for Solving the Traveling Salesman Problem

Florian Klug

•Jan 1, 2024•2 citations

The quantum mechanical solution of the traveling salesman problem

Hans R. Moser

Physica E Low-dimensional Systems and Nanostructures•Feb 1, 2003•11 citations

Study On Adaptive Quantum Algorithm In Traveling Salesman Problem

Liyuan Jia, HE Jian-xin, Chi Zhang

International Journal of Advancements in Computing Technology•Mar 15, 2013•0 citations

Tackling Traveling Salesman Problems with a Cluster-Based Quantum-Classical Optimization

Saweed Hussain, Hoon Ryu

KSII Transactions on Internet and Information Systems•May 31, 2026•0 citations

PUBO Formulation for MST and Application to Optimum-Path Forest

Guilherme E. L. Pexe, Lucas A. M. Rattighieri, Leandro A. Passos +5 more

The Optimum-Path Forest is a graph-based framework for designing classifiers that exploit inter-sample connectivity. A particular variant constructs decision boundaries based on prototypes computed by a Minimum Spanning Tree (MST) over the training data, which might become prohibitive for large-scale datasets. In this context, Quantum Machine Learning has emerged as a promising approach to overcome the high computational burden of combinatorial problems. We propose a quantum-inspired approach for prototype selection in OPF classifiers by reformulating the MST problem as a Polynomial Unconstrained Binary Optimization (PUBO) task and further employing the Feedback-Based Quantum Optimization (FALQON) algorithm for Hamiltonian minimization. The PUBO formulation reduces the need for qubits and eliminates the need for auxiliary variables, thereby addressing scalability constraints in current quantum hardware. Experiments on real-world datasets demonstrate that the FALQON-optimized MST achieves accuracies comparable to those of the classical Prim's algorithm while maintaining prototype quality. While FALQON occasionally reached local minima, it did not significantly impact the accuracy of the prototype selection process.

quant-pharXiv:2605.20637•May 21, 2026•0 citations
The Optimum-Path Forest is a graph-based framework for designing classifiers that exploit inter-sample connectivity. A particular variant constructs decision boundaries based on prototypes computed by a Minimum Spanning Tree (MST) over the training data, which might become prohibitive for large-scale datasets. In this context, Quantum Machine Learning has emerged as a promising approach to overcome the high computational burden of combinatorial problems. We propose a quantum-inspired approach for prototype selection in OPF classifiers by reformulating the MST problem as a Polynomial Unconstrained Binary Optimization (PUBO) task and further employing the Feedback-Based Quantum Optimization (FALQON) algorithm for Hamiltonian minimization. The PUBO formulation reduces the need for qubits and eliminates the need for auxiliary variables, thereby addressing scalability constraints in current quantum hardware. Experiments on real-world datasets demonstrate that the FALQON-optimized MST achieves accuracies comparable to those of the classical Prim's algorithm while maintaining prototype quality. While FALQON occasionally reached local minima, it did not significantly impact the accuracy of the prototype selection process.