Exact Chebyshev QFF does not extend to the α-perturbed n-cycle for α ≠ 0 due to eigenvalues outside [-1,1], but a truncated-Chebyshev LCU approximation achieves degree O(|α|t + √(t log(t/η))) that recovers the reversible √t scaling only when |α| = O(t^{-1/2}).
Quantum Walk Sampling by Growing Seed Sets
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as $\widetilde{O}(m^{1/3} \delta^{-1/3})$, with $m$ the number of edges and $\delta$ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for $st$-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an $n$-node graph in time $\widetilde{O}(2^{n/3})$, surpassing the $\Omega(2^{n/2})$ barrier set by index erasure.
fields
quant-ph 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Quantum Fast-Forwarding Beyond Reversibility: The $\alpha$-Perturbed $n$-Cycle
Exact Chebyshev QFF does not extend to the α-perturbed n-cycle for α ≠ 0 due to eigenvalues outside [-1,1], but a truncated-Chebyshev LCU approximation achieves degree O(|α|t + √(t log(t/η))) that recovers the reversible √t scaling only when |α| = O(t^{-1/2}).