An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable ... more >>>

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 an information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to ... more >>>