Single-qubit gate teleportation provides a quantum advantage

Libor Caha, Xavier Coiteux-Roy, Robert König

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

Abstract

Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: in seminal work [1], Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation [2], 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 parity, a well-studied problem in classical circuit complexity.

OriginalspracheEnglisch
FachzeitschriftQuantum
Jahrgang8
DOIs
PublikationsstatusVeröffentlicht - 2024
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Single-qubit gate teleportation provides a quantum advantage“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren