Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International journal of unconventional computing

Grand Challenge in Non-Classical Computation.

Susan Stepney, Stephen Emmott

Published Jan 1, 2007• 4 citations
OpenAlex

Related papers

Journeys in non-classical computation II: initial journeys and waypoints

Susan Stepney, Samuel L. Braunstein, John A. Clark +9 more

Our Grand Challenge for computer science is: to journey through the gateway event obtained by breaking our current classical computational assumptions, and thereby develop a mature science of Non-C...

International Journal of Parallel Emergent and Distributed Systems•Dec 27, 2005•36 citations

Classical computation

A. Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematics•May 31, 2002•1 citation

a Physics of Computation.

Wakefield Scott Stornetta

•Jan 1, 1989•0 citations

Journeys in non-classical computation I: A grand challenge for computing research

Susan Stepney, Samuel L. Braunstein, John A. Clark +9 more

A gateway event [35] is a change to a system that leads to the possibility of huge increases in kinds and levels of complexity. It opens up a whole new kind of phase space to the system's dynamics....

International Journal of Parallel Emergent and Distributed Systems•Mar 1, 2005•74 citations

Reopening the one clean qubit case of a semi-grand challenge

Christopher Mansell

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.

arXiv:2611.05046•Nov 3, 2026•0 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations
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.