Compare Papers

Paper 1

Quantum Algorithm for the Longest Trail Problem

Kamil Khadiev, Ruslan Kapralov

Year

2021

Journal

arXiv preprint

DOI

arXiv:2112.13847

arXiv

2112.13847

We present the quantum algorithm for the Longest Trail Problem. The problem is to search the longest edge-simple path for a graph with $n$ vertexes and $m$ edges. Here edge-simple means no edge occurs in the path twice, but vertexes can occur several times. The running time of our algorithm is $O^*(1.728^m)$.

Open paper

Paper 2

Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

Turbasu Chatterjee, Shah Ishmam Mohtashim, Akash Kundu

Year

2021

Journal

arXiv preprint

DOI

arXiv:2111.09821

arXiv

2111.09821

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.

Open paper