All reports by Author Ran Raz:

__
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

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