Energy landscape structure of small graph isomorphism under variational optimization

We investigate a quadratic unconstrained binary optimization formulation of the graph isomorphism problem using the quantum approximate optimization algorithm and the variational quantum eigensolver. For small graph instances, we observe that isomorphic pairs exhibit consistent clustering in variational energies, indicating that the Hamiltonian successfully encodes structural features. However, we demonstrate that low variational energy alone is an unreliable certifier of isomorphism due to the high probability of converging to infeasible states that violate bijection constraints. To address this, we analyze optimization trajectories rather than final energies, consistently outperforming naive energy…

• OS
  Ohio State University