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:2503.21582 · Theoretical Computer Science

Time hierarchies for sublogarithmic-space quantum computation

A. C. Cem Say

Published Nov 20, 2025• 1 citation
arXivHTMLPDF
DOI
10.1016/j.tcs.2025.115639

Related papers

Time peception, cyclic groups and quantum computation

Michel R. P. Planat

•Jan 1, 2003•0 citations

Quantum function computation using sublogarithmic space (abstract & poster)

A. C. Cem Say, Abuzer Yakaryılmaz

We prove that quantum Turing machines are strictly superior to probabilistic Turing machines in function computation for any space bound $ o(\log(n)) $.

arXiv:1009.3124•Sep 16, 2010•5 citations

Quantum algorithm for Clifford multiplication

Kagwe A. Muchane

Given two dense multivectors of the Clifford algebra $C\ell(V, Q)$ with $N=2^{p+q}$ coefficients, the fastest known classical algorithms compute their geometric product in $O(N^{ω/2})$ arithmetic operations, where $ω$ denotes the matrix multiplication exponent. I show that, under amplitude encoding, a quantum computer executes the geometric product in $O(\operatorname{polylog} N)$ time, using logarithmic space with sublogarithmic circuit depth. This exponential speedup establishes Clifford multiplication as a quantum primitive, providing an efficient computational foundation for quantum geometric algorithms and relativistic simulations.

quant-pharXiv:2607.10473•Jul 14, 2026•0 citations

Worst-case depth hierarchy for shallow quantum circuits

Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1 more

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

quant-pharXiv:2606.16425•Jun 16, 2026•2 citations

Models for Quantum Computation

Peter P. Rohde

Cambridge University Press eBooks•Sep 9, 2021•0 citations

Algorithms of quantum computation

Shinil Cho

Institute of Physics eBooks•Jul 1, 2022•8 citations
Given two dense multivectors of the Clifford algebra Cℓ(V,Q)C\ell(V, Q)Cℓ(V,Q) with N=2p+qN=2^{p+q}N=2p+q coefficients, the fastest known classical algorithms compute their geometric product in O(Nω/2)O(N^{ω/2})O(Nω/2) arithmetic operations, where ωωω denotes the matrix multiplication exponent. I show that, under amplitude encoding, a quantum computer executes the geometric product in O(polylog⁡N)O(\operatorname{polylog} N)O(polylogN) time, using logarithmic space with sublogarithmic circuit depth. This exponential speedup establishes Clifford multiplication as a quantum primitive, providing an efficient computational foundation for quantum geometric algorithms and relativistic simulations.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for QNC0\mathsf{QNC}^0QNC0. For each d≥12d\ge 12d≥12, we construct a family of two-round interactive problems on which no depth-(d−1)(d-1)(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than ddd by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every ddd, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0\mathsf{QNC}^0QNC0 over NC0\mathsf{NC}^0NC0. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within QNC0\mathsf{QNC}^0QNC0, establishing a genuinely quantum hierarchy.