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

CREATORMassimiliano Incudini, Casper Gyurik, Riccardo Molteni, Vedran Dunjko
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14932

Browse the full library ยท About the Tower of Babel