The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation

• URL: http://arxiv.org/abs/2603.04089v1
• Date: Wed, 04 Mar 2026 13:59:36 GMT
• Title: The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation
• Authors: Dan Li, Xiang-Hui Wu, Ji-Rong Liu,
• Abstract summary: The Steiner Tree Problem (STP) is a well-known NP-hard optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields.<n>Traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale instances.
• Score: 2.7455927123752173
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem.

Related papers

• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Quantum-Efficient Reinforcement Learning Solutions for Last-Mile On-Demand Delivery [1.8262547855491453]
  We investigate quantum computing to solve the large-scale Capacitated Pickup and Delivery Problem with Time Windows.<n>A novel problem-specific encoding quantum circuit with an entangling and variational layer is proposed.
  arXiv  Detail & Related papers  (2025-08-07T13:50:43Z)
• Variational Quantum Algorithm for Constrained Topology Optimization [4.067407250874754]
  A novel variational quantum algorithm for constrained topology optimization is proposed.<n>The gate complexity of the proposed quantum algorithm is analyzed.<n>The algorithm is demonstrated with compliance problems including truss structures and Messerschmitt-B"olkow-Blohm beams.
  arXiv  Detail & Related papers  (2024-12-10T01:38:40Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO [0.0]
  The paper explores the application of Quadratic Unconstrained Binary Optimization (QUBO) models in solving the Travelling Salesman Problem (TSP) through Quantum Annealing algorithms and Graph Neural Networks. It introduces a Graph Neural Network solution for TSP (QGNN-TSP), which learns the underlying structure of the problem and produces competitive solutions via gradient descent over a QUBO-based loss function.
  arXiv  Detail & Related papers  (2024-02-21T05:55:00Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem. Our results show the effectiveness of this construction and potential applications.
  arXiv  Detail & Related papers  (2022-03-29T05:44:07Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.