Quantum computing. A Brief Introduction to Quantum Computing (guest post by Roman Dushkin) Quantum Computing Algorithms

MINISTRY OF EDUCATION OF THE RUSSIAN FEDERATION

STATE EDUCATIONAL INSTITUTION

Essay

Quantum computing

Introduction

Chapter I. Basic concepts of quantum mechanics

Chapter II. Basic concepts and principles of quantum computing

Chapter III. Grover's algorithm

Conclusion

Bibliography

Introduction

Imagine a computer whose memory is exponentially larger than its sheer physical size would lead you to expect; a computer that can handle an exponentially larger set of input data simultaneously; a computer that performs calculations in Hilbert space, which is hazy for most of us.

Then you think about a quantum computer.

The idea of ​​a computing device based on quantum mechanics was first considered in the early 1970s and early 1980s by physicists and computer scientists such as Charles H. Bennett of the IBM Thomas J. Watson Research Center and Paul A. Benioff from Argonne National Laboratory in Illinois, David Deutsch from Oxford University, and later Richard P. Feynman from the California Institute of Technology (Caltech). The idea arose when scientists became interested in the fundamental limitations of computing. They realized that if technology continued to gradually reduce the size of computer networks packed into silicon chips, it would lead to individual elements becoming no more than a few atoms. Then a problem arose, since the laws of quantum physics operate at the atomic level, not classical ones. This raised the question of whether it was possible to construct a computer based on the principles of quantum physics.

Feynman was one of the first to try to answer this question. In 1982 he proposed a model of an abstract quantum system suitable for computation. He also explained how such a system could be a simulator in quantum physics. In other words, physicists could conduct computational experiments on such a quantum computer.

Later, in 1985, Deutsch realized that Feynman's claim might eventually lead to a general-purpose quantum computer, and he published landmark theoretical work showing that any physical process could in principle be simulated on a quantum computer.

Unfortunately, all they could come up with at that time were a few rather far-fetched mathematical problems, until Shor released his work in 1994, in which he presented an algorithm for solving an important problem from number theory on a quantum computer, namely, decomposition into prime factors. He showed how a set of mathematical operations designed specifically for a quantum computer could factorize(factorize) huge numbers fantastically quickly, much faster than conventional computers. This was a breakthrough that moved quantum computing from an academic interest to a problem of interest to the whole world.

Chapter I . Basic concepts of quantum mechanics

At the end of the 19th century, there was a widespread opinion among scientists that physics was a “virtually complete” science and that there was very little left for its complete “completeness”: to explain the structure optical spectra of atoms and spectral distribution thermal radiation . Optical spectra of an atom are obtained by the emission or absorption of light (electromagnetic waves) by free or weakly bound atoms; Monatomic gases and vapors, in particular, have such spectra.

Thermal radiation is a mechanism for transferring heat between spatially separated parts of the body due to electromagnetic radiation.

However, the beginning of the 20th century led to the understanding that there could be no talk of any “completeness”. It became clear that to explain these and many other phenomena, it was necessary to radically revise the concepts underlying physical science.

For example, based on the wave theory of light, it turned out to be impossible to give an exhaustive explanation of the entire set of optical phenomena.

When solving the problem of the spectral composition of radiation, the German physicist Max Planck in 1900 suggested that the emission and absorption of light by matter occurs in finite portions, or quanta. At the same time, the energy photon - quantum of electromagnetic radiation(in the narrow sense - light) is determined by the expression

Where is the frequency of emitted (or absorbed) light, and is the universal constant, now called Planck’s constant.

The Dirac constant is often used

Then the quantum energy is expressed as , where

Circular frequency of radiation.

The contradictions between viewing light as a stream of charged particles and as waves led to the concept wave-particle duality.

On the one hand, the photon demonstrates the properties of an electromagnetic wave in the phenomena diffraction(waves bend around obstacles comparable to the wavelength) and interference(superposition of waves with the same frequency and the same initial phase) on scales comparable to the wavelength of the photon. For example, single photons passing through a double slit create an interference pattern on the screen that can be described Maxwell's equations. However, the experiment shows that photons are emitted and absorbed entirely by objects whose dimensions are much smaller than the photon wavelength (for example, atoms), or, in general, to some approximation can be considered pointlike (for example, an electron), that is, they behave like particles - corpuscles. In the macrocosm around us, there are two fundamental ways of transferring energy and momentum between two points in space: the direct movement of matter from one point to another and the wave process of transferring energy without transferring matter. All energy carriers here are strictly divided into corpuscular and wave. On the contrary, in the microworld such division does not exist. All particles, and in particular photons, are attributed both corpuscular and wave properties. The situation is unclear. This is an objective property of quantum models.

The nearly monochromatic frequency radiation emitted by a light source can be thought of as consisting of "packets of radiation" that we call photons. Monochromatic radiation – having a very small frequency spread, ideally one wavelength.

The propagation of photons in space is correctly described by the classical Maxwell equations. In this case, each photon is considered classical in a train waves, defined by two vector fields - the electrostatic field strength and the magnetic field induction. A wave train is a series of disturbances with breaks between them. The radiation of an individual atom cannot be monochromatic, because the radiation lasts a finite period of time, having periods of rise and fall.

It is incorrect to interpret the sum of the squares of the amplitudes as the energy density in the space in which the photon moves; instead, each quantity that depends quadratically on the wave amplitude should be interpreted as a quantity proportional to the probability of some process. Let's say, it is not equal to the energy contributed by the photon to this region, but is proportional to the probability of detecting a photon in this region.

The energy transferred to any location in space by a photon is always equal to . Thereby where is the probability of finding a photon in a given area, and is the number of photons.

In 1921, the Stern-Gerlach experiment confirmed the presence of atoms back and the fact of spatial quantization of the direction of their magnetic moments (from the English spin - to rotate, spin.). Spin- the intrinsic angular momentum of elementary particles, which has a quantum nature and is not associated with the movement of the particle as a whole. When introducing the concept of spin, it was assumed that the electron could be considered as a “rotating top”, and its spin as a characteristic of such rotation. Spin is also the name given to the intrinsic angular momentum of an atomic nucleus or atom; in this case, the spin is defined as the vector sum (calculated according to the rules for adding moments in quantum mechanics) of the spins of the elementary particles forming the system, and the orbital moments of these particles, due to their motion within the system.

Spin is measured in units (reduced Planck constants, or Dirac constants) and is equal to , where J- an integer (including zero) or half-integer positive number characteristic of each type of particle - spin quantum number, which is usually called simply spin (one of the quantum numbers). In this regard, they speak of a whole or half-integer spin of a particle. However, the concepts of spin and spin quantum number should not be confused. A spin quantum number is a quantum number that determines the spin value of a quantum system (atom, ion, atomic nucleus, molecule), i.e., its own (internal) angular momentum. The projection of the spin onto any fixed direction z in space can take on the values J , J-1, ..., -J. Thus, a particle with spin J may be in 2J+1 spin states (at J= 1 / 2 - in two states), which is equivalent to the presence of an additional internal degree of freedom.

The key element of quantum mechanics is Heisenberg uncertainty principle, which says that it is impossible to simultaneously accurately determine the position of a particle in space and its momentum. This principle explains the quantization of light, as well as the proportional dependence of the photon energy on its frequency.

The motion of a photon can be described by Maxwell's system of equations, while the equation of motion of any other elementary particle such as an electron is described by the Schrödinger equation, which is more general.

Maxwell's system of equations is invariant under the Lorentz transformation. Lorentz transformations in the special theory of relativity are called transformations to which space-time coordinates are subjected (x,y,z,t) each event during the transition from one inertial frame of reference to another. In essence, these transformations are transformations not only in space, like Galileo's transformations, but also in time.

Chapter II . Basic concepts and principles of quantum computing

Although computers have become smaller and much faster at their task than before, the task itself remains the same: manipulate a sequence of bits and interpret that sequence as a useful computational result. A bit is a fundamental unit of information, usually represented as a 0 or 1 in your digital computer. Each classical bit is physically realized by a macroscopic physical system, such as the magnetization on a hard drive or the charge on a capacitor. For example, a text composed of n characters, and stored on a typical computer's hard drive, is described by a string of 8n zeros and ones. This is where the fundamental difference between your classical computer and a quantum computer lies. While a classical computer obeys the well-understood laws of classical physics, a quantum computer is a device that exploits quantum mechanical phenomena (especially quantum interference) to implement a completely new way of processing information.

In a quantum computer, the fundamental unit of information (called a quantum bit or qubit), is not binary, but rather quaternary in nature. This property of the qubit arises as a direct consequence of its subjection to the laws of quantum mechanics, which are radically different from the laws of classical physics. A qubit can exist not only in a state corresponding to logical 0 or 1, like a classical bit, but also in states corresponding to mixed or superpositions these classical states. In other words, a qubit can exist as a zero, as a one, and as both 0 and 1. In this case, you can specify a certain numerical coefficient representing the probability of being in each state.

Ideas about the possibility of building a quantum computer go back to the work of R. Feynman in 1982-1986. Considering the question of calculating the evolution of quantum systems on a digital computer, Feynman discovered the “unsolvability” of this problem: it turns out that the memory resources and speed of classical machines are insufficient to solve quantum problems. For example, a system of n quantum particles with two states (spins 1/2 ) It has 2 n basic states; to describe it, it is necessary to specify (and write into the computer memory) 2 n amplitudes of these states. Based on this negative result, Feynman suggested that it is likely that a “quantum computer” will have properties that will allow it to solve quantum problems.

“Classical” computers are built on transistor circuits that have nonlinear relationships between input and output voltages. They are essentially bistable elements; for example, when the input voltage is low (logical "0"), the input voltage is high (logical "1"), and vice versa. In the quantum world, such a bistable transistor circuit can be compared to a two-level quantum particle: we assign the values ​​of logical to the state, state, - boolean value. Transitions in a bistable transistor circuit here will correspond to transitions from level to level: . However, a quantum bistable element, called a qubit, has a new, compared to the classical, property of superposition of states: it can be in any superposition state, where are complex numbers, . States of a quantum system from P two-level particles have in general the form of a superposition 2 n basic condition . Ultimately, the quantum principle of superposition of states makes it possible to impart fundamentally new “abilities” to a quantum computer.

It has been proven that a quantum computer can be built from just two elements (gates): a one-qubit element and a two-qubit controlled NOT element (CNOT). Matrix 2x2 element has the form:

(1)

The gate describes the rotation of the qubit state vector from the z axis to the polar axis specified by the angles . If are irrational numbers, then by repeated use the state vector can be given any predetermined orientation. This is precisely the “universality” of a single-qubit gate in the form (1). In a particular case, we get a single-qubit logical element NOT (NOT): NOT=, NOT=. When physically implementing an element, it is NOT necessary to influence a quantum particle (qubit) with an external pulse that transfers the qubit from one state to another. The controlled NOT gate is executed by influencing two interacting qubits: in this case, through interaction, one qubit controls the evolution of the other. Transitions under the influence of external pulses are well known in pulsed magnetic resonance spectroscopy. The valve does NOT correspond to a spin flip under the influence of an impulse (rotation of the magnetization around the axis by an angle ) . The CNOT gate is executed on two spins 1/2 with Hamiltonian (spin controls ). CNOT is performed in three steps: impulse + free precession over time - impulse. If (the controlling qubit is in the state), then under the specified influences the controlled qubit makes transitions (or ). If (the controlling qubit is in the state), then the result of the evolution of the controlled qubit will be different: (). Thus, spin evolves differently at : here in is the state of the controlling qubit.

When considering the question of implementing a quantum computer on certain quantum systems, first of all, the feasibility and properties of elementary NOT and controlled NOT gates are investigated.

For what follows, it is also useful to introduce the one-qubit Hadamard transform:

In magnetic resonance technology these valves are carried out by pulses:

The diagram of a quantum computer is shown in the figure. Before the computer starts operating, all qubits (quantum particles) must be brought into the state, i.e. to the ground state. This condition in itself is not trivial.

It requires either deep cooling (to temperatures on the order of millikelvin) or the use of polarization methods. system P qubits in a state can be considered a memory register prepared for recording input data and performing calculations. In addition to this register, it is usually assumed that there are additional (auxiliary) registers necessary for recording intermediate results of calculations. Data is recorded by influencing each qubit of the computer in one way or another. Let us assume, for example, that a Hadamard transformation is performed on each qubit of the register:

As a result, the system went into a state of superposition from 2 p basis states with amplitude 2 - n /2 . Each basic state is a binary number from to . The horizontal lines in the figure indicate the time axes.

The execution of the algorithm is accomplished by a unitary superposition transformation. is a unitary matrix of dimension 2 p. When physically implemented through pulsed influences on qubits from the outside, the matrix must be represented as a vector product of matrices of dimension 2 and . The latter can be performed by sequentially influencing single qubits or pairs of qubits :

The number of factors in this expansion determines the duration (and complexity) of the calculations. Everything in (3) is performed using the operations NOT, CNOT, H (or their variations).

It is remarkable that the linear unitary operator acts simultaneously on all terms of the superposition

The results of the calculation are written in the spare register, which was in the state before use. In one run of the computational process we obtain the values ​​of the desired function f for all values ​​of the argument X = 0,..., 2 p - 1 . This phenomenon is called quantum parallelism.

Measuring the result of calculations is reduced to projecting the superposition vector in (4) onto the vector of one of the basic states :

(5)

Here one of the weak points of a quantum computer appears: the number “falls out” during the measurement process according to the law of chance. To find for a given , it is necessary to carry out calculations and measurements many times until it accidentally falls out .

When analyzing the unitary evolution of a quantum system performing a computational process, the importance of physical processes such as interference is revealed. Unitary transformations take place in the space of complex numbers, and the addition of the phases of these numbers has the nature of interference. The productivity of Fourier transforms in the phenomena of interference and spectroscopy is known. It turned out that quantum algorithms invariably contain Fourier transforms. The Hadamard transform is the simplest discrete Fourier transform. Gates of the NOT and CNOT types can be implemented directly on the Mach-Zehnder interferometer using the phenomenon of photon interference and rotation of its polarization vector.

Various ways to physically implement quantum computers are being explored. Model experiments on quantum computing were performed on a pulsed nuclear magnetic resonance spectrometer. In these models, two or three spins (qubits) worked, for example, two spins of 13 C nuclei and one spin of a proton in a trichlorethylene molecule

However, in these experiments the quantum computer was “ensemble”: the computer’s output signals are composed of a large number of molecules in a liquid solution (~ 10 20).

To date, proposals have been made to implement quantum computers on ions and molecules in traps in a vacuum, on nuclear spins in liquids (see above), on the nuclear spins of 31 P atoms in crystalline silicon, on the spins of electrons in quantum dots created in two-dimensional electronic gas in GaAs heterostructures, at Josephson junctions. As we see, in principle, a quantum computer can be built on atomic particles in a vacuum, liquid, or crystals. In each case, certain obstacles must be overcome, but among them there are several common ones, determined by the principles of operation of qubits in a quantum computer. Let's set the task of creating a full-scale quantum computer containing, say, 10 3 qubits (albeit at n = 100 a quantum computer could be a useful tool).

1. We need to find ways to “initialize” the computer’s qubits into the state. For spin systems in crystals, the use of ultra-low temperatures and ultra-strong magnetic fields is obvious. The use of spin polarization by pumping can be useful when cooling and high magnetic fields are simultaneously applied.

For ions in vacuum traps, ultra-low cooling of ions (atoms) is achieved by laser methods. The need for cold and ultra-high vacuum is also obvious.

2. It is necessary to have a technology for selective impact of pulses on any selected qubit. In the field of radio frequencies and spin resonance, this means that each spin must have its own resonant frequency (in terms of spectroscopic resolution). Differences in resonance frequencies for spins in molecules are due to chemical shifts for the spins of one isotope and one element; the necessary frequency differences exist for the spins of nuclei of various elements. However, common sense dictates that these naturally occurring differences in resonant frequencies are unlikely to be sufficient to work with 10 3 spins

More promising approaches seem to be those in which the resonant frequency of each qubit can be controlled externally. In the proposal for a silicon quantum computer, the qubit is the nuclear spin of an impurity atom 31 R. The resonance frequency is determined by the constant A hyperfine interaction of the nuclear and electron spins of the 31 R atom. The electric field on the nanoelectrode located above the 31 R atom polarizes the atom and changes the constant A(respectively, the resonant frequency of the nuclear spin). Thus, the presence of an electrode embeds a qubit into an electronic circuit and tunes its resonant frequency.

3. To perform the CNOT (controlled NOT) operation, interaction between qubits and the form is necessary . Such interaction occurs between the spins of nuclei in a molecule if the nuclei are separated by one chemical bond. In principle, it is necessary to be able to perform the operation on any pair of qubits . It is hardly possible to have physical interaction of qubits of the same magnitude scale and according to the “all with all” principle in the natural environment. There is an obvious need for a way to tune the environment between qubits from the outside by introducing electrodes with a controlled potential. In this way, it is possible to create, for example, an overlap of the wave functions of electrons in neighboring quantum dots and the emergence of an interaction of the form between electron spins [. The overlap of the wave functions of the electrons of neighboring 31 P atoms causes the appearance of an interaction of the type between nuclear spins.

To provide the operation , where and are distant qubits between which there is no interaction of the form, it is necessary to apply in the computer the operation of exchanging states along a chain so that the operation is ensured since the state coincides with the state .

4. During the execution of a unitary transformation corresponding to the selected algorithm, the computer’s qubits are exposed to influence from the environment; as a result, the amplitude and phase of the qubit state vector experience random changes - decoherence. Essentially, decoherence is the relaxation of those degrees of freedom of the particle that are used in the qubit. The decoherence time is equal to the relaxation time. In nuclear magnetic resonance in liquids, relaxation times are 1-10 s. For ions in traps with optical transitions between levels E 0 And E 1 The decoherence time is the time of spontaneous emission and the time of collisions with residual atoms. It is obvious that decoherence is a serious obstacle to quantum computing: the started computational process acquires the features of randomness after the decoherence time has elapsed. However, it is possible to achieve a stable quantum computing process for an arbitrarily long time m > ma if quantum coding and error correction methods (phase and amplitude) are systematically used. It has been proven that with relatively low requirements for error-free execution of elementary operations such as NOT and CNOT (error probability no more than 10 -5), quantum error correction (QEC) methods ensure stable operation of a quantum computer.

It is also possible to actively suppress the decoherence process if periodic measurements are carried out on the system of qubits. The measurement will most likely find the particle in the “correct” state, and small random changes in the state vector will collapse during the measurement (quantum Zeno effect). However, it is difficult to say yet how useful such a technique can be, since such measurements themselves can affect the computational process and disrupt it.

5. The states of the qubits after the completion of the computational process must be measured to determine the result of the computation. Today there is no mastered technology for such measurements. However, the path to searching for such a technology is obvious: it is necessary to use amplification methods in quantum measurement. For example, the nuclear spin state is transferred to the electron spin; the orbital wave function depends on the latter; knowing the orbital wave function, it is possible to organize charge transfer (ionization); the presence or absence of charge on a single electron can be detected by classical electrometric methods. Probe force microscopy methods will probably play a major role in these measurements.

To date, quantum algorithms have been discovered that lead to exponential acceleration of calculations compared to calculations on a classical computer. These include Shor's algorithm for determining prime factors of large (multi-digit) numbers. This purely mathematical problem is closely related to the life of society, since modern encryption codes are built on the “non-computability” of such factors. It was this circumstance that caused a sensation when Shor's algorithm was discovered. It is important for physicists that the solution of quantum problems (solving the Schrödinger equation for many-particle systems) is exponentially accelerated if a quantum computer is used.

Finally, it is very important that in the course of research into quantum computing problems, the main problems of quantum physics are subjected to new analysis and experimental verification: problems of locality, reality, complementarity, hidden parameters, wave function collapse.

The ideas of quantum computing and quantum communication arose a hundred years after the birth of the original ideas of quantum physics. The possibility of building quantum computers and communication systems has been demonstrated by theoretical and experimental studies completed to date. Quantum physics is “sufficient” for the design of quantum computers based on various “element bases”. Quantum computers, if they can be built, will be the technology of the 21st century. Their manufacture will require the creation and development of new technologies at the nanometer and atomic level. This work could likely take several decades. The construction of quantum computers would be another confirmation of the principle of the inexhaustibility of nature: nature has the means to carry out any task correctly formulated by man.

In a conventional computer, information is encoded as a sequence of bits, and these bits are processed sequentially by Boolean logic gates to produce the desired result. Similarly, a quantum computer processes qubits by performing a sequence of operations on quantum logic gates, each of which represents a unitary transformation acting on a single qubit or pair of qubits. By sequentially performing these transformations, a quantum computer can perform a complex unitary transformation over the entire set of qubits prepared in some initial state. After this, you can make measurements on the qubits, which will give the final result of the calculations. These similarities in computation between a quantum computer and a classical computer suggest that, at least in theory, a classical computer can exactly replicate the operation of a quantum computer. In other words, a classical computer can do everything a quantum computer can do. Then why all this fuss with a quantum computer? The point is that, although theoretically a classical computer can simulate a quantum computer, it is very inefficient, so inefficient that practically a classical computer is unable to solve many problems that a quantum computer can do. Simulating a quantum computer on a classical computer is a computationally difficult problem because the correlations between quantum bits are qualitatively different from the correlations between classical bits, as first shown by John Bell. For example, we can take a system of only a few hundred qubits. It exists in Hilbert space with dimension ~10 90 , which would require, when modeling with a classical computer, the use of exponentially large matrices (to perform calculations for each individual state that is also described by the matrix). This means that a classical computer will take exponentially more time compared to even a primitive quantum computer.

Richard Feynman was among the first to recognize the potential of quantum superposition to solve such problems much faster. For example, a system of 500 qubits, which is almost impossible to model classically, is a quantum superposition of 2 500 states. Each value of such a superposition is classically equivalent to a list of 500 ones and zeros. Any quantum operation on such a system, for example a tuned pulse of radio waves that can perform a controlled NOT operation on, say, the 100th and 101st qubits, will simultaneously affect 2 500 states. Thus, in one tick of the computer clock, the quantum operation calculates not one machine state, like conventional computers, but 2 500 states immediately! However, eventually a measurement is made on the system of qubits, and the system collapses into a single quantum state corresponding to a single solution to the problem, a single set of 500 ones and zeros, as dictated by the measurement axiom of quantum mechanics. This is a truly exciting result, since this solution, found by a collective process of quantum parallel computing with its origins in superposition, is equivalent to performing the same operation on a classical supercomputer with ~ 10 150 separate processors (which, of course, is impossible)!! The first researchers in this field were, of course, inspired by such gigantic possibilities, and so the hunt for suitable problems for such computing power soon began. Peter Shor, a researcher and computer scientist at AT&T's Bell Laboratories in New Jersey, proposed a problem that could be solved on a quantum computer and using a quantum algorithm. Shor's algorithm uses the power of quantum superposition to factor large numbers (on the order of ~10,200 bits or more) into factors in a few seconds. This problem has important practical applications for encryption, where the generally accepted (and best) encryption algorithm, known as RSA, is based precisely on the complexity of factoring large composite numbers. , which easily solves this problem, is of course of great interest to the many government organizations using RSA, which until now was considered "unhackable", and to anyone interested in the security of their data.

Encryption, however, is only one possible application of a quantum computer. Shor has developed a whole set of mathematical operations that can be performed exclusively on a quantum computer. Some of these operations are used in his factorization algorithm. Further, Feynman argued that a quantum computer could act as a simulation device for quantum physics, potentially opening the door to many discoveries in the field. Currently, the power and capabilities of a quantum computer are mainly a matter of theoretical speculation; the advent of the first truly functional quantum computer will undoubtedly bring many new and exciting practical applications.

Chapter III . Grover's algorithm

The search problem is as follows: there is an unordered database consisting of N-elements, of which only one satisfies the given conditions - this is the element that needs to be found. If an element can be inspected, then determining whether it meets the required conditions or not is a one-step process. However, the database is such that there is no ordering in place to help select an item. The most efficient classical algorithm for this task is to check the items from the database one by one. If the element satisfies the required conditions, the search is over; if not, then the element is set aside so that it is not checked again. Obviously, this algorithm requires an average of elements to be checked before the desired one is found.

When implementing this algorithm, you can use the same equipment as in the classical case, but specifying the input and output in the form superpositions states, you can find an object for O () quantum mechanical steps instead of ABOUT( N )) classic steps. Each quantum mechanical step consists of an elementary unitary operation, which we will consider below.

To implement this algorithm, we need the following three elementary operations. The first is the preparation of a state in which the system is with equal probability in any of its N basic states; the second is the Hadamard transform and the third is the selective phase rotation of states.

As is known, the main operation for quantum computing is the operation M, acting per bit, which is represented by the following matrix:

that is, a bit in state 0 turns into a superposition of two states: (1/, 1/). Similarly, a bit in state 1 is transformed into (1/, -1/,), i.e., the amplitude value for each state is 1/, but the phase in state 1 is reversed. The phase has no analogue in classical probabilistic algorithms. It arises in quantum mechanics, where the probability amplitude is complex. In a system in which the state is described P bits (i.e. there is N = 2 p possible states), we can carry out the transformation M on each bit independently, sequentially changing the state of the system. In the case where the initial configuration was a configuration with P bits in the first state, the resulting configuration will have equal amplitudes for each state. This is the way to create a superposition with the same amplitude for all states.

The third transformation we will need is to selectively rotate the phase of the amplitude in certain states. The transformation presented here for a two-state system is of the form:

Where j = And - arbitrary real numbers. Note that, unlike the Hadamard transform and other state transformation matrices, the probability of each state remains the same, since the square of the absolute magnitude of the amplitude in each state remains the same.

Let's consider the problem in abstract form.

Let the system have N = 2 p states, which are denoted as ,..., . These 2 p states are represented as n-bit strings. Let there be a single state, say , that satisfies the condition C() = 1, while for all other states S, WITH( ,) = 0 (it is assumed that for any state S the condition is evaluated per unit time). The task is to recognize the state

Let's move on to the algorithm itself

Steps (1) and (2) are a sequence of elementary unitary operations described earlier. Step (3) is the final measurement carried out by the external system.

(1) We bring the system into a state of superposition:

with identical amplitudes for each of the N states. This superposition can be obtained in steps.

(2) Let's repeat the following unitary operation ABOUT( ) once:

a. Let the system be in some state S:

When WITH( S ) = 1, rotate phase by radian;

When С(S) = 0, leave the system unchanged.

b . Apply diffusion transformation D which is determined by the matrix D as follows: if ;" and . D can be implemented as sequential execution of unitary transformations: , where W– Hadamard transformation matrix, R – phase rotation matrix.

(3) Measure the resulting state. This state will be the state WITH( )„ (i.e., the desired state that satisfies the condition (C() = 1) with a probability of at least no less than 0.5. Note that step (2a) is a phase rotation. Its implementation must include a recognition procedure state and the subsequent determination of whether or not to carry out the phase rotation. It must be carried out in such a way as not to leave a trace on the state of the system, so that there is confidence that the paths leading to the same final state are indistinguishable and can interfere. Note that this. procedure Not includes classical measurements.

This quantum search algorithm is likely to be simpler to implement compared to many other known quantum mechanical algorithms, since the required operations are only the Walsh-Hadamard transform and the conditional phase shift operation, each of which is relatively simple compared to the operations used by the others quantum mechanical algorithms.

Conclusion

Currently, quantum computers and quantum information technologies remain in a state of pioneering development. Solving the difficulties these technologies currently face will ensure that quantum computers will advance to their rightful place as the fastest computing machines physically possible. By now, error correction has advanced significantly, bringing us closer to the point where we can build computers that are robust enough to withstand the effects of decoherence. On the other hand, the creation of quantum equipment is still only an emerging industry; but the work done to date convinces us that it is only a matter of time before we can build machines large enough to run serious algorithms like Shor's algorithm. Thus, quantum computers will definitely appear. At the very least, these will be the most advanced computing devices, and the computers we have today will become obsolete. Quantum computing has its origins in very specific areas of theoretical physics, but its future will undoubtedly have a huge impact on the lives of all humanity.

Bibliography

1. Quantum computing: pros and cons. Ed. V.A. Sadovnichigo. – Izhevsk: Udmurt University Publishing House, 1999. – 212 p.

2. Belonuchkin V.E., Zaikin D.A., Tsypenyuk Yu.M., Fundamentals of Physics. General physics course: Textbook. In 2 vols. T. 2. Quantum and statistical physics. – M.: FIZMATLIT, 2001. – 504 p.

3. Valiev K.A. “Quantum computers: can they be made “big”?”, Advances in Physical Sciences, vol. 169, no. 6, 1999.

4. Valiev K.A. “Quantum information science: computers, communications and cryptography”, BULLETIN OF THE RUSSIAN ACADEMY OF SCIENCES, volume 70, no. 8, p. 688-695, 2000

5. Maslov. D. “Quantum computing and communication: reality and prospects”, Computerra, No. 46, 2004.

6. Khalfin L.A. “Quantum Zeno effect”, Advances in Physical Sciences, v. 160, no. 10, 1990.

7. Kholevo A. “Quantum information science: past, present, future,”

IN THE WORLD OF SCIENCE, No. 7, 2008.

8. Center for Quantum Technologies, National University of Singapore www.quantumlah.org

Historical reference

Quantum computing is unthinkable without control over the quantum state of individual elementary particles. Two physicists - the Frenchman Serge Lroche and the American David Wineland - succeeded. Lrosh caught single photons in the resonator and “unhooked” them from the outside world for a long time. Wineland trapped single ions with specific quantum states and isolated them from external influences. Harosh used atoms to observe the state of the photon. Wineland used photons to change the states of ions. They managed to make progress in studying the relationship between the quantum and classical worlds. They were awarded the 2012 Nobel Prize in Physics for “breakthrough experimental techniques that made it possible to measure and control individual quantum systems.”

The operation of quantum computers is based on the properties of a quantum bit of information. If computing processes use P qubits, then the Hilbert state space of a quantum system has a dimension equal to 2". Under Hilbert space we will understand a dimensional vector space in which the scalar product is defined under the condition that the value tends to P to infinity.

In our case, this means that there are 2" base states, and the computer can operate on a superposition of these 2" base states.

Note that an impact on any qubit immediately leads to a simultaneous change in all 2” base states. This property is called "quantum parallelism».

Quantum computing is a unitary transformation. This means that a linear transformation is carried out with complex coefficients, keeping the sum of the squares of the transformed variables unchanged. A unitary transformation is an orthogonal transformation in which the coefficients form a unitary matrix.

Under unitary matrix we will understand the square matrix ||aj|, the product of which by the complex conjugate and transposed matrix || aJI gives the identity matrix. Numbers ajk And a ki complex. If the numbers a ik are real numbers, then the unitary matrix will be orthogonal. A certain number of qubits form the quantum register of a computer. In such a chain of quantum bits, one- and two-bit logical operations can be carried out in the same way as the operations NOT, NAND, 2 OR-HE, etc. are carried out in a classical register. (Fig. 5.49).

Specific number N registers form essentially a quantum computer. The operation of a quantum computer occurs in accordance with developed calculation algorithms.

Rice. 5.49.

NOT - boolean NOT; CNOT - controlled NOT

Qubits as information carriers have a number of interesting properties that completely distinguish them from classical bits. One of the main theses of quantum information theory is state entanglement. Suppose there are two two-level qubits A And IN, realized in the form of an atom with an electronic or nuclear spin, a molecule with two nuclear spins. Due to the interaction of two subsystems A And IN a nonlocal correlation arises that is purely quantum in nature. This correlation can be described by the mixed state density matrix

Where p i- population or probability i- state, so R ( + p 2 + p 3 + + Ra = 1-

The property of coherent quantum states to have a sum of probabilities equal to one is called entanglement, or coupling, of states. Entangled, or entangled, quantum objects are connected to each other no matter how far they are located from each other. If the state of one of the linked objects is measured, then information about the state of other objects is immediately obtained.

If two qubits are interlocked, then they are devoid of individual quantum states. They depend on each other in such a way that the measurement for one type gives “O”, and for the other - “1” and vice versa (Fig. 5.50). In this case, the maximally linked pair is said to carry one e-bit cohesion.

Entangled states are a resource in quantum computing devices, and methods to reliably generate entangled qubits must be developed to replenish the number of entangled states. One of the methods

Rice. 5.50. The maximally entangled pair of qubits scheme is an algorithmic way to obtain entangled qubits on ions in traps, nuclear spins, or a pair of photons. The process of decay of a particle in a singlet state into two particles can be very effective. In this case, pairs of particles are generated that are entangled in coordinate, momentum, or spin.

Developing a comprehensive theory of entanglement is a key goal of quantum information theory. With its help, it will be possible to get closer to solving the problems of teleportation, ultra-dense coding, cryptography, and data compression. For this purpose, quantum algorithms are being developed, including quantum Fourier transforms.

The calculation scheme on a quantum computer has the following algorithm: a system of qubits is formed, on which the initial state is recorded. Through unitary transformations, the state of the system and its subsystems changes when logical operations are performed. The process ends with the measurement of new qubit values. The role of connecting conductors of a classical computer is played by qubits, and the logical blocks of a classical computer are played by unitary transformations. This concept of a quantum processor and quantum logic gates was formulated in 1989 by David Deutsch. He then proposed a universal logic block that could be used to perform any quantum computation.

Doina-Jozhi algorithm allows you to determine “in one calculation” whether a function of a binary variable /(/?) is constant (f x (ri)= Oh, f 2 (ri) = 1 regardless P) or "balanced" (f 3 ( 0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).

It turned out that to construct any calculation, two basic operations are sufficient. The quantum system gives a result that is correct only with some probability. But by slightly increasing the operations in the algorithm, you can bring the probability of obtaining the correct result as close as possible to one. Using basic quantum operations, it is possible to simulate the operation of ordinary logic gates that make up ordinary computers.

Grover's algorithm allows us to find a solution to the equation f(x) = 1 for 0 x in O(VN) time and is intended for database searching. Grover's quantum algorithm is obviously more efficient than any algorithm for unordered search on a classical computer.

Shor's Factorization Algorithm allows you to determine for prime factors aub given integer M= a"Xb by using an appropriate quantum circuit. This algorithm allows you to find the factors of an A-digit integer. It can be used to estimate the computational process time. At the same time, Shor's algorithm can be interpreted as an example of a procedure for determining the energy levels of a quantum computing system.

Zalka-Wiesner algorithm allows you to simulate the unitary evolution of a quantum system P particles in almost linear time using O(n) qubits.

Simon's algorithm solves the black box problem exponentially faster than any classical algorithm, including probabilistic algorithms.

Error Correction Algorithm makes it possible to increase the noise immunity of a quantum computing system that is susceptible to the destruction of fragile quantum states. The essence of this algorithm is that it does not require cloning qubits and determining their state. A quantum logic circuit is formed that is capable of detecting an error in any qubit without actually reading the individual state. For example, triplet 010 passing through such a device detects an incorrect middle bit. The device flips it over without determining the specific values ​​of any of the three bits. Thus, based on information theory and quantum mechanics, one of the fundamental algorithms arose - quantum error correction.

The listed problems are important for creating a quantum computer, but they fall within the competence of quantum programmers.

A quantum computer is more progressive than a classical one in a number of indicators. Most modern computers operate according to the von Neumann or Harvard scheme: P memory bits store state and are changed by the processor every time tick. In a quantum computer, a system of P qubits is in a state that is a superposition of all base states, so a change in the system affects everyone 2" basic states simultaneously. Theoretically, the new scheme can work exponentially faster than the classic one. An almost quantum database search algorithm shows a quadratic increase in power compared to classical algorithms.

The content of the concept of “quantum parallelism” can be revealed as follows: “The data in the calculation process represents quantum information, which at the end of the process is converted into classical information by measuring the final state of the quantum register. The gain in quantum algorithms is achieved due to the fact that when applying one quantum operation, a large number of superposition coefficients of quantum states, which contain classical information in virtual form, are transformed simultaneously.”

Quantum entanglement, also called “quantum superposition,” usually means the following: “Imagine an atom that could undergo radioactive decay in a certain period of time. Or it might not. We can expect that this atom has only two possible states: “decay” and “not decay”, /…/ but in quantum mechanics an atom can have some kind of unified state - “decay - not decay”, that is, neither one nor the other, but, as it were, between. This state is called “. superposition".

The basic characteristics of quantum computers in theory allow them to overcome some of the limitations encountered in the operation of classical computers.

Theory

Qubits

The idea of ​​quantum computing, first expressed by Yu. I. Manin and R. Feynman, is that a quantum system of L two-level quantum elements (qubits) has 2 L linearly independent states, and therefore, due to the principle of quantum superposition, 2 L-dimensional Hilbert state space. An operation in quantum computing corresponds to a rotation in this space. Thus, a quantum computing device of size L a qubit can execute 2 in parallel L operations.

Let's assume there is one qubit. In this case, after measurement, in the so-called classical form, the result will be 0 or 1. In reality, a qubit is a quantum object and therefore, due to the uncertainty principle, it can be both 0 and 1 with a certain probability. If a qubit is 0 (or 1) with one hundred percent probability, its state is denoted using the symbol |0> (or |1>) - in Dirac notation. |0> and |1> are the basic states. In the general case, the quantum state of a qubit is between the base ones and is written in the form , where | a|² and | b|² - probabilities of measuring 0 or 1, respectively; ; | a|² + | b|² = 1. Moreover, immediately after the measurement, the qubit goes into the basic quantum state, similar to the classical result.

There is a qubit in a quantum state In this case, the probability of getting when measuring In this case, when measuring, we got 0 with a 64% probability.

Then the qubit jumps to a new quantum state 1*|0>+0*|1>=|0>, that is, the next time we measure this qubit we will get 0 with one hundred percent probability. This is due to the fact that the Dirac state vector does not depend on time, that is, it is decomposed into a sum of vectors of basic states with time-independent coefficients.

To explain, let us give two examples from quantum mechanics: 1) the photon is in a state of superposition of two polarizations; the measurement once and for all collapses the state of the photon into one with a certain polarization; 2) a radioactive atom has a certain half-life; a measurement may reveal that it has not yet decayed, but this does not mean that it will never decay. a Let's move on to a system of two qubits. Measuring each of them can give 0 or 1. Therefore, the system has 4 classical states: 00, 01, 10 and 11. The basic quantum states are similar to them: |00>, |01>, |10> and |11>. And finally, the general quantum state of the system has the form . Now | a|²+| b|²+| |² - probability of measuring 00, etc. Note that ||²+| c d

|²=1 as the total probability. L In general, systems from L it has 2 qubits

classical states (00000...(L-zeros),...00001(L-digits),..., 11111...(L-units)), each of which can be measured with probabilities of 0-100%.

Thus, one operation on a group of qubits affects all the values ​​that it can take, unlike a classical bit. This ensures unprecedented parallelism of calculations.

Calculation

A simplified calculation scheme on a quantum computer looks like this: a system of qubits is taken, on which the initial state is recorded. The state of the system or its subsystems is then changed through basic quantum operations. At the end the value is measured and this is the result of the computer.

It turns out that to construct any calculation, two basic operations are sufficient. The quantum system gives a result that is correct only with some probability. But by slightly increasing the operations in the algorithm, you can bring the probability of obtaining the correct result as close as possible to one.

Why is a quantum computer better than a classical one? Most modern computers work according to the same scheme: n bits of memory store state and are changed by the processor every time cycle. In the quantum case, a system of n qubits is in a state that is a superposition of all base states, so a change in the system concerns all 2 n basic states simultaneously. Theoretically, the new scheme can work much (exponentially many times) faster than the classical one. In practice, Grover's (quantum) database search algorithm shows a quadratic increase in power compared to classical algorithms. So far they do not exist in nature.

Algorithms

It was shown that “quantum acceleration” is not possible for every algorithm.

Quantum teleportation

The teleportation algorithm implements the exact transfer of the state of one qubit (or system) to another. The simplest scheme uses 4 qubits: a source, a receiver and two auxiliary ones. Note that as a result of the algorithm, the initial state of the source will be destroyed - this is an example of the action of the general principle of impossibility of cloning- it is impossible to create an exact copy of a quantum state without destroying the original. In fact, it is quite easy to create identical states on qubits. For example, having measured 3 qubits, we will transfer each of them to the basic states (0 or 1) and on at least two of them they will coincide. Can't copy arbitrary state, and teleportation is a replacement for this operation.

Teleportation allows you to transfer the quantum state of a system using ordinary classical communication channels. Thus, it is possible, in particular, to obtain the bound state of a system consisting of subsystems located at a large distance.

Applications of quantum computers

Application specifics

It may seem that a quantum computer is a type of analog computer. But this is not true: at its core, it is a digital device, but with an analogue nature.

The main problems associated with the creation and use of quantum computers:

• it is necessary to ensure high measurement accuracy;
• external influences can destroy the quantum system or introduce distortions into it.

Applications to cryptography

Thanks to the enormous speed of decomposition into prime factors, a quantum computer will make it possible to decrypt messages encrypted using a popular asymmetric cryptographic algorithm, opening up new possibilities in the field of message transmission. Prototypes of systems of this kind are at the development stage.

Implementations

The Canadian company D-Wave announced in February 2007 the creation of a sample quantum computer consisting of 16 qubits (the device was called Orion). However, information about this device did not meet the strict requirements of accurate scientific reporting; the news did not receive scientific recognition. Moreover, the company’s further plans (to create a 1024-qubit computer in the near future) aroused skepticism among members of the expert community.

In November 2007, the same company, D-Wave, demonstrated the operation of a sample 28-qubit computer online at a conference on supercomputing. This demonstration also caused a certain kind of skepticism.

In December 2008, the company organized the Distributed Computing project AQUA@home( A diabatic Q.U. antum A lgorithms), which tests algorithms that optimize calculations on D-Wave adiabatic superconducting quantum computers.

see also

Notes

Literature

• Kilin S.Ya. Quanta and information / Progress in optics. - 2001. - Vol. 42. - P. 1-90.
• Kilin S. Ya. Quantum information / Advances in Physical Sciences. - 1999. - T. 169. - P. 507-527.
• Quantum computing pros and cons. Ed. Sadovnichy V. A.
• Quantum computer and quantum computing. Ed. Sadovnichy V. A.
• Valiev K. A., Kokin A. A. Quantum computers: hopes and reality. Moscow, Izhevsk: Regular and Chaotic Dynamics, 2004. 320 p. ISBN 5-93972-024-2

Links

• Quantum computer and its semiconductor elementary base
• Kitaev, A., Shen, A., Vyalyi, M. Classical and quantum computing
• QWiki (English) and Quantiki (English) - Wiki resources for quantum information science
• QCL programming language for quantum computers
• Course “Modern problems of theoretical computer science” (lectures on quantum computing: introduction, super-dense coding, quantum teleportation, Simon and Shor algorithms)
• InFuture.ru: The future of quantum computers is in ternary computing
• Valiev K. A. “Quantum computers and quantum computing” UFN 175 3 (2005)

Wikimedia Foundation.

• 2010.
• Quantum size effect

Quantum dimensional effects

See what “Quantum computing” is in other dictionaries: Quantum computers

- 3 qubits of a quantum register versus 3 bits of a conventional one. A quantum computer is a hypothetical computing device that, by executing quantum algorithms, significantly uses quantum mechanical effects in its operation, such as ... ... Wikipedia- quantum mechanical or quantum field theories, all correlation functions in which do not depend on the choice of coordinates and metrics both in space time and in other spaces involved in defining the theory. This allows you to use... ... Physical encyclopedia

Quantum computer- 3 qubits of a quantum register versus 3 bits of a conventional register. Quantum computer is a computing device operating on the basis of quantum mechanics. A quantum computer is fundamentally different from classical computers based on ... Wikipedia

Due to the general boom of blockchain and all kinds of big data, another promising topic has dropped from the top of tech news - quantum computing. And they, by the way, are capable of revolutionizing several IT areas at once, starting with the notorious blockchain and ending with information security. In the next two articles, Sberbank and Sberbank Technologies will tell you why quantum computing is cool and what they are doing with it now.

Classic calculations: AND, OR, NOT

To understand quantum computing, you should first brush up on classical computing. Here the unit of information processed is a bit. Each bit can be in only one of two possible states - 0 or 1. A register of N bits can contain one of 2 N possible combinations of states and is represented as a sequence of them.

To process and transform information, bitwise operations originating from Boolean algebra are used. The basic operations are one-bit NOT and two-bit AND and OR. Bit operations are described through truth tables. They show the correspondence of the input arguments to the resulting value.

A classical computing algorithm is a set of sequential bit operations. It is most convenient to reproduce it graphically, in the form of a diagram of functional elements (SFE), where each operation has its own designation. Here is an example of SFE for checking two bits for equivalence.

Quantum computing. Physical basis

Now let's move on to a new topic. Quantum computing is an alternative to classical algorithms based on the processes of quantum physics. It states that without interaction with other particles (that is, until the moment of measurement), the electron does not have unambiguous coordinates in the orbit of the atom, but is simultaneously located at all points of the orbit. The region in which the electron is located is called the electron cloud. In the famous double-slit experiment, one electron passes through both slits simultaneously, interfering with itself. Only during measurement does this uncertainty collapse and the electron coordinates become unambiguous.

The probabilistic nature of measurements inherent in quantum computing underlies many algorithms - for example, searching in an unstructured database. Algorithms of this type step by step increase the amplitude of the correct result, allowing it to be obtained at the output with maximum probability.

Qubits

In quantum computing, the physical properties of quantum objects are implemented in so-called qubits (q-bits). A classical bit can only be in one state – 0 or 1. Before measurement, a qubit can be in both states simultaneously, so it is usually denoted by the expression a|0⟩ + b|1⟩, where A and B are complex numbers satisfying the condition |A | 2 +|B| 2 =1. Measuring a qubit instantly “collapses” its state into one of the basic ones – 0 or 1. In this case, the “cloud” collapses into a point, the original state is destroyed, and all information about it is irretrievably lost.

One application of this property is Schrödinger's cat as a true random number generator. The qubit is introduced into a state in which the result of the measurement can be 1 or 0 with equal probability. This condition is described as follows:

Quantum and classical computing. First round

Let's start with the basics. There is a set of initial data for calculations, represented in binary format by vectors of length N.

In classical calculations, only one of 2 n data options is loaded into the computer memory and the value of the function is calculated for this option. As a result, only one out of 2 n possible data sets.

All 2n combinations of source data are simultaneously represented in the memory of a quantum computer. Transformations are applied to all these combinations at once. As a result, in one operation we calculate the function for all 2 n possible variants of the data set (measurement will still only give one solution in the end, but more on that later).

Both classical and quantum computing use logical transformations - gates. In classical computing, input and output values ​​are stored in different bits, which means that in gates the number of inputs can differ from the number of outputs:

Let's consider a real problem. We need to determine whether two bits are equivalent.

If during classical calculations we get one at the output, then they are equivalent, otherwise not:

Now let's imagine this problem using quantum computing. In them, all transformation gates have the same number of outputs as inputs. This is due to the fact that the result of the transformation is not a new value, but a change in the state of the current ones.

In the example, we compare the values ​​of the first and second qubits. The result will be in the zero qubit - the flag qubit. This algorithm is applicable only to the basic states - 0 or 1. Here is the order of quantum transformations.

1. We influence the qubit flag with the “Not” gate, setting it to 1.
2. We use the two-qubit “Controlled Not” gate twice. This gate reverses the value of the flag qubit only if the second qubit involved in the transformation is in state 1.
3. We measure the zero qubit. If the result is 1, then both the first and second qubits are either both in state 1 (the flag qubit changed its value twice) or in state 0 (the flag qubit remained in state 1). Otherwise, the qubits are in different states.

Next level. Quantum single-qubit Pauli gates

Let's try to compare classical and quantum computing in more serious problems. For this we need a little more theoretical knowledge.

In quantum computing, the information being processed is encoded in quantum bits—called qubits. In the simplest case, a qubit, like a classical bit, can be in one of two basic states: |0⟩ (short notation for the vector 1|0⟩ + 0|1⟩) and |1⟩ (for the vector 0|0⟩ + 1 |1⟩). A quantum register is a tensor product of qubit vectors. In the simplest case, when each qubit is in one of the basic states, the quantum register is equivalent to the classical one. A register of two qubits in the |0> state can be written as follows:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

To process and transform information in quantum algorithms, so-called quantum gates are used. They are represented in the form of a matrix. To obtain the result of applying the gate, we need to multiply the vector characterizing the qubit by the gate matrix. The first coordinate of the vector is the multiplier before |0⟩, the second coordinate is the multiplier before |1⟩. The matrices of the main single-qubit gates look like this:

Here is an example of using the Not gate:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

The factors in front of the basis states are called amplitudes and are complex numbers. The modulus of a complex number is equal to the root of the sum of the squares of the real and imaginary parts. The square of the magnitude of the amplitude in front of the basis state is equal to the probability of obtaining this basis state when measuring a qubit, so the sum of the squares of the magnitude of the amplitudes is always equal to 1. We could use arbitrary matrices for transformations over qubits, but due to the fact that the norm (length) vector must always be equal to 1 (the sum of the probabilities of all outcomes is always equal to 1), our transformation must preserve the norm of the vector. This means that the transformation must be unitary and the corresponding matrix must be unitary. Recall that the unitary transformation is invertible and UU † =I.

To more clearly work with qubits, they are depicted as vectors on the Bloch sphere. In this interpretation, single-qubit gates represent the rotation of the qubit vector around one of the axes. For example, the Not(X) gate rotates the qubit vector by Pi relative to the X axis. Thus, the state |0>, represented by a vector pointing straight up, goes into the state |1> pointing straight down. The state of the qubit on the Bloch sphere is determined by the formula cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Quantum two-qubit gates

To build algorithms, only single-qubit gates are not enough for us. Gates are needed that carry out transformations depending on certain conditions. The main such tool is the two-qubit gate CNOT. This gate is applied to two qubits and inverts the second qubit only if the first qubit is in the |1⟩ state. The CNOT gate matrix looks like this:

Here's an application example:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Using a CNOT gate is equivalent to performing a classic XOR operation and writing the result to the second qubit. Indeed, if we look at the truth table of the XOR and CNOT operators, we will see the correspondence:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

The CNOT gate has an interesting property - after its application, the qubits become entangled or unraveled, depending on the initial state. This will be shown in the next article, in the section on quantum parallelism.

Construction of the algorithm - classical and quantum implementation

With a full arsenal of quantum gates, we can begin to develop quantum algorithms. In a graphical representation, qubits are represented by straight lines - “strings” on which gates are superimposed. Single-qubit Pauli gates are designated by ordinary squares, inside of which the rotation axis is depicted. The CNOT gate looks a little more complicated:

Example of using the CNOT gate:

One of the most important actions in the algorithm is measuring the result obtained. The measurement is usually indicated by an arc scale with an arrow and a designation regarding which axis the measurement is being taken.

So, let's try to build a classical and quantum algorithm that adds 3 to the argument.

Summing ordinary numbers in a column implies performing two actions on each digit - the sum of the digits of the digit themselves and the sum of the result with a transfer from the previous operation, if there was such a transfer.

In the binary representation of numbers, the summation operation will consist of the same actions. Here is the code in python:

Arg = #set the argument result = #initialize the result carry1 = arg & 0x1 #add with 0b11, so that the carry from the low bit will appear if the argument has low bit = 1 result = arg ^ 0x1 #add the low bits carry2 = carry1 | arg #add with 0b11, so the carry from the high bit will appear if the argument has the high bit = 1 or there was a carry from the low bit result = arg ^ 0x1 #add the high bits result ^= carry1 #apply carry from the low bit result ^= carry2 #apply carry from the most significant bit print(result)
Now let's try to develop a similar program for a quantum computer:

In this scheme, the first two qubits are the argument, the next two are the transfers, and the remaining 3 are the result. This is how the algorithm works.

1. The first step to the barrier is to set the argument to the same state as in the classic case - 0b11.
2. Using the CNOT operator, we calculate the value of the first carry - the result of the operation arg & 1 is equal to one only when arg is equal to 1, in which case we invert the second qubit.
3. The next 2 gates implement the addition of the least significant bits - we transfer qubit 4 to the |1⟩ state and write the XOR result into it.
4. The large rectangle represents the CCNOT gate, an extension of the CNOT gate. This gate has two control qubits and the third one is inverted only if the first two are in state |1. The combination of 2 CNOT gates and one CCNOT gate gives us the result of the classic operation carry2 = carry1 | arg. The first 2 gates carry to one if one of them is 1, and the CCNOT gate handles the case when they are both equal to one.
5. We add the highest qubits and the transfer qubits.

Interim conclusions

Running both examples, we get the same result. On a quantum computer, this will take longer because additional compilation into quantum assembly code must be carried out and sent to the cloud for execution. The use of quantum computing would make sense if the speed of performing their elementary operations - gates - would be many times less than in the classical model.

Expert measurements show that the execution of one gate takes about 1 nanosecond. So algorithms for a quantum computer should not copy classical ones, but make maximum use of the unique properties of quantum mechanics. In the next article we will look at one of the main such properties - quantum parallelism - and talk about quantum optimization in general. Then we will identify the most suitable areas for quantum computing and describe their applications.

Based on materials