Eliminating Intermediate Measurements using Pseudorandom Generators
summary
Proves that any quantum circuit with intermediate measurements, time T and space S, simulates to a measurement-free circuit in time T poly S and space S log T, so deferral is both time- and space-efficient. Replaces T fresh random bits by a seed of length S log T using a variant of the INW generator, and handles quantum side information via a quantum extractor of Fehr and Shafner. Gives explicit reductions, seed-length bounds, and the T-to-seed conversion used to defer measurements.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:22Our Results
- 1:31Quantum Algorithms of Space S and Time T
- 6:35Principle of Deferred Measurements
- 8:12Space-efficient Elimination of Intermediate Measurements [FR21, GRZ21]
- 12:22Eliminating Intermediate Measurements is equivalent to Derandomization
- 13:30Pseudorandom Generator (PRG)
- 19:06PRGS = Eliminate Intermediate Measurements
- 20:50Proof of Main Lemma
- 27:07Summary
related talks
22mQuantum Controlled Measurements via Program Transformation
20mQuantum Assertion Testing Without Mid-Circuit Measurement: Strategies and Lower Bounds
48mQuantum Linear Algebra Using Subspace States
59mUtility, Computational Cost, and Effective Quantum Volume of NISQ Experiments
51mOn constant T-depth circuits
22mClassical Simulation of Quantum Circuits with Partial Interference Effects
01h 09mAre Random Quantum Circuits PRUs?
44mQuantum Meets Minimum Circuit Size Problem