Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Problem Statement

The paper addresses the Graph Isomorphism (GI) problem, a computational task determining whether two finite graphs are structurally identical. While the problem occupies a unique position in complexity theory (neither proven NP-complete nor solvable in polynomial time), it has significant practical applications in chemistry, biology, and social networks.

The authors investigate the application of Variational Quantum Algorithms (VQAs)—specifically the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE)—to solve GI. The core challenge lies in encoding the GI problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation (or Ising Hamiltonian) where valid graph isomorphisms correspond to the ground state (zero energy). The study focuses on whether variational optimization can effectively distinguish isomorphic from non-isomorphic graph pairs in the Noisy Intermediate Scale Quantum (NISQ) regime, particularly given the constraints of small graph instances and limited qubit counts.

Methodology

The research employs a hybrid quantum-classical approach using small-scale graph instances (4 and 5 nodes) to simulate NISQ conditions.

1. Problem Formulation:

   • The authors utilize QUBO formulations derived from prior work (Lucas, Zick et al., and Calude et al.).
   • The Hamiltonian includes penalty terms to enforce bijection constraints (ensuring a one-to-one mapping between vertices) and edge preservation (ensuring adjacency is maintained).
   • The number of logical qubits required scales as $O(n^2)$ for graphs of order $n$, limiting the study to small $n$ due to current hardware and simulation constraints.

2. Algorithms:

   • QAOA: Implemented with a shallow circuit depth ($p=1$) to remain within the NISQ-relevant regime. It uses a cost Hamiltonian derived from the QUBO and a mixer Hamiltonian.
   • VQE: Implemented with a deeper, more expressive ansatz (TwoLocal circuit with 5 repetitions) and the SPSA optimizer. This serves as a high-fidelity check to confirm if the Hamiltonian correctly encodes the problem structure.

3. Analysis Framework:

   • Instead of relying solely on final energy values, the authors analyze optimization trajectories.
   • They construct a feature vector comprising the number of vertices ($N$), final variational energy ($E_{final}$), optimization steps, and total energy decrease ($\Delta E$).
   • These features are fed into a suite of classical machine learning classifiers (Logistic Regression, SVM, Random Forest, Gradient Boosting, XGBoost, LightGBM, MLP) to test if trajectory-level data improves discrimination between isomorphic and non-isomorphic pairs.

Key Contributions and Results

1. Energy Clustering of Isomorphic Pairs
The study observes that isomorphic graph pairs exhibit consistent clustering in their variational energy landscapes.

• QAOA: For small systems ($N=4$), isomorphic pairs concentrate around lower energy values. However, as $N$ increases to 5, the ability to discriminate based solely on minimum energy degrades rapidly.
• VQE: Confirms the clustering phenomenon with higher fidelity, showing that isomorphic pairs converge to near-zero energy while non-isomorphic pairs converge to positive values. This validates that the Hamiltonian correctly encodes structural features.
• Controlled Ablation: Experiments varying graph topology (edge removal) while keeping isomorphism fixed demonstrated that energy shifts are driven by graph structure, not labeling artifacts, confirming the stability of the Hamiltonian encoding.

2. Limitations of Low Energy as a Certifier
A critical finding is that low variational energy is an unreliable certifier of isomorphism.

• Infeasible States: The optimization frequently converges to low-energy states that violate the bijection constraints (permutation constraints).
• Spectral Overlap: There is substantial overlap between the low-energy spectra of isomorphic and non-isomorphic instances. Many non-isomorphic graphs yield energies indistinguishable from isomorphic ones, particularly at shallow circuit depths.
• Degeneracy: The feasible set of valid permutations is vanishingly small compared to the total Hilbert space ($N! / 2^{N^2} \to 0$), leading to a landscape dominated by infeasible superpositions.

3. Performance of Trajectory-Based Classification
The authors tested whether analyzing the optimization path (trajectory) rather than just the final energy could improve classification.

• Results: While non-linear ensemble methods (Random Forest, Gradient Boosting) outperformed linear classifiers, the overall accuracy remained modest (best accuracy $\approx 75\%$).
• Conclusion: The failure of these models to achieve reliable separation indicates that the variational signal itself lacks sufficient discriminatory information, rather than the classifiers being insufficiently expressive. The overlap in low-energy spectra is an intrinsic limitation of the current variational encoding.

Significance and Claims

The paper positions its findings as a proof-of-principle investigation rather than a scalable solution to the Graph Isomorphism problem.

• Diagnostic Tool vs. Solver: The authors argue that variational algorithms should not be viewed as solvers for GI in the NISQ era. Instead, they serve as diagnostic tools to probe the structure of Hamiltonian encodings. The observed energy clustering reveals that the Hamiltonian successfully encodes structural features, but the inability to separate classes based on energy highlights the limitations of purely energetic heuristics.
• Limitations of Current Approaches: The study underscores that without mechanisms to explicitly enforce global permutation constraints or more advanced ansätze, variational algorithms will struggle to distinguish isomorphic from non-isomorphic graphs due to the prevalence of infeasible low-energy states.
• Future Direction: The work suggests that progress requires compact QUBO encodings, problem-tailored ansätze, and constraint-aware mixers. It also notes that scaling to larger graphs (6–8 nodes) and testing on real hardware with error mitigation are necessary next steps to bridge the gap between simulation and experimental feasibility.

In summary, the paper demonstrates that while variational quantum algorithms can identify low-energy basins corresponding to graph structures, energy minimization alone is insufficient for scalable graph isomorphism discrimination due to the high probability of converging to infeasible states and the spectral overlap between graph classes.