Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation
- URL: http://arxiv.org/abs/2407.01975v1
- Date: Tue, 2 Jul 2024 06:23:02 GMT
- Title: Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation
- Authors: Hannes Leipold, Federico M. Spedalieri, Stuart Hadfield, Eleanor Rieffel,
- Abstract summary: We give general expressions for finding Hamiltonian terms that satisfy constraint subsets and use these to give complexity characterizations of the related problems.
We then give algorithmic procedures to turn these primitives into Hamiltonian drivers and unitary mixers that can be used for Constrained Quantum Anneal Operator Ansatz (CQA) and Quantum Alternating Operator Ansatz (QAOA)
We empirically benchmark these approaches on instances sized between 12 and 22, showing the best relative performance for the tailored ansaetze and that exponential curve fits on the results are consistent with a quadratic speedup by utilizing alternative ansaetze to the
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constructing Driver Hamiltonians and Mixing Operators such that they satisfy constraints is an important ansatz construction for quantum algorithms. We give general algebraic expressions for finding Hamiltonian terms and analogously unitary primitives, that satisfy constraint embeddings and use these to give complexity characterizations of the related problems. Finding operators that enforce classical constraints is proven to be NP-Complete in the general case; algorithmic procedures with worse-case polynomial runtime to find any operators with a constant locality bound, applicable for many constraints. We then give algorithmic procedures to turn these algebraic primitives into Hamiltonian drivers and unitary mixers that can be used for Constrained Quantum Annealing (CQA) and Quantum Alternating Operator Ansatz (QAOA) constructions by tackling practical problems related to finding an appropriate set of reduced generators and defining corresponding drivers and mixers accordingly. We then apply these concepts to the construction of ansaetze for 1-in-3 SAT instances. We consider the ordinary x-mixer QAOA, a novel QAOA approach based on the maximally disjoint subset, and a QAOA approach based on the disjoint subset as well as higher order constraint satisfaction terms. We empirically benchmark these approaches on instances sized between 12 and 22, showing the best relative performance for the tailored ansaetze and that exponential curve fits on the results are consistent with a quadratic speedup by utilizing alternative ansaetze to the x-mixer. We provide very general algorithmic prescriptions for finding driver or mixing terms that satisfy embedded constraints that can be utilized to probe quantum speedups for constraints problems with linear, quadratic, or even higher order polynomial constraints.
Related papers
- Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop
Problem [0.0]
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.
arXiv Detail & Related papers (2023-11-07T16:16:52Z) - 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) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - 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) - 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) - Qualifying quantum approaches for hard industrial optimization problems.
A case study in the field of smart-charging of electric vehicles [0.0]
We present a case study for two industrial NP-Hard problems drawn from the strongly developing field of smart-charging of electric vehicles.
Quantum algorithms exhibit the same approximation ratios than conventional approximation algorithms, or improve them.
The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.
arXiv Detail & Related papers (2020-12-29T17:10:31Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
We propose a generalization extraient spaces which converges to a stationary point.
The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
arXiv Detail & Related papers (2020-10-31T21:35:42Z) - Constructing Driver Hamiltonians for Optimization Problems with Linear
Constraints [0.0]
We develop a simple and intuitive framework for reasoning about the commutation of Hamiltonians with linear constraints.
Because unitary operators are exponentials of Hermitian operators, these results can also be applied to the construction of mixers in the Quantum Alternating Operator Ansatz framework.
arXiv Detail & Related papers (2020-06-22T06:47:50Z)
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.