Classic computers to refer to data in the form of zeros and ones turn on and off transistors. Quantum computers use quantum bits – qubits, which, thanks to the strange nature of quantum physics, can be in a state of superposition, signifying both 1 and 0.

Superposition allows one qubit to perform two calculations simultaneously, and when two of the qubit are connected to each other through such quantum effects, like entanglement, they can perform 2²4 calculations simultaneously; three qubit capable of 2³, or eight calculations; and so on. In principle, a quantum computer with 300 qubits could perform many calculations at the same time that their number exceeded the number of available atoms in the Universe.

The question of how many qubits need to achieve a quantum advantage over standard computers, remains open. Last year Google announced that they have achieved quantum supremacy with 53 qubits for 200 after calculating that the most powerful supercomputer in the world would, according to estimations of the company, about 10 000 years. However, researchers from IBM in response to the article claiming that "a perfect simulation of the same task can be performed on a classical system over a period of 2.5 days, and with much greater accuracy".

To understand what really may require a quantum supremacy, the researchers analyzed three different quantum schemes that can solve tasks beyond conventional computers. Scheme IQP (instantaneous quantum polynomial time) allow especially easy to connect qubits in quantum circuits. Scheme the quantum algorithm of approximation optimization (QAOA) are more advanced. They use qubits in finding good solutions to optimization problems. The selection circuit bosons photons are used instead of qubits, analyzing the ways in which the photons are scattered after interaction with each other.

Assuming that quantum computers will compete with supercomputers capable of up to trillion (10¹⁸) of floating point operations per second (FLOPS), the researchers calculated that the quantum of superiority can be achieved by using 208 qubits in the circuit IQP, 420 qubits in the circuit QAOA and 98 photons sample of bosons

"I'm surprised we were able to give these figures, not so far removed from what can be seen today in existing devices," says the study's lead author Alexander Dalziel, a quantum physicist from the California Institute of technology in Pasadena. "In our first approach to solving this task we assumed that it would take at least 10 000 qubits in the second – not less than 2000. And finally, after the third iteration, we were able to significantly reduce overhead and to reduce the number of qubits to hundreds.

Also, scientists admit that quantum superiority may be achievable with an even smaller number of qubits. "In General, many of our assumptions come from the worst scenarios – but perhaps this will not be needed," says Dalziel.

What to Google, the researchers note that the statement this company is difficult to critique because the company chose this task to quantum computers, which are difficult to compare with known algorithms for classical computing.

"I think that their statement on the fact that they are using quantum devices did something that we don't know how to do on a classical device without spending huge resources, in my opinion, can be considered accurate – says Dalziel. – I'm really not sure that exists yet unknown classical algorithm that would allow us to reproduce their experiment, or even a larger version of it on realistic and classic device. I want to clarify, I'm not saying I believe in the existence of such an algorithm. I'm just saying that if it existed, it wouldn't be so surprising and unexpected".

And what, "have we reached the quantum computational superiority, if we managed to do something that we don't know what to do with the classic device? Or do we really want to make sure this is not possible even when using the not yet open algorithms? – asks Dalziel. – Google clearly takes the first point of view, and even acknowledges that algorithmic innovation to reduce the cost of classical simulation. But still they expect that the improvement of quantum devices will help them to remain in a state of quantum superiority. They rely on arguments from complexity theory, which suggests that it is unlikely the emergence of ways of radically improving the classical simulations. Such interpretation can be taken".

Future research can analyze how the assessment of the quantum of superiority come from noise present in quantum circuits. "In the absence of noise, the arguments in favor of the superiority of quantum computing seem convincing, says Dalziel. But add noise, and then the classical algorithm appears to be something that he can use".

Original author: Charles Q. Choi

Source: https://habr.com/ru/post/505716/

Tags: assessment , USA , science