A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint

• URL: http://arxiv.org/abs/2508.07007v1
• Date: Sat, 09 Aug 2025 14:59:47 GMT
• Title: A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• Authors: F. S. Luiz, F. F. Fanchini, Victor Hugo C. de Albuquerque, J. P. Papa, M. C. de Oliveira,
• Abstract summary: We present a novel quantum walk-based approach to solve the Minimum Spanning Tree (MST) problem under a maximal degree constraint (MDC)<n>We demonstrate that the quantum evolution naturally selects the MST by maximizing the cumulative transition probability (and thus the Shannon entropy) over the spanning tree.<n>Our method, termed Quantum Kruskal with MDC, significantly reduces the quantum resource requirement to $mathcalO(log N)$ qubits while retaining a competitive classical computational complexity.
• Score: 9.382719568546758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel quantum walk-based approach to solve the Minimum Spanning Tree (MST) problem under a maximal degree constraint (MDC). By recasting the classical MST problem as a quantum walk on a graph, where vertices are encoded as quantum states and edge weights are inverted to define a modified Hamiltonian, we demonstrate that the quantum evolution naturally selects the MST by maximizing the cumulative transition probability (and thus the Shannon entropy) over the spanning tree. Our method, termed Quantum Kruskal with MDC, significantly reduces the quantum resource requirement to $\mathcal{O}(\log N)$ qubits while retaining a competitive classical computational complexity. Numerical experiments on fully connected graphs up to $10^4$ vertices confirm that, particularly for MDC values exceeding $4$, the algorithm delivers MSTs with optimal or near-optimal total weights. When MDC values are less or equal to $4$, some instances achieve a suboptimal solution, still outperforming several established classical algorithms. These results open promising perspectives for hybrid quantum-classical solutions in large-scale graph optimization.

Related papers

• Second order cone relaxations for quantum Max Cut [3.237380113935023]
  Quantum Max Cut (QMC) is a QMA-complete problem relevant to quantum many-body physics and computer science. We give a second order cone relaxation for QMC, which optimize over the set of mutually consistent three-qubit reduced density matrices. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.
  arXiv  Detail & Related papers  (2024-11-06T18:54:26Z)
• Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
  We show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000qubit gates. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. For degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states.
  arXiv  Detail & Related papers  (2024-09-18T18:00:08Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
  We show that some existing quantum optimization methods can be unified into a solver to find the binary solution.<n>Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner.
  arXiv  Detail & Related papers  (2024-03-04T13:48:21Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Alleviating the quantum Big-$M$ problem [0.22615818641180715]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale.<n>We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$.<n>We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
  arXiv  Detail & Related papers  (2023-05-23T16:17:57Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.