Quantum-Informed Recursive Optimization Algorithms
- URL: http://arxiv.org/abs/2308.13607v3
- Date: Mon, 11 Mar 2024 01:57:44 GMT
- Title: Quantum-Informed Recursive Optimization Algorithms
- Authors: Jernej Rudi Fin\v{z}gar, Aron Kerschbaumer, Martin J. A. Schuetz,
Christian B. Mendl, Helmut G. Katzgraber
- Abstract summary: We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for optimization problems.
Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps.
We use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and implement a family of quantum-informed recursive optimization
(QIRO) algorithms for combinatorial optimization problems. Our approach
leverages quantum resources to obtain information that is used in
problem-specific classical reduction steps that recursively simplify the
problem. These reduction steps address the limitations of the quantum component
and ensure solution feasibility in constrained optimization problems.
Additionally, we use backtracking techniques to further improve the performance
of the algorithm without increasing the requirements on the quantum hardware.
We demonstrate the capabilities of our approach by informing QIRO with
correlations from classical simulations of shallow (depth $p=1$) circuits of
the quantum approximate optimization algorithm (QAOA), solving instances of
maximum independent set and maximum satisfiability problems with hundreds of
variables. We also demonstrate how QIRO can be deployed on a neutral atom
quantum processor available online on Amazon Braket to find large independent
sets of graphs. In summary, our scheme achieves results comparable to classical
heuristics, such as simulated annealing and greedy algorithms, even with
relatively weak quantum resources. Furthermore, enhancing the quality of these
quantum resources improves the performance of the algorithms, highlighting the
potential of QIRO. Notably, the modular nature of QIRO offers various avenues
for modifications, positioning our work as a blueprint for designing a broader
class of hybrid quantum-classical algorithms for combinatorial optimization.
Related papers
- PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio.
We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters.
Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
arXiv Detail & Related papers (2024-07-29T10:26:28Z) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - 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) - Graph Learning for Parameter Prediction of Quantum Approximate
Optimization Algorithm [14.554010382366302]
Quantum Approximate Optimization (QAOA) stands out for its potential to efficiently solve the Max-Cut problem.
We use Graph Neural Networks (GNN) as a warm-start technique to optimize QAOA, using GNN as a warm-start technique.
Our findings show GNN's potential in improving QAOA performance, opening new avenues for hybrid quantum-classical approaches in quantum computing.
arXiv Detail & Related papers (2024-03-05T20:23:25Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - 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) - Parallel circuit implementation of variational quantum algorithms [0.0]
We present a method to split quantum circuits of variational quantum algorithms (VQAs) to allow for parallel training and execution.
We apply this specifically to optimization problems, where inherent structures from the problem can be identified.
We show that not only can our method address larger problems, but that it is also possible to run full VQA models while training parameters using only one slice.
arXiv Detail & Related papers (2023-04-06T12:52:29Z) - Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device.
We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.
This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
arXiv Detail & Related papers (2022-09-07T18:01:01Z) - 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) - 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) - 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)
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.