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 $B_h$ with $n=2^h-1$ vertices and every space budget $h+1\le s\le n$, we give an algorithm with asymptotically optimal work $Θ(nh/\log(s+1))$. At the minimum budget $s=h+1$, this improves the $O(n\log n)$ bound of Kornerup, Sadun, and Soloveichik to $Θ(n\log n/\log\log n)$, resolving their time-optimality question. We also construct a parallel schedule with optimal depth \[ Θ\!\left(h+\frac ns \max\!\left\{\frac{h}{\log(s+1)},\,1+\log^*h\right\}\right). \] 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.
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 [ Θ!\left(h+\frac ns \max!\left{\frac{h}{\log(s+1)},,1+\log^*h\right}\right). ] 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.
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.
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an n-qubit register with depth O(logn) and size O(nlogn), using only the n input qubits and m=⌈log2(n+1)⌉ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only m ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even n. With only O(logn) ancillary qubits, we obtain expected depth O(log2n) using measurements and classical feedforward, and depth O(n1/4logn) using unitary gates alone.
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.)
Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives.
For a Hermitian decomposition A=∑j=1LαjHj, with ∥Hj∥=1 and α=∑j∣αj∣, we give two coherent ε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O(L(α/ε)o(1)), while the second uses O(loglog(α/ε)) ancillas and achieves depth O(L).
For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, log(1/ε)≤O((logQ)2+2alogQ), where Q is depth normalized by the number of Hamiltonian terms and a is the ancilla count. Thus polylogarithmic dependence on 1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L and error ε=η/L with fixed 0<η<1, we prove 2a=Ωη(L2/(T+L)), where T is the number of oracle queries. Hence a=Ω(logL) when T=O(Lα) for some α<2. Moreover, in the exact case, a≥logL regardless of T. We also extend this tradeoff to arbitrary nonnegative coefficients.
Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.
We construct an exact n-bit quantum adder with O(n) gates and O(logn) depth that requires no ancillary qubits. The circuit uses only X, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with O(nloglogn) gates and O(logn) depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with O(n) gates. Both the gate count and circuit depth are asymptotically optimal.
Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson [1] demonstrated that additional qubits (or ancillae) could be used to design “shallow” parallel circuits for quantum operators. They proved that any n-qubit CNOT circuit could be parallelized to O(log n) depth, with O(n2) ancillae. However, the near-term quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any m ≥ 0, any n-qubit CNOT circuit can be parallelized to depth, with m ancillae. We show that this bound is tight by a counting argument, and further show that even with arbitrary two-qubit quantum gates to approximate CNOT circuits, the depth lower bound still meets our construction, illustrating the robustness of our result. Our work improves upon two previous results, one by Moore and Nilsson [1] for O(log n)-depth quantum synthesis, and one by Patel, Markov, and Hayes [2] for m =0: for the former, we reduce the need for ancillae by a factor of log2 n by showing that m = O(n2 / log2 n) additional qubits — which is asymptotically optimal — suffice to build O(log n)-depth, O(n2 / log n)-size CNOT circuits; for the later, we reduce the depth by a factor of n to the asymptotically optimal bound . Our results can be directly extended to stabilizer circuits using an earlier result by Aaronson and Gottesman [3]. In addition, we provide relevant hardness evidence for synthesis optimization of CNOT circuits in term of both size and depth.