
Quadratic speedup for finding marked vertices by quantum walks
A quantum walk algorithm can detect the presence of a marked vertex on a...
read it

Quantum Walk Sampling by Growing Seed Sets
This work describes a new algorithm for creating a superposition over th...
read it

QSW_MPI: a framework for parallel simulation of quantum stochastic walks
QSW_MPI is a python package developed for the modeling of quantum stocha...
read it

Modeling Spontaneous Exit Choices in Intercity Expressway Traffic with Quantum Walk
In intercity expressway traffic, a driver frequently makes decisions to ...
read it

The Elephant Quantum Walk
We explore the impact of longrange memory on the properties of a family...
read it

Dynamic social learning under graph constraints
We argue that graphconstrained dynamic choice with reinforcement can be...
read it

How fast do quantum walks mix?
The fundamental problem of sampling from the limiting distribution of qu...
read it
Szegedy Walk Unitaries for Quantum Maps
Szegedy developed a generic method for quantizing classical algorithms based on random walks [Proceedings of FOCS, 2004, pp. 3241]. A major contribution of his work was the construction of a walk unitary for any reversible random walk. Such unitary posses two crucial properties: its eigenvector with eigenphase 0 is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of the random walk. It was an open question if it is possible to generalize Szegedy's quantization method for stochastic maps to quantum maps. We answer this in the affirmative by presenting an explicit construction of a Szegedy walk unitary for detailed balanced Lindbladians – generators of quantum Markov semigroups – and detailed balanced quantum channels. We prove that our Szegedy walk unitary has a purification of the fixed point of the Lindbladian as eigenvector with eigenphase 0 and that its eigenphase gap is quadratically larger than the spectral gap of the Lindbladian. To construct the walk unitary we leverage a canonical form for detailed balanced Lindbladians showing that they are structurally related to Davies generators. We also explain how the quantization method for Lindbladians can be applied to quantum channels. We give an efficient quantum algorithm for quantizing Davies generators that describe many important opensystem dynamics, for instance, the relaxation of a quantum system coupled to a bath. Our algorithm extends known techniques for simulating quantum systems on a quantum computer.
READ FULL TEXT
Comments
There are no comments yet.