TY - GEN

T1 - Quantum Logspace Computations are Verifiable

AU - Girish, Uma

AU - Raz, Ran

AU - Zhan, Wei

N1 - Publisher Copyright:
Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85194180774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85194180774&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85194180774

T3 - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

SP - 144

EP - 150

BT - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

A2 - Parter, Merav

A2 - Pettie, Seth

PB - Society for Industrial and Applied Mathematics Publications

T2 - 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024

Y2 - 8 January 2024 through 10 January 2024

ER -