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=\sum_{j=1}^L \alpha_j H_j$, with $\|H_j\|=1$ and $\alpha=\sum_j|\alpha_j|$, we give two coherent $\varepsilon$-approximate block-encoding constructions. The first uses one ancilla qubit and has depth $\widetilde O(L(\alpha/\varepsilon)^{o(1)})$, while the second uses $O(\log\log(\alpha/\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=\eta/L$ with fixed $0<\eta<1$, we prove $2^a=\Omega_\eta(L^2/(T+L))$, where $T$ is the number of oracle queries. Hence $a=\Omega(\log L)$ when $T=O(L^\alpha)$ for some $\alpha<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.

arXiv:2607.01843 [quant-ph]

(or arXiv:2607.01843v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.01843 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.