Origin
The idea of a quantum computer appeared about 40 years ago in the works of the Soviet scientist Yuri Manin, but was soon independently and in a much clearer form formulated by Richard Feynman.
The essence of the quantum computing paradigm is to use quantum systems for storing and processing data, the states of which can take any value in the continuum between the main positions, while in the classical case, a computer element, such as a transistor, is uniquely in one of two possible positions.
By analogy with ordinary bits of information, qubits are introduced in the quantum case. As a result, the system of N qubits is completely described only with the help of 2 N parameters, each of which can equal any number between zero and one. At the same time, a system of N classical bits is also described by 2 N parameters, but they can take only two extreme values.
It is worth noting that a quantum computer is not a substitute for the classical one, since it is still effective in solving various classes of problems. Moreover, only recently have scientists come up with the first example of a problem that, in principle, only a quantum computer can solve.
Evolution
Quantum computers did not attract much attention until the mid-1990s, when the first quantum algorithms appeared, that is, programs theoretically feasible with their help. The turning point occurred after the release of the work of Peter Shore, who found a way to effectively factor large numbers, that is, decompose them into prime factors.
The complexity of this task for a classic computer grows rapidly with increasing numbers, due to which it underlies some encryption mechanisms, in particular in the widespread RSA protocol. The cryptographic strength of this method is based on the fact that ordinary computers will not be able to select the number necessary for decryption in a reasonable time, and thanks to the Shore algorithm, a quantum computer is theoretically capable of this.
The development of quantum computers began scientists in many countries around the world. Moreover, commercial structures began to show interest, as Google, IBM, Microsoft and even some financial organizations, for example, Morgan Stanley Bank. The reason for this is the expected ability of quantum computers to solve cryptography and multidimensional optimization problems that arise, in particular, in the analysis of exchange rates.
In the early 2010s, the most optimistic analysts claimed that a useful quantum computer would appear in the next few years. More cautious specialists took a couple of decades to create it. In order to somehow formalize progress in this area and mark the completion of the initial stage of development, physicist John Preskill proposed the term “quantum superiority” in 2012.
Quantum superiority comes at a time when a quantum computer can perform a calculation that is inaccessible to the classical one, regardless of whether the result has practical significance.
This formulation is very loose and allows for many different interpretations. For example, it does not say anything about the method of comparison, nor about the classic counterpart used.
Superiority
October 23, Google employees published in the journal Nature, a work that talks about achieving quantum superiority. The researchers made such a statement based on the results of work with the 53-qubit Sycamore processor, which managed to solve a very specific problem in 200 seconds, while the estimated time to solve it on the most powerful modern Summit computer should be 10 thousand years.
The task was to perform a random but well-known sequence of one-qubit and two-qubit operations, to turn the resulting qubit state into a numeric string and repeat the procedure millions of times. As a result, it is possible to construct the probability distribution of qubits in certain states, which, like a sequence of operations, will not be random due to the interaction between qubits.
Rather, this task is technical, its only possible application is the generation of random numbers. It is also worth noting that due to the vague formulation of quantum superiority, the authors were able to choose a relatively simple task for themselves, which is difficult to solve on a classical computer.
Indeed, although efforts have been made to optimize algorithms for classical computers, progress in this area lags far behind the development of quantum computers.
This is once again confirmed by a statement by IBM employees who claim that the task execution time for a regular computer was significantly overestimated, and using optimization it can be completely reduced to several days.
Google replied to this that the algorithm proposed by IBM employees implies noticeable deviations from the usual mode of operation of supercomputers, so a real test of its performance is required. Also, the data received by the quantum processor has already been made publicly available, which will facilitate verification by both IBM and other teams.
The physical basis of qubits on a Google computer is superconducting circuits. This option is relatively easier to create, but suffers from fairly high noise and errors that make calculations difficult. This became an additional argument in favor of the chosen problem, since the algorithm for its solution is error-resistant and does not require correction.
Effects
Shortly after the release of the work of Google employees, a press conference was organized during which Martinis and other participants in the experiment commented on their achievement. They noted that random number generation could be the first practical application of a quantum computer. Scientists also reported that they are already conducting more complex experiments, in particular in the field of quantum chemical simulations of molecules.
The authors called their main task to attract a large number of researchers to the field they are studying, for which they create open software libraries. A motivated community of scientists should help find suitable practical applications of a quantum computer in the near future.
The Martinis group is going to start experiments with about a thousand qubits within a few years. This will allow, based on many physical qubits, to model the behavior of fewer logical ones whose characteristics will be much closer to ideal. In particular, their errors should be exponentially smaller.
The implementation of such a scheme will be an important step towards the creation of a quantum computer with error correction, which is suitable for solving a much wider class of problems.
When asked about a possible security risk for encryption, Google employees said that for a hackable cryptographic algorithm, such as RSA, that is being implemented, approximately hundreds of millions of physical qubits will be needed.
This is many times more than expected in the near future, so scientists believe we still have enough time to create and implement quantum-resistant encryption methods.
Martinis and his colleagues also noted that cryptographic security issues are being worked on by specialists both within Google and in the US government and other countries, so there is no need to worry about the inviolability of communications and digital transactions by the time such a powerful quantum computer appears.
IBM's quantum computing team criticized Google’s claim of quantum superiority with their device. In an article that accidentally became available to the public, it was stated that scientists were able to use a 53-qubit computer to carry out calculations in 200 seconds, which would require 10,000 years of operation of a classic computer. However, IBM believes that a conventional computer will do this in 2.5 days in the worst case, and the answer will be more accurate than that of a quantum computer, the blog says on the company's website, details are contained in a preprint on arXiv.org server.
A month ago, a preprint with the results of the work of employees of the department and Google was available on the NASA server. This text talked about testing the capabilities of a quantum computer Sycamore with 53 qubits. According to the authors of the article, they managed to achieve quantum superiority using this device, that is, to solve a problem in a reasonable time on a quantum computer, the search for an answer to which even the most powerful classical computer will take incomparably longer.
As a performance test, a group of John Martinis, a quantum computing manager at Google and a professor at the University of California at Santa Barbara, chose a very special task. It consisted of executing a well-known random sequence of commands, reading the final state of qubits in the form of a string of 53 numbers by the number of elements and repeating this operation millions of times. Then, the statistics of the resulting distribution of responses are compared with the expected, since for a known sequence of instructions it can be calculated.
This task has very limited potential in terms of practical applications, but the author of the term "quantum superiority" John Preskill did not distinguish between useful in reality and purely technical calculations. Apparently, Google specifically chose a relatively simple task for a quantum, but difficult for a classical computer.
An article by Martinis and co-authors claimed that they managed to reach such a level of coincidence of quantum states (fidelity) in 200 seconds that it would take about 10,000 years of work for Summit, the most powerful modern classic computer. Naturally, no one conducted such a check, this number is the result of a theoretical assessment of the complexity of the task, which is based on the assumption that it is impossible to keep all the information necessary for each stage of computing in the supercomputer's RAM, which makes it inevitable to use memory-saving algorithms to the detriment of time work.
The text of three employees of IBM, which is also actively engaged in the development of quantum computing, disputes the allegation about the inherent complexity of such calculations for a classic supercomputer. The authors argue that a modern classic calculator will be able to achieve much greater fidelity in 2.5 days, and this is a conservative estimate, that is, additional funds should further reduce the required time.
This conclusion was reached by IBM employees, including several optimization methods in theoretical analysis. The main one was that the classic computer will store the information necessary for current computing not only in RAM, but also on hard drives. It should be noted that this assessment is also theoretical and IBM only simulated the process, and did not carry out the necessary calculations in full.
In conclusion, the authors write that the results of Google, although of undoubted interest, can not be considered evidence of the superiority of quantum computers over classical ones. They also pay special attention to the ability of the term quantum superiority to confuse any person who does not specialize in research in this field, since only considering the issue in the right context allows us to draw the right conclusions.
Recently, physicists were able to simulate a quantum phase transition on a quantum computer and measured the qubit error with an accuracy of one millionth. We wrote in detail about the practically valuable results that scientists expect from quantum computers in the material The World from Qubits.
