Let’s agree to represent an integer of the form a = a0+ a02 + . . . + al−12l−1 with the base state |a0 a1 . . . al−1 i and place all aj from top to bottom. We will accept the same agreement for the output, only the binary signs bjof the number b = b0+b02+. . .+bl−12l−1 will be written in reverse order-from bottom to top.
The circles here denote the transformation W1, two-qubit operations have the form:
Uk,j =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 eiπ/2k−j
, k > j. (47)
To make sure of this, we will consider the amplitude of the transition from the base state a to the base state b. This concept is legitimate, this is the name of the corresponding element of the matrix of the operator under consideration. Here we will have to be patient - the calculation is ideologically simple, but it requires some tedium. First, we note that the modules of all such amplitudes are the same and, as in the inverse Fourier transform, are equal to 1/2l/2, so we only need to monitor the phase shift, i.e., the argument φ of the complex amplitude eiφ. We will account for this phase incursion by summing the contributions from Walsh transformations with the contributions from two-qubit phase shifts.
To simplify the calculation, we will introduce the following abbreviated notation: b0j = bl−1−j, j = 0, 1, . . . , l − 1 - this will be necessary in order to take into account the reverse order of the binary digits in a and bat the right time. Let’s imagine how the states change when moving from left to right along the wires of our circuit. Actually, the transition from a to b occurs only when performing the Hadamard operation, two-qubit operations do not change the diagonal and basic states, adding only the terms to the phase.
The contribution from the Hadamard operation will be as follows: πajb0j. This number is not equal to zero only if both the j digits of our input and output numbers are equal to 1, which exactly corresponds to the definition of the Hadamard transform. The contribution from a two-qubit operation for j < k will be πajb0k/2k−j, because the state of a changes to b only when the Hadamard device passes, and as can be seen from Figure 24, such a two-qubit operation is performed at the moment when the j-th qubit is still in the state of aj, and k - th is already in the state of b0k. Summing up all these terms of the phase shift, and taking into account that an integer multiple of π can not be taken into account at all, we get this:
π P
l>k>j≥0 ajb0k
2k−j + π P
l>j≥0
ajb0j =
2π P
l>j+k≥0
ajbk2j+k
2l =
2π P
l>j,k≥0
ajbk2j+k
2l =
2π 2l
P
l>j≥0
aj2j P
l>k≥0
bk2j = 2π2l.
(48)
This is exactly what is required in the definition of the inverse Fourier transform. If we need to perform a direct transformation, it is enough to reverse the order of the functional elements in the scheme under consideration and put a minus sign before the phase shift in the definition of two-qubit operations.
Now let’s look at what we just did. The scheme we have constructed that implements the Fourier transform contains about l2 functional elements. Note that if we do not chase the accuracy of this transformation, it will be possible to discard all two-qubit operations that involve qubits that are too far apart from each other. Indeed, the denominator in π/2k−j for them makes the entire fraction negligible, the exponent will be almost one, i.e. such transformations are almost singular and they can be discarded. The scheme will then be much simpler - its size will generally be linear-of the order of C l, where the constant C will, of course, depend on the accuracy we have chosen.
5.5 The Zalka-Wiesner algorithm
The RSA algorithm, which we have studied, operates with qubits, converting their classical (basic) states into quantum ones using the Hadamard operator. This technique illustrates the most important features of the description of evolution at the quantum level, but with a great loss of accuracy. A real particle can occupy several classical positions, not just two, like a qubit.
We will consider the algorithm Z for modeling quantum unitary evolution proposed in [19] (see also [20]), which actually generalizes the GSA to the case of many classical states of each particle. In it, instead of the Hadamard operator "smearing" the amplitude over two possible qubit states, the wave function of a particle capable of being in many classical spatial states is calculated at each step.
The Z algorithm differs from the direct solution of the Schrodinger equation on a classical computer only in that the amplitudes λj of the current quantum state |Ψ(t)i are not calculated directly, but are modeled by the quantum dynamics of qubits in a discrete representation |ji = |0i, |1i, ..., |N −1i of the space of classical states in the computational memory n qubit, N = 2n, in which the wave function is represented as |Ψ(t)i =
N −1
P
j=0
λj|ji.
Recall that the real one-dimensional space of classical states is first translated by a lin-ear transformation D into a segment [0,√
N ], which is then discretized by a qubit represen-tation of numbers with an approximation accuracy of 1/N : xk ≈ k/N, k = 0, 1, ..., N − 1.
Such a representation of the wave vector requires an appropriate discretization of the op-erators. The discrete form of the coordinate operator xdescr and the momentum operator pdiscr was considered in the section 5.3.
In this case, the potential energy operator V becomes a diagonal matrix diag(V (X0), V (X1), V (X2), ..., V (XN −1)), Xk=√
N xk
with potential energy values on the main diagonal, a diagonal representation of the ki-netic energy operator (in the space of its own eigenvectors of the momentum operator) also diagonally: Kdiag = diag(−~2p20/2m), −~2p21/2m), −~2p22/2m), ..., −~2(pN −1)2/2m)), where pk=√
N (xk−1/2), so that in the coordinate basis the kinetic energy is represented by the operator
K = A−1QF T−1 Kdiag QF T A, (49)
where A = diag(exp(πia))a=0,1,...,N −1.
Then the part of the evolution corresponding to the potential energy operator
exp(−iV t/~) in the simple form of the potential will be implemented as a quantum sub-routine, the quantum Fourier transform can also be implemented according to the Shor scheme, that we have considered above, and the operator corresponding to the kinetic en-ergy and time t can also be implemented as a quantum subroutine. Applying the Trotter approximation
exp(A + B) ≈ [exp(A dt) exp(B dt)]t/dt,
we will get an algorithm for computation the evolution Z in the form:
Ut = exp(−i
~
Ht) ≈ [exp(−i
~
K dt) exp(−i
~
V dt)]t/dt (50)
We obtain a model of unitary dynamics with quadratic deceleration compared to the real process. Prove this by using the exponential expansion to the first order by dt. Fix the order of the error = const and, using the accuracy of the Taylor approximation for the exponent, set the number of operations necessary to find the approximation of the resulting state. This number will be equal to t/dt, which will result in a quadratic time dilation compared to the time t of the real process.
The Z algorithm can be generalized to the case of several particles. In this case, the Fourier transform must be applied for each coordinate of each particle separately. This algorithm requires memory that grows proportionally to the first power of the number of real particles, but cannot be used to control a complex system, since it assumes a priori modeling of the process with the transfer of the result to a new similar process, whereas in reality any complex process is not exactly reproducible, and therefore its control requires modeling in real time.
Comparing this calculation with the calculation using the GSA algorithm, which has the form Gtau = (−I˜0Ixtar)τ, we see a complete analogy with the formula (50). In this case, the role of the Walsh-Hadamard operator in the representation of I˜0 = W H · I¯0· W H is played by the quantum Fouret operator in (49). For a single qubit, the Fourier operator just coincides with the Hadamard operator (see the implementation of the Fourier operator in the Appendix), so that the Z algorithm can be considered a generalization of the GSA for the case of many classical states of each of the particles.
So, we see that there are two methods of ultra-fast, inaccessible to a classical com-puter, concentration of the amplitude on the target unknown state. The first is the GSA algorithm, the second is the quantum Fourier transform. It can be shown (prove it!) that the roughest approximation of the Fourier transform is just the Walsh-Hadamard operator, which brings these two techniques together. The fast Shor integer factorization algorithm actually uses the same fundamental features of quantum dynamics as GSA.
The arsenal of quantum methods for spedup classical calculations is thus limited to these general methods of ampitude concentration for problems of the search type, in accordance with the general result [4]. In problems that are not spedup by parallelization, the quan-tum computer does not show any advantages over the classical one, except only for its amazing property of non-locality.