Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
arXiv:2111.09821 · doi:10.1063/5.0305337
Abstract
We investigate a quadratic unconstrained binary optimization (QUBO) formulation of the graph isomorphism problem using the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE). 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 outperform naive energy thresholding, though absolute performance remains limited. Our results characterize the current limits of variational algorithms for graph isomorphism, positioning energy landscape analysis as a diagnostic tool rather than a scalable decision procedure in the NISQ regime.
7 pages, 3 figures
References in corpus (20)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum adiabatic machine learning
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Does provable absence of barren plateaus imply classical simulability?
- A cross-disciplinary introduction to quantum annealing-based algorithms
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- Experimental quantum annealing: case study involving the graph isomorphism problem
- A perspective on protein structure prediction using quantum computers
- Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
- The Peierls argument for higher dimensional Ising models
- Simulating spin biology using a digital quantum computer: Prospects on a near-term quantum hardware emulator
- A near-term quantum simulation of the transverse field Ising model hints at Glassy Dynamics
- Symmetric Trotterization in digital quantum simulation of quantum spin dynamics
- Resource-efficient utilization of quantum computers
- Simulating spin dynamics with quantum computers
- RinQ: Towards predicting central sites in proteins on current quantum computers