{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:51:42Z","timestamp":1778215902594,"version":"3.51.4"},"reference-count":45,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T00:00:00Z","timestamp":1739836800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 &#x03F5;<\/mml:mi>&#x2208;<\/mml:mo>(<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>]<\/mml:mo><\/mml:math>, any classical computation requiring time T<\/mml:mi><\/mml:math> and space S<\/mml:mi><\/mml:math> can be implemented on a quantum computer using only O<\/mml:mi>(<\/mml:mo>T<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> gates and O<\/mml:mi>(<\/mml:mo>T<\/mml:mi>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:msup>S<\/mml:mi>1<\/mml:mn>&#x2212;<\/mml:mo>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math> qubits. This improves on the best known bound for the reversible pebble game with that number of qubits, which uses O<\/mml:mi>(<\/mml:mo>2<\/mml:mn>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:msup>T<\/mml:mi>)<\/mml:mo><\/mml:math> gates. For smaller space bounds, we show that the spooky pebble game can simulate arbitrary computation with O<\/mml:mi>(<\/mml:mo>T<\/mml:mi>1<\/mml:mn>+<\/mml:mo>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:msup>S<\/mml:mi>&#x2212;<\/mml:mo>&#x03F5;<\/mml:mi><\/mml:mrow><\/mml:msup>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> gates and O<\/mml:mi>(<\/mml:mo>S<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> qubits whereas any simulation via the reversible pebble game requires &#x03A9;<\/mml:mi>(<\/mml:mo>S<\/mml:mi>&#x22C5;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>+<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>T<\/mml:mi>\/<\/mml:mo><\/mml:mrow>S<\/mml:mi>)<\/mml:mo>)<\/mml:mo>)<\/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.<\/jats:p>","DOI":"10.22331\/q-2025-02-18-1636","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T16:41:00Z","timestamp":1739896860000},"page":"1636","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements"],"prefix":"10.22331","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1519-726X","authenticated-orcid":false,"given":"Niels","family":"Kornerup","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at Austin, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Sadun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2585-4120","authenticated-orcid":false,"given":"David","family":"Soloveichik","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, The University of Texas at Austin, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Ravi Sethi. ``Complete register allocation problems''. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing (STOC 1973). Page 182\u2013195. Association for Computing Machinery (1973).","DOI":"10.1145\/800125.804049"},{"key":"1","doi-asserted-by":"publisher","unstructured":"John Hopcroft, Wolfgang Paul, and Leslie Valiant. ``On time versus space''. J. ACM 24, 332\u2013337 (1977).","DOI":"10.1145\/322003.322015"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Martin Tompa. ``Time-space tradeoffs for computing functions, using connectivity properties of their circuits''. Journal of Computer and System Sciences 20, 118\u2013132 (1980).","DOI":"10.1016\/0022-0000(80)90056-2"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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\u2013160. Association for Computing Machinery (1976).","DOI":"10.1145\/800113.803643"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Thomas Lengauer and Robert E. Tarjan. ``Asymptotically tight bounds on time-space trade-offs in a pebble game''. J. ACM 29, 1087\u20131130 (1982).","DOI":"10.1145\/322344.322354"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Cynthia Dwork, Moni Naor, and Hoeteck Wee. ``Pebbling and proofs of work''. In Proceedings of the Advances in Cryptology (CRYPTO 2005). Pages 37\u201354. Springer Berlin Heidelberg (2005).","DOI":"10.1007\/11535218_3"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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\u2013285. Springer-Verlag (2016).","DOI":"10.1007\/978-3-662-53641-4_11"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013465. Springer International Publishing (2017).","DOI":"10.1007\/978-3-319-70500-2_15"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett. ``Time\/space trade-offs for reversible computation''. SIAM Journal on Computing 18, 766\u2013776 (1989).","DOI":"10.1137\/0218053"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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\u201379. Springer-Verlag (2022).","DOI":"10.1007\/978-3-031-22318-1_3"},{"key":"10","unstructured":"Craig Gidney. ``Spooky pebble games and irreversible uncomputation''. algassert.com\/post\/1905 (2019)."},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u2013219. (1996).","DOI":"10.1145\/237814.237866"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Mark Oskin, Frederic T. Chong, and Isaac L. Chuang. ``A practical architecture for reliable quantum computers''. Computer 35, 79\u201387 (2002).","DOI":"10.1109\/2.976922"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Robert Y. Levine and Alan T. Sherman. ``A note on Bennett\u2019s time-space tradeoff for reversible computation''. SIAM Journal on Computing 19, 673\u2013677 (1990).","DOI":"10.1137\/0219046"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Richard Kr\u00e1l'ovi\u010d. ``Time and space complexity of reversible pebbling''. In Proceedings of the Theory and Practice of Informatics (SOFSEM 2001). Pages 292\u2013303. Springer Berlin Heidelberg (2001).","DOI":"10.1007\/3-540-45627-9_26"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Simon Perdrix and Philippe Jorrand. ``Classically controlled quantum computation''. Mathematical Structures in Computer Science 16, 601 (2006).","DOI":"10.1017\/s096012950600538x"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u2013354. Springer Berlin Heidelberg (2002).","DOI":"10.1007\/3-540-45465-9_30"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u201392. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013).","DOI":"10.4230\/LIPICS.TQC.2013.80"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Arend-Jan Quist and Alfons Laarman. ``Optimizing quantum space using spooky pebble games''. In Reversible Computation (RC 2023). Pages 134\u2013149. Springer Nature Switzerland (2023).","DOI":"10.1007\/978-3-031-38100-3_10"},{"key":"19","doi-asserted-by":"crossref","unstructured":"Arend-Jan Quist and Alfons Laarman. ``Trade-offs between classical and quantum space using spooky pebbling'' (2024). arXiv:2401.10579.","DOI":"10.1007\/978-3-031-38100-3_10"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Ming Li and Paul Vitanyi. ``Reversibility and adiabatic computation: Trading time and space for energy''. Proceedings of the Royal Society A 452, 769\u2013789 (1996).","DOI":"10.1098\/rspa.1996.0039"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ming Li, John Tromp, and Paul Vit\u00e1nyi. ``Reversible simulation of irreversible computation''. Physica D: Nonlinear Phenomena 120, 168\u2013176 (1998).","DOI":"10.1016\/s0167-2789(98)00052-9"},{"key":"22","unstructured":"Eleanor Rieffel and Wolfgang Polak. ``Quantum computing: A gentle introduction''. The MIT Press. (2011). 1st edition."},{"key":"23","doi-asserted-by":"publisher","unstructured":"R. Landauer. ``Irreversibility and heat generation in the computing process''. IBM Journal of Research and Development 5, 183\u2013191 (1961).","DOI":"10.1147\/rd.53.0183"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett. ``Logical reversibility of computation''. IBM Journal of Research and Development 17, 525\u2013532 (1973).","DOI":"10.1147\/rd.176.0525"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Klaus-J\u00f6rn Lange, Pierre McKenzie, and Alain Tapp. ``Reversible space equals deterministic space''. Journal of Computer and System Sciences 60, 354\u2013367 (2000).","DOI":"10.1006\/jcss.1999.1672"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Mehdi Saeedi and Igor L. Markov. ``Synthesis and optimization of reversible circuits\u2014a survey''. ACM Computing Surveys 45, 1\u201334 (2013).","DOI":"10.1145\/2431211.2431220"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u201323:34. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2017).","DOI":"10.4230\/LIPIcs.ITCS.2017.23"},{"key":"28","unstructured":"Michael P. Frank and M. Josephine Ammer. ``Relativized separation of reversible and irreversible space-time complexity classes'' (2017). arXiv:1708.08480."},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u2013236. PLDI 2021. Association for Computing Machinery (2021). code: eth-sri\/Unqomp.","DOI":"10.1145\/3453483.3454040"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Raymond Wheeler and Richard Hughey. ``Optimizing reduced-space sequence analysis''. Bioinformatics 16, 1082\u20131090 (2000).","DOI":"10.1093\/bioinformatics\/16.12.1082"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Lee A. Newberg. ``Memory-efficient dynamic programming backtrace and pairwise local sequence alignment''. Bioinformatics 24, 1772\u20131778 (2008).","DOI":"10.1093\/bioinformatics\/btn308"},{"key":"32","unstructured":"Philippe Dumas. ``Reversing a finite sequence''. \"https:\/\/algo.inria.fr\/seminars\/sem94-95\/pottier.pdf\" (1995). Summary of a seminar talk given by Lo\u00efc Pottier."},{"key":"33","unstructured":"Jos\u00e9 Grimm, Lo\u00efc 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."},{"key":"34","doi-asserted-by":"publisher","unstructured":"W. J. Paul and R. E. Tarjan. ``Time-space trade-offs in a pebble game''. Acta Informatica 10, 111\u2013115 (1978).","DOI":"10.1007\/BF00289150"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Nicholas Pippenger. ``A time-space trade-off''. J. ACM 25, 509\u2013515 (1978).","DOI":"10.1145\/322077.322091"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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\u2013277. Association for Computing Machinery (1979).","DOI":"10.1145\/800135.804420"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Jo\u00ebl 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\u2013603. ACM (2015).","DOI":"10.1145\/2746539.2746622"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Jo\u00ebl 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\u201332. Springer (2017).","DOI":"10.1007\/978-3-319-56617-7_1"},{"key":"39","doi-asserted-by":"publisher","unstructured":"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\u2013324. Springer (2017).","DOI":"10.1007\/978-3-319-62127-2_27"},{"key":"40","doi-asserted-by":"crossref","unstructured":"Erik D. Demaine and Quanquan C. Liu. ``Inapproximability of the standard pebble game and hard to pebble graphs'' (2017). arXiv:1707.06343.","DOI":"10.1007\/978-3-319-62127-2_27"},{"key":"41","unstructured":"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)."},{"key":"42","doi-asserted-by":"publisher","unstructured":"Ralph C. Merkle. ``A digital signature based on a conventional encryption function''. In Proceedings of Advances in Cryptology (CRYPTO 1987). Pages 369\u2013378. Springer Berlin Heidelberg (1988).","DOI":"10.1007\/3-540-48184-2_32"},{"key":"43","doi-asserted-by":"publisher","unstructured":"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\u201333. Association for Computing Machinery (1973).","DOI":"10.1145\/800125.804032"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Balagopal Komarath, Jayalal Sarma, and Saurabh Sawlani. ``Reversible pebble game on trees''. In Proceedings of Computing and Combinatorics (COCOON 2015). Pages 83\u201394. Springer International Publishing (2015).","DOI":"10.1007\/978-3-319-21398-9_7"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-18-1636\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T16:41:15Z","timestamp":1739896875000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-18-1636\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,18]]},"references-count":45,"URL":"https:\/\/doi.org\/10.22331\/q-2025-02-18-1636","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,18]]},"article-number":"1636"}}