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:2610.09434

Optimal (Parallel) Spooky Pebbling on Binary Trees

Mingyu Lee, Sanghyun Lee, Kabgyun Jeong

Published Oct 7, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2610.09434

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

Exact quantum Hamming-weight computation at optimal depth and minimum width

Wei Zi, Pei Yuan, Junhong Nie

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(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ 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(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.

quant-pharXiv:2610.25315•Oct 20, 2026•0 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

Quantum space-depth tradeoffs for coherent block encodings

Yuxin Zhang, Changpeng Shao

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=\sum_{j=1}^L α_j H_j$, with $\|H_j\|=1$ and $α=\sum_j|α_j|$, we give two coherent $\varepsilon$-approximate block-encoding constructions. The first uses one ancilla qubit and has depth $\widetilde O(L(α/\varepsilon)^{o(1)})$, while the second uses $O(\log\log(α/\varepsilon))$ ancillas and achieves depth $\widetilde 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/\varepsilon)\le O((\log Q)^2+2^a\log Q)$, where $Q$ is depth normalized by the number of Hamiltonian terms and $a$ is the ancilla count. Thus polylogarithmic dependence on $1/\varepsilon$ requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients $1/L$ and error $\varepsilon=η/L$ with fixed $0<η<1$, we prove $2^a=Ω_η(L^2/(T+L))$, where $T$ is the number of oracle queries. Hence $a=Ω(\log L)$ when $T=O(L^α)$ for some $α<2$. Moreover, in the exact case, $a\ge \log L$ 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.

quant-pharXiv:2607.01843•Jul 3, 2026•3 citations

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

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ 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(n\log\log n)$ gates and $O(\log n)$ 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.

quant-pharXiv:2610.34446•Oct 27, 2026•0 citations
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 BhB_hBh​ with n=2h−1n=2^h-1n=2h−1 vertices and every space budget h+1≤s≤nh+1\le s\le nh+1≤s≤n, we give an algorithm with asymptotically optimal work Θ(nh/log⁡(s+1))Θ(nh/\log(s+1))Θ(nh/log(s+1)). At the minimum budget s=h+1s=h+1s=h+1, this improves the O(nlog⁡n)O(n\log n)O(nlogn) bound of Kornerup, Sadun, and Soloveichik to Θ(nlog⁡n/log⁡log⁡n)Θ(n\log n/\log\log n)Θ(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%20.86\%20.86% for a P-224 instance and 22.66%22.66\%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 nnn-qubit register with depth O(log⁡n)O(\log n)O(logn) and size O(nlog⁡n)O(n\log n)O(nlogn), using only the nnn input qubits and m=⌈log⁡2(n+1)⌉m=\lceil\log_2(n+1)\rceilm=⌈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 mmm ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even nnn. With only O(log⁡n)O(\log n)O(logn) ancillary qubits, we obtain expected depth O(log⁡2n)O(\log^2 n)O(log2n) using measurements and classical feedforward, and depth O(n1/4log⁡n)O(n^{1/4}\log n)O(n1/4logn) using unitary gates alone.
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.
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αjHjA=\sum_{j=1}^L α_j H_jA=∑j=1L​αj​Hj​, with ∥Hj∥=1\|H_j\|=1∥Hj​∥=1 and α=∑j∣αj∣α=\sum_j|α_j|α=∑j​∣αj​∣, we give two coherent ε\varepsilonε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O~(L(α/ε)o(1))\widetilde O(L(α/\varepsilon)^{o(1)})O(L(α/ε)o(1)), while the second uses O(log⁡log⁡(α/ε))O(\log\log(α/\varepsilon))O(loglog(α/ε)) ancillas and achieves depth O~(L)\widetilde O(L)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((log⁡Q)2+2alog⁡Q)\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)log(1/ε)≤O((logQ)2+2alogQ), where QQQ is depth normalized by the number of Hamiltonian terms and aaa is the ancilla count. Thus polylogarithmic dependence on 1/ε1/\varepsilon1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L1/L1/L and error ε=η/L\varepsilon=η/Lε=η/L with fixed 0<η<10<η<10<η<1, we prove 2a=Ωη(L2/(T+L))2^a=Ω_η(L^2/(T+L))2a=Ωη​(L2/(T+L)), where TTT is the number of oracle queries. Hence a=Ω(log⁡L)a=Ω(\log L)a=Ω(logL) when T=O(Lα)T=O(L^α)T=O(Lα) for some α<2α<2α<2. Moreover, in the exact case, a≥log⁡La\ge \log La≥logL regardless of TTT. 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.
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.)
We construct an exact nnn-bit quantum adder with O(n)O(n)O(n) gates and O(log⁡n)O(\log n)O(logn) depth that requires no ancillary qubits. The circuit uses only XXX, 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(nlog⁡log⁡n)O(n\log\log n)O(nloglogn) gates and O(log⁡n)O(\log n)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)O(n)O(n) gates. Both the gate count and circuit depth are asymptotically optimal.