Thanks for the comment, Simone. A couple of observations:
- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from ([arXiv:1705.08253][1]): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov chain in a number of steps equal to the diameter.
- In the more recent arxiv paper ([arXiv:1712.01609][2]) that you mention (remarkable that it came out a day before without coordination!), we strengthen theorem 2 of ([arXiv:1705.08253][1]), the same that is used by Danial, to show that a lifted Markov chain can simulate a quantum walk for an arbitrary initial state, as opposed to a fixed one, and mix as fast for arbitrary/unbounded time intervals. This in turn leads to a new conductance-type bound for quantum walks, and in fact any local stochastic process.
- Also, we provide an efficient construction of the stochastic bridges using a hidden variables result by Aaronson, answering the question that Danial raises towards the end of his paper.
Let us keep in touch about this common topic :-)
[1]: https://arxiv.org/abs/1705.08253
[2]: https://arxiv.org/abs/1712.01609
[3]: https://arxiv.org/abs/1705.08253
Thanks for the comment, Simone. A couple of observations:
- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from (arXiv:1705.08253): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov chain in a number of steps equal to the diameter.
- In the more recent arxiv paper (arXiv:1712.01609) that you mention (remarkable that it came out a day before without coordination!), we strengthen theorem 2 of (arXiv:1705.08253), the same that is used by Danial, to show that a lifted Markov chain can simulate a quantum walk for an arbitrary initial state, as opposed to a fixed one, and mix as fast for arbitrary/unbounded time intervals. This in turn leads to a new conductance-type bound for quantum walks, and in fact any local stochastic process.
- Also, we provide an efficient construction of the stochastic bridges using a hidden variables result by Aaronson, answering the question that Danial raises towards the end of his paper.
Let us keep in touch about this common topic :-)