  Gate-teleportation circuits are arguably among the most basic examples of
computations believed to provide a quantum computational advantage: In seminal
work [Quantum Inf. Comput., 4(2):134--145], Terhal and DiVincenzo have shown
that these circuits elude simulation by efficient classical algorithms under
plausible complexity-theoretic assumptions. Here we consider possibilistic
simulation [Phys. Rev. A 106, 062430 (2022)], a particularly weak form of this
task where the goal is to output any string appearing with non-zero probability
in the output distribution of the circuit. We show that even for single-qubit
Clifford-gate-teleportation circuits this simulation problem cannot be solved
by constant-depth classical circuits with bounded fan-in gates. Our results are
unconditional and are obtained by a reduction to the problem of computing the
parity, a well-studied problem in classical circuit complexity.
