Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints
- URL: http://arxiv.org/abs/2305.08056v1
- Date: Sun, 14 May 2023 03:49:10 GMT
- Title: Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints
- Authors: Ke Wan, Yiwen Liu
- Abstract summary: This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints.
The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
- Score: 5.259170150405252
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: When tackling binary optimization problems using quantum algorithms, the
conventional Ising representation and Quantum Approximate Optimization
Algorithm (QAOA) encounter difficulties in efficiently handling errors for
large-scale problems involving multiple constraints. To address these
challenges, this paper presents a hybrid framework that combines the use of
standard Ising Hamiltonians to solve a subset of the constraints, while
employing non-Ising formulations to represent and address the remaining
constraints. The resolution of these non-Ising constraints is achieved through
either penalty dephasing or the quantum Zeno effect. This innovative approach
leads to a collection of quantum circuits with adaptable structures, depending
on the chosen representation for each constraint. Furthermore, this paper
introduces a novel technique that utilizes the quantum Zeno effect by
frequently measuring the constraint flag, enabling the resolution of any
optimization constraint. Theoretical properties of these algorithms are
discussed, and their performance in addressing practical aircraft loading
problems is highly promising, showcasing significant potential for a wide range
of industrial applications.
Related papers
- Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations [0.0]
We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA.
By identifying and separating the problem into two stages, we transform soft constraints into hard constraints.
arXiv Detail & Related papers (2024-08-09T23:38:28Z) - 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) - Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation.
Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
arXiv Detail & Related papers (2023-10-06T19:09:55Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms.
We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem.
Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
arXiv Detail & Related papers (2023-02-08T17:09:20Z) - Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities.
We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
arXiv Detail & Related papers (2022-09-29T18:00:40Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs.
A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual.
The proposed approach is shown to converge (with linear rate) to the global optimum.
arXiv Detail & Related papers (2022-06-03T16:26:38Z) - 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) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization.
We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance.
The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
arXiv Detail & Related papers (2021-06-24T16:39:31Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace.
One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz.
We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
arXiv Detail & Related papers (2021-05-14T11:31:14Z) - 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.