What is order in a complex system? Order is an alternative to chaos. If the system is classical, and ¯p = (p0, p1, ..., pN −1) is a list of probabilities of finding this system in classical states x0, x1, ..., xN −1, then the degree of chaos is the Shannon entropy
Sh(¯p) = −
N −1
X
i=0
pi ln(pi),
When adding new elements to the system, the classical entropy is Sh(¯p) can only increase, therefore, the order cannot increase.
How to generalize the Shannon entropy to the case of a quantum system? A natural generalization is the von Neumann entropy
N (ρ) = −tr(ρ ln(ρ)),
where ρ is the density matrix, which in the quantum case replaces the probability distri-bution ¯p.
Consider the state of two qubits |Ψi = √1
2(|00i + |11i). Its entropy is zero. Indeed, the entropy of any pure state in general is zero. Prove this by reducing the matrix ρ to a diagonal form and showing that the entropy of the state of the form |jihj|, where |ji is one of the basis vectors, is zero.
Let’s assume that we have removed the second qubit by a large distance, so that only the first qubit remains in our hands. Then this qubit will be in a mixed state ρ1 = tr2(|ΨihΨ|), and N (ρ1) = ln(2) > 0. That is, when adding a second qubit, the entropy of the quantum state will decrease.
The effect of increasing the order during the expansion of the system is a counter-intuitive, purely quantum effect. It occurs due to the presence of entanglement, which connects the various physical parts of the system of many bodies.
3 Lecture 3. Quantum gates
The user interface of a quantum computer according to Feynman is based on quantum gates and arrays of them (quantum gate arrays). A quantum gate is a unitary operator operating in the state space of one, two or three qubits, which can be implemented phys-ically. If we take all single-qubit gates and add almost any two-qubit gate to them, for example, the gate
CNOT: |x, yi → |x, y ⊕ xi, we can get a complete system of gates: any unitary trans-formation can be expressed using gates from this set with any predetermined accuracy (see [9]). A huge variety of interesting operators can be built on combinations of gates.
A reader who loves algebraic exercises can refer to the book [10], which contains many interesting problems on quantum computing.
Thus, the first task of implementing the Feynman scheme of quantum computing is the implementation of single-qubit gates and CNOT. Consider a CiNOT gate that is close to CNOT: CiN OT |x, yi = eiπx/2CN OT |x, yi. We will show how to implement the one-qubit gate iN OT : |xi → i|x ⊕ 1i and the quantum gate CiNOT on the charge states of electrons in quantum dots. Having one-qubit gates and CiNOT, it is also possible to implement CNOT, since it is obtained from CiNOT by applying a one-qubit relative rotation of the phase e−iπx/2to the first qubit. This implementation of CNOT is one of the first proposals for the implementation of entangling gates on charge states (see [11]), its scheme is the simplest, although it presents certain technological difficulties.
We introduce the concept of a quantum dot. This is a small region in a solid-state structure in which a potential is created in the form of two wells with a sufficiently high potential barrier between them, and one electron can be in this potential (see figure 11).
Finding an electron in the right well means the state |0i, in the left - |1i.
The Hamiltonian of such a system has the form H = c1I − bσx, where σx is the first Pauli matrix defined in (9), b > 0. You can show that the eigenstates of this Hamiltonian will be
|φ0i = 1
√2(|0i + |1i, |φ1i = 1
√2(|0i − |1i, (29)
Figure 11: A quantum dot in the form of a two-hole potential
Figure 12: CiNOTon charge states
moreover, their eigenvalues are ordered so that E0 < E1, so that |φ0i will be the main state, and |φ1i will be the excited state. We find a solution to the Cauchy problem for the Schrodinger equation with such a Hamiltonian in the form
|Ψ(t)i = A0e−iE0t~ |φ0i + A1e−iE1t~ |φ1i = e−iE0t~ (A0|φ0i + e−i(E1−E0)t~ A1|φ1i) (30) and now, considering that the states of eiθ|Ψi are physically indistinguishable for any vector |Ψi, we come to the conclusion that to implement the gate NOT: |0i → |1i, |1i →
|0i, it is enough just to wait for a while 12τ = π~/(E1− E0).
It follows from the formula (30) that the basic states of an electron in a quantum dot oscillate, that is, they pass one into another |0i → |1i → |0i and |1i → |0i → |1i with the period τ = 2π~/(E1− E0), which we will call the oscillation period.
Here we ignored the phase multiplier e−iE0t~ , which has no physical meaning if the NOT operator is performed for any states. But suppose that NOT is performed conditionally, for example, only if some other qubit has the value 1, and if its value is 0, then NOT over x is not performed. In this case, it is necessary to take into account the total run of the phase, and take into account this multiplier. Find E0 and E1 and write an exact expression for the operator implemented by this subroutine at x = 1 for the time τ /2.
Answer: this is the iσx operator. We will show how to implement an operator close to CNOT on atomic excitations, where the Hamiltonian will have the inverse sign, and the similar operator will have the form −iσx.
The implementation of the CiNOT gate requires two quantum dots located perpendic-ular to each other, as shown in the figure 12. The Coulomb interaction of two electrons, each of which is located at one of these points, leads to the effect of changing the potential barrier at the point y. The potential barrier between the wells at the point y turns out to be higher if the electron of the point x is in the state |1i, compared to the situation when the electron of the point x is in the state |0i due to the fact that the repulsion of electrons is higher at a close distance.
Let’s first assume that we managed to fix the position of the electron x in some way, so that it does not tunnel between its wells. Then you can find such a time τCiN OT that after this time the conversion of CiN OT will occur. Indeed, let the difference of the energy levels of the y - electron corresponding to the positions of the x - electron |0i and |1i be equal to dE0 = E10− E00 and dE1 = E11− E01, respectively. Then the oscillation periods for the y electron when the x electron is at the position |0i and |1i will be, respectively, τ0 = 2π~/(dE0) and τ1 = 2π~/(dE1). By varying the distance between the points, we can choose these values in such a way that for a certain time value τCiN OT, an even number of oscillations with an upper index of 0 and an odd number with an upper index of 1 would fit into it, which will give us the required operator CN OT when fixing the position of thex electron. The details are provided to the listeners.
How to prevent tunneling of the x - electron? This can be done by increasing the potential barrier between the wells at the x point so that during the tunneling between them, the x electron was significantly less than τCiN OT, and then, after making CiN OT , again reduce this barrier to the usual level, which is done by the external potential. This is how the CiN OT gate is implemented. The problem is that an electron that is in the excited state |φ1i at one point is able to emit a photon, going into the state |φ0i, which will prevent the implementation of the CiN OT gate according to this scheme.
A similar problem always occurs when implementing confusing error gates. For short computations, they may be negligible, but for practically important long computations, they pose a problem. We will return to this topic later, when studying more realistic models of quantum computers.
3.1 Single-qubit gates , CN OT, CSign, Λ
φand T of f oli
Prove that one-qubit gates have the form eα
ei(φ+ξ)cos(θ) ei(φ+ξ)sin(θ)
−eiφsin(θ) cos(θ)
for some real α, ξ, θ, φ. Instruction: find the number of independent real parameters defin-ing the unitary operator.
How to get the root of the gate N OT - that is, such a gate V that V2 = N OT ? The gate CN OT is a 1-controlled NOT, it is defined as CN OT |x, yi = |x, x ⊕ yi, where ⊕ is addition modulo 2. Construct the matrix CN OT .
Figure 13: Implementation of a 2-controlled gate using CNOT and a one-bit V , where V2 = U
2-controlled gate U is defined as
Λ2U : |x, y, zi = |x, y, zi if xy = 0,
|x, yiU |xi, if xy = 1
Show that the gate Λ2U can be implemented using the quantum gate system shown in Figure 35.
Instructions. Consider only the actions of gates on the basic states.