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 introduce a new quantum algorithm for computing the Betti numbers of asimplicial complex. In contrast to previous quantum algorithms that work byestimating the eigenvalues of the combinatorial Laplacian, our algorithm is aninstance of the generic Incremental Algorithm for computing Betti numbers thatincrementally adds simplices to the simplicial complex and tests whether or notthey create a cycle. In contrast to existing quantum algorithms for computingBetti numbers that work best when the complex has close to the maximal numberof simplices, our algorithm works best for sparse complexes. To test whether asimplex creates a cycle, we introduce a quantum span-program algorithm. We showthat the query complexity of our span program is parameterized by quantitiescalled the effective resistance and effective capacitance of the boundary ofthe simplex. Unfortunately, we also prove upper and lower bounds on theeffective resistance and capacitance, showing both quantities can beexponentially large with respect to the size of the complex, implying that ouralgorithm would have to run for exponential time to exactly compute Bettinumbers. However, as a corollary to these bounds, we show that the spectral gapof the combinatorial Laplacian can be exponentially small. As the runtime ofall previous quantum algorithms for computing Betti numbers are parameterizedby the inverse of the spectral gap, our bounds show that all quantum algorithmsfor computing Betti numbers must run for exponentially long to exactly computeBetti numbers. Finally, we prove some novel formulas for effective resistanceand effective capacitance to give intuition for these quantities.

An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis