All reports by Author Ran Raz:

__
TR23-107
| 20th July 2023
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Computations are Verifiable

__
TR21-101
| 13th July 2021
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

__
TR21-087
| 22nd June 2021
__

Uma Girish, Ran Raz#### Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

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

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

Uma Girish, Ran Raz

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>