63 citations · 124 across the 20 of their papers we have counts for
8 papers · 1 filter
Distributional Variants of the Aaronson-Ambainis Conjecture
Uma Girish, Kunal Mittal, Barak Nehoran +1
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query…
Quantum Logspace Computations are Verifiable
Uma Girish, Ran Raz, Wei Zhan
In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has…
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu, Ran Raz, Wei Zhan
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on bits requires either bits of classical memory or an exponential number (…
Eliminating Intermediate Measurements using Pseudorandom Generators
Uma Girish, Ran Raz
We show that quantum algorithms of time and space with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T \cdot \m…
Quantum versus Randomized Communication Complexity, with Efficient Players
Uma Girish, Ran Raz, Avishay Tal
We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense tha…
Exponential separations for one-way quantum communication complexity, with applications to cryptography
Dmytro Gavinsky, Julia Kempe, Iordanis Kerenidis +2
We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean Hidden Matching Problem of…