Quantum space-depth tradeoffs for coherent block encodings
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 αj Hj, with |Hj|=1 and α=∑j|αj|, we give two coherent ε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth Õ(L(α/ε)o(1)), while the second uses O(loglog(α/ε)) ancillas and achieves depth Õ(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), 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=Ω(log L) when T=O(Lα) for some α<2. Moreover, in the exact case, a≥ 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.
Related
- Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
- Consecutive Measurement Tradeoffs in Quantum Cryptography
- Effective-Hamiltonian Quantum Solvers for Differential Equations: Alternative Constructions and Function Encodings
- Quantum Encodings, Private Messages, and Communication Complexity
- Optimizing quantum encodings for analog simulation through dynamical algebra reachability
BibTeX
@misc{zhang2026quantum,
title = {{Quantum space-depth tradeoffs for coherent block encodings}},
author = {Yuxin Zhang and Changpeng Shao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.01843},
eprint = {2607.01843},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.01843},
}
RIS
TY - UNPB
TI - Quantum space-depth tradeoffs for coherent block encodings
AU - Yuxin Zhang
AU - Changpeng Shao
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2607.01843
UR - https://arxiv.org/abs/2607.01843
AB - 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=1^L α_j H_j, with |H_j|=1 and α=∑_j|α_j|, we give two coherent ε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth Õ(L(α/ε)^o(1)), while the second uses O(loglog(α/ε)) ancillas and achieves depth Õ(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+2^alog Q), 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 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≥ 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.
ER -