Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INTERMEDIATE MEASUREMENTS:
Reports tagged with intermediate measurements:
TR21-087 | 22nd June 2021
Uma Girish, Ran Raz

Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

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


TR24-167 | 31st October 2024
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang

Space-bounded quantum interactive proof systems

Revisions: 1

We introduce two models of space-bounded quantum interactive proof systems, \mathbf{QIPL} and \mathbf{QIP_\mathrm{U}L}. The \mathbf{QIP_\mathrm{U}L} model, a space-bounded variant of quantum interactive proofs (\mathbf{QIP}) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, \mathbf{QIPL} allows logarithmically many intermediate measurements per ... more >>>




ISSN 1433-8092 | Imprint