Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2111.09821 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911399723139072 |
|---|---|
| author | Chatterjee, Turbasu Mohtashim, Shah Ishmam Kundu, Akash |
| author_facet | Chatterjee, Turbasu Mohtashim, Shah Ishmam Kundu, Akash |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_09821 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization Chatterjee, Turbasu Mohtashim, Shah Ishmam Kundu, Akash Quantum Physics 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. |
| title | Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2111.09821 |