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

Pebble games are popular models for analyzing time-space trade-offs. In particular, reversible pebble game strategies are frequently applied in quantum algorithms like Grover's search to efficiently simulate classical computation on inputs in superposition, as unitary operations are fundamentally reversible. However, the reversible pebble game cannot harness the additional computational power granted by intermediate measurements, which are irreversible. The spooky pebble game, which models interleaved Hadamard basis measurements and adaptive phase corrections, reduces the number of qubits beyond what purely reversible approaches can achieve. While the spooky pebble game does not reduce the total space (bits plus qubits) complexity of the simulation, it reduces the amount of space that must be stored in qubits. We prove asymptotically tight trade-offs for the spooky pebble game on a line with any pebble bound. This in turn gives a tight time-qubit tradeoff for simulating arbitrary classical sequential computation when using the spooky pebble game. For example, for all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&amp;#x03F5;</mml:mi><mml:mo>&amp;#x2208;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:math>, any classical computation requiring time <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> and space <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>S</mml:mi></mml:math> can be implemented on a quantum computer using only <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>T</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> gates and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>T</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:msup><mml:msup><mml:mi>S</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>&amp;#x2212;</mml:mo><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> qubits. This improves on the best known bound for the reversible pebble game with that number of qubits, which uses <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:msup><mml:mi>T</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> gates. For smaller space bounds, we show that the spooky pebble game can simulate arbitrary computation with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>T</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:msup><mml:msup><mml:mi>S</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mi>&amp;#x03F5;</mml:mi></mml:mrow></mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> gates and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>S</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> qubits whereas any simulation via the reversible pebble game requires <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>S</mml:mi><mml:mo>&amp;#x22C5;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>T</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>S</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math> qubits.We also consider the spooky pebble game on more general directed acyclic graphs (DAGs), capturing fine-grained data dependency in computation. We show that for an arbitrary DAG even approximating the number of required pebbles in the spooky pebble game is PSPACE-hard. Despite this, we are able to construct a time-efficient strategy for pebbling binary trees that uses the minimum number of pebbles.