4 papers · 1 filter
Quasi-optimal quantum Markov chain spectral gap estimation
Adam Connolly, Steven Herbert, Julien Sorci
This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for…
Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
Ismail Yunus Akhalwaya, Ahmed Bhayat, Adam Connolly +4
Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances…
Average Mixing in Quantum Walks of Reversible Markov Chains
Julien Sorci
The Szegedy quantum walk is a discrete time quantum walk model which defines a quantum analogue of any Markov chain. The long-term behavior of the quantum walk can be encoded in a…
Almost-Optimal Computational Basis State Transpositions
Steven Herbert, Julien Sorci, Yao Tang
We give an explicit construction to perform any -qubit computational basis state transposition using gates. This nearly coincides with the lower bound o…