For the first time, a research group at Kyoto University and others has theoretically proved that even a "weak" quantum computer that can use only one qubit is "stronger" than a classical computer.
A quantum computer is a computer that operates based on the physical theory "quantum mechanics" that explains the micro world.It is said that ultra-high-speed calculations far surpassing the "classical computers" we are currently using are possible.
However, the realization of a huge universal quantum computer that can freely handle a large number of qubits is still in the distant future.Therefore, there is a lot of research to show that even "weak" quantum computers, which can be realized in the near future, have an advantage over classical computers (quantum spremacy).
For example, the "one-clean qubit model" is one of the oldest "weak" quantum computing models proposed in 1998. While only one qubit can be used and looks weak, it has been shown to be able to efficiently calculate quantities for which there is no known efficient method for calculating Jones polynomials.However, if an efficient classical algorithm for computing Jones polynomials is discovered, the one-clean qubit model loses its superiority to the classics, so it cannot be said to be a reliable quantum premacy.
Under these circumstances, the research group succeeded in theoretically proving the superiority of the one-clean qubit model for the first time using a new method.Furthermore, the method discovered this time can be applied to other types of weak quantum computational models, and we have succeeded in proving quantum premacy for those models on a stronger computational complexity theory basis than before.
This result lays the theoretical foundation for quantum spray research that is advancing all over the world, and is expected to greatly contribute to the development of quantum computational research in the future.
Paper information:[PHYSICAL REVIEW LETTERS] Impossibility of classically simulating one-clean-qubit model with multiplicative error
