  We introduce a novel Quadratic Unconstrained Binary Optimization (QUBO)
formulation method for spanning tree problems. Instead of encoding the presence
of edges in the tree individually, we opt to encode spanning trees as a
permutation problem. We apply our method to four NP-hard spanning tree
variants, namely the k-minimum spanning tree, degree-constrained minimum
spanning tree, minimum leaf spanning tree, and maximum leaf spanning tree. Our
main result is a formulation with $\mathcal{O}(|V|k)$ variables for the
k-minimum spanning tree problem, beating related strategies that need
$\mathcal{O}(|V|^{2})$ variables.
