English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the complexity of a classic problem in computational topology, thehomology problem: given a description of some space $X$ and an integer $k$,decide if $X$ contains a $k$-dimensional hole. The setting and statement of thehomology problem are completely classical, yet we find that the complexity ischaracterized by quantum complexity classes. Our result can be seen as anaspect of a connection between homology and supersymmetric quantum mechanics[Wit82].  We consider clique complexes, motivated by the practical application oftopological data analysis (TDA). The clique complex of a graph is thesimplicial complex formed by declaring every $k+1$-clique in the graph to be a$k$-simplex. Our main result is that deciding whether the clique complex of aweighted graph has a hole or not, given a suitable promise, is$\text{QMA}_1$-hard and contained in $\text{QMA}$.  Our main innovation is a technique to lower bound the eigenvalues of thecombinatorial Laplacian operator. For this, we invoke a tool from algebraictopology known as spectral sequences. In particular, we exploit a connectionbetween spectral sequences and Hodge theory [For94]. Spectral sequences willplay a role analogous to perturbation theory for combinatorial Laplacians. Inaddition, we develop the simplicial surgery technique used in prior work[CK22].  Our result provides some suggestion that the quantum TDA algorithm [LGZ16]cannot be dequantized. More broadly, we hope that our results will open up newpossibilities for quantum advantage in topological data analysis.

Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$