Exploiting Symmetry Reduces the Cost of Training QAOA

• URL: http://arxiv.org/abs/2101.10296v3
• Date: Wed, 10 Mar 2021 21:00:56 GMT
• Title: Exploiting Symmetry Reduces the Cost of Training QAOA
• Authors: Ruslan Shaydulin, Stefan M. Wild
• Abstract summary: We propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems.
• Score: 6.295931120803673
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A promising approach to the practical application of the Quantum Approximate Optimization Algorithm (QAOA) is finding QAOA parameters classically in simulation and sampling the solutions from QAOA with optimized parameters on a quantum computer. Doing so requires repeated evaluations of QAOA energy in simulation. We propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. We show how by considering only the terms that are not connected by symmetry, we can significantly reduce the cost of evaluating the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems. Our results are directly applicable to nonlocal QAOA generalization RQAOA. We outline how available fast graph automorphism solvers can be leveraged for computing the symmetries of the problem in practice. We implement the proposed approach on the MaxCut problem using a state-of-the-art tensor network simulator and a graph automorphism solver on a benchmark of 48 graphs with up to 10,000 nodes. Our approach provides an improvement for $p=1$ on $71.7\%$ of the graphs considered, with a median speedup of $4.06$, on a benchmark where $62.5\%$ of the graphs are known to be hard for automorphism solvers.

Related papers

• Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
  We use the Nauty package to identify graph automorphisms, focusing on determining edge equivalence classes. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian. Our results show that using automorphism-based symmetries to reduce the Pauli terms in the Hamiltonian can significantly decrease computational overhead without compromising the quality of the solutions obtained.
  arXiv  Detail & Related papers  (2024-10-29T17:10:25Z)
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA [0.5999777817331315]
  We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) In particular, perturbations on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. Through an analysis of the spectrum of the graphs and their perturbations, we aim to extract valuable insights into how symmetry impacts the performance of QAOA.
  arXiv  Detail & Related papers  (2024-08-27T21:38:23Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve optimisation problems. While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance. This work introduces the eXpressive QAOA (XQAOA) that assigns more classical parameters to the ansatz to improve its performance at low depths.
  arXiv  Detail & Related papers  (2023-02-09T07:47:06Z)
• 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)
• 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)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• 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)
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems [1.8732539895890135]
  We report on the energy-expectation-value landscapes produced by the single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) The landscapes are obtained using an analytical formula that we derive. We provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits.
  arXiv  Detail & Related papers  (2020-12-07T02:23:37Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)

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.