  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.
