Constrained mixers for the quantum approximate optimization algorithm

• URL: http://arxiv.org/abs/2203.06095v5
• Date: Wed, 22 Jun 2022 14:17:33 GMT
• Title: Constrained mixers for the quantum approximate optimization algorithm
• Authors: Franz G. Fuchs, Kjetil Olsen Lye, Halvor M{\o}ll Nilsen, Alexander J. Stasik, and Giorgio Sartor
• Abstract summary: 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.
• Score: 55.41644538483948
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints; 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. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.

Related papers

• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization [6.407238428292173]
  We introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space.
  arXiv  Detail & Related papers  (2024-10-08T05:48:46Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation [0.0]
  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
  arXiv  Detail & Related papers  (2024-07-02T06:23:02Z)
• 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)
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism [0.0]
  We present a novel formalism to both understand and construct mixers that preserve a given subspace. We call our approach logical X-Mixer or logical X QAOA.
  arXiv  Detail & Related papers  (2023-06-29T16:36:07Z)
• 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)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
  A semidefinite program (SDP) is a convex optimization problem with applications in operations research, optimization, quantum information science, and beyond. We propose variational quantum algorithms for approximately solving SDPs.
  arXiv  Detail & Related papers  (2021-12-16T13:10:48Z)
• 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.