Quantum computers and quantum computing - new , which was added to our information space along with , and other high-tech terms. At the same time, I was never able to find material on the Internet that would put together a puzzle in my head called “how quantum computers work”. Yes, there are many excellent works, including on Habré (see. ), the comments to which, as is usually the case, are even more informative and useful, but the picture in my head, as they say, did not add up.
Recently, colleagues approached me and asked, “Do you understand how a quantum computer works? Can you tell us?” And then I realized that not only I have a problem with folding a complete picture in my head.
As a result, an attempt was made to compile information about quantum computers into a consistent logic circuit, in which basic level, without a deep dive into mathematics and the structure of the quantum world, explained what a quantum computer is, on what principles it works, and also what problems scientists face in its creation and operation.
Table of contents
Disclaimer
The author is not an expert in quantum computing, and the target audience of the article is the same IT people, not quantum specialistswho also want to put together a picture called “How Quantum Computers Work” in their heads. Because of this, many concepts in the article are deliberately simplified for a better understanding of quantum technologies at the “basic” level, but without .
In the article, in some places materials from other sources are used, . Wherever possible, direct references and references to the original text, table or figure are inserted. If somewhere I forgot something (or someone), write - I will correct it.
Introduction
In this chapter, we will briefly look at how the quantum era began, what was the motive for the emergence of the idea of a quantum computer, who (which countries and corporations) are currently the leading players in this field, and also briefly talk about the main directions in the development of quantum computing.
History in brief
The starting point of the quantum era is considered to be 1900, when M. Planck first put forward that energy is emitted and absorbed not continuously, but in separate quanta (portions). The idea was picked up and developed by many prominent scientists of that time - Bohr, Einstein, Heisenberg, Schrödinger, which ultimately led to the creation and development of such a science as . There are many good materials about the formation of quantum physics as a science on the Web, in this article we will not dwell on this in detail, but it was necessary to indicate the date when we entered the new quantum era.
Quantum physics has brought many inventions and technologies into our everyday life, without which it is now difficult to imagine the world around us. For example, the laser, which is now used everywhere, from household appliances (laser levels, etc.) to high-tech systems (lasers for vision correction, hello ). It would be logical to assume that sooner or later someone will put forward the idea that why not use quantum systems for computing. And in 1980 it happened.
Wikipedia indicates that the first idea of quantum computing was expressed in 1980 by our scientist Yuri Manin. But they really started talking about it only in 1981, when the notorious R. Feynman in , noted that it is impossible to simulate the evolution of a quantum system on a classical computer in an efficient way. He proposed an elementary model , which will be able to carry out such a simulation.
The web has , wherein is considered more academically and in detail, but we will go over it briefly:
The main milestones in the history of the creation of quantum computers:
- [1994]. P. Shor. Designed
- [1998]. Created
- [2001]. IBM introduced the execution to decompose the number 15
- [2007-2016]. creates and develops a computer with 128-2000 qubits
- [2012]. Implemented at the University of California
- [2016]. Google on a 9 qubit computer
- [2017]. (three atoms)
- [2019]. . 20 qubit computer in the cloud
- [2019]. . 53 qubit computer. ?
As you can see, 17 years have passed (from 1981 to 1998) from the moment of the idea to its first implementation in a computer with 2 qubits, and 21 years (from 1998 to 2019) until the number of qubits increased to 53. It took 11 years (from 2001 to 2012) to improve the result of the Shor algorithm (we will dwell on it in more detail a little later) from the number 15 to 21. It was also only three years ago that we came close to implementing what Feynman was talking about, and learn to model the simplest physical systems.
The development of quantum computing is slow. Scientists and engineers face very difficult tasks, quantum states are very short-lived and fragile, and in order to keep them long enough to perform calculations, one has to build tens of millions of dollars of sarcophagi, which are maintained at a temperature just above absolute zero, and which are maximally protected from external influences. In what follows, we will discuss these tasks and problems in more detail.
Leading Players
The slides for this section are taken from the article , from researcher Alexei Fedorov. Let me quote directly:
All technologically successful countries are currently actively engaged in the development of quantum technologies. A huge amount of money is being invested in these studies, special programs are being created to support quantum technologies.
Not only states, but also private companies are participating in the quantum race. In total, Google, IBM, Intel and Microsoft have invested about $ 0,5 billion in the development of quantum computers recently, have created large laboratories and research centers.
There are many articles on Habré and on the Web, for example, , и , in which the current state of affairs with the development of quantum technologies in different countries is considered in more detail. For us, the main thing now is that all the leading technologically developed countries and players are investing heavily in research in this direction, which gives hope for a way out of the current technological impasse.
Directions of development
At the moment (I may be wrong, correct me) the main efforts (and more or less significant results) of all the leading players are focused on two areas:
- Specialized quantum computers, which are aimed at solving one specific specific problem, for example, an optimization problem. An example of a product is D-Wave quantum computers.
- Universal quantum computers - who are able to implement arbitrary quantum algorithms (Shor, Grover, etc.). Implementations from IBM, Google.
Other development vectors that quantum physics gives us, such as:
- as a basis for
- and more
certainly also on the list of areas for research, but there are no more or less significant results at the present time.
Additionally, you can read , well, google “", For example, , и .
Basics. Quantum object and quantum systems
The most important thing to understand from this section is that
Quantum computer (unlike usual) uses as information carriers quantum objects, and for calculations, quantum objects must be connected in quantum system.
What is a quantum object?
quantum object - an object of the microworld (quantum world), which exhibits quantum properties:
- Has a certain state with two boundary levels
- Is in a superposition of its state until the moment of measurement
- Entangles with other objects to create quantum systems
- Fulfills the no-cloning theorem (you can't copy the state of an object)
Let's analyze each property in more detail:
Has a defined state with two boundary levels (final state)
A classic example from the real world is a coin. It has a “side” state, which takes two boundary levels - “heads” and “tails”.
Is in a superposition of its state until the moment of measurement
A coin is tossed and it flies and spins. While it is rotating, it is impossible to tell which of the boundary levels its “side” state is in. But as soon as we slam it down and look at the result, the superposition of states immediately collapses into one of the two boundary states — heads and tails. Clapping a coin in our case is the measurement.
Entangles with other objects to create quantum systems
With a coin it is difficult, but we will try. Imagine we tossed three coins so that they rotate clinging to each other, such juggling with coins. At each moment of time, not only each of them is in a superposition of states, but these states mutually influence each other (the coins collide).
Fulfills the no-cloning theorem (you can't copy the state of an object)
While the coins are flying and rotating, there is no way we can create a copy of the rotating state of any of the coins separate from the system. The system lives in itself and is very jealous of giving out any information.
A couple more words about the concept itself "superpositions", in almost all articles superposition is explained as “is in all states at the same time”, which, of course, is true, but at times it is unnecessarily confusing. The superposition of states can also be imagined as the fact that at each moment of time a quantum object has there are certain probabilities of collapsing into each of its boundary levels, and the sum of these probabilities, of course, is equal to 1. Further, when considering a qubit, we will dwell on this in more detail.
For coins, this can be imagined visually - depending on the initial speed, the angle of toss, the state of the environment in which the coin flies, at each moment in time the probability of getting heads or tails is different. And, as mentioned earlier, the state of such a flying coin can be imagined as “being in all its boundary states at the same time, but with different probability of their realization.”
Any object for which the above properties hold and which we can create and manage can be used as an information carrier in a quantum computer.
A little further we will talk about the current state of affairs with the physical implementation of qubits as quantum objects, and what scientists are now using in this capacity.
So, the third property says that quantum objects can be entangled to create quantum systems. What is a quantum system?
quantum system is a system of entangled quantum objects with the following properties:
- A quantum system is in a superposition of all possible states of the objects of which it consists
- It is impossible to know the state of the system before the measurement
- At the moment of measurement, the system realizes one of the possible variants of its boundary states
(and jumping ahead a bit)
Corollary for quantum programs:
- A quantum program has a given state of the system at the input, a superposition inside, a superposition at the output
- At the output of the program after the measurement, we have a probabilistic realization of one of the possible final states of the system (plus possible errors)
- Any quantum program has a chimney architecture (input -> output. No cycles, you can't see the state of the system in the middle of the process.)
Comparison of a quantum computer and a conventional one
Let's now compare a conventional computer and a quantum one.
| regular computer | Quantum computer | |
|
Logic
|
0 / 1 | `a|0> + b|1>, a^2+b^2=1` |
|
Physics
|
semiconductor transistor | quantum object |
|
Information carrier.
|
Voltage levels | Polarization, spin,… |
|
operations
|
NOT, AND, OR, XOR over bits | Valves: CNOT, Hadamard,… |
|
Interrelation
|
semiconductor chip | Entanglement among themselves |
|
Algorithms
|
Standard (see whip) | Special (Shor, Grover) |
|
Principle
|
Digital, deterministic | analog, probabilistic |
logic level
In a normal computer, this is a bit. Well known to us through and through deterministic bit. Can be either 0 or 1. He does a great job logical unit for a normal computer, but completely unsuitable for describing the state quantum object, which, as we have already said, in the wild is found insuperpositions of their boundary states.
For this they invented . In its boundary states, it implements states similar to 0 and 1 , and in superposition is probability distribution over its boundary states |0> и |1>:
a|0> + b|1>, такое, что a^2+b^2=1a and b are , and the squares of their moduli are the actual probabilities of obtaining just such values of the boundary states |0> и |1>, if you collapse a qubit with a measurement right now.
Physical layer
At the current technological level of development, the physical implementation of a bit for a conventional computer is semiconductor transistor, for quantum, as we have already said, any quantum object. In the next section, we will talk about what is currently used as the physical carriers of qubits.
Storage medium
For a typical computer this is electricity - voltage levels, the presence or absence of current, etc., for quantum - the same state of a quantum object (polarization direction, spin, etc.) that may be in a state of superposition.
operations
To implement logical circuits on a conventional computer, we all use the well-known , for operations on qubits, we had to come up with a completely different system of operations, called . Gates are single-qubit and two-qubit, depending on how many qubits are being transformed.
Examples of quantum gates:
There is a concept universal set of valves, which is enough to perform any quantum computation. For example, a set that includes a Hadamard gate, a phase shift gate, a CNOT gate, and a π⁄8 gate is universal. They can be used to perform any quantum computation on an arbitrary set of qubits.
In this article, we will not dwell on the system of quantum gates, you can read more about them and logical operations on qubits, for example, . The main thing to remember:
- Operations on quantum objects require the creation of new logical operators (quantum gates)
- Quantum gates come in one-qubit and two-qubit
- There are universal sets of gates that can be used to perform any quantum computation.
Interrelation
One transistor is completely useless to us, in order to make calculations we need to connect many transistors to each other, that is, to create a semiconductor chip from millions of transistors, on which we can already build logic circuits, and, ultimately, get a modern processor in its classic form.
One qubit is also completely useless to us (well, if only in academic terms),
to make calculations we need a system of qubits (quantum objects)
which, as we have already said, is created by entangling qubits with each other so that changes in their states occur in concert.
Algorithms
The standard algorithms that mankind has accumulated to date are completely unsuitable for implementation on a quantum computer. Yes, in general, and there is no need. Quantum computers based on gate logic over qubits require the creation of completely different algorithms, quantum algorithms. Three of the most well-known quantum algorithms can be distinguished:
- (factorization)
- (quick search in an unordered database)
- (answer to question, constant or balanced function)
Principle
And the most important difference is the principle of operation. On a standard computer, this digital, rigidly deterministic principle, based on the fact that if we set some initial state of the system and passed it through a given algorithm, then the calculation result will be the same, no matter how many times we run this calculation. Actually, this behavior is exactly what we expect from a computer.
The quantum computer runs on analog, probabilistic principle. The result of the work of the given algorithm on the given initial state is sample from a probability distribution final implementations of the algorithm plus possible errors.
Such a probabilistic nature of quantum computing is due to the very probabilistic essence of the quantum world. “God does not play dice with the universe”, said old Einstein, but all experiments and observations so far (in the current scientific paradigm) confirm the opposite.
Physical implementations of qubits
As we have already said, a qubit can be represented by a quantum object, that is, such a physical object that implements the quantum properties described above. That is, roughly speaking, any physical object in which there are two states and these two states are in a state of superposition can be used to build a quantum computer.
“If we can put an atom in two different levels and control them, then here is a qubit. If we can do that with an ion, it's a qubit. It's the same with current. If we run it clockwise and counterclockwise at the same time, here is a qubit.”
There is к , in which the current variety of physical implementations of the qubit is considered in more detail, we will simply list the most famous and common:
- and many other exotic ideas (anions, etc.)
Of all this variety, the most developed is the first method for obtaining qubits, based on . , , and other leading players use it to build their systems.
Well, read more possible qubits from .
Basics. The principle of operation of a quantum computer
Materials for this section (problem and pictures) are taken from the article .
So let's imagine we have the following task:
There is a group of three people: (A)ndrei, (B)oldya and (C)erezha. There are two taxis (0 and 1).
It is also known that:
- (A) ndrey, (B) olodya - friends
- (A) ndrey, (C) erezha - enemies
- (B) olodya and (C) erezha are enemies
Task: Place the people in a taxi so that Max(friends) и Min(enemies)
Evaluation: L = (number of friends) - (number of enemies) for each accommodation option
IMPORTANT: Assume that there are no heuristics, there is no optimal solution. In this case, the problem is solved only by a complete enumeration of options.
Solution on a regular computer
How to solve this problem on a regular (super)computer (or cluster) - it is clear that loop through all possible options. If we have a multiprocessor system, then we can parallelize the calculation of solutions for several processors and then collect the results.
We have 2 possible accommodation options (taxi 0 and taxi 1) and 3 people. Solution space 2 ^ 3 = 8. You can go through 8 options even on a calculator, this is not a problem. And now let's complicate the task - we have 20 people and two buses, the solution space 2^20 = 1. Nothing complicated either. Let's increase the number of people by 2.5 times - let's take 50 people and two trains, the solution space is now 2^50 = 1.12 x 10^15. A normal (super) computer is already starting to have serious problems. We will increase the number of people by 2 times, 100 people will give us 1.2x10^30 possible options.
That's it, this task cannot be calculated in a reasonable time.
We connect a supercomputer
The most powerful computer is currently the number 1 of , this , performance 122 . Suppose that 100 operations are enough for us to calculate one option, then to solve the problem for 100 people we need:
(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 x 10^37 years.
As we see with an increase in the dimension of the initial data, the space of solutions grows according to a power law, in the general case, for N bits, we have 2 ^ N possible solutions, which, with relatively small N (100), give us an uncomputable (at the current technological level) solution space.
Are there alternatives? As you may have guessed, yes, there is.
But before we move on to how and why quantum computers can effectively solve such problems, let's remember a little about what quantum computers are. probability distribution. Do not be alarmed, the article is a review, there will be no hard mathematics here, we will get by with a classic example with a bag and balls.
Quite a bit of combinatorics, probability theory and a strange experimenter
Take a bag and put it in 1000 white and 1000 black balls. We will conduct an experiment - take out the ball, write down the color, return the ball to the bag and mix the balls in the bag.
Conducted the experiment 10 times drawn 10 black balls. Maybe? Quite. Does this sample give us any reasonable idea of the true distribution in the bag? Obviously not. What needs to be done is rightrepeat the experiment a million times and calculate the frequencies of black and white balls. We get, for example 49.95% black and 50.05% white. In this case, the structure of the distribution from which we sample (take out one ball) is already more or less clear.
The main thing to understand is that the experiment itself has a probabilistic nature, with one sample (ball) we will not know the true structure of the distribution, we need to repeat the experiment many times and average the results.
Let's add to our bag 10 red and 10 green balls (errors). Let's repeat the experiment 10 times. INpulled out 5 red and 5 green. Maybe? Yes. We can say something about the true distribution - No. What needs to be done - well, you understand.
To gain an understanding of the structure of a probability distribution, it is necessary to repeatedly sample individual outcomes from this distribution and average the results.
Connecting theory with practice
Now instead of black and white balls, let's take billiard balls and put them in a bag 1000 balls with number 2, 1000 with number 7 and 10 balls with other numbers. Let's imagine an experimenter who is trained in the simplest actions (get the ball, write down the number, put the ball back into the bag, mix the balls in the bag) and he does it in 150 microseconds. Well, such an experimenter on speeds (not drug advertising !!!). Then in 150 seconds he will be able to conduct our experiment 1 million times. and provide us with the results of the averaging.
They sat the experimenter down, gave him a bag, turned away, waited 150 seconds, and got:
number 2 - 49.5%, number 7 - 49.5%, the rest of the numbers in total - 1%.
Yes that's right, our bag is a quantum computer with an algorithm that solves our problem, and the balls are possible solutions. Since there are two correct solutions, then a quantum computer will give us equally likely any of these possible solutions, and 0.5% (10/2000) errors, which we will discuss later.
To obtain the result of a quantum computer, it is necessary to repeatedly run the quantum algorithm on the same input data set and average the result.
Scalability of a quantum computer
Now imagine that for a task with 100 people (solution space 2^100 we remember this), there are only two correct solutions. Then, if we take 100 qubits and write an algorithm that calculates our objective function (L, see above) over these qubits, then we will get a bag in which there will be 1000 balls with the number of the first correct answer, 1000 with the number of the second correct answer and 10 balls with other numbers. And our experimenter in the same 150 seconds will give us an estimate of the probability distribution of correct answers.
The execution time of a quantum algorithm (with some assumptions) can be considered constant O(1) with respect to the dimension of the solution space (2^N).
And this is precisely the property of a quantum computer - runtime constancy in relation to the complexity of the solution space increasing according to a power law and is the key one.
Qubit and parallel worlds
How does it happen? What allows a quantum computer to calculate so quickly? It's all about the quantum nature of the qubit.
Look, we said that a qubit is like a quantum object. realizes one of its two states when observed, but in "wildlife" is in superpositions of states, that is, it is in both of its boundary states simultaneously (with some probability).
Take (A)ndreya and represent its state (what vehicle it is in - 0 or 1) as a qubit. Then we have (in quantum space) two parallel worlds, in one (BUT) sits in taxi 0, in another world - in taxi 1. Simultaneously in two taxis, but with some probability to find it in each of them when observing.
Take (B) olodu and also represent its state as a qubit. There are two other parallel worlds. But while these pairs of worlds (BUT) и (AT) do not interact at all. What needs to be done to create bound system? That's right, we need these qubits to tie up (to confuse). We take and confuse (A) with (B) - we get a quantum system of two qubits (A, B) realizing within itself four interdependent parallel worlds. Adding (C) Sergey and get a system of three qubits (ABC), implementing eight interdependent parallel worlds.
The essence of quantum computing (implementation of a chain of quantum gates over a system of connected qubits) is the fact that the calculation takes place in all parallel worlds simultaneously.
And it doesn't matter how many we have, 2^3 or 2^100, the quantum algorithm will execute in finite time over all these parallel worlds and will give us the result, which is a sample from the probability distribution of the algorithm's responses.
For a better understanding, one can imagine that a quantum computer at the quantum level runs 2^N parallel decision processes, each of which works on one possible option, then collects the results of the work - and gives us the answer in the form of a superposition of the solution (probabilistic distribution of responses), from which we each time (for each experiment) sample one.
Remember the time required by our experimenter (150 µs) for the experiment, this will be useful to us a little later, when we talk about the main problems of quantum computers and about the decoherence time.
Quantum Algorithms
As already mentioned, conventional algorithms based on binary logic are not applicable to a quantum computer using quantum logic (quantum gates). For him, he had to come up with new ones that fully use the potential inherent in the quantum nature of computing.
The most well-known algorithms today are:
Unlike classical computers, quantum computers are not universal.
So far, only a small number of quantum algorithms have been found.
Thank you for a link to , the place where, according to the author (), the best representatives of the quantum-algorithmic world have been gathered and continue to gather.
In this article, we will not analyze quantum algorithms in detail, there are many excellent materials on the Web for any level of complexity, but it is still necessary to briefly go over the three most famous ones.
Shor's algorithm.
The most famous quantum algorithm is (invented in 1994 by an English mathematician ), which is aimed at solving the problem of factoring numbers into prime factors (the problem of factorization, discrete logarithm).
It is this algorithm that is cited as an example when they write that your banking systems and passwords will soon be hacked. Given that the length of the keys used today is at least 2048 bits, the time for the cap has not yet come.
Today more than modest. Best Factorization Results with Shor's Algorithm - Numbers и , which is much less than 2048 bits. For the rest of the results from the table, a different calculations, but even the best result (291311) according to this algorithm is far from real application.
You can read more about the Shor algorithm, for example,. About practical implementation - .
One of complexity and power required to factorize a number of 2048 bits is a computer with . We sleep peacefully.
Grover's algorithm
— solving the enumeration problem, that is, finding a solution to the equation F(X) = 1, where F is from n variables. It was proposed by an American mathematician в .
Grover's algorithm can be used to find и number line. Moreover, it can be used to solve problems by exhaustive search among the many possible solutions. This can result in a significant speed boost over classical algorithms, although without providing "" in general.
You can read more, or . Yet there is a good explanation of the algorithm using boxes and a ball as an example, but, unfortunately, for reasons beyond anyone's control, this site does not open for me from Russia. If you have is also blocked, then here is a brief squeeze:
Grover's algorithm. Imagine that you have N pieces of numbered closed boxes. They are all empty except for one, which contains the ball. Your task is to find out the number of the box that contains the ball (this unknown number is often denoted by the letter w).
How to solve this problem? The dumbest way is to take turns opening the boxes, and sooner or later you will stumble upon a box with a ball. And how many boxes, on average, must be checked before a ball box is found? On average, you need to open about half of the N / 2 boxes. The main point here is that if we increase the number of boxes by 100 times, then the average number of boxes that need to be opened before the ball box is found will also increase by the same 100 times.
Now let's make one more clarification. Suppose we do not open the boxes ourselves with our hands and check the presence of a ball in each, but there is a certain intermediary, let's call it the Oracle. We tell the Oracle “check box number 732”, and the Oracle honestly checks and answers “there is no ball in box number 732”. Now instead of talking about how many boxes we need to open on average, we say "how many times on average we have to go to the Oracle in order to find the number of the ball box"
It turns out that if we translate this problem with boxes, a ball and the Oracle into quantum language, then we get a wonderful result: to find the number of a box with a ball among N boxes, we need to disturb the Oracle only about SQRT(N) times!
That is, the complexity of the enumeration task using Grover's algorithm is reduced by the square root of times.
Deutsch-Joji algorithm
Deutsch-Joji algorithm (also referred to as Deutsch-Josa algorithm) - [quantum algorithm](%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный и в , and became one of the first examples of algorithms designed to be executed on . _
The Deutsch-Joji problem is to determine whether the function of several binary variables F(x1, x2, ... xn) is constant (it takes either the value 0 or 1 for any arguments) or balanced (it takes the value 0 for half of the domain of definition, and the value 1 for the other half XNUMX). In this case, it is considered a priori known that the function is either constant or balanced.
You can still read . A simpler explanation:
The Deutsch (Deutsch-Jozhi) algorithm is based on enumeration, but allows you to do it faster than usual. Imagine that there is a coin on the table and you need to find out if it is fake or not. To do this, you need to look at the coin twice and determine: “heads” and “tails” are real, two “eagles”, two “tails” are fake. So, if we use the quantum Deutsch algorithm, then this definition can be made at a glance - measurement.
Problems of quantum computers
When designing and operating quantum computers, scientists and engineers face a huge number of problems that are currently being solved with varying degrees of success. According to () the following problems can be identified:
- Sensitivity to the environment and interaction with the environment
- Accumulation of errors in calculations
- Difficulties with initial initialization of qubit states
- Difficulties with creating multi-qubit systems
I highly recommend reading the article”, especially the comments to it.
Let's organize all the main problems into three large groups and consider each of them in more detail:
Decoherence
.
Quantum state very fragile thing, entangled qubits are extremely unstable, any external influence can destroy (and destroys) this connection. A change in temperature by the smallest fraction of a degree, pressure, a random photon flying nearby - all this destabilizes our system.
To solve this problem, low-temperature sarcophagi are being built, in which the temperature (-273.14 degrees Celsius) is slightly above absolute zero, with maximum isolation of the internal chamber with the processor from all (possible) environmental influences.
The maximum lifetime of a quantum system of several entangled qubits, during which it retains its quantum properties and can be used to perform calculations, is called the decoherence time.
Currently, the decoherence time in the best quantum solutions is on the order of tens and hundreds of microseconds.
There is a lovely where you can see all created quantum systems. In this article, for example, only two top-end processors are taken out - from IBM and from . As we can see, the decoherence time (T2) does not exceed 200 μs.
I did not find exact data on Sycamore, but in the two figures are given 1 million calculations in 200 seconds, in another place for 130 seconds without loss to control signals and more. Either way, this gives us decoherence time about 150 µs. Remember our experimenter with bag? Well, here he is.
| computer Name | N Qubits | Max paired | T2 (µs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~ 150-200 |
What threatens us with decoherence?
The main problem is that after 150 µs, our computing system of N entangled qubits will start to output instead of the probabilistic distribution of correct solutions - probabilistic white noise.
That is, we need:
- Initialize qubit system
- Perform calculation (chain of gate operations)
- Read result
And do all this in 150 µs. I didn’t have time - the result turned into a pumpkin.
But that's not all…
Errors
As we said, quantum processes and quantum computing are probabilistic in nature, we cannot be 100% sure of anything, but only with some probability. The situation is further aggravated by the fact that quantum computing is error prone. The main types of errors in quantum computing are:
- Decoherence errors due to system complexity and interaction with the external environment
- Computational gate errors (due to the quantum nature of computing)
- Errors in reading the final state (result)
Errors related to decoherence, arise as soon as we have entangled our qubits and started doing calculations. The more qubits we entangle, the more complex the systemand the easier it is to destroy. Low-temperature sarcophagi, protected chambers, all these technological tricks are just aimed at reducing the number of errors and prolonging the decoherence time.
Computational Gate Errors - any operation (gate) on qubits can, with some probability, fail, and we need to execute hundreds of gates to implement the algorithm, so imagine what we will get at the end of our algorithm. The classic answer to the question - "What is the probability of meeting a dinosaur in an elevator?" - 50x50, or you will meet or not.
The problem is further aggravated by the fact that standard error correction methods (duplication of calculations and averaging) do not work in the quantum world due to the no-cloning theorem. For in quantum computing had to invent . Roughly speaking, we take N ordinary qubits and make 1 of them logic qubit with fewer errors.
But here another problem arises - total number of qubits. Look, let's say we have a processor with 100 qubits, of which 80 qubits are occupied by error correction, then we only have 20 left for calculations.
Errors in reading the final result - as we remember, the result of quantum computing is presented to us in the form probability distribution of answers. But reading the final state can also fail.
On the same there are comparative tables of processors by error levels. For comparison, let's take the same processors as in the previous example - IBM и :
| Desktop | 1-Qubit Gate Fidelity | 2-Qubit Gate Fidelity | Readout Fidelity |
| IBM Q System One | Present in several = 99.96% | Present in several = 98.31% | — |
| Google Sycamore | Present in several = 99.84% | Present in several = 99.38% | Present in several = 96.2% |
Here is a measure of the similarity of two quantum states. The magnitude of the error can be roughly represented as 1-Fidelity. As we can see, errors on 2-qubit gates and reading errors are the main obstacle to the execution of complex and long algorithms on existing quantum computers.
You can still read years from for solving the problem of error correction.
Processor architecture
In theory, we build and operate schemes of dozens of entangled qubits, but in reality it is more complicated. All existing quantum chips (processors) are built in such a way that they provide a painless entanglement of one qubit with only its neighbors, which is not more than six.
If we need to confuse the 1st qubit with, say, the 12th, then we have to build a chain of additional quantum operations, use additional qubits, and so on, which increases the overall level of errors. Yes, and don't forget decoherence time, perhaps by the time you finish linking the qubits into the circuit you need, time will run out and the whole circuit will turn into nice white noise generator.
Also don't forget that the architecture of all quantum processors is different, and the program written in the emulator in the “connectivity of all with all” mode will need to be “recompiled” into the architecture of a particular chip. There are even to perform this operation.
Maximum connectivity and maximum number of qubits for the same top-end chips:
| computer Name | N Qubits | Max paired | T2 (µs) |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~ 150-200 |
And, for comparison, table with data of the previous generation of processors. Compare the number of qubits, decoherence time and error rate with what we have now with the new generation. Still, progress is slowly, but moving.
So:
- At the moment there are no fully connected architectural schemes of > 6 qubits
- In order to confuse a 0 s qubit on a real processor, for example, the 15th qubit may require several dozen additional operations
- More operations -> more errors -> stronger effect of decoherence
Results
Decoherence is the Procrustean bed of modern quantum computing. In 150 µs we have to fit everything:
- Initialization of the initial state of qubits
- Computing a Problem Using Quantum Gates
- Carry out error correction to get a meaningful result
- Read the result
So far, the results are disappointing, although claim to achieve 0.5s coherence retention time on a quantum computer based on :
We measure a qubit coherence time in excess of 0.5 s, and with magnetic shielding we expect this to improve to be longer than 1000 s
Read more about this technology or, for example, .
The situation is further complicated by the fact that when performing complex calculations, it is necessary to use quantum error correction schemes, which also eats up both time and available qubits.
And, finally, modern architectures do not allow implementing entanglement schemes better than 1 to 4 or 1 to 6 at minimal cost.
Problem solving
To solve the above problems, the following approaches and methods are currently used:
- Use of cryochambers with low temperatures (10 mK (-273,14°C))
- Use of processor units that are maximally protected from external influences
- Using quantum error correction systems (Logic qubit)
- Using optimizers when programming circuits for a specific processor
Research is also being carried out aimed at increasing the decoherence time, searching for new (and improving known) physical implementations of quantum objects, optimizing correction schemes, and so on and so forth. There is progress (look above at the characteristics of earlier and today's top chips), but so far it is going slowly, very very slowly.
D-Wave
2000-qubit D-Wave 2000Q computer. Source:
Against the background of Google's claim to achieve quantum supremacy using a processor with 53 qubits, и from the D-Wave company, in which the number of qubits is in the thousands, is somewhat confusing. Well, indeed, if 53 qubits could achieve quantum supremacy, then what is a computer with 2048 qubits capable of? But not everything is so good...
In short (taken from the wiki):
Computers work on the principle () can solve a very limited subclass of optimization problems, and are not suitable for implementing traditional quantum algorithms and quantum gates.
For more details, see, for example, , (carefully, it may not open from Russia), or в out of it . By the way, I highly recommend reading his blog in general, there is a lot of good material there.
In general, from the very beginning of the announcements, the scientific community had questions about D-Wave computers. For example, in 2014, IBM questioned the fact that D-Wave It got to the point that in 2015, Google, together with NASA, bought one of these quantum computers, and after research that yes, the computer works and calculates the task faster than usual. You can read more about Google's statement and for example .
The main thing is that D-Wave computers, with their hundreds and thousands of qubits, cannot be used to calculate and run quantum algorithms. You can't run Shor's algorithm on them, for example. All they can do is use certain quantum mechanisms to solve a certain optimization problem. We can assume that D-Wave is such a quantum ASIC for a specific task.
A little about the emulation of quantum computers
Quantum computing can be emulated on a conventional computer. Indeed, :
- The state of the qubit can be complex number, occupying from 2x32 to 2x64 bits (8-16 bytes) depending on the processor architecture
- The state of N bound qubits can be represented as 2^N complex numbers, i.e. 2^(3+N) for 32-bit architecture and 2^(4+N) for 64-bit architecture.
- A quantum operation on N qubits can be represented by a 2^N x 2^N matrix
Then:
- To store the emulated states of 10 qubits, 8 KB are needed
- To store the states of 20 qubits, 8 MB are needed
- To store the states of 30 qubits, you need 8 GB
- To store the states of 40 qubits, 8 terabytes are needed
- It takes 50 petabytes to store the states of 8 qubits, and so on.
For comparison, () carries only 2.8 Petabytes of memory.
— 49 qubit delivered last year on the largest Chinese supercomputer ()
The limit of quantum computer simulation on classical systems is determined by the amount of RAM required to store the state of qubits.
I recommend to read more . From there:
By operations - for accurate emulation of a circuit for 49 qubits from some 39 "cycles" (independent layers of gates) 2^63 complex multiplications - 4 pflops supercomputer for 4 hours
Emulation of a quantum computer of 50+ qubits on classical systems is considered unfeasible in a reasonable amount of time. One of the reasons why Google used a processor with 53 qubits for its quantum supremacy experiment.
Quantum computing superiority.
Wikipedia gives us the following definition of quantum computing superiority:
Quantum supremacy is the ability devices to solve problems that classical computers are practically unable to solve.
In fact, the achievement of quantum superiority means that, for example, the factorization of large numbers by the Shor algorithm can be solved in adequate time, or complex chemical molecules can be emulated at the quantum level, and so on. That is, a new era has begun.
But there is a loophole in the wording of the definition, “which classical computers are practically unable to solve". In fact, this means that if you create a quantum computer of 50+ qubits and run some quantum circuit on it, then, as we discussed above, the result of this circuit cannot be simulated on a conventional computer. That is a classic computer will not be able to recreate the result of such a circuit.
Whether such a result is a real quantum superiority or not is more of a philosophical question. But to understand what Google has done and what it is based on necessary.
Google's Quantum Supremacy Statement
54 qubit Sycamore processor
So, in October 2019, Google developers published an article in the scientific publication Nature “". The authors announced the achievement of quantum supremacy for the first time in history using the 54-qubit "Sycamore" processor.
On the web in articles, Sycamore is often referred to either as a 54-qubit processor, or as a 53-x one. The truth is that according to , the processor physically consists of 54 qubits, but one of them is non-working and decommissioned. Thus, in reality, we have a 53-qubit processor.
On the web right now materials on this topic, the degree of which ranged from to .
Later, employees of the quantum computing department of IBM stated that . The company claims that a conventional calculator will cope with this task in the worst case in 2,5 days, and at the same time the answer will be more accurate than that of a quantum computer. This conclusion was made based on the results of the theoretical analysis of several optimization methods.
Well and of course before could not ignore this statement. His along with all links and As usual, they are worth your time. On Habré of this FAQ, and be sure to read the comments, there are links to preliminary documents leaked to the Web before the official announcement.
What has Google actually done? For a detailed understanding, read Aaronson, and briefly here:
I can, of course, tell you, but I feel stupid about it. The calculation is as follows: the experimenter generates a random quantum circuit C (i.e., a random sequence of 1-qubit and 2-qubit gates between nearest neighbors, with a depth of, for example, 20, acting on a 2D network of n=50-60 qubits). After that, the experimenter sends C to the quantum computer, and asks him to apply C to an initial state of 0, measure the result in the {0,1} basis, send back an n-bit observed sequence (string) and repeat several thousand or million times. Finally, using his knowledge of C, the experimenter performs a statistical check to see if the result matches the expected output from the quantum computer.
Quite briefly:
- A random circuit of length 20 out of 53 qubits is created using gates
- The circuit starts with the initial state [0…0] for execution
- The output of the circuit is a random bit string (sample)
- The distribution of the result is not random (interference)
- The distribution of received samples is compared with the expected one
- The conclusion about quantum superiority is made
That is, Google has implemented a synthetic task on a 53-qubit processor, and bases its claim of achieving quantum superiority on the fact that it is impossible to emulate such a processor on standard systems in a reasonable time.
For understanding - this section does not detract from the achievement of Google, engineers are really great, and the question of whether this can be considered real quantum superiority or not, as mentioned earlier, is more philosophical than engineering. But we must understand that having achieved such a computational superiority, we have not moved a single step towards the ability to run the Shor algorithm on 2048-bit numbers.
Summary
Quantum computers and quantum computing is a very promising, very young and still little industrially applicable area of information technology.
The development of quantum computing will allow (someday) to solve problems:
- Modeling complex physical systems at the quantum level
- Unsolvable on a conventional computer due to computational complexity
The main problems in the creation and operation of quantum computers:
- Decoherence
- Errors (decoherence and gating)
- Processor architecture (fully connected qubit circuits)
Current state of affairs:
- In fact, the very first .
- There is no REAL commercial operation yet (and it is not clear when it will be)
What can help:
- Some kind of physical discovery that reduces the cost of tying and operating processors
- Discovery of something that will increase decoherence time by an order of magnitude and/or reduce errors
In my opinion (solely personal opinion), in the current scientific paradigm of knowledge, we will not achieve significant success in the development of quantum technologies, here we need a qualitative breakthrough in some area of fundamental or applied science, which will give impetus to new ideas and methods.
In the meantime, we are gaining experience in quantum programming, assembling and creating quantum algorithms, testing ideas, and so on and so forth. Looking forward to a breakthrough.
Conclusion
In this article, we walked through the main milestones in the development of quantum computing and quantum computers, analyzed the principle of their operation, considered the main problems that engineers face in the development and operation of quantum processors, and also looked at what multi-qubit computers actually are D- Wave and Google's recent announcement of achieving quantum supremacy.
Behind the scenes were the questions of programming quantum computers (languages, approaches, methods, etc.) and questions related to the specific physical implementation of processors, how qubits are controlled, bound, read, etc. Perhaps this will be the topic of the next article or articles.
Thank you for your attention, I hope this article will be useful to someone.
(C)
Acknowledgements
for proofreading and comments on the original text, as well as for the article
for informative comments on , and not only to her, which in many ways helped me deal with this puzzle.
To all authors of articles and publications whose materials were used in writing this article.
List of resources
Current State Articles from [The National Academies Press]
Articles from Habr (in random order)
Unsorted (but no less interesting) articles from the vastness of the Web
Courses and lectures
Source: habr.com