REVIEW 2 cited by
Quantum Walks On Graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
Forward citations
Cited by 2 Pith papers
-
Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity
Reducing a graph walk to distance-layers reproduces Krylov/spread complexity, yielding analytic finite-q SYK Lanczos coefficients and hypercube complexity D sin²(t/D), with faster saturation than classical-walk circuits.
-
Response to glassy disorder in coin on spread of quantum walker
Glassy disorder in the coin of a 1D discrete-time quantum walk inhibits ballistic spread while keeping it faster than classical diffusion, with slow or fast falloff and mid-strength inflection points depending on the ...
Discussion (0). Sign in to comment.