4 papers · 1 filter
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…
Promises should be taken seriously: On relativization with promise problems
David Miloschewsky, Supartha Podder, Dorian Rudolph
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of…
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 …
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…