Reopening the one clean qubit case of a semi-grand challenge
Abstract
In his 2005 list of semi-grand challenges for quantum computing theory, Scott Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time. An affirmative answer was claimed for the one clean qubit model of quantum computation. The supporting mathematical arguments relied on an exhaustive characterization of circuits that stay in separable states. Here, we give a counterexample where one pure qubit, known as the clean qubit, controls a sequence of three gates that act on a maximally mixed three-qubit register. The overall unitary that accumulates as these gates are applied has the properties that ensure the state of all four qubits remains fully separable. Crucially, we show that the final unitary cannot be put into the form required by the claimed simulation result. We also give a continuous-time implementation of the same circuit that keeps the qubits fully separable throughout and ends at the same unitary. We extend our counterexamples to a uniform family, and pinpoint the gap in the earlier proof. Since our circuits are themselves efficient to simulate classically, this work does not settle Aaronson's question. It does, however, reopen the semi-grand challenge for an actively researched model of quantum computation.
Related
- One-clean-qubit spectroscopy of simulated Kitaev chains
- Recent benchmarks in the Analysis Grand Challenge and integration with Combine (and HS3)
- Semi-Device-Independent Certification of multi-qubit Entangled Basis Measurement
- Quantum Uncomputation of Clean and Dirty Ancilla Qubits
- Superheating field of clean superconductors near the type-I--type-II boundary: the low-temperature Meissner stability limit of niobium
BibTeX
@misc{mansell2026reopening,
title = {{Reopening the one clean qubit case of a semi-grand challenge}},
author = {Christopher W. Mansell},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05046},
eprint = {2611.05046},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05046},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reopening the one clean qubit case of a semi-grand challenge
AU - Christopher W. Mansell
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05046
UR - https://arxiv.org/abs/2611.05046
AB - In his 2005 list of semi-grand challenges for quantum computing theory, Scott Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time. An affirmative answer was claimed for the one clean qubit model of quantum computation. The supporting mathematical arguments relied on an exhaustive characterization of circuits that stay in separable states. Here, we give a counterexample where one pure qubit, known as the clean qubit, controls a sequence of three gates that act on a maximally mixed three-qubit register. The overall unitary that accumulates as these gates are applied has the properties that ensure the state of all four qubits remains fully separable. Crucially, we show that the final unitary cannot be put into the form required by the claimed simulation result. We also give a continuous-time implementation of the same circuit that keeps the qubits fully separable throughout and ends at the same unitary. We extend our counterexamples to a uniform family, and pinpoint the gap in the earlier proof. Since our circuits are themselves efficient to simulate classically, this work does not settle Aaronson's question. It does, however, reopen the semi-grand challenge for an actively researched model of quantum computation.
ER -