Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop
Problem
- URL: http://arxiv.org/abs/2311.04100v1
- Date: Tue, 7 Nov 2023 16:16:52 GMT
- Title: Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop
Problem
- Authors: Lilly Palackal, Leonhard Richter, Maximilian Hess
- Abstract summary: The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, optimization solutions.
As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit.
We develop mixing operators for a wide range of scheduling problems including the flexible job shop problem.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the most promising attempts towards solving optimization problems with
quantum computers in the noisy intermediate scale era of quantum computing are
variational quantum algorithms. The Quantum Alternating Operator Ansatz
provides an algorithmic framework for constrained, combinatorial optimization
problems. As opposed to the better known standard QAOA protocol, the
constraints of the optimization problem are built into the mixing layers of the
ansatz circuit, thereby limiting the search to the much smaller Hilbert space
of feasible solutions. In this work we develop mixing operators for a wide
range of scheduling problems including the flexible job shop problem. These
mixing operators are based on a special control scheme defined by a constraint
graph model. After describing an explicit construction of those mixing
operators, they are proven to be feasibility preserving, as well as exploring
the feasible subspace.
Related papers
- Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints.
In this study, we investigate a hybrid quantum-classical method for constrained optimization problems.
Our proposed method relies on relaxations to local quantum Hamiltonians, defined through commutative maps.
arXiv Detail & Related papers (2024-04-30T11:40:07Z) - Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
We present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation.
Existing quantum solvers are limited to solving unconstrained binary programming problems.
Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
arXiv Detail & Related papers (2023-06-01T21:33:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Free Job-Shop Scheduling With Hardcoded Constraints [0.0]
We show that desired properties of similarly constructed mixers can be directly linked to a purely classical object.
We propose a new variational quantum algorithm that incorporates the underlying group structure more naturally.
arXiv Detail & Related papers (2022-11-10T19:25:20Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - 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) - 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) - 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.