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

Understand

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 efficiently simulate classical computation on inputs in superposition.
• However, the reversible pebble game cannot harness the additional computational power granted by irreversible intermediate measurements.
• The spooky pebble game, which models interleaved measurements and adaptive phase corrections, reduces the number of qubits beyond what reversible approaches can achieve.