Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

Elfs, transducers and quantum walks

  • Simon Apers
  • Jérémie Roland
  • Yuxin Zhang
Open at sourcePDFDOICite

Abstract

Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool by showing that there exists a zero-error transducer for implementing elfs. More broadly, we establish a zero-error transducer for reflecting about the intersection of two subspaces, yielding an errorfree transducer version of the effective gap lemma. Building on this result, we obtain improved quantum walk algorithms for estimating effective resistances and span program witness sizes with an optimal error scaling, and for sampling from the random walk arrival distribution, via the composition of many elfs. Using this last algorithm, we obtain an up-to-quadratic quantum speedup for semi-supervised learning on expander graphs.

Related

  1. Improved quantum volume estimation with transducers and amortized quantum walks
    Arjan Cornelissen, Simon Apers, Sander Gribling
    HALPreprintCC BY 4.0Full textQuantum physics & quantum informationHALarXiv
  2. Spectral Criterion for Disorder-Free Localization of Quantum Walks on Hypercube: QBN Approach
    Ce Wang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsMathematical physicsarXiv
  3. Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
    Ce Wang
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs
    Mostafa Atallah, Daniel Dilley, Jishnu Mahmud +2
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Exact diffusion coefficients for quantum--classical hybrid walks
    Cook Hyun Kim, Jaesub Park, Namshik Han
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationStatistical & nonlinear physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{apers2026elfs,
  title = {{Elfs, transducers and quantum walks}},
  author = {Simon Apers and Jérémie Roland and Yuxin Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2605.30013},
  eprint = {2605.30013},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.30013},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Elfs, transducers and quantum walks
AU  - Simon Apers
AU  - Jérémie Roland
AU  - Yuxin Zhang
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2605.30013
UR  - https://arxiv.org/abs/2605.30013
AB  - Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool by showing that there exists a zero-error transducer for implementing elfs. More broadly, we establish a zero-error transducer for reflecting about the intersection of two subspaces, yielding an errorfree transducer version of the effective gap lemma. Building on this result, we obtain improved quantum walk algorithms for estimating effective resistances and span program witness sizes with an optimal error scaling, and for sampling from the random walk arrival distribution, via the composition of many elfs. Using this last algorithm, we obtain an up-to-quadratic quantum speedup for semi-supervised learning on expander graphs.
ER  -