Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.02121 · Design, Automation, and Test in Europe

Reversible Pebbling Game for Quantum Memory Management

Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bjørner, Giovanni De Micheli

Published Mar 1, 2019• 42 citations
arXivHTMLPDF

Abstract

Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. In this work, we propose an automatic tool for quantum memory management. We show how this problem exactly matches the reversible pebbling game. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed tool empowers the designer with the flexibility required to explore the trade-off between memory resources and number of operations. We present two show-cases to prove the validity of our approach. First, we apply the algorithm to straight-line programs, widely used in cryptographic applications. Second, we perform a comparison with the existing approach, showing an average improvement of 52.77%.

DOI
10.23919/date.2019.8715092

Related papers

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, 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 ϵ∈(0,1] , any classical computation requiring time T and space S can be implemented on a quantum computer using only O(T/ϵ) gates and O(TϵS1−ϵ) qubits. This improves on the best known bound for the reversible pebble game with that number of qubits, which uses O(21/ϵT) gates. For smaller space bounds, we show that the spooky pebble game can simulate arbitrary computation with O(T1+ϵS−ϵ/ϵ) gates and O(S/ϵ) qubits whereas any simulation via the reversible pebble game requires Ω(S⋅(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.

arXiv:2110.08973•Quantum•Feb 18, 2025•19 citations

The Spooky Pebble Game.

Niels Kornerup, Jonathan Sadun, David Soloveichik

Pebble games are commonly used to study space-time trade-offs in computation. We present a pebble game that explores this trade-off in quantum simulation of arbitrary classical circuits on non-classical inputs. Many quantum algorithms, such as Shor's algorithm and Grover's search, include subroutines that require simulation of classical functions on inputs in superposition. The current state of the art uses generic reversible simulation through Bennett's pebble game and universal reversible gate sets such as the Toffoli. Using measurement-based uncomputation, we replace many of the ancilla qubits used by existing constructions with classical control bits, which are cheaper. Our pebble game forms a natural framework for reasoning about measurement-based uncomputation, and we prove tight bounds on the time complexity of all algorithms that use our pebble game. For any $\epsilon \in (0,1)$, we present an algorithm that can simulate irreversible classical computation that uses $\mathcal{T}$ time and $\mathcal{S}$ space in $O(\frac{1}{\epsilon}\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})$ time with $O(\frac{1}{\epsilon}\mathcal{S})$ qubits. With access to more qubits we present algorithms that run in $O(\frac{1}{\epsilon}\mathcal{T})$ time with $O(\mathcal{S}^{1-\epsilon}\mathcal{T}^\epsilon)$ qubits. Both of these results show an improvement over Bennett's construction, which requires $O(\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})$ time when using $O(\epsilon2^{1/\epsilon} \mathcal{S} (1+\log \frac{\mathcal{T}}{\mathcal{S}}))$ qubits. Additionally the results in our paper combine with Barrington's theorem to provide a general method to efficiently compute any log-depth circuit on quantum inputs using a constant number of ancilla qubits. We also explore a connection between the optimal structure of our pebbling algorithms and backtracking from dynamic programming.

•Oct 18, 2021•0 citations

Reversible circuit compilation with space constraints

Alex Parent, Martin Roetteler, Krysta M. Svore

We develop a framework for resource efficient compilation of higher-level programs into lower-level reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. This is motivated by the limited availability of qubits for the foreseeable future. We apply three main techniques to keep the number of required qubits small when computing classical, irreversible computations by means of reversible networks: first, wherever possible we allow the compiler to make use of in-place functions to modify some of the variables. Second, an intermediate representation is introduced that allows to trace data dependencies within the program, allowing to clean up qubits early. This realizes an analog to "garbage collection" for reversible circuits. Third, we use the concept of so-called pebble games to transform irreversible programs into reversible programs under space constraints, allowing for data to be erased and recomputed if needed. We introduce REVS, a compiler for reversible circuits that can translate a subset of the functional programming language F# into Toffoli networks which can then be further interpreted for instance in LIQui|>, a domain-specific language for quantum computing and which is also embedded into F#. We discuss a number of test cases that illustrate the advantages of our approach including reversible implementations of SHA-2 and other cryptographic hash-functions, reversible integer arithmetic, as well as a test-bench of combinational circuits used in classical circuit synthesis. Compared to Bennett's method, REVS can reduce space complexity by a factor of $4$ or more, while having an only moderate increase in circuit size as well as in the time it takes to compile the reversible networks.

arXiv:1510.00377•Oct 1, 2015•47 citations

Memory Management Strategies for Software Quantum Simulators

Gilberto Javier Díaz, Luiz Angelo Steffenel, Carlos Barrios-Hernandez +1 more

Software quantum simulators are essential tools for designing and testing quantum algorithms on classical computing architectures, especially given the current limitations of physical quantum hardware. This work focuses on studying and evaluating memory management strategies for scalable quantum state simulation. We examine full-state representation, dynamic state pruning, shared-memory parallelization with OpenMP, distributed memory execution using MPI, and error-bounded floating-point compression with ZFP. These techniques are implemented in a prototype simulator and assessed using the quantum Fourier transform as a benchmark, with performance compared against leading open-source simulators such as Intel-QS, QuEST, and qsim. The results show the trade-offs between computational overhead and memory efficiency, and demonstrate that hybrid approaches combining distributed memory and compression can significantly extend the number of qubits that can be simulated. This work contributes practical insights for improving the scalability of software quantum simulators on classical hardware through optimized memory usage.

Quantum Reports•Sep 9, 2025•0 citations

A Divide-And-Conquer Pebbling Strategy for Oracle Synthesis in Quantum Computing

Kezhen Zhang, Riling Li, Mingsheng Ying

Quantum oracles are quantum circuits that implement classical Boolean functions, frequently used as independent black boxes in quantum algorithm design. The hierarchical reversible logic synthesis approach, a scalable method for large-scale oracle synthesis, relies on ancilla qubits to store intermediate results. The sequence in which these results are computed and uncomputed, governed by the reversible pebble game, greatly affects both qubit usage and circuit gate count. This paper introduces a novel divide-and-conquer pebbling strategy that reduces qubit count while maintaining a reasonable circuit gate count. Experimental results show up to a 90% reduction in qubits compared to the most commonly-used strategy, with an average increase of 3 to 4 times in quantum operations, all achieved within a reasonable runtime. In qubit-constrained tasks, our method achieves over 90% reduction in T-count. Additionally, we have incorporated our strategy into the hierarchical synthesis method and implemented it as a potential synthesizer for Qiskit, with experiments demonstrating that it outperforms the default synthesizer. The proposed approach shows promise in optimizing both qubit usage and circuit gate count for large-scale oracle synthesis problems.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 15, 2025•1 citation

Parallel Quantum Pebbling: Analyzing the Post-Quantum Security of iMHFs.

Jeremiah Blocki, Seunghoon Lee

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $\mathcal{O}(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity -- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a new (parallel) quantum pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new quantum pebbling game to analyze the quantum space-time complexity of several important graphs: the line graph, Argon2i-A, Argon2i-B, and DRSample. (See the paper for the full abstract.)

•Oct 8, 2021•0 citations
Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. In this work, we propose an automatic tool for quantum memory management. We show how this problem exactly matches the reversible pebbling game. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed tool empowers the designer with the flexibility required to explore the trade-off between memory resources and number of operations. We present two show-cases to prove the validity of our approach. First, we apply the algorithm to straight-line programs, widely used in cryptographic applications. Second, we perform a comparison with the existing approach, showing an average improvement of 52.77%.
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 ϵ∈(0,1] , any classical computation requiring time T and space S can be implemented on a quantum computer using only O(T/ϵ) gates and O(TϵS1−ϵ) qubits. This improves on the best known bound for the reversible pebble game with that number of qubits, which uses O(21/ϵT) gates. For smaller space bounds, we show that the spooky pebble game can simulate arbitrary computation with O(T1+ϵS−ϵ/ϵ) gates and O(S/ϵ) qubits whereas any simulation via the reversible pebble game requires Ω(S⋅(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.
Pebble games are commonly used to study space-time trade-offs in computation. We present a pebble game that explores this trade-off in quantum simulation of arbitrary classical circuits on non-classical inputs. Many quantum algorithms, such as Shor's algorithm and Grover's search, include subroutines that require simulation of classical functions on inputs in superposition. The current state of the art uses generic reversible simulation through Bennett's pebble game and universal reversible gate sets such as the Toffoli. Using measurement-based uncomputation, we replace many of the ancilla qubits used by existing constructions with classical control bits, which are cheaper. Our pebble game forms a natural framework for reasoning about measurement-based uncomputation, and we prove tight bounds on the time complexity of all algorithms that use our pebble game. For any ϵ∈(0,1)\epsilon \in (0,1)ϵ∈(0,1), we present an algorithm that can simulate irreversible classical computation that uses T\mathcal{T}T time and S\mathcal{S}S space in O(1ϵT1+ϵSϵ)O(\frac{1}{\epsilon}\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})O(ϵ1​SϵT1+ϵ​) time with O(1ϵS)O(\frac{1}{\epsilon}\mathcal{S})O(ϵ1​S) qubits. With access to more qubits we present algorithms that run in O(1ϵT)O(\frac{1}{\epsilon}\mathcal{T})O(ϵ1​T) time with O(S1−ϵTϵ)O(\mathcal{S}^{1-\epsilon}\mathcal{T}^\epsilon)O(S1−ϵTϵ) qubits. Both of these results show an improvement over Bennett's construction, which requires O(T1+ϵSϵ)O(\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})O(SϵT1+ϵ​) time when using O(ϵ21/ϵS(1+log⁡TS))O(\epsilon2^{1/\epsilon} \mathcal{S} (1+\log \frac{\mathcal{T}}{\mathcal{S}}))O(ϵ21/ϵS(1+logST​)) qubits. Additionally the results in our paper combine with Barrington's theorem to provide a general method to efficiently compute any log-depth circuit on quantum inputs using a constant number of ancilla qubits. We also explore a connection between the optimal structure of our pebbling algorithms and backtracking from dynamic programming.
We develop a framework for resource efficient compilation of higher-level programs into lower-level reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. This is motivated by the limited availability of qubits for the foreseeable future. We apply three main techniques to keep the number of required qubits small when computing classical, irreversible computations by means of reversible networks: first, wherever possible we allow the compiler to make use of in-place functions to modify some of the variables. Second, an intermediate representation is introduced that allows to trace data dependencies within the program, allowing to clean up qubits early. This realizes an analog to "garbage collection" for reversible circuits. Third, we use the concept of so-called pebble games to transform irreversible programs into reversible programs under space constraints, allowing for data to be erased and recomputed if needed. We introduce REVS, a compiler for reversible circuits that can translate a subset of the functional programming language F# into Toffoli networks which can then be further interpreted for instance in LIQui|>, a domain-specific language for quantum computing and which is also embedded into F#. We discuss a number of test cases that illustrate the advantages of our approach including reversible implementations of SHA-2 and other cryptographic hash-functions, reversible integer arithmetic, as well as a test-bench of combinational circuits used in classical circuit synthesis. Compared to Bennett's method, REVS can reduce space complexity by a factor of 444 or more, while having an only moderate increase in circuit size as well as in the time it takes to compile the reversible networks.
Software quantum simulators are essential tools for designing and testing quantum algorithms on classical computing architectures, especially given the current limitations of physical quantum hardware. This work focuses on studying and evaluating memory management strategies for scalable quantum state simulation. We examine full-state representation, dynamic state pruning, shared-memory parallelization with OpenMP, distributed memory execution using MPI, and error-bounded floating-point compression with ZFP. These techniques are implemented in a prototype simulator and assessed using the quantum Fourier transform as a benchmark, with performance compared against leading open-source simulators such as Intel-QS, QuEST, and qsim. The results show the trade-offs between computational overhead and memory efficiency, and demonstrate that hybrid approaches combining distributed memory and compression can significantly extend the number of qubits that can be simulated. This work contributes practical insights for improving the scalability of software quantum simulators on classical hardware through optimized memory usage.
Quantum oracles are quantum circuits that implement classical Boolean functions, frequently used as independent black boxes in quantum algorithm design. The hierarchical reversible logic synthesis approach, a scalable method for large-scale oracle synthesis, relies on ancilla qubits to store intermediate results. The sequence in which these results are computed and uncomputed, governed by the reversible pebble game, greatly affects both qubit usage and circuit gate count. This paper introduces a novel divide-and-conquer pebbling strategy that reduces qubit count while maintaining a reasonable circuit gate count. Experimental results show up to a 90% reduction in qubits compared to the most commonly-used strategy, with an average increase of 3 to 4 times in quantum operations, all achieved within a reasonable runtime. In qubit-constrained tasks, our method achieves over 90% reduction in T-count. Additionally, we have incorporated our strategy into the hierarchical synthesis method and implemented it as a potential synthesizer for Qiskit, with experiments demonstrating that it outperforms the default synthesizer. The proposed approach shows promise in optimizing both qubit usage and circuit gate count for large-scale oracle synthesis problems.
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function fff with a static data-dependency graph GGG. Of particular interest in the field of cryptography are data-independent memory-hard functions fG,Hf_{G,H}fG,H​ which are defined by a directed acyclic graph (DAG) GGG and a cryptographic hash function HHH. The pebbling complexity of the graph GGG characterizes the amortized cost of evaluating fG,Hf_{G,H}fG,H​ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain X\mathcal{X}X, i.e., given y∈{0,1}∗y \in \{0,1\}^*y∈{0,1}∗ find x∈Xx \in \mathcal{X}x∈X such that fG,H(x)=yf_{G,H}(x)=yfG,H​(x)=y. While a classical attacker will need to evaluate the function fG,Hf_{G,H}fG,H​ at least m=∣X∣m=|\mathcal{X}|m=∣X∣ times a quantum attacker running Grover's algorithm only requires O(m)\mathcal{O}(\sqrt{m})O(m​) blackbox calls to a quantum circuit CG,HC_{G,H}CG,H​ evaluating the function fG,Hf_{G,H}fG,H​. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit CG,HC_{G,H}CG,H​. We first observe that a legal black pebbling strategy for the graph GGG does not necessarily imply the existence of a quantum circuit with comparable complexity -- in contrast to the classical setting where any efficient pebbling strategy for GGG corresponds to an algorithm with comparable complexity evaluating fG,Hf_{G,H}fG,H​. Motivated by this observation we introduce a new (parallel) quantum pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new quantum pebbling game to analyze the quantum space-time complexity of several important graphs: the line graph, Argon2i-A, Argon2i-B, and DRSample. (See the paper for the full abstract.)