6 papers
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…
Modifications of Quantum Computation and Adaptive Queries to PP
David Miloschewsky, Supartha Podder
In 2004, Aaronson introduced the complexity class ( with postselection) and showed that it is equal to . Following their line of work,…
New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
David Miloschewsky, Supartha Podder
Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsi…