A quantum computer is a completely new type of computer that operates according to quantum mechanics.It is believed that it has a computing performance that far surpasses that of the computer we are currently using (classical computer), and there are great expectations for its realization.

　Above all, the development of a general-purpose quantum computer that can run any quantum algorithm is regarded as one of the ultimate goals, and many researchers around the world are working on it.However, it is still difficult to realize a general-purpose quantum computer that can handle a large number of qubits, and recently, attention has been focused on the development of non-general-purpose quantum computers that enable excellent calculations for specific problems rather than general-purpose ones. ..

　The oldest example of a non-general purpose quantum computer is the one-clean-qubit model. The one-clean-qubit model cannot perform arbitrary quantum computations, but it can solve certain problems, such as knot invariant computations, faster than the best algorithms of the current classic.This fact suggests that the one-clean-qubit model is more powerful than the classic computer, but no proof has been made so far.

　In this study, we have theoretically proved that this one-clean-qubit model is faster than the classical computer for the first time based on the computational complexity theory.It is expected that this will enable us to demonstrate the superiority of quantum computers over classical computers with technologies that can be realized in the near future without making complicated general-purpose quantum computers.

Paper information:[Physical Review A Rapid Communications] Hardness of classically sampling one clean qubit model with constant total variation distance error