arXiv preprint ·
Reopening the one clean qubit case of a semi-grand challenge
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Anti-distinguishability of quantum channels
Static and dynamical Casimir effects in a wedge within the worldline formulation
Entanglement Allocation for Quantum Integrated Sensing and Communication
Exact teleportation bounds for fermionic Hawking thermality beyond the single-mode approximation
Quantum identity authentication protocol via perturbed probability amplitudes
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.