Showing 2026 · quant-phShow all
3 papers · 2 filters
quant-ph2026
Hardness of Pathfinding in a Welded Tree
David Miloschewsky, Supartha Podder
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open quest…
quant-ph2026
En Route to a Standard QMA1 vs. QCMA Oracle Separation
David Miloschewsky, Supartha Podder, Dorian Rudolph
We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in but not in …
quant-ph2026
A Framework for Ruling Out Quantum Speedups
Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky +1
We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two comple…