Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization

• URL: http://arxiv.org/abs/2410.22247v2
• Date: Sun, 03 Nov 2024 05:31:37 GMT
• Title: Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization
• Authors: Vaibhav. N Prakash,
• Abstract summary: 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.
• Score: 0.0
• License:
• Abstract: In this article we report on the application of the Quantum Approximate Optimization Algorithm (QAOA) to solve the unweighted MaxCut problem on tree-structured graphs. Specifically, we utilize the Nauty (No Automorphisms, Yes?) package to identify graph automorphisms, focusing on determining edge equivalence classes. These equivalence classes also correspond to symmetries in the terms of the associated Ising Hamiltonian. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian, thereby facilitating more efficient quantum simulations. We conduct benchmark experiments on graphs with up to 34 nodes on memory and CPU intensive TPU provided by google Colab, applying QAOA with a single layer ($p=1$). The approximation ratios obtained from both the full and symmetry-reduced Hamiltonians are systematically compared. 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.

Related papers

• 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)
• Quantum walk informed variational algorithm design [0.0]
  We present a theoretical framework for the analysis of amplitude transfer in Quantum Variational Algorithms (QVAs) We develop algorithms for unconstrained and constrained novel optimisations. We show significantly improved convergence over preexisting QVAs.
  arXiv  Detail & Related papers  (2024-06-17T15:04:26Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Pymablock: an algorithm and a package for quasi-degenerate perturbation theory [0.0]
  We introduce an algorithm for constructing an effective Hamiltonian as well as a Python package, Pymablock, that implements it. We demonstrate how the package handles constructing a k.p model, analyses a superconducting qubit, and computes the low-energy spectrum of a large tight-binding model.
  arXiv  Detail & Related papers  (2024-04-04T18:00:08Z)
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
  The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.
  arXiv  Detail & Related papers  (2023-07-28T16:45:16Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
  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.
  arXiv  Detail & Related papers  (2021-01-25T18:25:44Z)
• 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.