Equivariant QAOA and the Duel of the Mixers

• URL: http://arxiv.org/abs/2405.07211v1
• Date: Sun, 12 May 2024 08:22:41 GMT
• Title: Equivariant QAOA and the Duel of the Mixers
• Authors: Boris Tsvelikhovskiy, Ilya Safro, Yuri Alexeev,
• Abstract summary: We present a systematic methodology for constructing the QAOA tailored mixer Hamiltonian. Key to our approach is to identify an operator that commutes with the action of the group of symmetries on the QAOA underlying Hilbert space.
• Score: 1.1985053703926616
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constructing an optimal mixer for Quantum Approximate Optimization Algorithm (QAOA) Hamiltonian is crucial for enhancing the performance of QAOA in solving combinatorial optimization problems. We present a systematic methodology for constructing the QAOA tailored mixer Hamiltonian, ensuring alignment with the inherent symmetries of classical optimization problem objectives. The key to our approach is to identify an operator that commutes with the action of the group of symmetries on the QAOA underlying Hilbert space and meets the essential technical criteria for effective mixer Hamiltonian functionality. We offer a construction method specifically tailored to the symmetric group $S_d$, prevalent in a variety of combinatorial optimization problems. By rigorously validating the required properties, providing a concrete formula and corresponding quantum circuit for implementation, we establish the viability of the proposed mixer Hamiltonian. Furthermore, we demonstrate that the classical mixer $B$ commutes only with a subgroup of $S_d$ of significantly smaller order than the group itself, enhancing the efficiency of the proposed approach. To evaluate the effectiveness of our methodology, we compare two QAOA variants utilizing different mixer Hamiltonians: conventional $B=\sum X_i$ and the newly proposed $H_M$ in edge coloring and graph partitioning problems across various graphs. We observe statistically significant differences in mean values, with the new variant consistently demonstrating superior performance across multiple independent simulations. Additionally, we analyze the phenomenon of poor performance in alternative warm-start QAOA variants, providing a conceptual explanation supported by recent literature findings.

Related papers

• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms. Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
  arXiv  Detail & Related papers  (2023-08-17T08:34:58Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz [0.0]
  We introduce a strategy for parameter setting suitable for common cases in which the number of distinct cost values grows onlyly with the problem size. We define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity holds exactly, and which yields information describing both states and expectation values. For up to $3$ QAOA levels we are easily able to find parameters that match approximation ratios returned by previous globally optimized approaches.
  arXiv  Detail & Related papers  (2022-11-17T00:18:06Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Parent Hamiltonian as a benchmark problem for variational quantum eigensolvers [0.6946929968559495]
  Variational quantum eigensolver (VQE) finds a ground state of a given Hamiltonian by variationally optimizing the parameters of quantum circuits called ansatz. This work provides a systematic way to analyze energies for VQE and contribute to the design of ansatz and its initial parameters.
  arXiv  Detail & Related papers  (2021-09-24T06:09:10Z)
• Classical symmetries and QAOA [3.2880869992413246]
  We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function.
  arXiv  Detail & Related papers  (2020-12-08T20:02:09Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
  arXiv  Detail & Related papers  (2020-06-08T18:00:18Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.