Can I read Quantum Logspace Computations are Verifiable on EtoBox?

Quantum Logspace Computations are Verifiable by Girish, Uma; Raz, Ran; Zhan, Wei is a scholarly article available to read on EtoBox.

What is Quantum Logspace Computations are Verifiable about?

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 the verifier. The verifier has a read-once one-way access to that proof and is able to verify that the computation was performed correctly. That is, if the input is in the language and the prover is honest, the verifier accepts with high probability, and, if the input is not in the language, the verifier rejects with high probability even if the prover is adversarial. Moreover, the verifier uses only $O(\log n)$ random bits.

Author

Girish, Uma; Raz, Ran; Zhan, Wei

Published

2023

Language

EN