What do QAOA energies reveal about graphs?

• URL: http://arxiv.org/abs/1912.12277v2
• Date: Tue, 31 Dec 2019 09:23:58 GMT
• Title: What do QAOA energies reveal about graphs?
• Authors: Mario Szegedy
• Abstract summary: We use the dependence of QAOA energy on the graph structure for randomly or judiciously chosen parameters to learn about graphs. Many of our discoveries can be interpreted as computing $U(G)$ under various restrictions.
• Score: 2.0305676256390934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm to approximately solve NP optimization problems such as MAX-CUT. We describe a new application area of QAOA circuits: graph structure discovery. We omit the time-consuming parameter-optimization phase and utilize the dependence of QAOA energy on the graph structure for randomly or judiciously chosen parameters to learn about graphs. In the first part, Following up on Wang et. al. and Brandao et. al. we give explicit formulas. We show that the layer-one QAOA energy for the MAX-CUT problem for three regular graphs carries exactly the information: {\em (# of vertices, # of triangles)}. We have calculated our explicit formulas differently from \cite{wang2018quantum}, by developing the notion of the $U$ polynomial of a graph $G$. Many of our discoveries can be interpreted as computing $U(G)$ under various restrictions. The most basic question when comparing the structure of two graphs is if they are isomorphic or not. We find that the QAOA energies separate all non-isomorphic three-regular graphs up to size 18, all strongly regular graphs up to size 26 and the Praust and the smallest Miyazaki examples. We observe that the QAOA energy values can be also used as a proxy to how much graphs differ. Unfortunately, we have also found a sequence of non-isomorphic pairs of graphs, for which the energy gap seems to shrink at an exponential rate as the size grows. Our negative findings however come with a surprise: if the QAOA energies do not measurably separate between two graphs, then both of their energy landscapes must be extremely flat (indistinguishable from constant), already when the number of QAOA layers is intermediately large. This holds due to a remarkable uncoupling phenomenon that we have only deduced from computer simulation.

Related papers

• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
  arXiv  Detail & Related papers  (2026-03-03T06:43:41Z)
• Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
  A graph that encodes its commutatitivity structure, i.e., by its frustration graph, provides a natural interface between graph theory and quantum information.<n>We call this class $hbar$-perfect, as it extends the class of perfect and $h$-perfect graphs.<n>We find efficient schemes for entanglement detection, a connection to the complexity of shadow tomography, tight uncertainty relations and a construction for computing good lower on ground state energies.
  arXiv  Detail & Related papers  (2025-11-17T16:05:28Z)
• Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
  We present a new QAOA ansatz that introduces only one additional parameter to the standard ansatz. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs.
  arXiv  Detail & Related papers  (2024-11-07T22:20:01Z)
• Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs [26.8902894372334]
  In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs.
  arXiv  Detail & Related papers  (2024-10-06T08:57:30Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• G-Mixup: Graph Data Augmentation for Graph Classification [55.63157775049443]
  Mixup has shown superiority in improving the generalization and robustness of neural networks by interpolating features and labels between two random samples. We propose $mathcalG$-Mixup to augment graphs for graph classification by interpolating the generator (i.e., graphon) of different classes of graphs. Experiments show that $mathcalG$-Mixup substantially improves the generalization and robustness of GNNs.
  arXiv  Detail & Related papers  (2022-02-15T04:09:44Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Application of graph theory in quantum computer science [0.0]
  We demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. The quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
  arXiv  Detail & Related papers  (2021-09-27T12:07:25Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
  arXiv  Detail & Related papers  (2021-07-05T11:41:16Z)
• Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks [74.26734952400925]
  We propose a novel Minimum Graph Entropy (MinGE) algorithm for Node Embedding Dimension Selection (NEDS) MinGE considers both feature entropy and structure entropy on graphs, which are carefully designed according to the characteristics of the rich information in them. Experiments with popular Graph Neural Networks (GNNs) on benchmark datasets demonstrate the effectiveness and generalizability of our proposed MinGE.
  arXiv  Detail & Related papers  (2021-05-07T11:40:29Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23:09Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
  The quantum circuit has p applications of a unitary operator that respects the locality of the graph. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large.
  arXiv  Detail & Related papers  (2020-04-20T00:48:02Z)

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.