Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
1Department of Computer Science, The University of Texas at Austin, United States of America
2Department of Electrical and Computer Engineering, The University of Texas at Austin, United States of America
| Published: | 2025-02-18, volume 9, page 1636 |
| Editor: | Tom Gur |
| Eprint: | arXiv:2110.08973v3 |
| Doi: | https://doi.org/10.22331/q-2025-02-18-1636 |
| Citation: | Quantum 9, 1636 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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 $\epsilon \in (0,1]$, any classical computation requiring time $T$ and space $S$ can be implemented on a quantum computer using only $O(T/ \epsilon)$ gates and $O(T^{\epsilon}S^{1-\epsilon})$ qubits. This improves on the best known bound for the reversible pebble game with that number of qubits, which uses $O(2^{1/\epsilon} T)$ gates. For smaller space bounds, we show that the spooky pebble game can simulate arbitrary computation with $O(T^{1+\epsilon} S^{-\epsilon}/\epsilon)$ gates and $O(S / \epsilon)$ qubits whereas any simulation via the reversible pebble game requires $\Omega(S \cdot (1+\log(T/S)))$ 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.
Featured image: An example circuit using the spooky pebble game to implement intermediate measurements that reduce the number of qubits needed to perform a classical subroutine on inputs in superposition. The green gates indicate computational steps, the red steps indicate ghosting operations, and the yellow gates represent ghost removal. Bent wires indicate qubits that are $|0\rangle$ in the computational basis and thus can be reused as if they were fresh ancilla. Any logically reversible implementation of the same computation would require one additional wire worth of qubits.
Popular summary
► BibTeX data
► References
[1] Ravi Sethi. ``Complete register allocation problems''. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing (STOC 1973). Page 182–195. Association for Computing Machinery (1973).
https://doi.org/10.1145/800125.804049
[2] John Hopcroft, Wolfgang Paul, and Leslie Valiant. ``On time versus space''. J. ACM 24, 332–337 (1977).
https://doi.org/10.1145/322003.322015
[3] Martin Tompa. ``Time-space tradeoffs for computing functions, using connectivity properties of their circuits''. Journal of Computer and System Sciences 20, 118–132 (1980).
https://doi.org/10.1016/0022-0000(80)90056-2
[4] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. ``Space bounds for a game on graphs''. In Proceedings of the Eighth Annual ACM Symposium on Theory of Computing (STOC 1976). Page 149–160. Association for Computing Machinery (1976).
https://doi.org/10.1145/800113.803643
[5] Thomas Lengauer and Robert E. Tarjan. ``Asymptotically tight bounds on time-space trade-offs in a pebble game''. J. ACM 29, 1087–1130 (1982).
https://doi.org/10.1145/322344.322354
[6] Cynthia Dwork, Moni Naor, and Hoeteck Wee. ``Pebbling and proofs of work''. In Proceedings of the Advances in Cryptology (CRYPTO 2005). Pages 37–54. Springer Berlin Heidelberg (2005).
https://doi.org/10.1007/11535218_3
[7] Ling Ren and Srinivas Devadas. ``Proof of space from stacked expanders''. In Proceedings of the 14th International Conference on Theory of Cryptography (TCC 2016). Volume 9985, page 262–285. Springer-Verlag (2016).
https://doi.org/10.1007/978-3-662-53641-4_11
[8] Jeremiah Blocki and Samson Zhou. ``On the depth-robustness and cumulative pebbling cost of argon2i''. In Proceedings of the Theory of Cryptography (TCC 2017). Pages 445–465. Springer International Publishing (2017).
https://doi.org/10.1007/978-3-319-70500-2_15
[9] Charles H. Bennett. ``Time/space trade-offs for reversible computation''. SIAM Journal on Computing 18, 766–776 (1989).
https://doi.org/10.1137/0218053
[10] Jeremiah Blocki, Blake Holman, and Seunghoon Lee. ``The parallel reversible pebbling game: Analyzing the post-quantum security of imhfs''. In Proceedings of the Theory of Cryptography: 20th International Conference (TCC 2022). Page 52–79. Springer-Verlag (2022).
https://doi.org/10.1007/978-3-031-22318-1_3
[11] Craig Gidney. ``Spooky pebble games and irreversible uncomputation''. algassert.com/post/1905 (2019).
http://algassert.com/post/1905
[12] Lov K. Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM Symposium on Theory of Computing (STOC 1996). Pages 212–219. (1996).
https://doi.org/10.1145/237814.237866
[13] Mark Oskin, Frederic T. Chong, and Isaac L. Chuang. ``A practical architecture for reliable quantum computers''. Computer 35, 79–87 (2002).
https://doi.org/10.1109/2.976922
[14] Robert Y. Levine and Alan T. Sherman. ``A note on Bennett’s time-space tradeoff for reversible computation''. SIAM Journal on Computing 19, 673–677 (1990).
https://doi.org/10.1137/0219046
[15] Richard Král'ovič. ``Time and space complexity of reversible pebbling''. In Proceedings of the Theory and Practice of Informatics (SOFSEM 2001). Pages 292–303. Springer Berlin Heidelberg (2001).
https://doi.org/10.1007/3-540-45627-9_26
[16] Simon Perdrix and Philippe Jorrand. ``Classically controlled quantum computation''. Mathematical Structures in Computer Science 16, 601 (2006).
https://doi.org/10.1017/s096012950600538x
[17] Farid Ablayev, Cristopher Moore, and Christopher Pollett. ``Quantum and stochastic branching programs of bounded width''. In Proceedings of Automata, Languages and Programming (ICALP 2002). Pages 343–354. Springer Berlin Heidelberg (2002).
https://doi.org/10.1007/3-540-45465-9_30
[18] Alessandro Cosentino, Robin Kothari, and Adam Paetznick. ``Dequantizing read-once quantum formulas''. In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Volume 22 of LIPIcs, pages 80–92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013).
https://doi.org/10.4230/LIPICS.TQC.2013.80
[19] Arend-Jan Quist and Alfons Laarman. ``Optimizing quantum space using spooky pebble games''. In Reversible Computation (RC 2023). Pages 134–149. Springer Nature Switzerland (2023).
https://doi.org/10.1007/978-3-031-38100-3_10
[20] Arend-Jan Quist and Alfons Laarman. ``Trade-offs between classical and quantum space using spooky pebbling'' (2024). arXiv:2401.10579.
arXiv:2401.10579
[21] Ming Li and Paul Vitanyi. ``Reversibility and adiabatic computation: Trading time and space for energy''. Proceedings of the Royal Society A 452, 769–789 (1996).
https://doi.org/10.1098/rspa.1996.0039
[22] Ming Li, John Tromp, and Paul Vitányi. ``Reversible simulation of irreversible computation''. Physica D: Nonlinear Phenomena 120, 168–176 (1998).
https://doi.org/10.1016/s0167-2789(98)00052-9
[23] Eleanor Rieffel and Wolfgang Polak. ``Quantum computing: A gentle introduction''. The MIT Press. (2011). 1st edition.
[24] R. Landauer. ``Irreversibility and heat generation in the computing process''. IBM Journal of Research and Development 5, 183–191 (1961).
https://doi.org/10.1147/rd.53.0183
[25] Charles H. Bennett. ``Logical reversibility of computation''. IBM Journal of Research and Development 17, 525–532 (1973).
https://doi.org/10.1147/rd.176.0525
[26] Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. ``Reversible space equals deterministic space''. Journal of Computer and System Sciences 60, 354–367 (2000).
https://doi.org/10.1006/jcss.1999.1672
[27] Mehdi Saeedi and Igor L. Markov. ``Synthesis and optimization of reversible circuits—a survey''. ACM Computing Surveys 45, 1–34 (2013).
https://doi.org/10.1145/2431211.2431220
[28] Scott Aaronson, Daniel Grier, and Luke Schaeffer. ``The Classification of Reversible Bit Operations''. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017).
https://doi.org/10.4230/LIPIcs.ITCS.2017.23
[29] Michael P. Frank and M. Josephine Ammer. ``Relativized separation of reversible and irreversible space-time complexity classes'' (2017). arXiv:1708.08480.
arXiv:1708.08480
[30] Anouk Paradis, Benjamin Bichsel, Samuel Steffen, and Martin Vechev. ``Unqomp: Synthesizing uncomputation in quantum circuits''. In Proceedings of the 42nd International Conference on Programming Language Design and Implementation (SIGPLAN 2021). Page 222–236. PLDI 2021. Association for Computing Machinery (2021). code: eth-sri/Unqomp.
https://doi.org/10.1145/3453483.3454040
[31] Raymond Wheeler and Richard Hughey. ``Optimizing reduced-space sequence analysis''. Bioinformatics 16, 1082–1090 (2000).
https://doi.org/10.1093/bioinformatics/16.12.1082
[32] Lee A. Newberg. ``Memory-efficient dynamic programming backtrace and pairwise local sequence alignment''. Bioinformatics 24, 1772–1778 (2008).
https://doi.org/10.1093/bioinformatics/btn308
[33] Philippe Dumas. ``Reversing a finite sequence''. "https://algo.inria.fr/seminars/sem94-95/pottier.pdf" (1995). Summary of a seminar talk given by Loïc Pottier.
https://algo.inria.fr/seminars/sem94-95/pottier.pdf
[34] José Grimm, Loïc Pottier, and Nicole Rostaing-Schmidt. ``Optimal Time and Minimum Space-Time Product for Reversing a Certain Class of Programs''. Technical Report RR-2794. INRIA (1996). url: https://inria.hal.science/inria-00073896.
https://inria.hal.science/inria-00073896
[35] W. J. Paul and R. E. Tarjan. ``Time-space trade-offs in a pebble game''. Acta Informatica 10, 111–115 (1978).
https://doi.org/10.1007/BF00289150
[36] Nicholas Pippenger. ``A time-space trade-off''. J. ACM 25, 509–515 (1978).
https://doi.org/10.1145/322077.322091
[37] Thomas Lengauer and Robert Endre Tarjan. ``Upper and lower bounds on time-space tradeoffs''. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing (STOC 1979). Page 262–277. Association for Computing Machinery (1979).
https://doi.org/10.1145/800135.804420
[38] Joël Alwen and Vladimir Serbinenko. ``High parallel complexity graphs and memory-hard functions''. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015). Page 595–603. ACM (2015).
https://doi.org/10.1145/2746539.2746622
[39] Joël Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. ``Depth-robust graphs and their cumulative memory complexity''. In Proceedings of the Advances in Cryptology (EUROCRYPT 2017). Pages 3–32. Springer (2017).
https://doi.org/10.1007/978-3-319-56617-7_1
[40] Erik D. Demaine and Quanquan C. Liu. ``Inapproximability of the standard pebble game and hard to pebble graphs''. In Proceedings of Algorithms and Data Structures (WADS 2017). Pages 313–324. Springer (2017).
https://doi.org/10.1007/978-3-319-62127-2_27
[41] Erik D. Demaine and Quanquan C. Liu. ``Inapproximability of the standard pebble game and hard to pebble graphs'' (2017). arXiv:1707.06343.
arXiv:1707.06343
[42] D.D.M. Cracken, D.D. McCracken, W.S. Dorn, and Ltd John Wiley & Sons. ``Numerical methods and fortran programming: With applications in engineering and science''. Goldstine Printed Materials. Wiley. (1964).
[43] Ralph C. Merkle. ``A digital signature based on a conventional encryption function''. In Proceedings of Advances in Cryptology (CRYPTO 1987). Pages 369–378. Springer Berlin Heidelberg (1988).
https://doi.org/10.1007/3-540-48184-2_32
[44] Stephen A. Cook. ``An observation on time-storage trade off''. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing (STOC 1973). Page 29–33. Association for Computing Machinery (1973).
https://doi.org/10.1145/800125.804032
[45] Balagopal Komarath, Jayalal Sarma, and Saurabh Sawlani. ``Reversible pebble game on trees''. In Proceedings of Computing and Combinatorics (COCOON 2015). Pages 83–94. Springer International Publishing (2015).
https://doi.org/10.1007/978-3-319-21398-9_7
Cited by
[1] Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher, Lecture Notes in Computer Science 16541, 371 (2026) ISBN:978-3-032-25290-6.
[2] Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, and Katherine Van Kirk, Lecture Notes in Computer Science 16541, 402 (2026) ISBN:978-3-032-25290-6.
[3] Alessandro Luongo, Antonio Michele Miti, Varun Narasimhachar, and Adithya Sireesh, 2025 62nd ACM/IEEE Design Automation Conference (DAC) 1 (2025) ISBN:979-8-3315-0304-8.
[4] Alessandro Luongo, Varun Narasimhachar, and Adithya Sireesh, 2025 62nd ACM/IEEE Design Automation Conference (DAC) 1 (2025) ISBN:979-8-3315-0304-8.
[5] Alessandro Luongo, Antonio Michele Miti, Varun Narasimhachar, and Adithya Sireesh, "Measurement-based uncomputation of quantum circuits for modular arithmetic", arXiv:2407.20167, (2024).
[6] Arend-Jan Quist and Alfons Laarman, "Trade-offs between classical and quantum space using spooky pebbling", arXiv:2401.10579, (2024).
[7] Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, and Katherine Van Kirk, "Parallel Spooky Pebbling Makes Regev Factoring More Practical", arXiv:2510.08432, (2025).
[8] Kengo Hirata and Chris Heunen, "Qurts: Automatic Quantum Uncomputation by Affine Types with Lifetime", arXiv:2411.10835, (2024).
[9] Han Luo, Ziyi Yang, Jingquan Luo, Ziruo Wang, Yuexin Su, Xiaoming Sun, Lvzhou Li, and Tongyang Li, "Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition", arXiv:2607.13816, (2026).
[10] Siyi Wang, Kyungbae Jang, Hyunji Kim, Anik Basu Bhaumik, Anubhab Baksi, Hwajeong Seo, and Anupam Chattopadhyay, "Quantum Arithmetic Circuits in Public-Key Cryptography", arXiv:2607.11713, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 06:03:50) and SAO/NASA ADS (last updated successfully 2026-08-09 15:56:37). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-08-10 06:03:50: Cannot retrieve data from ADS due to rate limitations.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.