Variational (matrix) product states for combinatorial optimization

• URL: http://arxiv.org/abs/2512.20613v1
• Date: Tue, 23 Dec 2025 18:58:35 GMT
• Title: Variational (matrix) product states for combinatorial optimization
• Authors: Guillermo Preisser, Conor Mc Keever, Michael Lubasch,
• Abstract summary: We compute approximate solutions for optimization problems based on the product state (PS) and matrix product state (MPS) ansatzes.<n>We show that they can outperform traditional (M)PS methods, classical ILS, the quantum approximate optimization algorithm and other variational quantum-inspired solvers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To compute approximate solutions for combinatorial optimization problems, we describe variational methods based on the product state (PS) and matrix product state (MPS) ansatzes. We perform variational energy minimization with respect to a quantum annealing Hamiltonian and utilize randomness by embedding the approaches in the metaheuristic iterated local search (ILS). The resulting quantum-inspired ILS algorithms are benchmarked on maximum cut problems of up to 50000 variables. We show that they can outperform traditional (M)PS methods, classical ILS, the quantum approximate optimization algorithm and other variational quantum-inspired solvers.

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-Enhanced Optimization by Warm Starts [1.1666234644810893]
  We present an approach, which we term quantum-enhanced optimization, to accelerate classical optimization algorithms by leveraging quantum samples.<n>Our method uses quantum-generated samples as warm starts to classical samplings for solving novel problems like Max-Cut and Maximum Independent Set (MIS)
  arXiv  Detail & Related papers  (2025-08-22T11:36:19Z)
• Performant near-term quantum combinatorial optimization [1.1999555634662633]
  We present a variational quantum algorithm for solving optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target quantum function. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
  arXiv  Detail & Related papers  (2024-04-24T18:49:07Z)
• Variational Quantum Multi-Objective Optimization [5.381539115778766]
  We present a variational quantum optimization algorithm to solve discrete multi-objective optimization problems on quantum computers. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives.
  arXiv  Detail & Related papers  (2023-12-21T18:59:21Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Monte Carlo Tree Search based Hybrid Optimization of Variational Quantum Circuits [7.08228773002332]
  We propose a new variational quantum algorithm called MCTS-QAOA. It combines a Monte Carlo tree search method with an improved natural policy gradient solver to optimize the discrete and continuous variables in the quantum circuit. We find that MCTS-QAOA has excellent noise-resilience properties and outperforms prior algorithms in challenging instances of the generalized QAOA.
  arXiv  Detail & Related papers  (2022-03-30T23:15:21Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Optimization of the Variational Quantum Eigensolver for Quantum Chemistry Applications [0.0]
  The variational quantum eigensolver algorithm is designed to determine the ground state of a quantum mechanical system. We study methods of reducing the number of required qubit manipulations, prone to induce errors, for the variational quantum eigensolver.
  arXiv  Detail & Related papers  (2021-02-02T22:20:12Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• 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)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems. We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms) The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
  arXiv  Detail & Related papers  (2020-01-07T14:43:13Z)

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.