Quantum walks on configuration matroids revisited, with a corrected speedup and a rigorous classical comparison
This is version 2 of this record. It corrects and supersedes the version 1 manuscript "Quantum Walks on Configuration Matroids: A Rigorous Framework for Electrical Network Reconfiguration with Provable Speedup" (December 2025), and includes the full replication package. The paper restates the framework on the down-up chain of the cographic dual, where the Anari, Liu, Oveis Gharan and Vinzant bound gives spectral gap at least 1/k, with k the number of independent loops, in place of 1/n with n the number of buses. The corrected cost is T_Q = O(sqrt(k|T|/|M|)) against T_C = O(k|T|/|M|), and the version 1 claim that the speedup grows as sqrt(n) with network size is withdrawn. The gap is moreover exactly 1/k on every real feeder, since any degree-two bus forces equality, as proved in the companion note "Exact spectral gap of the down-up walk on matroids with parallel elements" (doi 10.5281/zenodo.21745073). The empirical sections are regenerated on the true configuration spaces (50751 and 407924 configurations for the IEEE 33-bus and 69-bus feeders, in place of the version 1 counts) with the observable the theorem actually bounds, and the framework is benchmarked against classical competitors the original does not consider. On the published feeders, branch exchange reaches the exact global optimum from every start using two AC power-flow solves in total. On a panel of 22 operational marked sets covering post-fault restoration, N-1 security and loss minimisation, with the classical side given the cheap proxies those criteria admit and both sides charged symmetrically, QWCM is cheaper in AC power-flow solves in 0 of 44 comparisons. The surviving contribution is a query-complexity separation against the chain's own random walk, with an executable gate-level oracle construction. An appendix records fourteen errata against version 1. The deposit contains the paper (PDF) and the complete replication package (ZIP): code, seeds and recorded outputs reproducing all 53 numerical values printed in the paper, with a standalone verification log, an automated test suite, and a README mapping every claim to the script that produces it.
Authors
- Lucas Damián Alaniz Pintos (ORCID: https://orcid.org/0009-0008-5179-2534)
Institutions
- Ingenieria Y Economia Del Transporte (ES)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-08-03
- DOI
- https://doi.org/10.5281/zenodo.21770708
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint