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 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), we present an algorithm that can simulate irreversible classical computation that uses T time and S space in O(ϵ1SϵT1+ϵ) time with O(ϵ1S) qubits. With access to more qubits we present algorithms that run in O(ϵ1T) time with O(S1−ϵTϵ) qubits. Both of these results show an improvement over Bennett's construction, which requires O(SϵT1+ϵ) time when using 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.
Pebble games are used to study space/time trade-offs. Recently, spooky pebble games were introduced to study classical space / quantum space / time trade-offs for simulation of classical circuits on quantum computers. In this paper, the spooky pebble game framework is applied for the first time to general circuits. Using this framework we prove an upper bound for quantum space in the spooky pebble game. We also prove that solving the spooky pebble game is PSPACE-complete. Moreover, we present a solver for the spooky pebble game based on satisfiability solvers combined with heuristic optimizers. This spooky pebble game solver was empirically evaluated by calculating optimal classical space / quantum space / time trade-offs. Within limited runtime, the solver could find a strategy reducing quantum space when classical space is taken into account, showing that the spooky pebble model is useful to reduce quantum space.
Pebble games model computations under a fixed space budget. Spooky pebbling allows quantum memory to be released by measurement, with the resulting phases corrected later. We study two-input computations with binary-tree dependencies and determine the optimal work and parallel depth for complete binary trees. Our key idea is to clean up the tree in blocks, reducing repeated recomputation of intermediate values. For the complete tree Bh with n=2h−1 vertices and every space budget h+1≤s≤n, we give an algorithm with asymptotically optimal work Θ(nh/log(s+1)). At the minimum budget s=h+1, this improves the O(nlogn) bound of Kornerup, Sadun, and Soloveichik to Θ(nlogn/loglogn), resolving their time-optimality question. We also construct a parallel schedule with optimal depth Θ(h+snmax{log(s+1)h,1+log∗h}). Our lower bounds hold for every full binary tree. We also show that achieving optimal parallel depth can require asymptotically more work than minimizing work alone. Applying our schedule to the RNS point-addition trees in the public implementation of Chevignard, Fouque, and Schrottenloher reduces their Toffoli/AND gate count by 20.86% for a P-224 instance and 22.66% for a P-256 instance, using the same arithmetic circuits and peak workspace.
Hierarchical reversible logic synthesis can find quantum circuits for large combinational functions. The price for a better scalability compared to functional synthesis approaches is the requirement for many additional qubits to store temporary results of the hierarchical input representation. However, implementing a quantum circuit with large number of qubits is a major hurdle. In this paper, we demonstrate and establish how reversible pebble games can be used to reduce the number of stored temporary results, thereby reducing the qubit count. Our proposed algorithm can be constrained with number of qubits, which is aimed to meet. Experimental studies show that the qubit count can be significantly reduced (by up to 63.2%) compared to the state-of-the-art algorithms, at the cost of additional gate count.
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 fG,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 fG,H multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain X, i.e., given y∈{0,1}∗ find x∈X such that fG,H(x)=y. While a classical attacker will need to evaluate the function fG,H at least m=∣X∣ times a quantum attacker running Grover's algorithm only requires O(m) blackbox calls to a quantum circuit CG,H evaluating the function 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,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 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.)
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.