Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements

Niels Kornerup, Jonathan Sadun, David Soloveichik

Pebble games are popular models for analyzing time-space trade-offs. In particular, the reversible pebble game is often applied in quantum algorithms like Grover's search to effici…