Quantum computers and quantum computing are a new , which has joined our information space alongside , and other high-tech terms. However, I have yet to find material online that could piece together the puzzle titled âhow quantum computers workâ. Yes, there are many excellent works, including those on Habr (see ), the comments to which are, as is often the case, even more informative and useful, but the picture in my head, so to speak, just wasnât coming together.
Recently, colleagues approached me and asked, âDo you understand how a quantum computer works? Can you explain it to us?â And it struck me that the challenge of piecing together a coherent picture is not mine alone.
As a result, an attempt was made to compile information about quantum computers into a coherent logical scheme, which would explain at a basic level, without delving deeply into the mathematics and structure of the quantum world, what a quantum computer is, on what principles it operates, and also what problems scientists face in its creation and operation.
Table of Contents
Disclaimer
The author is not a specialist in quantum computing, and the target audience of the article consists of similar IT professionals, not quantum specialists, who also want to piece together a picture titled âHow quantum computers work.â Due to this, many concepts in the article are consciously simplified for better understanding of quantum technologies at a âbasicâ level, yet without .
In the article, some sections use materials from other sources, Wherever possible, direct links and references to the original text, table, or figure have been inserted. If I forgot something (or someone) anywhere, please let me knowâI will correct it.
Introduction
In this chapter, we'll briefly review how the quantum era began, what prompted the idea of quantum computers, which countries and corporations are currently the leading players in this field, and we will also touch on the main directions of development in quantum computing.
How It All Started
The starting point of the quantum era is generally considered to be the year 1900, when M. Planck first proposed that energy is emitted and absorbed not continuously, but in discrete quanta (packets). This idea was picked up and developed by many outstanding scientists of that timeâBohr, Einstein, Heisenberg, Schrödingerâwhich ultimately led to the creation and development of the science known as There are many good resources online about the development of quantum physics as a science; we won't go into detail on this in this article, but it was necessary to indicate the date when we entered a new quantum era.
Quantum physics has brought many inventions and technologies into our everyday lives that are now hard to imagine living without. For example, the laser, which is now used everywhere, from household devices (laser levels and more) to high-tech systems (lasers for vision correction, hello ). It would be logical to assume that sooner or later someone would propose the idea of using quantum systems for computations. And in 1980, it happened.
Wikipedia indicates that the first to propose the idea of quantum computing in 1980 was our scientist Yuri Manin. However, it was not until 1981 that it gained attention, when the well-known R. Feynman, in noted that it is impossible to effectively simulate the evolution of a quantum system on a classical computer. He proposed a simple model of that would be capable of performing such simulations.
There is , which includes This is considered more academically and in detail; we will give a brief overview:
Key milestones in the history of quantum computers:
- [1994]. P. Shor. Developed
- [1998]. Created
- [2001]. IBM demonstrated the execution to factor the number 15
- [2007-2016]. develops and advances a computer with 128-2000 qubits
- [2012]. At the University of California, implemented
- [2016]. Google on a 9-qubit computer
- [2017]. (three atoms)
- [2019]. . A 20-qubit computer in the cloud
- [2019]. . A 53-qubit computer. ?
As you can see, it took 17 years (from 1981 to 1998) from the idea to its first implementation in a 2-qubit computer, and 21 years (from 1998 to 2019) for the number of qubits to increase to 53. It took 11 years (from 2001 to 2012) to improve the result of Shor's algorithm (we will discuss it in more detail shortly) from 15 to 21. Also, just three years ago, we approached what Feynman spoke about and learned to model the simplest physical systems.
The development of quantum computing is slow. Scientists and engineers face very complex tasks; quantum states are very ephemeral and fragile, and in order to preserve them long enough for computation, they have to build sarcophagi costing tens of millions of dollars, which maintain a temperature just above absolute zero and are maximally protected from external influences. We will discuss these tasks and problems in more detail later.
Leading players
Slides for this section were taken from the article , by researcher Alexey Fedorov. I will allow myself to use direct quotes:
All technologically successful countries are currently actively developing quantum technologies. A huge amount of funding is being invested in this research, special support programs for quantum technologies are being created.
In the quantum race, not only states but also private companies are participating. In total, Google, IBM, Intel, and Microsoft have invested about $0.5 billion in the development of quantum computers recently, creating large laboratories and research centers.
There are many articles on Habr and the internet, for example, , and , in which the current state of development of quantum technologies in different countries is discussed in more detail. What is most important for us now is that all leading technologically advanced countries and players are investing huge amounts of money into research in this area, which gives hope for a way out of the current technological deadlock.
Development directions
At the moment (I could be wrong, please correct me) the main efforts (and more or less significant results) of all leading players are focused on two directions:
- Specialized quantum computers, which are aimed at solving one specific task, for example, optimization problems. An example product includes D-Wave quantum computers.
- Universal quantum computers â which are capable of executing arbitrary quantum algorithms (Shor's, Grover's, etc.). Implementations from IBM, Google.
Other development vectors offered by quantum physics, such as:
- as a foundation for
- and much more
are also definitely on the list of research directions, but as of now, there seem to be no more or less significant results.
Additionally, you can read , and you can also Google ââ, for example, , and .
Basics. Quantum objects and quantum systems
The most important thing to understand from this section is that
A quantum computer (unlike a classical one) uses quantum objects, and for computations, quantum objects must be connected in a quantum system..
What is a quantum object?
A quantum object â an object of the micro world (quantum world), which exhibits quantum properties:
- Has a definite state with two boundary levels
- Exists in a superposition of its state until measurement occurs
- Entangles with other objects to form quantum systems.
- Implements the no-cloning theorem (you cannot copy the state of an object)
Let's examine each property in more detail:
Has a specific state with two boundary levels (final state)
A classic real-world example is a coin. It has a state of 'face' that takes two boundary levels - 'heads' and 'tails'.
Exists in a superposition of its state until measurement occurs
We tossed the coin, and it is spinning. While it spins, it is impossible to determine which of the boundary levels its state 'face' is in. But as soon as we catch it and look at the result â the superposition of states collapses into one of the two boundaries â 'heads' or 'tails'. 'Catching' the coin in our case is the measurement.
Entangles with other objects to form quantum systems.
Itâs difficult with the coin, but letâs try. Imagine we tossed three coins so that they spin, linking with each other, such as in juggling coins. At every moment in time, not only is each one in a superposition of states, but these states mutually influence each other (the coins collide).
Implements the no-cloning theorem (you cannot copy the state of an object)
While the coins are flying and spinning, we cannot create a separate copy of the rotating state of any of the coins separate from the system. The system lives on its own and is very protective about releasing any information outside.
A couple more words about the concept of âsuperpositionâ, in practically all articles, superposition is explained as âbeing in all states simultaneously,â which, of course, is correct, but sometimes it can be overly confusing. Superposition of states can also be understood as the fact that at every moment in time, a quantum object has certain probabilities of collapsing into each of its boundary levels, and in total, these probabilities equal 1.Further, when considering a qubit, we will elaborate on this more specifically.
For the coins, it can be visualized â depending on the initial speed, the angle of the toss, and the state of the surrounding environment in which the coin flies, at every moment in time, the probability of getting 'heads' or 'tails' varies. And, as mentioned earlier, the state of such a flying coin can be imagined as 'being in all of its boundary states simultaneously, but with different probabilities of their realization.'
Any object that meets the aforementioned properties and that we can create and manage can be used as an information carrier in a quantum computer.
A little further on, we will talk about the current state of affairs regarding the physical realization of qubits as quantum objects and what scientists are currently using for this purpose.
Thus, the third property states that quantum objects can become entangled to create quantum systems. What is a quantum system?
Quantum system â a system of entangled quantum objects that possesses the following properties:
- A quantum system is in a superposition of all possible states of the objects from which it consists.
- One cannot know the state of the system until the moment of measurement.
- At the moment of measurement, the system realizes one of the possible variants of its boundary states.
(and, looking ahead slightly)
Implication for quantum programs:
- A quantum program has a given system state as input, a superposition inside, and a superposition as output.
- At the output of the program after 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, cannot look at the state of the system in the middle of the process.)
Comparison of quantum computers and classical ones
Now let's compare a conventional computer and a quantum one.
| Conventional computer | A quantum computer | |
Logic | 0 / 1 | `a|0> + b|1>, a^2+b^2=1` |
Physics | Semiconductor transistor | A quantum object |
Information carrier | Voltage levels | Polarization, spin,⊠|
Operations | NOT, AND, OR, XOR over bits | Gates: CNOT, Hadamard,⊠|
Interconnection | Semiconductor chip | Entanglement with each other |
Algorithms | Standard (see Knuth) | Special (Shor, Grover) |
Principle | Digital, deterministic | Analog, probabilistic |
Logical level
In a conventional computer, this is a bit. Well-known to us throughout. A deterministic bit. It can take values of either 0 or 1. It perfectly fulfills the role of a logical unit for a conventional computer, but is completely unsuitable for describing the state of a quantum object, which, as we have already mentioned, inherently exists in asuperposition of its boundary states..
For this purpose, they invented . In its boundary states, it realizes states similar to 0 and 1 , and in superposition represents a probability distribution over its boundary states |0> and |1>:
a|0> + b|1>, such that a^2 + b^2 = 1a and b represent , and the squares of their moduli are the actual probabilities of obtaining those specific boundary state values |0> and |1>, if we collapse the qubit by measurement right now.
Physical Layer
At the current level of technological development, the physical implementation of a bit for a conventional computer is a semiconductor transistor, and for a quantum computer, as we mentioned, any quantum object. In the next section, we will discuss what is currently used as physical carriers of qubits.
Information carrier
For a conventional computer, this is electric current â voltage levels, presence or absence of current, etc., while for quantum, it's precisely the state of the quantum object (polarization direction, spin, etc.), which can be in a state of superposition.
Operations
To implement logical circuits on a conventional computer, we use well-known , but for operations on qubits, we had to devise a completely different system of operations called . Gates can be single-qubit or two-qubit, depending on how many qubits the transformation is performed on.
Examples of quantum gates:
There is a concept of a universal set of gates, which is enough to perform any quantum computation. For example, a universal set includes the Hadamard gate, the phase shift gate, the CNOT gate, and the Ï/8 gate. With these, you can perform any quantum computation on an arbitrary set of qubits.
In this article, we will not go into detail about the system of quantum gates, more information about them and logical operations on qubits can be found, for example, . The main thing to remember is that
- Operations on quantum objects require the creation of new logical operators (quantum gates)
- Quantum gates can be single-qubit or two-qubit
- There are universal sets of gates that allow performing any quantum computation
Interconnection
One transistor is completely useless for performing computations; we need to connect many transistors together, creating a semiconductor chip made of millions of transistors on which logical circuits can be built. and ultimately obtain a modern processor in its classic form.
One qubit is also completely useless (well, at least from an academic perspective),
to perform computations we need a system of qubits (quantum objects)
which, as we mentioned, is created by entangling qubits with each other so that their state changes occur coherently.
Algorithms
The standard algorithms that humanity has accumulated up to this point are completely unsuitable for implementation on a quantum computer. In fact, there is no need for them. Quantum computers based on gate logic over qubits require the development of entirely different algorithms, quantum algorithms. Among the most well-known quantum algorithms, three stand out:
- (factorization)
- (fast search in an unordered database)
- (answer to the question of whether a function is constant or balanced)
Principle
And the most important difference is the principle of operation. For a standard computer, it is a digital, strictly deterministic principle, based on the idea that if we set an initial state of the system and run it through a given algorithm, the result of the computation will be the same no matter how many times we execute it. Essentially, this behavior is exactly what we expect from a computer.
A quantum computer operates on an analog, probabilistic principle. The result of executing a given algorithm on a specific initial state represents a sample from a probability distribution of the final realizations of the algorithm plus potential errors.
This probabilistic nature of quantum computations is conditioned by the inherently probabilistic nature of the quantum world. "God does not play dice with the universe,"Einstein once said, yet all experiments and observations so far (within the current scientific paradigm) confirm the opposite.
Physical implementations of qubits
As we mentioned, a qubit can be represented by a quantum object, meaning a physical object that exhibits the quantum properties described above. In simple terms, any physical object that has two states and those two states are in a superposition can be used to build a quantum computer.
If we can place an atom in two different levels and control them, then here's your qubit. If we can do this with an ion, that's a qubit. It's the same with current. If we run it clockwise and counterclockwise simultaneously, there's your qubit.
There is to , in which the current variety of physical realizations of a qubit is examined in more detail, we will just list the most well-known and common ones:
- and many other exotic ideas (anyons and others)
Of all this diversity, the most developed is the first method of obtaining qubits based on . , , and other leading players use this method to build their systems.
And also read about possible of qubits by .
Basics. The principle of operation of a quantum computer
The materials for this section (task and images) are taken from the article .
So, let's imagine that we have the following task:
There is a group of three people: (A)ndrey, (B)olodiya, and (C)erezhĐ°. There are two taxis (0 and 1).
It is also known that:
- (A)ndrey and (B)olodiya are friends
- (A)ndrey and (C)erezhĐ° are enemies
- (B)olodiya and (C)erezhĐ° are enemies
Task: Place people in taxis so that Max(friends) and Min(enemies)
Evaluation: L = (number of friends) - (number of enemies) for each placement option
IMPORTANT: Assume that there are no heuristics, there is no optimal solution. In this case, the task is solved only by exhaustively examining the options.
Solution on a regular computer
How to solve this problem on a regular (super)computer (or cluster) â it is clear that we need to cycle through all possible options. If we have a multiprocessor system, we can parallelize the calculation of solutions across several processors and then gather the results.
We have 2 possible placement options (taxi 0 and taxi 1) and 3 people. Solution space 2^3 = 8You can evaluate 8 options even on a calculator; it's not a problem. Now let's complicate the task â we have 20 people and two buses, the solution space 2^20 = 1 048 576. is also not too complicated. Let's increase the number of people by 2.5 times â we'll take 50 people and two trains, and now the solution space is 2^50 = 1.12 x 10^15. A regular (super)computer already encounters serious problems. Doubling the number of people, 100 people will give us 1.2 x 10^30 possible options.
That's it, this task cannot be computed in a reasonable time.
We connect a supercomputer
The most powerful computer currently is ranked number 1 in . To keep this information confidential, , with a performance of 122 Assuming that calculating one option requires 100 operations, then to solve the task for 100 people we would need:
(1.2 x 10^30 100) / 122Ă10^15 / (606024365) = 3 x 10^37 years.
As we can see, with the increase in the dimensionality of the initial data, the solution space grows according to a power law,in general for N bits we have 2^N possible solution options, which for relatively small N (100) gives us an incomputable (at the current technological level) solution space.
Are there alternatives? As you might guess, yes, there are.
But before we delve into how and why quantum computers can effectively solve such tasks, let's briefly recall what a probability distributionis. Don't worry, this is a review article; there won't be any hard math, we'll manage with a classic example of a bag and balls.
Just a bit of combinatorics, probability theory, and a strange experimenter.
Let's take a bag and put into it 1000 white and 1000 black balls.We will conduct an experiment â draw a ball, record its color, return the ball to the bag, and mix the balls in the bag.
We conducted the experiment 10 times, pulled out 10 black balls.Is this possible? Quite so. Does this sample give us a reasonable notion of the true distribution in the bag? Obviously not. What should we do? Correct, we need torepeat the experiment a million times and calculate the frequencies of black and white balls. For example, we might get 49.95% black and 50.05% white.In this case, the structure of the distribution from which we sample (draw one ball) is already somewhat clearer.
The main point to understand is that the experiment itself has a probabilistic nature., with a single sample (ball) we cannot discern the true structure of the distribution, we need to repeat the experiment multiple times and average the results.
Let's add to our bag 10 red and 10 green balls (errors). We will repeat the experiment 10 times. Inwe pulled out 5 red and 5 green. Is it possible? Yes. Can we say something about the true distribution â No. What should we do â well, you get the idea.
To gain an understanding of the structure of the probability distribution, we need to sample individual outcomes from this distribution multiple times and average the results.
Connecting theory to practice
Now instead of black and white balls, let's take billiard balls and put in the bag 1000 balls with the number 2, 1000 with the number 7, and 10 balls with other numbers. Imagine an experimenter who is trained in simple actions (pulling out a ball, writing down the number, putting the ball back in the bag, mixing the balls in the bag) and he does this in 150 microseconds. A speed-fueled experimenter (not advertising drugs!!!). Then in 150 seconds, he could conduct our experiment 1 million times and provide us with the results of averaging.
We seated the experimenter, gave him the bag, turned away, waited 150 seconds â and got:
number 2 â 49.5%, number 7 â 49.5%, the other numbers in total â 1%.
Yes, that's correct, our bag is a quantum computer with an algorithm solving our problem, and the balls are possible solutions. Since there are two correct solutions, the quantum computer will give us either of these possible solutions with equal probability, and 0.5% (10/2000) errors, which we will discuss later.
To achieve the result from a quantum computer's operation, we need to run the quantum algorithm multiple times on the same input data set and average the results.
Scalability of the quantum computer
Now imagine that for a task involving 100 people (the solution space 2^100 we remember this), there are also only two correct solutions. Therefore, if we take 100 qubits and write an algorithm that computes our target function (L, see above) over these qubits, we will obtain a bag containing 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 will provide us with an estimate of the probability distribution of the correct answers in just 150 seconds..
The execution time of a quantum algorithm (with some assumptions) can be considered constant O(1) relative to the dimensionality of the solution space (2^N).
And this property of quantum computers is precisely the constancy of execution time relative to the increasing exponentially complex solution space, which is key.
Qubit and parallel worlds
How does this happen? What allows a quantum computer to perform calculations so quickly? It's all about the quantum nature of qubits.
Look, we said that a qubit, as a quantum object realizes one of its two states when observed, but in its "natural state" is in a superposition of states, meaning it exists in both of its boundary states simultaneously (with some probability).
Letâs take (A)ndrey and represent his state (which vehicle he is in â 0 or 1) as a qubit. Then we have (in quantum space) two parallel worlds, in one (A) is in taxi 0, and in the other world â in taxi 1. Simultaneously in two taxis, but with some probability of finding him in each of them when observed.
Letâs take (V)olodya and also represent his state as a qubit. This creates two other parallel worlds. But for now these pairs of worlds (A) and (V) do not interact. What must be done to create an entangled system? Correct, these qubits need to be entangled. We take and entangle (A) with (V) â we get a quantum system of two qubits (A, V), which realizes four interdependent parallel worlds. We add (S)ergey and get a system of three qubits (ABC), realizing eight interdependent parallel worlds.
The essence of quantum computing (performing a sequence of quantum gates on a system of entangled qubits) is the fact that computation happens in all parallel worlds simultaneously.
And it doesn't matter how many we have, 2^3 or 2^100, the quantum algorithm will complete in finite time across all these parallel worlds and will give us a result that represents a sample from the probability distribution of the algorithmâs responses.
For better understanding, one can imagine that A quantum computer at the quantum level initiates 2^N parallel processes for solving, each of which works on a single possible variant, then collects the results of the work â and provides us with an answer in the form of a superposition of solutions (a probabilistic distribution of answers), from which we sample one each time (during each experiment).
Remember the time required by our experimenter (150 microseconds) to conduct the experiment; this will be useful later when we discuss the main problems of quantum computers and decoherence time.
Quantum algorithms
As mentioned, classical algorithms based on binary logic are not applicable to a quantum computer using quantum logic (quantum gates). New algorithms had to be devised that fully utilize the potential inherent in the quantum nature of computations.
The most well-known algorithms today are:
Unlike classical computers, quantum computers are not universal.
Only a small number of quantum algorithms have been discovered so far.
Thank you for the reference to , a place where, according to the author (), the best representatives of the quantum algorithm world are gathered and continue to be gathered.
In this article, we will not delve deeply into quantum algorithms; the internet has many excellent materials at any level of complexity, but we should briefly cover the three most well-known ones.
Shor's algorithm.
The most renowned quantum algorithm is (invented in 1994 by English mathematician ), which aims to solve the problem of factoring numbers into their prime components (the factorization problem, discrete logarithm).
This algorithm is often cited when discussing how your banking systems and passwords will soon be compromised. Given that the length of keys currently in use is at least 2048 bits, the time for a breach has not yet arrived.
Currently is rather modest. The best results of factoring using Shor's algorithm are for numbers and , which is significantly less than 2048 bits. Other results in the table used different calculations, but even the best result from this algorithm (291311) is far from practical application.
You can read more about Shor's algorithm, for example,. Regarding practical implementation â .
One of the of the complexity and required power for factorizing a 2048-bit number is a computer with We can sleep soundly.
Grover's algorithm
â for solving the search problem, that is, finding the solution to the equation F(X) = 1,where F is a from n of variables. It was proposed by American mathematician downward API support (simultaneously with this in .
Grover's algorithm can be used to find the and of a number series. Additionally, it can be applied to solve problems through exhaustive search among a multitude of possible solutions. This may lead to a significant speedup compared to classical algorithms, although it does not provide a ââ in general..
You can read more about it, or There is also a good explanation of the algorithm using the example of boxes and a ball, but unfortunately, for reasons beyond anyone's control, this site is not accessible from Russia. If you have this site Grover's algorithm. Imagine you have N numbered closed boxes. All are empty except for one containing a ball. Your task: find 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 most straightforward way is to open the boxes one by one, and sooner or later you'll come across the box with the ball. On average, how many boxes need to be checked before the box with the ball is found? On average, you need to open about half of the boxes, N/2. The main point here is that if we increase the number of boxes 100 times, the average number of boxes needed to be opened before the box with the ball is found will also increase by the same factor.
How to solve this problem? The most straightforward way is to open the boxes one by one, and sooner or later you will come across the box with the ball. On average, how many boxes need to be checked before finding the box with the ball? On average, you need to open about half of the boxes, N/2. The key point here is that if we increase the number of boxes by 100 times, the average number of boxes that need to be opened before finding the box with the ball will increase by the same 100 times.
Now let's make one more clarification. Suppose we don't open the boxes ourselves and check for the presence of a ball in each, but there is a certain intermediary, let's call him the Oracle. We tell the Oracle, "check box number 732," and the Oracle honestly checks and replies, "there is no ball in box number 732." Instead of talking about how many boxes we need to open on average, we say, "how many times on average do we need to consult the Oracle to find the number of the box with the ball?"
It turns out that if we translate this task with boxes, a ball, and the Oracle into quantum language, we get a remarkable result: to find the number of the box with the ball among N boxes, we only need to disturb the Oracle approximately SQRT(N) times!
That is, the complexity of the search task using Grover's algorithm decreases by the square root.
Deutsch-Jozsa algorithm
The Deutsch-Josza algorithm (also referred to as the Deutsch-Jozsa algorithm) is a [quantum algorithm](), proposedthe algorithm proposed and downward API support (simultaneously with this in quantum computers. . _
You can also read more
. A simpler explanation is: The Deutsch algorithm (Deutsch-Josza) is based on search but allows it to be done faster than usual. Imagine there is a coin on the table, and you need to find out if it is fake. To do this, you need to look at the coin twice and determine: "heads" and "tails" â the real coin; two "heads" or two "tails" â itâs fake. So, if you use the quantum Deutsch algorithm, this determination can be made in one glance â by measuring.
In the design and operation of quantum computers, scientists and engineers face a huge number of problems that are currently being solved with varying degrees of success. According to
Problems of quantum computers
and here as well (the following series of problems can be identified:
- Sensitivity to the environment and interaction with the environment
- Accumulation of errors during computations
- Difficulties with the initial initialization of qubit states
- Challenges in creating multi-qubit systems
I highly recommend reading the article ââ, especially the comments on it.
Let's organize all the main problems into three major groups and examine each of them in more detail:
Decoherence
.
Quantum state is a very fragile thing, qubits in an entangled state are extremely unstable, any external influence can destroy (and does destroy) this connection. A change in temperature by the slightest fraction of a degree, pressure, a random photon flying nearby â all of this destabilizes our system.
To solve this problem, low-temperature sarcophagi are constructed, where the temperature (-273.14 degrees Celsius) is just slightly above absolute zero, with maximum insulation of the inner chamber containing the processor from all (possible) external influences.
The maximum lifetime of a quantum system consisting of several entangled qubits, during which it retains its quantum properties and can be used for computations, is called the decoherence time.
Currently, the decoherence time in the best quantum solutions is about tens and hundreds of microseconds.
There is a great example , on which one can view of all created quantum systems. This article highlights only two top processors â from IBM and from . As we can see, the decoherence time (T2) does not exceed 200 ”s.
I couldn't find precise data on Sycamore, but in the article about quantum supremacy 1 million calculations in 200 seconds , in another place â for130 seconds without losses on control signals and others . In any case, this gives usa decoherence time of about 150 ”s. Remember ourexperimenter with a bag Computer Name? ĐŃ ŃĐ°Đș ĐČĐŸŃ ĐŸĐœ.
| N Qubits | Max paired | T2 (”s) | What threat does decoherence pose? |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
The main problem is that after 150 ”s, our computational system of N entangled qubits will begin to output instead of a probabilistic distribution of correct solutions â probabilistic white noise.
So we need to:
Initialize the qubit system
- Perform the computation (a chain of gate operations)
- Perform the computation (chain of gate operations)
- Count the result
And do all this in 150 microseconds. If you didn't make it, the result will turn into a pumpkin.
But that's not allâŠ
Errors
As we have already mentioned, quantum processes and quantum computations have a probabilistic nature, we cannot be 100% certain about anything, only with some probability. The situation is further complicated by the fact that quantum computations are prone to errors. The main types of errors in quantum computing are:
- Decoherence errors, caused by the complexity of the system and its interaction with the external environment
- Gate computational errors (caused by the quantum nature of computations)
- Final state (result) readout errors
Errors related to decoherence, arise as soon as we entangle our qubits and start performing calculations. The more qubits we entangle, the more complex the system, and the easier it is to break it. Low-temperature sarcophagi, shielded chambers, all these technological tricks are aimed at reducing the number of errors and prolonging the decoherence time.
Gate computational errors â any operation (gate) on qubits can end with an error with some probability, and to implement the algorithm, we need to perform hundreds of gates, so just imagine what we will end up with after completing our algorithm. The classical answer to the question â "What is the probability of encountering a dinosaur in an elevator?" â is 50-50, either you will meet it or you won't.
The problem is further exacerbated by the fact that standard error correction methods (duplicating computations and averaging) do not work in the quantum world due to the no-cloning theorem. For in quantum computing, it was necessary to come up with . Simply put, we take N ordinary qubits and create 1 logical qubit with a lower error rate.
But another problem arises â the overall number of qubits. Let's say we have a processor with 100 qubits, out of which 80 qubits are occupied with error correction, leaving us only 20 for computations.
Final result read errors â as we remember, the result of quantum computations is presented to us in the form of probability distributions of responses. However, reading the final state can also end with an error.
At 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 and :
| Computer | 1-Qubit Gate Fidelity | 2-Qubit Gate Fidelity | Readout Fidelity |
| IBM Q System One | 99.96% | 98.31% | â |
| Google Sycamore | 99.84% | 99.38% | 96.2% |
Here â a measure of the similarity of two quantum states. The error magnitude can roughly be represented as 1-Fidelity. As we can see, errors at 2-qubit gates and readout errors are the main obstacles to executing complex and long algorithms on existing quantum computers.
. A simpler explanation is: year from to solve the error correction problem.
Processor Architecture
In theory, we build and operate schemes with dozens of entangled qubits, in reality, it is much more complicated. All existing quantum chips (processors) are designed to ensure painless entanglement of one qubit only with its neighbors, which are no more than six.
If, however, we need to entangle the 1st qubit with, say, the 12th, we will have to build a chain of additional quantum operations, involve additional qubits and others, which increases the overall error level. And donât forget about decoherence time, by the time you finish connecting the qubits in the scheme you need, the time may expire and the entire scheme will turn into a nice white noise generator.
Also, keep in mind that the architecture of all quantum processors is different, and the program written in the emulator in 'connectivity of all with all' mode will need to be 'recompiled' for the architecture of a specific chip. There are even to perform this operation.
Maximum connectivity and the maximum number of qubits for the same top chips:
| N Qubits | Max paired | T2 (”s) | What threat does decoherence pose? |
| IBM Q System One | 20 | 6 | 70 |
| Google Sycamore | 53 | 4 | ~150-200 |
And, for comparison, a table with data from the previous generation of processors. Compare the number of qubits, decoherence time, and error percentage with what we currently have in the new generation. After all, progress is slowly but surely moving.
So:
- At present, there are no fully connected architectural schemes with > 6 qubits
- To entangle qubit 0 with, for example, the 15th on a real processor, several dozen additional operations may be required
- More operations -> more errors -> stronger decoherence influence
Summary
Decoherence is the crucible of modern quantum computing. We have to fit everything into 150 ”s:
- Initializing the initial state of qubits
- Calculating tasks using quantum gates
- Perform error correction to obtain meaningful results
- Read the obtained results
So far, the results are disappointing, although they claim to achieve 0.5s coherence 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
You can read more about this technology or, for example, .
The situation is further complicated by the fact that complex computations require the use of quantum error correction circuits, which also consumes time and available qubits.
Finally, modern architectures do not allow us to implement entanglement schemes more efficiently than a ratio of 1 to 4 or 1 to 6.
Ways to solve problems
To address the above issues, the following approaches and methods are currently used:
- Using cryostats with low temperatures (10 mK (â273.14°C))
- Using processor blocks that are maximally protected from external influences
- Using quantum error correction systems (Logical qubit)
- Using optimizers when programming circuits for specific processors
Research is also being conducted to increase decoherence time, to find new (and improve known) physical realizations of quantum objects, to optimize correction circuits, and so on. Progress is being made (see above for the specifications of earlier and today's top chips), but it is slow, very, very slow.
It is too early to talk about the mass implementation of quantum computers. Even disregarding the high cost of the machines, they have serious technological limitations.
2000-qubit computer D-Wave 2000Q. Source:
Against the backdrop of Googleâs announcement of achieving quantum supremacy using a 53-qubit processor, and from D-Wave, where the number of qubits counts in thousands, can be somewhat confusing. Indeed, if 53 qubits were able to achieve quantum supremacy, what is a computer with 2048 qubits capable of? But not everything is so straightforward...
In short (from Wikipedia):
Computers they operate on the principle of (), can solve a very limited sub-class of optimization problems, and are not suitable for implementing traditional quantum algorithms and quantum gates.
For more details, you can read, for example, , (caution, may not open from Russia), or at downward API support (simultaneously with this in from his . By the way, I highly recommend reading his blog; there is a lot of good material there.
From the very beginning of the announcements, the scientific community had questions about D-Wave computers. For instance, in 2014, IBM challenged the fact that D-Wave It came to the point where in 2015, Google along with NASA bought one of these quantum computers, and after research , it turned out that yes, the computer works and solves tasks faster than a classical one. You can also read about Google's statement and, for example, .
The main point is that D-Wave computers, with their hundreds and thousands of qubits, cannot be used to compute and run quantum algorithms. For example, you cannot run Shor's algorithm on them. All they can do is use certain quantum mechanisms to solve specific optimization tasks. One could say that D-Wave is a kind of quantum ASIC for a particular task.
A bit about emulating quantum computers
Quantum computations can be emulated on a classical computer. Indeed, :
- The state of a qubit can be by a complex number, occupying from 2^32 to 2^64 bits (8-16 bytes) depending on the processor architecture.
- The state of N linked 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.
- 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 is needed.
- To store the states of 20 qubits, 8 MB is needed.
- To store the states of 30 qubits, 8 GB is needed.
- To store the states of 40 qubits, 8 Terabytes are needed.
- To store the states of 50 qubits, 8 Petabytes are needed, and so on.
For comparison, () carries only 2.8 Petabytes of memory.
â 49 qubits set last year on the largest Chinese supercomputer ()
The limit of simulating a quantum computer on classical systems is determined by the amount of RAM required to store the state of the qubits.
I recommend reading . From there:
Regarding operations â for a precise emulation of a scheme with 49 qubits from some 39 'ticks' (independent layers of gates) 2^63 complex multiplications â 4 Petaflops of a supercomputer over 4 hours
The emulation of a quantum computer with 50+ qubits on classical systems is considered unfeasible within a reasonable timeframe. This fact is part of why Google used a processor with 53 qubits for its quantum supremacy experiment.
Quantum computational supremacy.
Wikipedia provides us with the following definition of quantum computational supremacy:
Quantum supremacy â the ability devices to solve problems that classical computers practically cannot solve.
In fact, achieving quantum supremacy means that, for instance, factoring large numbers using Shor's algorithm can be done in a reasonable time, or complex chemical molecules can be emulated at the quantum level, and so on. A new era has begun.
However, there is a loophole in the formulation of the definition: âthat classical computers practically cannot solve.â This means that if a quantum computer with 50+ qubits is created and some quantum circuit is run on it, as discussed above, the result of that circuit's operation will be impossible to simulate on a regular computer. Therefore, a classical computer will not be able to recreate the result of such a circuit's operation..
Whether such a result constitutes real quantum supremacy is rather a philosophical question. However, it is important to understand what Google has done and the basis of its .
Google's claim of achieving quantum supremacy
The 54-qubit Sycamore processor
So, in October 2019, Google developers published an article in the scientific journal Nature titled "." The authors announced the first-ever achievement of quantum supremacy using a 54-qubit processor âSycamore.â
Online, articles often refer to Sycamore as a 54-qubit processor or a 53-qubit processor. The truth is that according to , the processor physically consists of 54 qubits, but one of them is non-functional and has been taken out of service. Thus, in reality, we have a 53-qubit processor.
The community immediately materials on this topic, the degree of which varied from up to .
Later, employees of the quantum computing division at IBM stated that . The company claims that a regular computer would handle this task in the worst case in 2.5 days, and the provided answer would be more accurate than that of a quantum computer. This conclusion was drawn from the theoretical analysis of several optimization methods conducted.
And, of course, in your couldn't help but pay attention to this statement. His along with all the links and are, as usual, worth spending your time on. On Habr, of this FAQ, and be sure to read the comments; there are links to preliminary documents leaked online before the official announcement.
So, what did Google actually do? For a detailed understanding, read Aaronson, but briefly hereâs what happened:
I can, of course, tell you, but I feel a bit silly doing so. The computation 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 about 20, acting on a 2D network of n=50-60 qubits). After that, the experimenter sends C to the quantum computer and asks it to apply C to an initial state of 0, measure the result in the basis {0,1}, send back an n-bit observed sequence (string), and repeat this several thousand or millions of times. Finally, using their knowledge of C, the experimenter conducts a statistical check on the correspondence of the result with the expected output from the quantum computer.
In short:
- A random circuit of length 20 is created using 53 qubits and gates.
- The circuit is launched with the initial state [0âŠ0] for execution.
- The output of the circuit represents a random bit string (sample).
- The distribution of the result is not random (interference).
- The distribution of the obtained samples is compared with the expected one.
- A conclusion is made about quantum supremacy.
This means that Google has implemented a synthetic task on a 53-qubit processor and bases its claim of achieving quantum supremacy on the fact that such a processor cannot be emulated on standard systems in a reasonable time.
To understand â this section does not diminish Google's achievement at all,the engineers indeed did a great job, and the question of whether this can be considered real quantum supremacy, as previously mentioned, is more philosophical than engineering. But it should be understood that having reached such computational superiority, we have not made any progress towards being able to run Shor's algorithm on 2048-bit numbers.
Summary
Quantum computers and quantum computing are a promising, very young, and currently not widely applicable field of information technology.
The development of quantum computing will (someday) enable solving tasks:
- Modeling complex physical systems at a quantum level,
- Problems unsolvable on a regular computer due to computational complexity.
The main issues when creating and operating quantum computers are:
- Decoherence
- Errors (decoherence and gate errors),
- Processor architecture (fully connected qubit schemes),
The current state of affairs:
- In fact â it's at the very beginning. .
- There is NO REAL commercial operation yet (and it's unclear when it will be),
What could help:
- Some physical discovery that lowers the costs of interfacing and operating processors,
- The discovery of something that significantly increases decoherence time and/or reduces the number of errors.
In my opinion (strictly personal view), within the current scientific paradigm, we will not achieve significant progress in developing quantum technologies.A qualitative breakthrough in some area of fundamental or applied science is needed to spark new ideas and methods.
Meanwhile, we are gaining experience in quantum programming, collecting and creating quantum algorithms, testing ideas, and so on. We await a breakthrough.
Conclusion
In this article, we covered the main milestones in the development of quantum computing and quantum computers, discussed their operational principles, examined the key challenges engineers face in the development and operation of quantum processors, and took a closer look at what multi-qubit D-Wave computers really are and Googleâs recent announcement regarding the achievement of quantum supremacy.
The issues of programming quantum computers (languages, approaches, methods, etc.) and questions related to the specific physical realization of processors, such as how qubits are controlled, interconnected, read, etc., remain unaddressed. Perhaps this will be the topic of the next article(s).
Thank you for your attention; I hope this article proves useful to someone.
(C)
Acknowledgments
for proofreading and comments on the original text, as well as for the article
for the information-rich comments on , and not just that one, which greatly helped me piece together this puzzle.
To all the authors of articles and publications whose materials were used in writing this article.
Resource List
Articles on the current state of affairs from [The National Academies Press]
Articles from Habr (in random order)
Unsorted (but no less interesting) articles from around the web
Courses and lectures
Source: habr.com
