Quasi-optimal quantum Markov chain spectral gap estimation
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 all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.07601
curl -X POST /api/v1/records/arxiv/2601.07601/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.07601/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'