5 papers · 1 filter
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…
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…
Are uncloneable proof and advice states strictly necessary?
Rohit Chatterjee, Srijita Kundu, Supartha Podder
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes Q…
The Role of piracy in quantum proofs
Anne Broadbent, Alex B. Grilo, Supartha Podder +1
A well-known feature of quantum information is that it cannot, in general, be cloned. Recently, a number of quantum-enabled information-processing tasks have demonstrated various f…