Testing the presence of balanced and bipartite components in a sparse graph is ๐ฐ๐ฌ๐ 1 \mathsf{QMA}_{1} -hard
Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, Vedran Dunjko ยท 2024
Read Testing the presence of balanced and bipartite components in a sparse graph is ๐ฐ๐ฌ๐ 1 \mathsf{QMA}_{1} -hard by Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, Vedran Dunjko (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14932.txt.
Description
Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, and Vedran Dunjko proved in 2024 that testing certain graph traits is QMA1-hard, a quantum hardness class. Their starting point is a known hard task: telling whether a simplicial complex has multi-dimensional holes, a task tied to the kernel of the Combinatorial Laplacian.
The team maps that operator's spectral traits onto those of signed and unsigned graph Laplacians, while keeping sparse access efficient. From this, testing for balanced parts in signed graphs and for bipartite parts in unsigned graphs both prove hard. Those traits matter in network science, and the result adds a case to quantum Hamiltonian complexity.
Catalog record
| CREATOR | Massimiliano Incudini, Casper Gyurik, Riccardo Molteni, Vedran Dunjko |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-14932