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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Quantum walks on configuration matroids revisited, with a corrected speedup and a rigorous classical comparison

Lucas Damián Alaniz Pintos
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

Quantum walks on configuration matroids revisited, with a corrected speedup and a rigorous classical comparison

Lucas Damián Alaniz Pintos
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Ingenieria Y Economia Del Transporte (ES)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.