pith. sign in

arxiv: 2605.20637 · v1 · pith:ZCTMBOIOnew · submitted 2026-05-20 · 🪐 quant-ph

PUBO Formulation for MST and Application to Optimum-Path Forest

Guilherme E. L. Pexe , Lucas A. M. Rattighieri , Leandro A. Passos , Danilo S. Jodas , Douglas Rodrigues , Felipe F. Fanchini , Jo\~ao P. Papa , Kelton A. P. Costa This is my paper

Pith reviewed 2026-05-21 05:40 UTC · model grok-4.3

classification 🪐 quant-ph
keywords Minimum Spanning TreePolynomial Unconstrained Binary OptimizationOptimum-Path ForestFALQONPrototype SelectionGraph-based ClassifiersQuantum-inspired Optimization
0
0 comments X

The pith

Reformulating minimum spanning trees as polynomial unconstrained binary optimization lets FALQON select prototypes for optimum-path forest classifiers at classical accuracy levels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that casting the minimum spanning tree computation as a polynomial unconstrained binary optimization task allows the FALQON algorithm to produce usable solutions without auxiliary variables or extra qubits. A sympathetic reader would care because classical construction of these trees for prototype selection becomes prohibitive on large training sets, limiting graph-based classifiers like the Optimum-Path Forest. If the approach works, it opens a route to handle bigger datasets by moving the combinatorial step into a form that current quantum-inspired solvers can tackle directly. Experiments on real-world data indicate the resulting classifiers match the performance of those built with Prim's algorithm.

Core claim

The central claim is that the minimum spanning tree problem admits a direct polynomial unconstrained binary optimization formulation that eliminates the need for auxiliary variables, enabling Hamiltonian minimization via the FALQON algorithm to identify prototypes for Optimum-Path Forest classifiers. On real-world datasets this quantum-inspired procedure yields spanning trees whose quality supports classifier accuracies comparable to those obtained from the classical Prim algorithm, even in cases where FALQON settles at local minima.

What carries the argument

The polynomial unconstrained binary optimization formulation of the minimum spanning tree, which encodes edge selection directly into binary decision variables for minimization by FALQON without added slack variables.

If this is right

  • The FALQON-optimized minimum spanning tree preserves the quality of selected prototypes for Optimum-Path Forest classifiers.
  • Classification accuracies remain comparable to those achieved by the classical Prim algorithm across tested real-world datasets.
  • The formulation reduces qubit count by removing the need for auxiliary variables.
  • Occasional convergence of FALQON to local minima does not measurably degrade final classifier performance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same binary optimization encoding could be reused for other graph-construction steps inside machine-learning pipelines.
  • If the qubit savings scale with problem size, the method might eventually handle training sets too large for repeated classical minimum-spanning-tree runs.
  • Hybrid pipelines that warm-start FALQON with classical heuristics could further improve solution quality on near-term hardware.

Load-bearing premise

Solutions obtained from FALQON that may stop at local minima still produce spanning trees close enough to the true minimum that the accuracy of the downstream Optimum-Path Forest classifier does not drop measurably.

What would settle it

A side-by-side run on a dataset where an exact minimum spanning tree from Prim's algorithm yields visibly higher classifier accuracy than the tree returned by FALQON would show that local-minima convergence does affect results.

Figures

Figures reproduced from arXiv: 2605.20637 by Danilo S. Jodas, Douglas Rodrigues, Felipe F. Fanchini, Guilherme E. L. Pexe, Jo\~ao P. Papa, Kelton A. P. Costa, Leandro A. Passos, Lucas A. M. Rattighieri.

Figure 1
Figure 1. Figure 1: Flow of the training and testing process for the OPF classifier using the FALQON algorithm. The [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Example graph built from the Heart Disease dataset, where the vertices correspond to the dataset [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Results of FALQON execution on the MST problem. (a) Evolution of the expected value of the [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FALQON results for the MST formulated as a QUBO problem. (a) Evolution of the expectation [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FALQON results for the MST formulated as a PUBO problem. (a) Evolution of the expectation [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The paper reformulates the Minimum Spanning Tree (MST) problem as a Polynomial Unconstrained Binary Optimization (PUBO) task without auxiliary variables, derives the corresponding Hamiltonian, and applies the Feedback-Based Quantum Optimization (FALQON) algorithm to select prototypes for Optimum-Path Forest (OPF) classifiers. Experiments on real-world datasets are reported to show that FALQON solutions yield classification accuracies comparable to those from classical Prim's algorithm while preserving prototype quality, despite occasional convergence to local minima.

Significance. If the experimental parity holds under statistical scrutiny, the work supplies a parameter-free PUBO encoding of MST that lowers qubit count and demonstrates a concrete quantum-inspired pipeline for a graph-based classifier on real data, including direct end-to-end accuracy tables and prototype counts. This provides a falsifiable benchmark against Prim's algorithm and bounds the practical effect of local minima by observed performance.

major comments (1)
  1. Results section (accuracy tables): the manuscript presents per-dataset accuracies and prototype counts but omits error bars, number of independent runs, or statistical tests (e.g., paired t-test or Wilcoxon) to substantiate the 'comparable' claim. Given the explicit caveat that FALQON occasionally reaches local minima, this weakens the load-bearing performance equivalence without additional quantification.
minor comments (3)
  1. Abstract: specific dataset names, sizes, and numerical accuracy values should be added to make the central claim self-contained rather than qualitative.
  2. Notation: the binary edge variables and higher-order penalty terms in the PUBO formulation would benefit from an explicit small example (e.g., K_4) to clarify cycle penalization and connectivity enforcement.
  3. Figure clarity: the Hamiltonian derivation figure or table should explicitly label which terms arise from the MST objective versus the cycle/degree constraints.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address the major comment below and agree that additional statistical quantification will improve the clarity and rigor of our experimental claims.

read point-by-point responses

  1. Referee: Results section (accuracy tables): the manuscript presents per-dataset accuracies and prototype counts but omits error bars, number of independent runs, or statistical tests (e.g., paired t-test or Wilcoxon) to substantiate the 'comparable' claim. Given the explicit caveat that FALQON occasionally reaches local minima, this weakens the load-bearing performance equivalence without additional quantification.

    Authors: We agree that the current results section would benefit from explicit statistical support to substantiate the comparability claim, particularly given the noted possibility of local minima. In the revised manuscript we will (i) state that all reported accuracies are averages over 10 independent FALQON runs per dataset, (ii) add error bars showing the standard deviation, and (iii) include a Wilcoxon signed-rank test comparing FALQON and Prim accuracies across datasets. These additions will quantify the observed equivalence and bound the practical effect of any local-minima solutions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained against external baselines

full rationale

The paper explicitly constructs the PUBO encoding for MST using binary edge variables with higher-order penalty terms for cycles and connectivity, derives the corresponding Hamiltonian, and applies FALQON to minimize it. All reported results are end-to-end experimental accuracies on real datasets compared directly to the independent classical baseline of Prim's algorithm on identical splits. No equation reduces a reported accuracy or prototype quality metric to a fitted parameter or self-referential definition, and no load-bearing premise rests on a self-citation chain that itself lacks external verification. The local-minima caveat is bounded by the observed parity rather than assumed away.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on the standard mathematical equivalence between MST and certain binary optimization objectives plus the correctness of the FALQON feedback loop; no new physical axioms or invented particles are introduced.

axioms (2)
  • domain assumption The minimum spanning tree objective can be exactly encoded as a PUBO without auxiliary variables.
    This encoding is the central technical step asserted in the abstract.
  • domain assumption FALQON can be applied to the resulting Hamiltonian to produce usable MST approximations.
    Invoked when the abstract states the algorithm is employed for Hamiltonian minimization.

pith-pipeline@v0.9.0 · 5748 in / 1369 out tokens · 31057 ms · 2026-05-21T05:40:51.324606+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Aggarwal, S

    A. Aggarwal, S. V . Singh, S. Bansal, V . Bhutani, A Detailed Overview of Quantum Computing Machine Learning Techniques, in: 2024 International Conference on Communication, Computer Sciences and Engineering (IC3SE), 2024, pp. 1721– 1725. 20

    work page 2024

  2. [2]

    Abbas, D

    A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, S. Woerner, The power of quantum neural networks, Nature Computational Science 1 (6) (2021) 403–409

    work page 2021

  3. [3]

    Nokhwal, S

    S. Nokhwal, S. Nokhwal, S. Pahune, A. Chaudhary, Quantum generative adversar- ial networks: Bridging classical and quantum realms, in: Proceedings of the 2024 8th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, 2024, pp. 105–109

    work page 2024

  4. [4]

    S. S. Dutta, S. Sandeep, S. Sridevi, M. R. Sridhar, C. Singh, Quantum Kernel based Support Vector Machine with Quantum Approximate Optimization Algorithm Embedding for Improved Lung Cancer Prediction, in: 2024 15th international conference on computing communication and networking technologies (ICCCNT), IEEE, 2024, pp. 1–6

    work page 2024

  5. [5]

    X. Ye, G. Yan, J. Yan, Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver, in: International Conference on Machine Learning, PMLR, 2023, pp. 39903–39912

    work page 2023

  6. [7]

    J. P. Papa, A. X. Falcão, V . H. C. Albuquerque, J. M. R. S. Tavares, Efficient su- pervised optimum-path forest classification for large datasets, Pattern Recognition 45 (1) (2012) 512–520

    work page 2012

  7. [8]

    J. P. Papa, S. E. N. Fernandes, A. X. Falcão, Optimum-path forest based on k- connectivity: Theory and applications, Pattern Recognition Letters 87 (2017) 117–126

    work page 2017

  8. [9]

    L. M. Rocha, F. A. M. Cappabianco, A. X. Falcão, Data clustering as an optimum- path forest problem with applications in image analysis, International Journal of Imaging Systems and Technology 19 (2) (2009) 50–68. 21

    work page 2009

  9. [10]

    W. P. Amorim, A. X. Falcão, M. H. de Carvalho, Semi-supervised Pattern Clas- sification Using Optimum-Path Forest, in: 2014 27th SIBGRAPI Conference on Graphics, Patterns and Images, IEEE, 2014, pp. 111–118

    work page 2014

  10. [11]

    P. B. Ribeiro, L. A. Passos, L. A. Da Silva, K. A. da Costa, J. P. Papa, R. A. Romero, Unsupervised breast masses classification through optimum-path forest, in: 2015 IEEE 28th International Symposium on Computer-Based Medical Systems, IEEE, 2015, pp. 238–243

    work page 2015

  11. [12]

    D. S. Jodas, L. A. Passos, D. Rodrigues, T. J. Lucas, K. A. P. Da Costa, J. P. Papa, OPFsemble: An Ensemble Pruning Approach via Optimum-Path Forest, in: 2023 30th International Conference on Systems, Signals and Image Processing (IWSSIP), IEEE, 2023, pp. 1–5

    work page 2023

  12. [13]

    T. J. Lucas, L. A. Passos, D. Rodrigues, D. Jodas, J. P. Papa, K. A. P. Da Costa, R. Scherer, Ensemble Diversity Pruning on Cybersecurity: Optimizing Intrusion Detection Systems, in: 2024 31st International Conference on Systems, Signals and Image Processing (IWSSIP), IEEE, 2024, pp. 1–6

    work page 2024

  13. [14]

    L. A. Passos, D. S. Jodas, L. C. Ribeiro, M. Akio, A. N. De Souza, J. P. Papa, Handling imbalanced datasets through optimum-path forest, Knowledge-Based Systems 242 (2022) 108445

    work page 2022

  14. [15]

    D. S. Jodas, L. A. Passos, G. D. N. Velasco, M. H. C. Longo, A. R. Machado, J. P. Papa, Multiclass Oversampling via Optimum-Path Forest for Tree Species Classification from Street-view Perspectives, in: 2022 35th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), V ol. 1, IEEE, 2022, pp. 121–126

    work page 2022

  15. [16]

    L. A. Passos, D. S. Jodas, L. C. F. Ribeiro, T. Pinheiro, J. P. Papa, O2PF: Over- sampling via Optimum-Path Forest for Breast Cancer Detection, in: IEEE 33th International Symposium on Computer-Based Medical Systems, IEEE, 2020

    work page 2020

  16. [17]

    Allène, J.-Y

    C. Allène, J.-Y . Audibert, M. Couprie, R. Keriven, Some links between extremum spanning forests, watersheds and min-cuts, Image and Vision Computing 28 (10) (2010) 1460–1471, image Analysis and Mathematical Morphology. 22

    work page 2010

  17. [18]

    Stein, F

    J. Stein, F. Chamanian, M. Zorn, J. Nüßlein, S. Zielinski, M. Kölle, C. Linnhoff- Popien, Evidence that pubo outperforms qubo when solving continuous optimiza- tion problems with the qaoa, GECCO ’23 Companion, Association for Computing Machinery, New York, NY , USA, 2023, p. 2254–2262

    work page 2023

  18. [19]

    A. B. Magann, K. M. Rudinger, M. D. Grace, M. Sarovar, Feedback- based quantum optimization, Phys. Rev. Lett. 129 (2022) 250502. doi:10.1103/PhysRevLett.129.250502. URLhttps://link.aps.org/doi/10.1103/PhysRevLett.129.250502

    work page doi:10.1103/physrevlett.129.250502 2022

  19. [20]

    A. B. Magann, K. M. Rudinger, M. D. Grace, M. Sarovar, Lyapunov-control- inspired strategies for quantum combinatorial optimization, Phys. Rev. A 106 (2022) 062414. doi:10.1103/PhysRevA.106.062414. URLhttps://link.aps.org/doi/10.1103/PhysRevA.106.062414

    work page doi:10.1103/physreva.106.062414 2022

  20. [21]

    J. B. Larsen, M. D. Grace, A. D. Baczewski, A. B. Magann, Feedback-based quantum algorithms for ground state preparation, Phys. Rev. Res. 6 (2024) 033336. doi:10.1103/PhysRevResearch.6.033336. URLhttps://link.aps.org/doi/10.1103/PhysRevResearch.6.033336

    work page doi:10.1103/physrevresearch.6.033336 2024

  21. [22]

    G. E. L. Pexe, L. A. M. Rattighieri, A. L. Malvezzi, F. F. Fanchini, Using a feedback-based quantum algorithm to analyze the critical properties of the annni model without classical optimization, Phys. Rev. B 110 (2024) 224422. doi:10.1103/PhysRevB.110.224422. URLhttps://link.aps.org/doi/10.1103/PhysRevB.110.224422

    work page doi:10.1103/physrevb.110.224422 2024

  22. [23]

    L. A. M. Rattighieri, G. E. L. Pexe, B. L. Bernardo, F. F. Fanchini, Accelerating feedback-based quantum algorithms through time rescaling, Phys. Rev. A 112 (2025) 042607. doi:10.1103/qc91-5mj2. URLhttps://link.aps.org/doi/10.1103/qc91-5mj2

    work page doi:10.1103/qc91-5mj2 2025

  23. [24]

    D. Arai, K. N. Okada, Y . Nakano, K. Mitarai, K. Fujii, Scalable circuit depth reduction in feedback-based quantum optimization with a quadratic approximation, Phys. Rev. Res. 7 (2025) 013035. doi:10.1103/PhysRevResearch.7.013035. URLhttps://link.aps.org/doi/10.1103/PhysRevResearch.7.013035 23

    work page doi:10.1103/physrevresearch.7.013035 2025

  24. [25]

    M. A. K. Miranda, F. F. Fanchini, L. A. Passos, D. Rodrigues, K. A. P. d. Costa, R. Sherer, J. P. Papa, A quantum-inspired approach to estimate optimum-path forest prototypes based on the traveling salesman problem, in: A. Antonacopoulos, S. Chaudhuri, R. Chellappa, C.-L. Liu, S. Bhattacharya, U. Pal (Eds.), Pattern Recognition, Springer Nature Switzerlan...

    work page 2025

  25. [26]

    Saravanan, R

    M. Saravanan, R. Ravi, S. Prabaharan, A survey on distributed algorithms for constructing minimum spanning trees in wireless sensor networks, American- Eurasian Journal of Scientific Research 8 (4) (2013) 192––197

    work page 2013

  26. [27]

    J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society 7 (1) (1956) 48–50. doi:10.1090/S0002-9939-1956-0078686-7

    work page doi:10.1090/s0002-9939-1956-0078686-7 1956

  27. [28]

    R. C. Prim, Shortest connection networks and some generalizations, The Bell System Technical Journal 36 (6) (1957) 1389–1401. doi:10.1002/j.1538- 7305.1957.tb01515.x

    work page doi:10.1002/j.1538- 1957

  28. [29]

    J. P. Papa, A. X. Falcão, C. T. N. Suzuki, Supervised pattern classification based on optimum-path forest, International Journal of Imaging Systems and Technology 19 (2) (2009) 120–131

    work page 2009

  29. [30]

    Carvalho, Qubo formulations for np-hard spanning tree problems (2022)

    I. Carvalho, Qubo formulations for np-hard spanning tree problems (2022). arXiv:2209.05024. URLhttps://arxiv.org/abs/2209.05024

    work page arXiv 2022

  30. [31]

    Lucas, Ising formulations of many np prob- lems, Frontiers in Physics 2 (2014)

    A. Lucas, Ising formulations of many NP problems, Frontiers in Physics 2 (2014). doi:10.3389/fphy.2014.00005

    work page doi:10.3389/fphy.2014.00005 2014

  31. [32]

    Janosi, W

    A. Janosi, W. Steinbrunn, M. Pfisterer, R. Detrano, Heart Disease, UCI Machine Learning Repository (1989). doi:https://doi.org/10.24432/C52P4X

    work page doi:10.24432/c52p4x 1989

  32. [33]

    Sigillito, S

    V . Sigillito, S. Wing, L. Hutton, , K. Baker, Ionosphere, UCI Machine Learning Repository, DOI: https://doi.org/10.24432/C5W01B (1989). 24

    work page doi:10.24432/c5w01b 1989

  33. [34]

    Z. Hong, J. Yang, Lung Cancer, UCI Machine Learning Repository, DOI: https://doi.org/10.24432/C57596 (1991)

    work page doi:10.24432/c57596 1991

  34. [35]

    R. A. Fisher, Iris, UCI Machine Learning Repository, DOI: https://doi.org/10.24432/C56C76 (1936)

    work page doi:10.24432/c56c76 1936

  35. [36]

    G. H. de Rosa, J. P. Papa, Opfython: A python imple- mentation for optimum-path forest, Software Impacts (2021) 100113doi:https://doi.org/10.1016/j.simpa.2021.100113

    work page doi:10.1016/j.simpa.2021.100113 2021

  36. [37]

    Fowler, Improved qubo formulations for d-wave quantum computing (05 2017)

    A. Fowler, Improved qubo formulations for d-wave quantum computing (05 2017). doi:10.13140/RG.2.2.31829.73445. 25

    work page doi:10.13140/rg.2.2.31829.73445 2017