3 papers
quant-ph2023
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…
cs.CC2023
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…
quant-ph2023
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…