What do QAOA energies reveal about graphs?

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.

References in corpus (17)

• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Classical and Quantum Bounded Depth Approximation Algorithms
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Solving the Graph Isomorphism Problem with a Quantum Annealer
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Fast graph operations in quantum computation
• k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs
• Benchmark Graphs for Practical Graph Isomorphism
• On quantum invariants and the graph isomorphism problem
• Quantum states and knowledge: Between pure states and density matrices

Cited by in corpus (10)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Optimal Control for Closed and Open System Quantum Optimization
• Analytical Framework for Quantum Alternating Operator Ansätze
• Alibaba Cloud Quantum Development Platform: Surface Code Simulations with Crosstalk
• Low overhead universality and quantum supremacy using only $Z$-control
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation