Not so simple with a quantum computer

D-Wave's computer, which she calls quantum

Efforts towards a quantum computer have been undertaken since the early 80s of the last century — centuries of great scientific achievements, among which CM is in the first place (although it would not have developed without SRT). The basis of quantum computing is the notion of entanglement. However, the prevailing and widely popularized views on this subject, in my opinion, have gone too far from what strictly follows from the CM. The article is devoted to the paradigm of entanglement, and here the problem of quantum computing is considered. The main content of this article is criticism of the scientific foundations of the dream of the Holy Grail of the Internet era.
')

About qubits for those who are not in the subject

The initial concept is a qubit (quantum bit) - the elementary information carrier. In principle, any quantum object having two basic states, which are denoted

$| 0 \ rangle$ and

$| 1 \ rangle$ . For example, a photon with one of two perpendicular polarizations or an electron with one of two opposite spin directions is suitable for the role of a qubit. From a mathematical point of view, states are vectors that can be multiplied by complex numbers, as well as added together. Thus, in addition to the basic states

$| 0 \ rangle$ and

$| 1 \ rangle$ which are similar to 0 and 1 in the normal bit, the qubit can be in the quantum state

$| x \ rangle = c_0 \ cdot | 0 \ rangle + c_1 \ cdot | 1 \ rangle \ qquad \ qquad (1)$

Where

$c_0, c_1$ - any complex numbers (in particular, real). In this case, the physical state of the qubit will not change if the coefficients

$c_0, c_1$ multiply by the same number

$a \ neq 0$ . Therefore, the vector

$| x \ rangle$ can be normalized, i.e., select a multiplier

$a \ in {\ mathbb C}$ so that new factors

$c_j '= ac_j$ satisfied condition

$| c_0 '| ^ 2 + | c_1' | ^ 2 = 1$ . Then vector

$| x '\ rangle = c_0' \ cdot | 0 \ rangle + c_1 '\ cdot | 1 \ rangle$ called normalized or single.

The physical meaning of state (1), which is called the superposition of the base states, is as follows. If the vector

$| x \ rangle$ are single, then numbers

$| c_0 | ^ 2$ and

$| c_1 | ^ 2$ give the probability that when measuring the state of the qubit will be obtained

$| 0 \ rangle$ and

$| 1 \ rangle$ respectively. After measurement, the qubit will remain in the baseline state that was measured. Only external influence can bring it out. Thus, we can say that a qubit in the normalized state (1) with probability

$| c_0 | ^ 2$ equals 0 and with probability

$| c_1 | ^ 2$ equals 1. Nothing like this can happen with a normal (classic) bit. Superposition - essentially quantum effect! The term "basic" in relation to conditions

$| 0 \ rangle$ and

$| 1 \ rangle$ means that any other state of a qubit can be expressed by their superposition in the sense of (1) for some numbers

$c_0, c_1$ (defined up to proportionality).

The working register of a quantum computer is thought to be a set of

$n$ qubits that are somehow interconnected are tangled . In order to realize its grand potential, the number

$n$ should be big enough let's say

$n> 100$ . Let every qubit number

$j$ in the register is in its state

$| x_j \ rangle$ where

$x_ {j} \ in \ {0,1 \}$ . If we consider a set of

$n$ qubits as a quantum object, its state can be described by a set of vectors

$| x_1 \ rangle | x_2 \ rangle ... | x_n \ rangle$ which is briefly indicated

$| x_1x_2 ... x_n \ rangle$ . Often used the term "tensor product" and designations like

$| x_1 \ rangle \ otimes ... \ otimes | x_n \ rangle$ able to confuse many readers of articles about quantum computers. They can be advised to simply ignore the icon.

$\ otimes$ believing

$| x_1 \ rangle \ otimes | x_2 \ rangle \ otimes ... \ otimes | x_n \ rangle = | x_1x_2 ... x_n \ rangle \ qquad \ qquad (2)$

So far there is no confusion - just a collection of independent qubits, although they are considered to be a single object. Entanglement will appear if we introduce into consideration a superposition of states (2), i.e., vectors (more precisely, tensors) of register states that have the form

$\ sum_ {j = 1} ^ n c_j \ cdot | x_ {1j} x_ {2j}, ..., x_ {nj} \ rangle \ qquad \ qquad (3)$

Where

$c_j$ - complex numbers,

$| x_ {kj} \ rangle$ - state vector

$k$ - go qubit,

$x_ {kj} \ in \ {0,1 \}$ . The set of all possible vectors of the form (3) is called a tensor product

$n$ of the state spaces of single qubits, although it is quite possible to do without the word “tensor” (in the fundamental book of Dirac “Principles of quantum mechanics” it never occurs).

A good article is recommended for an initial but accurate and not popular science introduction to this topic, with paragraphs 2, 3, 4, 5, and 7.1 being sufficient. Paragraph 6 may be omitted without prejudice to the understanding of the main ideas. After you have read this introduction, it will be easier to deal with it, and the presentation of the foundations of quantum mechanics can be completely missed.

Quantum confusion

By definition, state (3) is confusing if this vector cannot be decomposed into a product

$| A_1 \ rangle | A_2 \ rangle ... | A_n \ rangle$ single qubit state vectors. In this case, the effect on any of the qubits can be reflected in the states of some other register qubits. Note that each vector

$| A_j \ rangle$ generally speaking is a superposition of the base so that

$| A_j \ rangle = c_ {j0} | 0 \ rangle + c_ {j1} | 1 \ rangle$ for some numbers

$c_ {j0}, c_ {j1}$ .

To illustrate, consider the case of two qubits. Their general condition

$| 01 \ rangle$ is not confusing, because

$| 01 \ rangle = | 0 \ rangle | 1 \ rangle$ . Measuring, say, the second qubit, we find it in the state

$| 1 \ rangle$ . In this case, the first will remain in the same state

$| 0 \ rangle$ that is, the measurement of the second did not affect him. Now suppose a pair of qubits is in a state

$| 01 \ rangle + | 10 \ rangle$ . It is confusing, because this vector cannot be represented as a product

$| A_1 \ rangle | A_2 \ rangle$ (easy to check).

When measuring the second qubit, we are equally likely

$0.5$ find it in the state

$| 0 \ rangle$ or

$| 1 \ rangle$ . If the second qubit is found in the state

$| 0 \ rangle$ then it means that the tangled pair is in

$| 10 \ rangle$ . Accordingly, the first qubit automatically fell into the state.

$| 1 \ rangle$ . If the second qubit is measured in the state

$| 1 \ rangle$ then the pair turned into

$| 01 \ rangle$ . Consequently, the first qubit was able to

$| 0 \ rangle$ the moment we measured the second. Thus, the measurement of the state of one of the two entangled qubits instantly affects the state of the second. In this case, the initial, general state of a pair of qubits collapses, which is dramatically called the collapse of the wave function (the term “wave function” can be considered a synonym for “state vector”, although there is still a formal difference between them).

Examples of entangled qubits are electrons of one atom or one orbitals, considered in spin states. The Pauli principle forbids two electrons to have a common energy level, orbital and spin moment. Suppose that for one electron we managed to measure the spin, and before that it was in a superposition of spin states. Then the second electron on the same orbital immediately acquires the reverse of its spin, although before that it was also in superposition. Even if when measuring the first electron the second one was not affected!

The figure illustrates the measurement of one qubit in a quantum register of 6 qubits

About the butterfly shaking the galaxy

All this really follows from quantum mechanics, but ... any mathematical model has limited applicability. Obviously, for the applicability of QM, qubits must be really interconnected within a single, quantum system. It is difficult to give a rigorous statement, although everything is intuitive.

Suppose that qubits are photons in polarization states. Obviously, as a single quantum system, they must be part of a single, coherent field, which remains so in the process of its propagation. If each of the photons is in a separate wave packet and they are separated from each other in space (for example, between packages ~ 1 m with package sizes ~ 1 mm), then it is hardly worth talking about their real entanglement.

You can formally consider the vectors of general states of the form (3), but this does not confuse our photons. Physical reality a 'priori corresponds only to vectors of the form (2), which express the fact that each photon is in its “personal” state of polarization, without any connection with others. Quantum mechanics by no means implies that superpositions (3) of such “common states” are related to physical reality. This is a question about the applicability of a mathematical model to which she herself will not answer.

However, enthusiasts of quantum magic essentially believe that any set of homogeneous quantum objects, formally combined into something whole, automatically forms a quantum system with a state space consisting of vectors of the form (3). Since among such states there are tangled, these objects can be confused. It is only necessary to think of how ... or from where to get already confused. Dogmatization of this idea, apparently, greatly contributed to mathematics with their penchant for formal constructions. Quantum computing is a huge field for application of mathematical efforts, on which beautiful results like Shore's algorithm grow! In this case, all refer to the CM, as the supposedly reliable basis of their faith.

Let us return to the example of a pair of qubits in a confused state.

$| 01 \ rangle + | 10 \ rangle$ . Assume that they are separated from each other by a distance that excludes physical interaction (directly and through other bodies). Proponents of quantum magic believe that if the expansion occurs by inertia without external influence, then this entangled state will remain so regardless of the distance between the qubits. Formally, nothing prevents this from counting, but what actually happens after we measure the 1st qubit and find it in the state

$| 1 \ rangle$ , for example? According to the magical paradigm, a pair of qubits will be able to

$| 10 \ rangle$ . But this would mean that by measuring the 1st qubit we automatically influence the 2nd. Even if it is at the other end of the galaxy! The absurdity of such a conclusion does not confuse the scientific community, which accepts the EPR - miracles, as if formally arising from quantum mechanics.

It is more reasonable to assume that the measurement of the 1st qubit will not affect the 2nd one in any way, but will only destroy their joint state without any consequences for the 2nd qubit. He will remain in an individual state.

$| 0 \ rangle + | 1 \ rangle$ which was originally. Accepting this point of view, we must simply clarify the concept of measuring a composite system. Namely: its measurement (which is capable of causing a jump in its own state of the measured quantity) is only such interaction with a macroscopic object, which affects all subsystems, the union of which this system produces.

Thus, the absurd conclusions from the EPR pseudoparadox, which constitute quantum magic, force us to clarify the concept of perturbation. But instead, it is given an absolute sense, as if the flap of a butterfly's wing was considered a perturbation of the Universe, ... although from a philosophical point of view it is so. Of course, these considerations do not refute the EPR - paradigm. The measure of truth is only an experiment. In the article, the fundamental experiments of Alan Aspe are criticized from the point of view of quantum mechanics. There are good reasons to believe that they were misinterpreted.

Magical confusion is necessary to control qubits. It is obvious that a person will be able to interact with individual qubits in the register through pairwise entangled with them, spatially separated objects or spreading qubits to macroscopic distances while maintaining entanglement between them. Otherwise, it is hardly possible to read / write data into quantum registers. Regardless of the physical reality of entanglement in the sense of EPR, the theory of quantum computers has its own difficulties. Consider the specific problem of quantum computing, which is known to many experts, but in general does not attract due attention. It is associated with the symmetry / antisymmetry of joint states of identical particles.

The product of an unsuccessful teleportation of a person (screenshot from the movie “The Fly”)

Quantum teleportation

The EPR is based on the idea of teleportation, that is, a method of transferring the state of qubits to other qubits located at any distance. You can read about this technology in clause 4.2.2 of the article to which I will refer, indicating only paragraphs. The description of the algorithm exactly follows p. 4.1.

A small digression. The theory of quantum computation proceeds from the hypothesis that any unitary transformation of the state space of a quantum register can be physically realized through acting on its qubits (all together or separately). The definition of a unitary transformation is given in § 4 (Quantum gates). The unitarity condition underlies quantum mechanics. In quantum computing, such transformations are called quantum gates (gate), which indicates a connection with the circuitry. In essence, these are reversible logic circuits that convert data in registers, only they act on qubits, not bits. But some quantum gates do not have classical analogs, for example, the 1-qubit Hadamard transform

$H$ (paragraph 4.1.1).

For example valve

$C_ {not}$ it is CONTROLLED-NOT acting on a pair of qubits, like a classic

$C_ {not}$ for a couple of bits. In addition, quantum

$C_ {not}$ preserves state superpositions, i.e .:

$C_ {not} \ bigl (c_ {00} | 00 \ rangle + c_ {01} | 01 \ rangle + c_ {10} | 10 \ rangle + c_ {11} | 11 \ rangle \ bigr) = c_ {00 } | 00 \ rangle + c_ {01} | 01 \ rangle + c_ {10} | 11 \ rangle + c_ {11} | 10 \ rangle)$

Let's return to teleportation. Let Alice and Bob have one qubit each from a tangled pair in general condition

$| \ psi_0 \ rangle = | 00 \ rangle + | 11 \ rangle$ . Alice wants to teleport another qubit to Bob, who is able to

$| \ varphi \ rangle = a | 0 \ rangle + b | 1 \ rangle$ . The state of the set of these qubits can be set by vector

First qubit in the top three

$| xyz \ rangle$ subject to teleportation, the second and third - this is a tangled pair of Alice and Bob qubits, respectively. Alice applies a valve to a vector (4)

$C_ {not} \ otimes I$ , and then

$H \ otimes I \ otimes I$ where

$I$ - identical transformation. In fact, it affects

$C_ {not}$ on the first two qubits that are available to her, and the third remains unchanged. Then it applies a valve to the first qubit.

$H$ , while the other two do not touch.

Then Alice measures the first two qubits, which are in one of the states

$| xy \ rangle$ where

$x, y \ in \ {0,1 \}$ . Accordingly, the bob's qubit entangled with them goes into one of the four states indicated in the table at the end of p. 4.2.2. Alice sends a pair of bits from the measurement to Alice by Bob via a normal connection over the Internet. Depending on the values obtained, he applies one of the gates to his qubit.

$I, x, y, z$ , according to the table at the end of clause 4.2.2. Act

$X, y, z$ described at the beginning of clause 4.1.

As a result of all these manipulations, Bob's qubit enters the state

$a | 0 \ rangle + b | 1 \ rangle$ the qubit that Alice wanted to teleport. At the same time, the state of the latter was destroyed, since state cloning is impossible (proven). Thus, the transfer of the qubit state took place, and the necessary information for this was transmitted in the usual way.

Can you call it teleportation? Even if it were possible to transfer the quantum state of a macroscopic object, then to reproduce it in another place, a physically identical object is required. First, this “blank” must be placed at the place of arrival. Therefore, fantasies about teleportation, as a way to overcome the monstrous, interstellar distances have no basis. In addition, for a person who has undergone such a “null transportation”, it would simply mean death. A copy of the original person that originated at the place of arrival would be a different person, albeit with the same set of memories (see the movie "Moon 2112" and the article ). In any case, the limitation of movement by the speed of light remains in force, since quantum teleportation method involves the transmission of information through signals.

Apparently, even the state of one qubit cannot be teleported. The reason is that it is hardly possible to create a pair of distant, entangled qubits. However, suppose it is possible.

According to quantum mechanics, particles are divided into two classes: bosons and fermions. The first are photons, and the second are electrons. If a set of

$n$ bosons form a single quantum object, the state vectors (3) admissible for it must be symmetrical with respect to any permutations of particles. This means that if in every term

$| x_ {1j} x_ {2j} ... x_ {nj} \ rangle$ rearranging the factors in the same way, the vector (3) should not change. To dial from

$n$ fermions, the admissible states (3) must be antisymmetric with respect to any permutations. This means that if in each term the factors are equally rearranged, then for an even permutation the vector (3) will not change, and for an odd one it will change the sign. It is the difference in behavior when permutations of sets of identical particles divides them into bosons and fermions.

Thus, a pair of entangled Qbits, which are bosons, can be in states

$| 00 \ rangle$ ,

$| 11 \ rangle$ ,

$| 01 \ rangle + | 10 \ rangle$ but cannot be in the state

$| 10 \ rangle$ because during transposition it goes into

$| 01 \ rangle$ . A pair of qubits, which are fermions, cannot be in states

$| 00 \ rangle$ and

$| 11 \ rangle$ because with transposition (odd permutation) they do not change. A pair of fermions may be in a (entangled) state.

$| 01 \ rangle- | 10 \ rangle$ because during transposition it goes into

$| 10 \ rangle- | 01 \ rangle = - (| 01 \ rangle- | 10 \ rangle)$ (i.e. change sign).

The CONTROLLED-NOT transformation does not preserve the symmetry and antisymmetry of states:

$C_{not}(|11\rangle)=|10\rangle$ - the image of the symmetric vector is not symmetrical and not antisymmetric;

$C_{not}(|10\rangle-|01\rangle)=|11\rangle-|01\rangle$ - the image of the antisymmetric vector is not symmetrical and not antisymmetric.

So by applying the transform

$C_{not}$ to a pair of entangled bosons, we obtain a state in which this pair cannot be. Similarly, applying

$C_{not}$ to a pair of entangled fermions, we obtain a state in which they cannot be together. Therefore, any attempt at physical implementation

$C_{not}$ leads to the fact that the state of Alice's two qubits is no longer confused, and the single quantum system will degenerate into a pair of independent qubits with a common state

$|x\rangle|y\rangle$ .

The vector (4), which serves as the initial state of a triplet of qubits, is not symmetric and is not antisymmetric. This also applies to the result of manipulation of it (see § 4.2.2). Thus, this triple of qubits cannot be in an entangled state, since it cannot form a single quantum system of three bosons or three fermions. However, the algorithm assumes that the first pair of qubits is entangled with the third. Since the second and third qubits are entangled, the first two qubits must be entangled among themselves (up to the measurement of the state of their qubits by Alice). But, as shown above, the conversion

$C_{not}$ will destroy this connection.

So, this teleportation algorithm cannot be implemented using physically identical, that is, indistinguishable qubits. And in the case of different quantum particles, the entanglement mechanism does not work. In fact, the state

$|x\rangle|y\rangle+|y\rangle|x\rangle$ does not make sense because if a

$|x\rangle$ is the state vector of the 1st particle, it cannot be the state of the 2nd, similarly

$|y\rangle$ . Swap these factors can not be! In addition, teleportation generally loses its meaning for different particles (you cannot copy the proton state on a neutron)

Apparently, symmetry / antisymmetry considerations can be used to prove the impossibility of teleportation of the qubit state through other algorithms.

But what about the successful experiments on the teleportation of a single qubit, referred to in Section 4.2.2?! The first of these experiments is described in the article . It is clear from the annotation that this experiment was not teleportation in the sense discussed above. It is alleged that there was a measurement of the polarization of one of a pair of entangled and distant photons. It turned out that (as predicted by EPR), the second photon had the same polarization. The authors called this result teleportation. Such freedom to manipulate sci-fi terms introduces a fair amount of confusion in the minds!

But was this experiment confirmed the phenomenon of entanglement of mutually distant particles, which is the basis of quantum magic? Let me say no! Experiments with entangled photons were misinterpreted. In all such experiments, in fact, the facts of the "entanglement" of photons with themselves were recorded. This question is discussed in detail in the article .

Quantum computing

If fermions, for example, electrons in spin states, are used as qubits, then with the number of qubits

$n \ geq 3$ any register state vector is zero. This follows from the general statement: any poly-vector is zero in space, the dimension of which is less than its rank. It is easy to check directly by trying to make an antisymmetric state of the form vectors

$| 000 \ rangle, | 001 \ rangle, \ ldots, | 111 \ rangle$ . Nothing will come out! Do not confuse a zero register state vector that does not correspond to any physical state with a state vector in which all qubits have the value 0.

Thus, fermions are not suitable for quantum registers of more than two qubits. In practice, this means that quantum computers can only be created on the "element base" of bosons . For example, photons or alpha particles, although for the latter it is not clear what to consider as states

$| 0 \ rangle$ and

$| 1 \ rangle$ .

However, as it is customary to describe quantum computers, they are not feasible with boson qubits either!

It is known that any transformation of the binary code can be performed through the composition of the Fredkin gates.

$F$ and toffoli

$T$ (clause 5.1). It is easy to check that the quantum valve

$T$ destroys the symmetry of states:

$T (| 111 \ rangle) = | 110 \ rangle$ . Valve

$F$ acts on symmetric vectors, as the identity transformation. Indeed:

$F (| 111 \ rangle) = | 111 \ rangle$

$\ quad F (| 000 \ rangle) = | 000 \ rangle$

It is easy to understand that any symmetric, three-qubit state vector is a linear combination of vectors in the left sides of these equations. Consequently, the Fredkin valve does not change the symmetric state. Therefore, any sequence of transformations

$F$ and

$T$ applied to triples of qubits in the corresponding bits of the data registers will destroy the entangled states of such triples or leave them unchanged. Therefore, quantum computation implemented by a sequence of gates

$F$ and

$T$ , physically impracticable. From similar considerations (violation of the symmetry of the general state of qubits) it follows that almost all quantum computations can not be done .

God's computer

Suppose you need to calculate some function

$f (x)$ which for the whole argument with

$n$ binary digits takes an integer with

$k$ binary digits. For this you need a register of

$n$ qubits for writing argument values and register from

$k$ qubits for recording function values. Variable

$x$ may be equal

$0, 1, \ ldots, 2 ^ n-1$ . Each of these values corresponds to the state vector of the first register corresponding to the qubit states.

$| 0 \ rangle$ or

$| 1 \ rangle$ which are determined by binary digits of the number

$x$ . Such register states will be denoted by

$| x \ rangle$ , eg

$x = 01 \ ldots 01$ .

Before starting the calculations, the following (normalized) state of the first register is initiated:

$\ frac {1} {\ sqrt {2 ^ n}} \ cdot \ sum_ {x = 0} ^ {2 ^ n-1} | x \ rangle \ qquad \ qquad (5)$

For this to the state

$| 00 \ ldots 0 \ rangle$ the Walsh-Hadamard transform is applied (§ 4.1.1). When measuring the qubits in the state (5) with probability

$P = 2 ^ {- n}$ any integer from

$ inline $ 0 $ inline $ before

$2 ^ n-1$ . Then the second register is set to

$| 0 \ ldots 0 \ rangle$ after which the two register system is able to

$2 ^ {- n / 2} \ cdot \ sum_ {x = 0} ^ {2 ^ n-1} | x, 0 \ rangle$ . In general, it is not confusing. It is believed that this state will become confusing after applying a unitary transformation to the pair of registers.

$U_f$ determined by function

$f (x)$ (see the last paragraph on p. 27 of the article extremal-mechanics.org/wp-content/uploads/2015/07/RIFFEL.pdf , which I constantly refer to). It turns out the following state of this pair:

$\ frac {1} {\ sqrt {2 ^ n}} \ cdot \ sum_ {x = 0} ^ {2 ^ n-1} | x, f (x) \ rangle \ qquad \ qquad (6)$

As seen, one valve application

$U_f$ it was enough to calculate the values

$f (x)$ for all values

$x = 0, 1, \ ldots, 2 ^ n-1$ at the same time.

This is the natural parallelism of quantum computing. With a working number of qubits of the first register of several hundred, the number

$2 ^ n$ will be gigantic, so this parallelism is fundamentally not available on conventional supercomputers. God’s computer is an adequate comparison! However, when reading the results from the second register with the probability

$P = 2 ^ {- n}$ any of the values may be

$f (x)$ . To solve this problem, Grover’s algorithm is proposed, which also suffers from symmetry breaking (see below).

The physical realizability of such parallel computations seems doubtful, if we proceed from symmetry considerations. As was shown above, only bosons can play the role of qubits. Therefore, the vectors of their entangled states should be symmetric, that is, not changing with any permutations. However, it is clear that vector (6) is not symmetric - the transposition of qubits from the first and second registers can change it.

So after applying the transform

$U_f$ the overall state of the register pair is not confusing. Consequently, when measuring the second register in order to obtain the result of the calculations, we will get some number

$f (x_0)$ but can't figure out exactly which value

$x = x_0$ it matches. The fact is that state (6) is physically impossible due to symmetry breaking, therefore the vector

$| x_0, f (x_0) \ rangle$ - one of the components of the vector (6) cannot be obtained by measuring the registers.

A supercomputer cannot be compared with a quantum computer, only the latter can hardly be done in principle.

Grover's algorithm

So, quantum parallelism when calculating arbitrary functions cannot be physically implemented. But suppose for some function

$f (x)$ we managed to do this and we got a couple of registers in general condition (6). How to get access to the results of calculations if all the states in superposition (6) are equiprobable? Just by measuring the state of the registers we get a random pair of binary numbers.

$x, f (x)$ . In this case, the registers will be able to

$| x \ rangle | f (x) \ rangle$ , and all other results of calculations will be irretrievably lost (here it is - the collapse of the wave function!). To solve this problem, Grover came up with a beautiful algorithm (Section 7.1).

Let's say we want to know the value

$f (x_0)$ for quite certain

$x = x_0$ . It is necessary to add one more qubit to the registers to write the values of the logic function.

$P (x)$ which by definition is equal to 1 when

$f (x) = f (x_0)$ and equals 0 when

$f (x) \ neq f (x_0)$ . Then to the vector

$\ frac {1} {\ sqrt {2 ^ n}} \ cdot \ sum_ {x = 0} ^ {2 ^ n-1} | x, f (x), P (x) \ rangle \ qquad \ qquad (7)$

A valve that reverses the signs of the coefficients

$a_x$ with all vectors

$| x, f (x), P (x) \ rangle$ in the amount of (7) for which

$P (x) = 1$ (clause 7.1.2). Initially all

$a_x = 1 / \ sqrt {2 ^ n}$ .

The inversion transformation of all coefficients is applied to the vector (7) thus modified.

$a_x$ relative to their mean

$A$ . It is described in clause 7.1.1, and the summation should be kept to

$N-1 = 2 ^ n-1$ where

$n$ - the number of qubits in the first register. Number inversion

$a_x$ relative to the mean means symmetrical reflection of the corresponding points relative to the point

$A$ on the complex plane. As a result of these witty actions, the coefficients in front of the view vectors

$| x, f (x), 1 \ rangle$ in the sum (7) will increase in absolute value in comparison with the coefficients in front of the type vectors

$| x, f (x), 0 \ rangle$ .

After the described steps of the Grover algorithm are repeated

$\ pi \ sqrt {2 ^ n} / 4$ times (no more!), probability amplitudes (i.e., coefficients

$a_x$ ) for states

$| x, f (x), 1 \ rangle$ become significantly larger than for states

$| x, f (x), 0 \ rangle$ . This means that measuring the second register is most likely to be given by the number

$f (x_0)$ , and the binary code in the first register will be equal to a certain number

$x = \ widetilde x$ , so that

$f (x_0) = f (\ widetilde x)$ (possibly

$\ widetilde x = x_0$ ). This will obtain the desired value of the function.

$f (x)$ at

$x = x_0$ .

If the measurement still does not give the number

$f (x_0)$ then the whole process, including quantum computing, should be repeated until the desired result is obtained. Since he is not known in advance, in any case, you will have to repeat several times, after which you should choose

$f (x)$ the number that occurs most often. Due to the high probability of the event

$P (x) = 1$ There won't be too many such repetitions. So you can get the value

$f (x_0)$ for anyone

$x_0 = 0, 1, \ ldots, 2 ^ n-1$ .

The described method of increasing the amplitudes of the probabilities

$a_x$ in species states

$\ sum_ {x = 0} ^ {2 ^ n-1} a (x) \ cdot | x, f (x), P (x) \ rangle \ qquad \ qquad (8)$

also suffers from violation of symmetry of entangled qubit states. In fact, if any addend

$| x_0, f (x_0), 1 \ rangle$ enters (8) with a coefficient

$a_ {x_0}$ significantly higher than the modulus coefficients of the type vectors

$| x, f (x), 0 \ rangle$ , then such a vector (8) will not be symmetric (antisymmetric).

Therefore, Grover’s algorithm cannot be physically implemented on registers whose qubits are indistinguishable bosons (fermions). It also can not be used for the unordered search records in the file, except for some special cases.

Emulation using Fock spaces

The problem with the symmetry of states is known, but most of the specialists above it clearly do not think about it. As a solution, it is proposed to emulate quantum registers using fermion chains (fermionic lattices) or, in other words, Fock spaces. This idea is as follows.

Let given

$n$ states

$| \ psi_1 \ rangle, \ ldots, | \ psi_n \ rangle$ he cannot accept any fermion, and other states. Then state

$| x_1x_2 \ ldots x_n \ rangle$ virtual, quantum register is proposed to emulate a set of

$k$ such fermions, where

$k$ - number of units in binary code

$x_1x_2 \ ldots x_n$ . In this case, the fermions are in the general antisymmetric state corresponding to the occupied states

$| \ psi_ {j_1} \ rangle, \ ldots, | \ psi_ {j_k} \ rangle$ where

$j_1, \ ldots, j_k$ - numbers of register digits in which there are units. Accordingly, linear combinations of the form (3) of virtual register states are emulated by the same linear combinations of states of fermion chains corresponding to them.

The choice of fermions, not bosons, is due to the fact that no two fermions in this system can be in the same state

$| \ psi_j \ rangle$ . Otherwise, such emulation would be impossible. Thus, the Fock space of fermionic states in which the number of particles varies from

$ inline $ 0 $ inline $ before

$n$ .

It is believed that such an emulation solves the problem of violation of the symmetry of states in the process of quantum calculations. However, it catastrophically complicates the physical implementation of quantum algorithms! The fact is that it is necessary to distinguish and control not 2 states of each qubit in the register from

$n$ qubits as well

$n$ states of fermions in the system, where the number of these particles changes during the calculation. Wherein

$n$ reaches hundreds or thousands if you need a quantum computer with all its fantastic capabilities. The problem of decoherence of physical qubits looks like child's play against this background, and the efforts aimed at solving it were spent largely in vain.

There are also theoretical difficulties associated with emulating entangled states of a virtual register. To determine the entanglement according to the states of the fermion chains, they resort to tricks that do not provide a complete solution to the problem. The consequence of this was for example the fact that the fermion state

$| 10 \ rangle- | 01 \ rangle$ denied the right to be confused on the grounds that this state is supposedly non-physical !

Thus, contrary to the general enthusiasm, the real prospects of quantum computers look very vague. Even without regard to the issue of the physical reality of quantum magic, the fundamental feasibility of quantum computing raises deep doubts. About them, scientists prefer not to tell the society, judging by the popular science enthusiasm around checking violations of Bell's inequality. A huge array of scientific papers and dissertations on quantum computers does not serve as proof of the feasibility of what their authors do. However, the scientific community is no longer able to critically evaluate the EPR paradigm - entanglement, which has become a dogma. In my opinion, perhaps a false view, all this is a grandiose myth, and the gulf between the micro and the macrocosm is insurmountable. People just want to believe in miracles!

Source: https://habr.com/ru/post/401315/

All Articles

Not so simple with a quantum computer

About qubits for those who are not in the subject

Quantum confusion

About the butterfly shaking the galaxy

Quantum teleportation

Quantum computing

God's computer

Grover's algorithm

Emulation using Fock spaces

More articles: