January 29th, 2017
For me, the phrase "quantum computer" is comparable, for example, with "photon engine", that is, it is something very complex and fantastic. However, I'm reading now in the news - "a quantum computer is sold to anyone who wants it." It's strange, either this expression now means something else, or is it just a fake?
Let's take a closer look...
HOW IT ALL BEGAN?
It was not until the mid-1990s that the theory of quantum computers and quantum computing established itself as a new area Sciences. As is often the case with great ideas, it's hard to single out a pioneer. Apparently, the Hungarian mathematician I. von Neumann was the first to draw attention to the possibility of developing quantum logic. However, at that time, not only quantum, but also ordinary, classical computers had not yet been created. And with the advent of the latter, the main efforts of scientists were directed primarily to the search and development of new elements for them (transistors, and then integrated circuits), and not on the creation of fundamentally different computing devices.
In the 1960s, the American physicist R. Landauer, who worked at IBM Corporation, tried to draw the attention of the scientific world to the fact that calculations are always some kind of physical process, which means that it is impossible to understand the limits of our computing capabilities without specifying what physical implementation they are. match. Unfortunately, at that time, the prevailing view among scientists was that computation was some kind of abstract logical procedure that should be studied by mathematicians, not physicists.
As computers proliferated, scientists involved in quantum objects came to the conclusion that it was practically impossible to directly calculate the state of an evolving system consisting of only a few dozen interacting particles, such as a methane (CH4) molecule. This is explained by the fact that for complete description complex system, it is necessary to keep in the computer memory an exponentially large (in terms of the number of particles) number of variables, the so-called quantum amplitudes. A paradoxical situation arose: knowing the equation of evolution, knowing with sufficient accuracy all the potentials of the interaction of particles with each other and the initial state of the system, it is practically impossible to calculate its future, even if the system consists of only 30 electrons in a potential well, and a supercomputer with RAM is available , the number of bits of which is equal to the number of atoms in the visible region of the Universe (!). And at the same time, to study the dynamics of such a system, one can simply set up an experiment with 30 electrons, placing them in a given potential and initial state. This, in particular, drew the attention of the Russian mathematician Yu. I. Manin, who in 1980 pointed out the need to develop a theory of quantum computing devices. In the 1980s, the same problem was studied by the American physicist P. Benev, who clearly showed that a quantum system can perform calculations, as well as the English scientist D. Deutsch, who theoretically developed a universal quantum computer that surpasses its classical counterpart.
R. Feynman, Nobel Prize winner in physics, attracted much attention to the problem of developing quantum computers. Thanks to his authoritative appeal, the number of specialists who paid attention to quantum computing has increased many times over.
The basis of Shor's algorithm: the ability of qubits to store multiple values at the same time)
Yet for a long time it remained unclear whether the hypothetical computing power could be used quantum computer to speed up the solution practical tasks. But in 1994, P. Shor, an American mathematician at Lucent Technologies (USA), stunned the scientific world by proposing a quantum algorithm that allows fast factorization of large numbers (the importance of this problem has already been discussed in the introduction). Compared to the best of the classical methods known today, Shor's quantum algorithm gives a multiple acceleration of calculations, and the longer the factorizable number, the greater the gain in speed. The fast factorization algorithm is of great practical interest for various intelligence services that have accumulated banks of undecrypted messages.
In 1996, Shor's colleague at Lucent Technologies, L. Grover, proposed a quantum fast search algorithm in an unordered database. (An example of such a database is a telephone book, in which the names of subscribers are not arranged alphabetically, but arbitrarily.) The task of searching, selecting optimal element among numerous options, it is very often found in economic, military, engineering tasks, in computer games. Grover's algorithm allows not only to speed up the search process, but also to approximately double the number of parameters taken into account when choosing the optimum.
The real creation of quantum computers was hindered, in essence, by the only serious problem - errors, or interference. The fact is that the same level of interference spoils the process of quantum computing much more intensively than classical ones.
If you say in simple words, then: " a quantum system gives a result that is correct only with some probability. In other words, if you calculate 2+2, then 4 will come out only with some degree of accuracy. You will never get exactly 4. The logic of its processor is not at all similar to the processor we are used to.
There are methods to calculate the result with a predetermined accuracy, naturally with an increase in computer time.
This feature defines the list of tasks. And this feature is not advertised, and the public gets the impression that a quantum computer is the same as a regular PC (the same 0 and 1), only fast and expensive. This is fundamentally not true.
Yes, and another point - for a quantum computer and quantum computing in general, especially in order to use the "power and speed" of quantum computing, special algorithms and models are developed specially for the specifics of quantum computing. Therefore, the difficulty of using a quantum computer is not only in the presence of hardware, but also in the compilation of new, hitherto unused calculation methods. "
Now let's go back to practical implementation quantum computer: a commercial 512-qubit D-Wave processor has existed for some time already and is even being sold !!!
Here, he, it would seem, is a real breakthrough !!! And a group of reputable scientists in the no less reputable journal Physical Review convincingly testifies that quantum entanglement effects have indeed been discovered in D-Wave.
Accordingly, this device has every right to be called a real quantum computer, architecturally it fully allows for a further increase in the number of qubits, and, therefore, has excellent prospects for the future ... (T. Lanting et al. Entanglement in a Quantum Annealing Processor. PHYSICAL REVIEW X 4 , 021041 (2014) (http://dx.doi.org/10.1103/PhysRevX.4.021041))
True, a little later, another group of reputable scientists in the equally reputable journal Science, who studied the same D-Wave computing system, evaluated it purely practically: how well this device performs its computing functions. And this group of scientists demonstrates just as thoroughly and convincingly as the first one that in real verification tests, which are optimally suited for this design, the D-Wave quantum computer does not give any speed gain compared to conventional, classical computers. (T.F. Ronnow, M. Troyer et al. Defining and detecting quantum speedup. SCIENCE, Jun 2014 Vol. 344 #6190 (http://dx.doi.org/10.1126/science.1252319))
In fact, there were no tasks for the expensive but specialized "machine of the future" where it could demonstrate its quantum superiority. In other words, the very meaning of the very expensive efforts to create such a device is in great doubt ...
The results are as follows: now there is no doubt in the scientific community that the work of elements in the D-Wave computer processor really takes place on the basis of real quantum effects between qubits.
But (and this is an extremely serious BUT), the key features in the design of the D-Wave processor are such that in real operation, all of its quantum physics does not give any gain in comparison with a conventional powerful computer that has a special software, tailored for solving optimization problems.
Simply put, not only scientists testing D-Wave have not yet been able to see a single real task, where a quantum computer could convincingly demonstrate its computational superiority, but even the manufacturer itself has no idea what kind of task it could be ...
It's all about the design features of the 512-qubit D-Wave processor, which is assembled from groups of 8 qubits. At the same time, inside these groups of 8 qubits, they all communicate directly with each other, but between these groups, the connections are very weak (ideally, ALL processor qubits should communicate directly with each other). This, of course, VERY significantly reduces the complexity of building a quantum processor ... BUT, from here a lot of other problems grow, closing in the final and on very expensive cryogenic equipment that cools the circuit to ultra-low temperatures.
So what are they offering us now?
The Canadian company D-Wave announced the start of sales of its D-Wave 2000Q quantum computer, announced in September last year. Adhering to its own version of Moore's Law, according to which the number of transistors on an integrated circuit doubles every two years, D-Wave placed 2,048 qubits on a CPU (quantum processing device). The growth dynamics of the number of qubits on the CPU in recent years looks like this:
2007 — 28
…
— 2013 — 512
— 2014 — 1024
— 2016 — 2048.
Moreover, unlike traditional processors, CPUs and GPUs, doubling the qubits is accompanied not by a 2-fold, but by a 1000-fold increase in performance. Compared with a computer with a traditional architecture and configuration of a single-core CPU and 2500-core GPU, the performance difference is 1,000 to 10,000 times. All these figures are certainly impressive, but there are a few “buts”.
First, the D-Wave 2000Q is extremely expensive at $15 million. It is a fairly massive and complex device. Its brain is a CPU made of a non-ferrous metal called niobium, whose superconducting properties (required for quantum computers) occur in a vacuum at a temperature close to absolute zero below 15 millikelvins (that's 180 times lower than the temperature in outer space).
Maintaining such an extremely low temperature requires a large amount of energy, 25 kW. But still, according to the manufacturer, this is 100 times less than traditional supercomputers of equivalent performance. So the performance of the D-Wave 2000Q per watt of power consumption is 100 times higher. If the company manages to continue to follow its "Moore's law", then in its future computers this difference will grow exponentially, while maintaining energy consumption at current levels.
First, quantum computers have a very specific purpose. In the case of D-Wave 2000Q, we are talking about the so-called. adiabatic computers and solving problems of quantum normalization. They occur in particular in the following areas:
Machine learning:
Detection of statistical anomalies
— finding compressed models
— recognition of images and patterns
- neural network training
— verification and approval of software
— classification of unstructured data
- diagnosing errors in the circuit
Security and Planning
Virus and network hack detection
— distribution of resources and finding optimal ways
— definition of belonging to a set
— analysis of chart properties
- factorization of integers (used in cryptography)
financial modeling
Identification of market instability
— development of trading strategies
— optimization of trading trajectories
— optimization of asset pricing and hedging
— portfolio optimization
Health care and medicine
Fraud detection (probably health insurance)
— generation of targeted (“molecular-targeted”) drug therapy
– optimization of [cancer] treatment with radiotherapy
— creation of protein models.
The first buyer of the D-Wave 2000Q was TDS (Temporal Defense Systems), a cybersecurity company. In general, D-Wave products are used by companies and institutions such as Lockheed Martin, Google, NASA Ames Research Center, the University of Southern California and Los Alamos National Laboratory at the US Department of Energy.
Thus, we are talking about a rare (D-Wave is the only company in the world that produces commercial samples of quantum computers) and expensive technology with a rather narrow and specific application. But the rate of growth of its productivity is amazing, and if this dynamics continues, then thanks to the adiabatic computers D-Wave (which other companies may eventually join) in the coming years, we can expect real breakthroughs in science and technology. Of particular interest is the combination of quantum computers with such a promising and rapidly developing technology as artificial intelligence, especially since such an authoritative specialist as Andy Rubin sees a future in this.
By the way, did you know that the IBM Corporation allowed Internet users to connect for free to the universal quantum computer it built and experiment with quantum algorithms. This device is not powerful enough to break cryptographic systems with public key, but if IBM's plans come true, the emergence of more complex quantum computers is just around the corner.
The quantum computer that IBM made available contains five qubits: four are used to work with data, and the fifth is for correcting errors during calculations. Error correction is the main innovation that its developers are proud of. It will make it easier to increase the number of qubits in the future.
IBM emphasizes that its quantum computer is universal and capable of executing any quantum algorithms. This distinguishes it from the adiabatic quantum computers that D-Wave is developing. Adiabatic quantum computers are designed to search optimal solution functions and are not suitable for other purposes.
It is believed that universal quantum computers will allow solving some problems that are beyond the power of conventional computers. The best-known example of such a problem is factoring numbers into prime factors. It would take hundreds of years for an ordinary computer, even a very fast one, to find the prime factors of a large number. A quantum computer will find them using Shor's algorithm almost as fast as multiplying integers.
The impossibility of quickly decomposing numbers into prime factors is the basis of public-key cryptographic systems. If this operation is learned to be performed at the speed promised by quantum algorithms, then for the most part modern cryptography will have to forget.
It is possible to run Shor's algorithm on an IBM quantum computer, but until there are more qubits, this is of little use. Over the next ten years, the situation will change. By 2025, IBM plans to build a quantum computer containing from fifty to one hundred qubits. According to experts, even with fifty qubits, quantum computers will be able to solve some practical problems.
Here is some more interesting information about computer technology: read how, but it also turns out that it is possible and what kind of
Quantum computing, at least in theory, has been talked about for decades. Modern types of machines that use non-classical mechanics to process potentially unimaginable amounts of data have been a big breakthrough. According to the developers, their implementation turned out to be perhaps the most complex technology ever created. Quantum processors work at the levels of matter that humanity learned about only 100 years ago. The potential of such calculations is huge. Using the bizarre properties of quantums will speed up calculations, so many problems that are currently beyond the power of classical computers will be solved. And not only in the field of chemistry and materials science. Wall Street is also showing interest.
Investment in the future
CME Group has invested in Vancouver-based 1QB Information Technologies Inc., which develops software for quantum-type processors. According to investors, such calculations are likely to have the greatest impact on industries that work with large volumes of time-sensitive data. Financial institutions are an example of such consumers. Goldman Sachs has invested in D-Wave Systems, and In-Q-Tel is funded by the CIA. The first produces machines that do what is called "quantum annealing", that is, solve low-level optimization problems using a quantum processor. Intel is also investing in this technology, although it considers its implementation a matter of the future.
Why is this needed?
The reason why quantum computing is so exciting is because of its perfect combination with machine learning. Currently, this is the main application for such calculations. Part of the very idea of a quantum computer is the use of a physical device to find solutions. Sometimes this concept explain on the example of the game Angry Birds. The tablet CPU uses mathematical equations to simulate gravity and the interaction of colliding objects. Quantum processors turn this approach on its head. They "throw" a few birds and see what happens. Birds are recorded on the microchip, they are thrown, what is the optimal trajectory? Then all are checked possible solutions or at least a very large combination of them, and a response is returned. In a quantum computer, there is no mathematician; instead, the laws of physics work.
How does it function?
The basic building blocks of our world are quantum mechanical. If you look at molecules, the reason they form and stay stable is because of the interaction of their electron orbitals. All quantum mechanical calculations are contained in each of them. Their number grows exponentially with the number of simulated electrons. For example, for 50 electrons there is 2 to the 50th power options. This is phenomenal, therefore it cannot be calculated today. Connecting information theory to physics can point the way to solving such problems. A 50-qubit computer can do it.
The dawn of a new era
According to Landon Downes, President and Co-Founder of 1QBit, quantum processor is the ability to use the computing power of the subatomic world, which is of great importance for obtaining new materials or creating new drugs. There is a transition from the discovery paradigm to a new era of design. For example, quantum computing can be used to model catalysts that allow carbon and nitrogen to be removed from the atmosphere and thereby help stop global warming.
At the forefront of progress
The developer community for this technology is extremely excited and busy. Teams around the world in startups, corporations, universities and government labs are racing to build machines that use different approaches to quantum information processing. Superconducting qubit chips and trapped ion qubits have been created by researchers at the University of Maryland and the US National Institute of Standards and Technology. Microsoft is developing a topological approach called Station Q that aims to exploit a non-Abelian anion whose existence has not yet been conclusively proven.
Probable breakthrough year
And this is just the beginning. As of the end of May 2017, the number of quantum-type processors that unequivocally do something faster or better than a classical computer is zero. Such an event would establish "quantum supremacy," but so far it has not happened. Although it is likely that this can happen this year. Most insiders say the clear favorite is google group led by UC Santa Barbara physics professor John Martini. Its goal is to achieve computational superiority with a 49-qubit processor. By the end of May 2017, the team had successfully tested a 22-qubit chip as an intermediate step towards disassembling a classic supercomputer.
How did it all start?
The idea of using quantum mechanics to process information is decades old. One of the key events happened in 1981 when IBM and MIT jointly organized a conference on the physics of computing. The famous physicist proposed to build a quantum computer. According to him, for modeling, one should use the means of quantum mechanics. And this is a great task, because it does not look so simple. The principle of operation of a quantum processor is based on several strange properties of atoms - superposition and entanglement. A particle can be in two states at the same time. However, when measured, it will be in only one of them. And it is impossible to predict in which, except from the standpoint of probability theory. This effect underlies the thought experiment with Schrödinger's cat, which is both alive and dead in a box until an observer sneaks a peek into it. Nothing in Everyday life doesn't work like that. However, about 1 million experiments conducted since the beginning of the 20th century show that superposition does exist. And next step will be figuring out how to use this concept.
Quantum processor: job description
Classical bits can take the value 0 or 1. If you pass their string through “logical gates” (AND, OR, NOT, etc.), then you can multiply numbers, draw images, etc. A qubit can take values 0, 1 or both at the same time. If, say, 2 qubits are entangled, then that makes them perfectly correlated. A quantum type processor can use logic gates. T. n. the Hadamard gate, for example, puts the qubit in a state of perfect superposition. When superposition and entanglement are combined with cleverly placed quantum gates, the potential of subatomic computing begins to unfold. 2 qubits allow you to explore 4 states: 00, 01, 10 and 11. The principle of operation of a quantum processor is such that the execution of a logical operation makes it possible to work with all positions at once. And the number of available states is 2 to the power of the number of qubits. So, if you make a 50-qubit universal quantum computer, then theoretically you can explore all 1.125 quadrillion combinations at the same time.
Kudity
A quantum processor in Russia is seen somewhat differently. Scientists from the Moscow Institute of Physics and Technology and the Russian Quantum Center have created "kudits", which are several "virtual" qubits with different "energy" levels.
Amplitudes
The quantum-type processor has the advantage that quantum mechanics is based on amplitudes. Amplitudes are like probabilities, but they can also be negative and complex numbers. So, if you need to calculate the probability of an event, you can add the amplitudes of all possible options for their development. The idea behind quantum computing is to try to tune in such a way that some paths to incorrect answers have positive amplitude and some have negative amplitude so that they cancel each other out. And the paths leading to the correct answer would have amplitudes that are in phase with each other. The trick is to organize everything without knowing in advance which answer is correct. So the exponentiality of quantum states, combined with the potential for interference between positive and negative amplitudes, is an advantage of this type of computation.
Shor's algorithm
There are many problems that a computer cannot solve. For example, encryption. The problem is that it's not easy to find the prime factors of a 200-digit number. Even if the laptop runs great software, it may take years to find the answer. So another milestone in quantum computing was an algorithm published in 1994 by Peter Shor, now a professor of mathematics at MIT. His method is to search for factors of a large number using a quantum computer, which did not yet exist. Essentially, the algorithm performs operations that point to regions with the correct answer. The following year, Shor discovered a way to quantum error correction. Then many realized that it is - alternative way calculations, which in some cases can be more powerful. Then followed a surge of interest on the part of physicists to create qubits and logic gates between them. And now, two decades later, humanity is on the verge of creating a full-fledged quantum computer.
Humanity, like 60 years ago, is again on the verge of a grandiose breakthrough in the field of computing technologies. Quantum computers will soon replace today's computers.
How much progress has been made
Back in 1965, Gordon Moore said that in a year the number of transistors that fit in a silicon microchip doubles. This pace of progress recent times slowed down, and doubling occurs less frequently - once every two years. Even at this pace, in the near future, transistors will reach the size of an atom. Then there is a line that cannot be crossed. From the point of view of the physical structure of the transistor, it cannot be less than atomic quantities. Increasing the size of the chip does not solve the problem. The operation of transistors is associated with the release of thermal energy, and processors need a high-quality cooling system. Multi-core architecture also does not solve the issue of further growth. Reaching the peak in the development of modern processor technology will happen soon.
Developers came to understand this problem at a time when personal computers were just beginning to be available to users. In 1980, one of the founders of quantum informatics, Soviet professor Yuri Manin, formulated the idea of quantum computing. A year later, Richard Feiman proposed the first model of a computer with a quantum processor. Theoretical basis of what quantum computers should look like, formulated by Paul Benioff.
The principle of operation of a quantum computer
To understand how it works new processor, it is necessary to have at least a superficial knowledge of the principles of quantum mechanics. It makes no sense to give here mathematical layouts and derive formulas. It is enough for the layman to get acquainted with the three distinctive features of quantum mechanics:
- The state or position of a particle is determined only with some degree of probability.
- If a particle can have several states, then it is in all possible states at once. This is the principle of superposition.
- The process of measuring the state of the particle leads to the disappearance of the superposition. Characteristically, the knowledge about the state of the particle obtained by the measurement differs from the real state of the particle before the measurements.
From the point of view of common sense - complete nonsense. In our ordinary world, these principles can be represented as follows: the door to the room is closed, and at the same time open. Closed and open at the same time.
This is the striking difference between calculations. A conventional processor operates in its actions with a binary code. Computer bits can only be in one state - have a logical value of 0 or 1. Quantum computers operate on qubits, which can have a logical value of 0, 1, 0 and 1 at once. For certain tasks, they will have a multimillion-dollar advantage over traditional computers. Today there are already dozens of descriptions of work algorithms. Programmers create special program code that can work according to new principles of computing.
Where will the new computer be used?
A new approach to the computing process allows you to work with huge amounts of data and perform instant computing operations. With the advent of the first computers, some people, including statesmen, had great skepticism about their use in the national economy. There are still people today who are full of doubts about the importance of fundamentally new generation computers. For a very long time, technical journals refused to publish articles about quantum computing, considering this area a common fraudulent ploy to fool investors.
The new way of computing will create the prerequisites for scientific grandiose discoveries in all industries. Medicine will solve many problematic issues, which have accumulated quite a lot recently. It will be possible to diagnose cancer at an earlier stage of the disease than it is now. The chemical industry will be able to synthesize products with unique properties.
A breakthrough in astronautics will not keep you waiting. Flights to other planets will become as commonplace as daily trips around the city. The potential inherent in quantum computing will certainly transform our planet beyond recognition.
Other distinguishing feature, which quantum computers have is the ability of quantum computing to quickly pick up desired code or cipher. An ordinary computer performs a mathematical optimization solution sequentially, going through one option after another. A quantum competitor works with the entire data array at once, instantly choosing the most suitable options in an unprecedentedly short time. Banking transactions will be deciphered in the blink of an eye, which is not available to modern computers.
However, the banking sector may not worry - its secret will be saved by the quantum encryption method with the paradox of measurement. If you try to open the code, a distortion will occur transmitted signal. The information received will not make any sense. The secret services, for which espionage is a common thing, are interested in the possibilities of quantum computing.
Design difficulties
The difficulty lies in creating the conditions under which a quantum bit can be in a state of superposition for an infinitely long time.
Each qubit is a microprocessor that operates on the principles of superconductivity and the laws of quantum mechanics.
A number of unique environmental conditions are created around the microscopic elements of the logic engine:
- temperature 0.02 degrees Kelvin (-269.98 Celsius);
- system of protection against magnetic and electric radiation (reduces the impact of these factors by 50 thousand times);
- heat removal and vibration damping system;
- rarefaction of air below atmospheric pressure by 100 billion times.
A slight environmental deviation causes the qubits to momentarily lose their superposition state, resulting in a malfunction.
Ahead of the planet
All of the above could be attributed to the creativity of the inflamed mind of a science fiction writer, if Google, together with NASA, did not purchase a D-Wave quantum computer last year from a Canadian research corporation, the processor of which contains 512 qubits.
With its help, the leader in the computer technology market will solve problems machine learning in sorting and analyzing large data arrays.
An important revealing statement was made by Snowden, who left the United States - the NSA also plans to develop its own quantum computer.
2014 - the beginning of the era of D-Wave systems
Successful Canadian athlete Geordie Rose, after a deal with Google and NASA, began building a processor of 1000 qubits. The future model in terms of speed and volume of calculations will surpass the first commercial prototype by at least 300,000 times. The quantum computer, the photo of which is located below, is the world's first commercial version of the fundamentally new technology computing.
He was prompted to engage in scientific development by his acquaintance at the university with the works of Colin Williams on quantum computing. I must say that Williams today works in the Rose Corporation as a business project manager.
Breakthrough or scientific deception
Rose himself does not fully know what quantum computers are. In ten years, his team has gone from creating a 2-qubit processor to today's first commercial offspring.
From the very beginning of his research, Rose aimed to create a processor with a minimum number of qubits of 1,000. And he must have had a commercial option - to sell and earn money.
Many, knowing Rose's obsession and commercial acumen, try to accuse him of forgery. Allegedly, the most ordinary processor is issued for quantum. This is facilitated by the fact that the phenomenal speed of the new technique shows when performing certain types of calculations. Otherwise, it behaves like a completely ordinary computer, only very expensive.
When will they appear
There is not long to wait. The research group, organized by the joint prototype purchasers, will soon report on the result of research on D-Wave.
Perhaps the time is coming soon in which quantum computers will turn our understanding of the world around us. And all of humanity at that moment will reach a higher level of its evolution.
Candidate of Physical and Mathematical Sciences L. FEDICHKIN (Physico-Technological Institute of the Russian Academy of Sciences.
Using the laws of quantum mechanics, it is possible to create a fundamentally new type of computers that will allow solving some problems that are inaccessible even to the most powerful modern supercomputers. The speed of many complex calculations will increase dramatically; messages sent over quantum communication lines can neither be intercepted nor copied. Today, prototypes of these quantum computers of the future have already been created.
American mathematician and physicist of Hungarian origin Johann von Neumann (1903-1957).
American theoretical physicist Richard Phillips Feynman (1918-1988).
American mathematician Peter Shor, a specialist in the field of quantum computing. He proposed a quantum algorithm for fast factorization of large numbers.
Quantum bit or qubit. The states and correspond, for example, to the direction of the spin of the atomic nucleus up or down.
A quantum register is a chain of quantum bits. One- or two-qubit quantum gates perform logical operations on qubits.
INTRODUCTION, OR A LITTLE ABOUT INFORMATION PROTECTION
What do you think is the most licensed program in the world? I won't venture to insist that I know the right answer, but I do know one wrong one: this is not any of the versions Microsoft Windows. The most common operating system is ahead of a modest product from RSA Data Security, Inc. - a program that implements the RSA public key encryption algorithm, named after its authors - American mathematicians Rivest, Shamir and Adelman.
The fact is that RSA algorithm built into most commercial operating systems, as well as many other applications used in various devices - from smart cards to cell phones. In particular, it is also available in Microsoft Windows, which means that it is obviously more widespread than this popular operating system. To detect traces of RSA, for example, in Internet browser Explorer (a program for viewing www-pages on the Internet), just open the "Help" menu (Help), enter the "About Internet Explorer" submenu and view a list of third-party products used. Another common browser, Netscape Navigator, also uses the RSA algorithm. Generally hard to find well-known company working in the area high technology who would not buy a license for this program. To date, RSA Data Security, Inc. has already sold over 450 million(!) licenses.
Why is the RSA algorithm so important?
Imagine that you need to quickly exchange a message with a person who is far away. Thanks to the development of the Internet, such an exchange has become available today to most people - you just need to have a computer with a modem or network card. Naturally, when exchanging information over the network, you would like to keep your messages secret from outsiders. However, it is impossible to completely protect an extended communication line from eavesdropping. This means that when sending messages, they must be encrypted, and when received, they must be decrypted. But how do you and your interlocutor agree on which key you will use? If you send the key to the cipher along the same line, then an eavesdropping attacker can easily intercept it. You can, of course, send the key over some other communication line, for example, send it by telegram. But such a method is usually inconvenient and, moreover, not always reliable: another line can also be tapped. It’s good if you and your addressee knew in advance that you would exchange encryptions, and therefore handed over the keys to each other in advance. But what if, for example, you want to send a confidential offer a potential business partner or buy a product you like in a new online store with a credit card?
In the 1970s, encryption systems were proposed to solve this problem, using two kinds of keys for the same message: open (not requiring secret storage) and closed (strictly secret). The public key is used to encrypt the message, and the private key is used to decrypt it. You send your correspondent the public key, and he encrypts his message with it. All that an attacker who has intercepted the public key can do is to encrypt his letter with it and send it to someone. But he will not be able to decipher the correspondence. You, knowing the private key (it is initially stored with you), will easily read the message addressed to you. To encrypt the response messages, you will use the public key sent by your correspondent (and he keeps the corresponding private key for himself).
Just such a cryptographic scheme is used in the RSA algorithm - the most common public key encryption method. Moreover, the following important hypothesis is used to create a pair of public and private keys. If there are two large ones (requiring more than a hundred decimal digits for their entry) simple numbers M and K, then it will not be difficult to find their product N=MK (it is not even necessary to have a computer for this: a fairly accurate and patient person can multiply such numbers with a pen and paper). But to solve the inverse problem, that is, knowing big number N, decompose it into prime factors M and K (the so-called factorization problem) - almost impossible! It is this problem that an attacker who decides to "crack" the RSA algorithm and read the information encrypted with it will face: in order to find out the private key, knowing the public key, one will have to calculate M or K.
To test the validity of the hypothesis about the practical complexity of factoring large numbers, special competitions have been and are still being held. The record is the decomposition of only 155-digit (512-bit) number. The calculations were carried out in parallel on many computers over the course of seven months in 1999. If this task were performed on one modern personal computer, it would take about 35 years of computer time! Calculations show that using even a thousand modern workstations and the best computational algorithm known today, one 250-digit number can be factorized in about 800 thousand years, and a 1000-digit number in 10 25 (!) years. (For comparison, the age of the Universe is ~10 10 years.)
Therefore, cryptographic algorithms like RSA, operating with sufficiently long keys, were considered absolutely reliable and were used in many applications. And everything was fine until then ...until quantum computers appeared.
It turns out that using the laws of quantum mechanics, you can build computers for which the factorization problem (and many others!) Is not difficult. It is estimated that a quantum computer with only about 10,000 quantum bits of memory can factorize a 1,000-digit number into prime factors in just a few hours!
HOW IT ALL BEGAN?
Only by the mid-1990s did the theory of quantum computers and quantum computing establish itself as a new field of science. As is often the case with great ideas, it's hard to single out a pioneer. Apparently, the Hungarian mathematician I. von Neumann was the first to draw attention to the possibility of developing quantum logic. However, at that time, not only quantum, but also ordinary, classical computers had not yet been created. And with the advent of the latter, the main efforts of scientists turned out to be directed primarily to the search and development of new elements for them (transistors, and then integrated circuits), and not to the creation of fundamentally different computing devices.
In the 1960s, the American physicist R. Landauer, who worked at IBM Corporation, tried to draw the attention of the scientific world to the fact that calculations are always some kind of physical process, which means that it is impossible to understand the limits of our computing capabilities without specifying what physical implementation they are. match. Unfortunately, at that time, the prevailing view among scientists was that computation was some kind of abstract logical procedure that should be studied by mathematicians, not physicists.
As computers proliferated, scientists involved in quantum objects came to the conclusion that it was practically impossible to directly calculate the state of an evolving system consisting of only a few dozen interacting particles, such as a methane (CH 4) molecule. This is explained by the fact that for a complete description of a complex system, it is necessary to keep in the computer memory an exponentially large (in terms of the number of particles) number of variables, the so-called quantum amplitudes. A paradoxical situation arose: knowing the equation of evolution, knowing with sufficient accuracy all the potentials of the interaction of particles with each other and the initial state of the system, it is practically impossible to calculate its future, even if the system consists of only 30 electrons in a potential well, and a supercomputer with RAM is available , the number of bits of which is equal to the number of atoms in the visible region of the Universe (!). And at the same time, to study the dynamics of such a system, one can simply set up an experiment with 30 electrons, placing them in a given potential and initial state. This, in particular, drew the attention of the Russian mathematician Yu. I. Manin, who in 1980 pointed out the need to develop a theory of quantum computing devices. In the 1980s, the same problem was studied by the American physicist P. Benev, who clearly showed that a quantum system can perform calculations, as well as the English scientist D. Deutsch, who theoretically developed a universal quantum computer that surpasses its classical counterpart.
The Nobel Prize winner in physics R. Feynman, who is well known to regular readers of Science and Life, attracted much attention to the problem of developing quantum computers. Thanks to his authoritative appeal, the number of specialists who paid attention to quantum computing has increased many times over.
And yet, for a long time it remained unclear whether the hypothetical computing power of a quantum computer could be used to speed up the solution of practical problems. But in 1994, P. Shor, an American mathematician at Lucent Technologies (USA), stunned the scientific world by proposing a quantum algorithm that allows fast factorization of large numbers (the importance of this problem has already been discussed in the introduction). Compared to the best of the classical methods known today, Shor's quantum algorithm gives a multiple acceleration of calculations, and the longer the factorizable number, the greater the gain in speed. The fast factorization algorithm is of great practical interest for various intelligence services that have accumulated banks of undecrypted messages.
In 1996, Shor's colleague at Lucent Technologies, L. Grover, proposed a quantum fast search algorithm in an unordered database. (An example of such a database is a telephone book, in which the names of subscribers are not arranged alphabetically, but arbitrarily.) The task of finding, choosing the optimal element among numerous options is very common in economic, military, engineering tasks, in computer games. Grover's algorithm allows not only to speed up the search process, but also to approximately double the number of parameters taken into account when choosing the optimum.
The real creation of quantum computers was hindered, in essence, by the only serious problem - errors, or interference. The fact is that the same level of interference spoils the process of quantum computing much more intensively than classical ones. Ways to solve this problem were outlined in 1995 by P. Shor, who developed a scheme for encoding quantum states and correcting errors in them. Unfortunately, the topic of error correction in quantum computers is as important as it is difficult to cover in this article.
DEVICE OF A QUANTUM COMPUTER
Before describing how a quantum computer works, let us recall the main features of quantum systems (see also "Science and Life" No. 8, 1998; No. 12, 2000).
To understand the laws quantum world should not be based directly on everyday experience. In the usual way (in the everyday sense), quantum particles behave only if we constantly "peep" behind them, or, more strictly speaking, constantly measure what state they are in. But as soon as we "turn away" (stop observing), quantum particles immediately pass from a completely definite state into several different hypostases at once. That is, an electron (or any other quantum object) will be partially at one point, partially at another, partially at a third, etc. This does not mean that it is divided into segments, like an orange. Then it would be possible to reliably isolate some part of the electron and measure its charge or mass. But experience shows that after a measurement, an electron always turns out to be “safe and sound” at one single point, despite the fact that before that it had time to visit almost everywhere at the same time. This state of an electron, when it is located at several points in space at once, is called superposition of quantum states and are usually described by the wave function introduced in 1926 by the German physicist E. Schrödinger. The absolute value of the wave function at any point, squared, determines the probability of finding a particle at that point at a given moment. After measuring the position of a particle, its wave function, as it were, contracts (collapses) to the point where the particle was detected, and then begins to spread again. The property of quantum particles to be in many states at the same time, called quantum parallelism, has been successfully used in quantum computing.
quantum bit
The basic unit of a quantum computer is a quantum bit, or, for short, qubit(q-bits). This is a quantum particle that has two basic states, which are denoted 0 and 1, or, as is customary in quantum mechanics, and. Two values of a qubit can correspond, for example, to the ground and excited states of an atom, the up and down directions of the spin of the atomic nucleus, the direction of the current in a superconducting ring, two possible positions of an electron in a semiconductor, and so on.
quantum register
The quantum register is arranged almost in the same way as the classical one. This is a chain of quantum bits over which one- and two-bit logical operations can be performed (similar to the use of NOT, 2AND-NOT, etc. operations in a classical register).
The basic states of a quantum register formed by L qubits include, just as in the classical one, all possible sequences of zeros and ones of length L. In total, there can be 2 L different combinations. They can be considered as a record of numbers in binary form from 0 to 2 L -1 and denoted. However, these basic conditions do not exhaust all possible values quantum register (in contrast to the classical one), since there are also superposition states specified by complex amplitudes related by the normalization condition. Most of the possible values of the quantum register (with the exception of the basic ones) simply do not have a classical analogue. The states of the classical register are only a pitiful shadow of the entire wealth of states of a quantum computer.
Imagine that an external influence is being applied to the register, for example, electrical impulses are applied to a part of space or directed laser beams. If this is a classical register, an impulse, which can be considered as a computational operation, will change L variables. If this is a quantum register, then the same impulse can simultaneously transform to variables. Thus, a quantum register, in principle, is capable of processing information many times faster than its classical counterpart. This immediately shows that small quantum registers (L<20) могут служить лишь для демонстрации отдельных узлов и принципов работы квантового компьютера, но не принесут большой практической пользы, так как не сумеют обогнать современные ЭВМ, а стоить будут заведомо дороже. В действительности квантовое ускорение обычно значительно меньше, чем приведенная грубая оценка сверху (это связано со сложностью получения большого количества амплитуд и считывания результата), поэтому практически полезный квантовый компьютер должен содержать тысячи кубитов. Но, с другой стороны, понятно, что для достижения действительного ускорения вычислений нет необходимости собирать миллионы квантовых битов. Компьютер с памятью, измеряемой всего лишь в килокубитах, будет в некоторых задачах несоизмеримо быстрее, чем классический суперкомпьютер с терабайтами памяти.
However, it should be noted that there is a class of problems for which quantum algorithms do not provide significant acceleration compared to classical ones. One of the first to show this was the Russian mathematician Yu. Ozhigov, who built a number of examples of algorithms that are fundamentally not accelerated on a quantum computer by a single clock cycle.
Nevertheless, there is no doubt that computers operating according to the laws of quantum mechanics are a new and decisive stage in the evolution of computing systems. It remains only to build them.
QUANTUM COMPUTERS TODAY
Prototypes of quantum computers already exist today. True, so far only small registers, consisting of only a few quantum bits, have been experimentally assembled. For example, recently a group led by the American physicist I. Chang (IBM) announced the assembly of a 5-bit quantum computer. Undoubtedly, this is a great success. Unfortunately, the existing quantum systems are not yet capable of providing reliable calculations, as they are either insufficiently controllable or very susceptible to noise. However, there are no physical prohibitions on building an efficient quantum computer, it is only necessary to overcome technological difficulties.
There are several ideas and proposals on how to make reliable and easily manageable quantum bits.
I. Chang develops the idea of using the spins of the nuclei of some organic molecules as qubits.
Russian researcher M. V. Feigelman, who works at the Institute of Theoretical Physics. L. D. Landau, Russian Academy of Sciences, proposes to assemble quantum registers from miniature superconducting rings. Each ring plays the role of a qubit, and states 0 and 1 correspond to the direction of the electric current in the ring - clockwise and counterclockwise. Such qubits can be switched by a magnetic field.
At the Institute of Physics and Technology of the Russian Academy of Sciences, a group led by Academician K. A. Valiev proposed two options for placing qubits in semiconductor structures. In the first case, the role of a qubit is played by an electron in a system of two potential wells created by a voltage applied to mini-electrodes on the semiconductor surface. States 0 and 1 are the positions of the electron in one of these wells. The qubit is switched by changing the voltage on one of the electrodes. In another version, the qubit is the nucleus of a phosphorus atom embedded at a certain point in the semiconductor. States 0 and 1 - the direction of the spin of the nucleus along or against the external magnetic field. The control is carried out using the joint action of magnetic pulses of resonant frequency and voltage pulses.
Thus, research is being actively conducted and it can be assumed that in the very near future - in ten years - an effective quantum computer will be created.
A LOOK INTO THE FUTURE
Thus, it is very possible that in the future quantum computers will be manufactured using traditional microelectronic technology methods and contain many control electrodes, resembling a modern microprocessor. In order to reduce the level of noise, which is critical for the normal operation of a quantum computer, the first models will most likely have to be cooled with liquid helium. It is likely that the first quantum computers will be bulky and expensive devices that do not fit on a desk and are manned by a large staff of white-coated system programmers and hardware technicians. At first, only state structures will have access to them, then rich commercial organizations. But the era of conventional computers began in much the same way.
And what will happen to classical computers? Will they die? Unlikely. Both classical and quantum computers have their own applications. Although, apparently, the ratio in the market will still gradually shift towards the latter.
The introduction of quantum computers will not lead to the solution of fundamentally unsolvable classical problems, but will only speed up some calculations. In addition, quantum communication will become possible - the transfer of qubits over a distance, which will lead to the emergence of a kind of quantum Internet. Quantum communication will provide a protected (by the laws of quantum mechanics) from eavesdropping connection of everyone with each other. Your information stored in quantum databases will be more protected from copying than it is now. Companies producing programs for quantum computers will be able to protect them from any, including illegal, copying.
For a deeper understanding of this topic, you can read the review article by E. Riffel, V. Polak "Fundamentals of Quantum Computing", published in the Russian journal "Quantum Computers and Quantum Computing" (No. 1, 2000). (By the way, this is the first and so far the only journal in the world devoted to quantum computing. Additional information about it can be found on the Internet at http://rcd.ru/qc .). Having mastered this work, you will be able to read scientific articles on quantum computing.
A somewhat greater preliminary mathematical preparation will be required when reading the book by A. Kitaev, A. Shen, M. Vyaly "Classical and Quantum Computing" (Moscow: MTsNMO-Chero, 1999).
A number of fundamental aspects of quantum mechanics that are essential for quantum computing are analyzed in the book "Quantum teleportation - an ordinary miracle" by V. V. Belokurov, O. D. Timofeevskaya, O. A. Khrustalev (Izhevsk: RHD, 2000).
The RCD publishing house is preparing to publish a translation of A. Steen's review on quantum computers as a separate book.
The following literature will be useful not only in cognitive, but also in historical terms:
1) Yu. I. Manin. Computable and non-computable.
M.: Sov. radio, 1980.
2) I. von Neumann. Mathematical foundations of quantum mechanics.
Moscow: Nauka, 1964.
3) R. Feynman. Simulation of physics on computers // Quantum computer and quantum computing:
Sat. in 2 volumes - Izhevsk: RHD, 1999. Vol. 2, p. 96-123.
4) R. Feynman. Quantum mechanical computers
// Ibid., p. 123.-156.
See in a room on the same topic
