A Fast Numerical Solver of Quantum-inspired Ising Optimization Problems
- URL: http://arxiv.org/abs/2312.05837v1
- Date: Sun, 10 Dec 2023 09:43:15 GMT
- Title: A Fast Numerical Solver of Quantum-inspired Ising Optimization Problems
- Authors: Langyu Li and Yu Pan
- Abstract summary: We propose a fast and efficient solver for the Ising optimization problems.
Our solver can be an order of magnitude faster than the classical solver, and at least two times faster than the quantum-inspired annealers.
- Score: 1.6890316763606814
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum annealers, coherent Ising machines and digital Ising machines for
solving quantum-inspired optimization problems have been developing rapidly due
to their near-term applications. The numerical solvers of the digital Ising
machines are based on traditional computing devices. In this work, we propose a
fast and efficient solver for the Ising optimization problems. The algorithm
consists of a pruning method that exploits the graph information of the Ising
model to reduce the computational complexity, and a domain selection method
which introduces significant acceleration by relaxing the discrete feasible
domain into a continuous one to incorporate the efficient gradient descent
method. The experiment results show that our solver can be an order of
magnitude faster than the classical solver, and at least two times faster than
the quantum-inspired annealers including the simulated quantum annealing on the
benchmark problems. With more relaxed requirements on hardware and lower cost
than quantum annealing, the proposed solver has the potential for near-term
application in solving challenging optimization problems as well as serving as
a benchmark for evaluating the advantage of quantum devices.
Related papers
- Sparks of Quantum Advantage and Rapid Retraining in Machine Learning [0.0]
We leverage adiabatic quantum computers to optimize Kolmogorov-Arnold Networks.
We create a fixed-sized solution space independent of the number of training samples.
Our approach sparks of quantum advantage through faster training times compared to classicals.
arXiv Detail & Related papers (2024-07-22T19:55:44Z) - Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut
Problems with QAOA [1.5047640669285467]
Quantum approximate optimization algorithm (QAOA) is one of the popular quantum algorithms that are used to solve optimization problems via approximations.
However, performing QAOA on virtual quantum computers suffers from a slow simulation speed for solving optimization problems.
We propose techniques to accelerate QCS for QAOA using mathematical optimizations to compress quantum operations.
arXiv Detail & Related papers (2023-12-05T06:08:57Z) - 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) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems.
We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
arXiv Detail & Related papers (2022-05-02T21:30:56Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - 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) - Integer Programming from Quantum Annealing and Open Quantum Systems [0.8049701904919515]
We develop an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer.
We find that the algorithm outperforms random guessing but is limited to small problems.
arXiv Detail & Related papers (2020-09-24T22:18:01Z) - 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.