VeloxQ: A Fast and Efficient QUBO Solver

• URL: http://arxiv.org/abs/2501.19221v1
• Date: Fri, 31 Jan 2025 15:27:50 GMT
• Title: VeloxQ: A Fast and Efficient QUBO Solver
• Authors: J. Pawłowski, J. Tuziemski, P. Tarasiuk, A. Przybysz, R. Adamski, K. Hendzel, Ł. Pawela, B. Gardas,
• Abstract summary: VeloxQ is a fast and efficient solver for Quadratic Unconstrained Binary Optimization problems. We benchmark VeloxQ against the state-of-the-art QUBO solvers based on emerging technologies.
• Score: 0.0
• License:
• Abstract: We introduce VeloxQ, a fast and efficient solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to numerous real-world optimization tasks. Unlike other physics-inspired approaches to optimization problems, such as quantum annealing and quantum computing, VeloxQ does not require substantial progress of technology to unlock its full potential. We benchmark VeloxQ against the state-of-the-art QUBO solvers based on emerging technologies. Our comparison includes quantum annealers, specifically D-Wave's Advantage, and Advantage2 prototype platforms, the digital-quantum algorithm designed to solve Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum, physics-inspired algorithms: Simulated Bifurcation and Parallel Annealing and an algorithm based on tropical tensor networks. We also take into account modern developments of conventional algorithms: Branch and Bound algorithm, an optimal implementation of the brute-force algorithm and BEIT QUBO solver. Our results show that VeloxQ not only matches but often surpasses the mentioned solvers in solution quality and runtime. Additionally, VeloxQ demonstrates excellent scalability being the only solver capable of solving large-scale optimization problems, including up to $2\times 10^{8}$ sparsely connected variables, that are currently intractable for its competitors. These findings position VeloxQ as a powerful and practical tool for tackling large-scale QUBO and HUBO problems, offering a compelling alternative to existing quantum and classical optimization methods.

Related papers

• Tensor Network Based HOBO Solver [0.0]
  The proposed solver is a promising tool with significant potential for future extensions in terms of formulation. This solver holds promising potential for a wide range of applications in quantum computing.
  arXiv  Detail & Related papers  (2024-07-23T00:33:34Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Quantum-Inspired Optimization over Permutation Groups [0.2294014185517203]
  Quantum-inspired optimization (QIO) algorithms are computational techniques that emulate certain quantum mechanical effects on a classical hardware. We develop an algorithmic framework, called Perm-QIO, to tailor QIO tools to solve an arbitrary optimization problem.
  arXiv  Detail & Related papers  (2022-12-06T00:02:39Z)
• 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)
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels [0.0]
  The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. We build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz. We find that the performance of the quantum algorithm depends heavily on what noise model is used.
  arXiv  Detail & Related papers  (2022-05-13T11:29:12Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  Vehicle routing problem (VRP) is an NP-hard optimization problem. This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
  arXiv  Detail & Related papers  (2021-12-28T10:20:42Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• 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)
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization [0.14755786263360526]
  We explore which quantum algorithms for optimization might be most practical to try out on a small fault-tolerant quantum computer. Our results discourage the notion that any quantum optimization realizing only a quadratic speedup will achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2020-07-14T22:54:04Z)

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.