DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.38

Non-Clifford Gates Are Required for Long-Term Memory

Authors: Jon Nelson, Joel Rajakumar, and Michael J. Gullans

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

We show that all Clifford circuits under interspersed depolarizing noise lose memory of their input exponentially quickly in the depth of the circuit, even when given access to a supply of fresh qubits initialized in arbitrary states. This result applies only in the absence of intermediate measurements, i.e. without intervention by a noiseless external observer such as a classical computer. Nonetheless, this result is surprising given that non-Clifford circuits with access to a supply of fresh qubits can preserve quantum states for arbitrary lengths of time, and even perform fault tolerant quantum computation on them, without requiring any intermediate measurements (Aharonov et al., STOC 1997). Our result shows that such fault tolerance protocols are impossible using only Clifford gates, demonstrating that non-Clifford gates are fundamentally required to store quantum or classical information for long periods of time.

Cite as

Jon Nelson, Joel Rajakumar, and Michael J. Gullans. Non-Clifford Gates Are Required for Long-Term Memory. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nelson_et_al:LIPIcs.CCC.2026.38,
  author =	{Nelson, Jon and Rajakumar, Joel and Gullans, Michael J.},
  title =	{{Non-Clifford Gates Are Required for Long-Term Memory}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.38},
  URN =		{urn:nbn:de:0030-drops-270800},
  doi =		{10.4230/LIPIcs.CCC.2026.38},
  annote =	{Keywords: Fault Tolerance, Quantum Error Correction}
}

Search Results

Documents authored by Gullans, Michael J.

Non-Clifford Gates Are Required for Long-Term Memory

Abstract

Cite as

Thanks for your feedback!

Could not send message