Quantum Logspace Computations are Verifiable

Uma Girish, Ran Raz, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2024 Symposium on Simplicity in Algorithms, SOSA 2024
EditorsMerav Parter, Seth Pettie
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages7
ISBN (Electronic)9781713887171
StatePublished - 2024
Event7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 - Alexandria, United States
Duration: Jan 8 2024Jan 10 2024

Publication series

Name2024 Symposium on Simplicity in Algorithms, SOSA 2024


Conference7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)


Dive into the research topics of 'Quantum Logspace Computations are Verifiable'. Together they form a unique fingerprint.

Cite this