Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2302.12454v3
• Date: Thu, 29 Jun 2023 03:23:02 GMT
• Title: Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems
• Authors: Naoya Onizawa and Ryoma Sasaki and Duckgyu Shin and Warren J. Gross and Takahiro Hanyu
• Abstract summary: SSQA is designed based on computing and quantum Monte Carlo. It can handle a 100-times larger problem size compared to QA and atimes larger problem size compared to a traditional SA method.
• Score: 9.516147599772243
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce stochastic simulated quantum annealing (SSQA) for large-scale combinatorial optimization problems. SSQA is designed based on stochastic computing and quantum Monte Carlo, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. The proposed method achieves a convergence speed an order of magnitude faster than a conventional stochastic simulaated annealing method. Additionally, it can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities.

Related papers

• Sampling-based Quantum Optimization Algorithm with Quantum Relaxation [0.0]
  Variational Quantum Algorithm (VQA) is a hybrid algorithm for noisy quantum devices. Sampling-based Quantum Algorithms have recently been successfully applied to large-scale quantum chemistry problems.
  arXiv  Detail & Related papers  (2025-04-17T04:13:51Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods. We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• 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 that finds the binary solution that is most likely measured from the optimal quantum state. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO outperforms the Goemans--Williamson method and is comparable to state-of-the-art classical solvers.
  arXiv  Detail & Related papers  (2024-03-04T13:48:21Z)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  We apply variational quantum algorithm QAOA to a variant of satisfiability problem (SAT): Not-All-Equal SAT. We show that while the runtime of both solvers scales exponentially with the problem size, the scaling for QAOA is smaller for large enough circuit depths.
  arXiv  Detail & Related papers  (2024-01-05T15:11:24Z)
• 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)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• 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)
• 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)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems. We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
  arXiv  Detail & Related papers  (2020-05-20T18:00:01Z)
• 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.