3 citations · 7 across the 12 of their papers we have counts for
5 papers · 1 filter
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal +1
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where the depth corresponds to the number of adapti…
One Clean Qubit Suffices for Quantum Communication Advantage
Srinivasan Arunachalam, Uma Girish, Noam Lifshitz
We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has…
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
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…
Trade-offs between Entanglement and Communication
Srinivasan Arunachalam, Uma Girish
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we…