COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Quantum Fast-Forwarding: Markov Chains and Graph Property Testing

## Quantum Fast-Forwarding: Markov Chains and Graph Property TestingAdd to your list(s) Download to your calendar using vCal - Simon Apers, INRIA
- Thursday 21 February 2019, 14:15-15:15
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact Johannes Bausch. I will introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. In a number of quantum walk steps that scales as the square root of the classical runtime, and inversely proportional to the 2-norm of the classical distribution, it retrieves a quantum superposition that encodes the classical distribution. This shows that quantum walks can accelerate the transient dynamics of Markov chains, thereby complementing the line of results that proves the acceleration of their limit behavior. This tool leads to speedups on random walk algorithms in a very natural way. Specifically I will consider random walk algorithms for testing the graph expansion and clusterability, and show that QFF allows to quadratically improve the dependency of the classical property testers on the random walk runtime; Moreover, this new quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, I use QFF to determine whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Interested Talks
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- bld31
Note that ex-directory lists are not shown. |
## Other listsWolfson College Lunchtime Seminar Series - Wednesdays of Full Term Kettle's Yard Lunchtime Talks## Other talksLearning from rivers about long-term controls on Earthâ€™s climate Clueless Voting 200TH ANNIVERSARY TWO-DAY MEETING - The Futures of Sciences Through a glass darkly - interpreting animal behaviour with the aid of machines CTEQ-TEA: Precise analysis of hadron structure in the LHC era Exoplanets, Aliens and God |