Fetching the paper…

Reading the bibliography…

2019

Review of a Quantum Algorithm for Betti Numbers

Gunn, Sam, Kornerup, Niels

Original
PDF
Post on X

Understand

We looked into the algorithm for calculating Betti numbers presented by Lloyd, Garnerone, and Zanardi (LGZ).

We present a new algorithm in the same spirit as LGZ with the intent of clarifying quantum algorithms for computing Betti numbers.
Our algorithm is simpler and slightly more efficient than that presented by LGZ.
We present a thorough analysis of our algorithm, pointing out reasons that both our algorithm and that presented by LGZ do not run in polynomial time for most inputs.

Review of a Quantum Algorithm for Betti Numbers · Around

Built on

A lower bound for rational approximations to pi
M Hata · 1993
Earlier work this paper cites.
Computing betti numbers via combinatorial laplacians
Joel Friedman · 1996
Earlier work this paper cites.
Tight Bounds on Quantum Searching
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp · 1998
Earlier work this paper cites.
Quantum Counting
Gilles Brassard, Peter Hoyer, and Alain Tapp · 1998
Earlier work this paper cites.

Similar

Computing persistent homology
Original
Afra Zomorodian and Gunnar Carlsson · 2005
Cited alongside, same era.
Extremal Betti numbers of Rips complexes
Original
Michael Goff · 2009
Cited alongside, same era.
Combinatorial laplacian and entropy of simplicial complexes associated with complex networks
Slobodan Maletic and Milan Rajkovic · 2012
Cited alongside, same era.

Then

Quantum algorithms for topological and geometric analysis of big data
Original
Seth Lloyd, Silvano Garnerone, and Paolo Zanardi · 2014
Later among the works it cites.
Hamiltonian simulation with nearly optimal dependence on all parameters
Original
Dominic W. Berry, Andrew M. Childs, and Robin Kothari · 2015
Later among the works it cites.
Proof of bijection for combinatorial number system
Original
Abu Bakar Siddique, Saadia Farid, and Muhammad Tahir · 2016
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…