Quantum Programming Foundations: Linear Algebra
Jan 11, 2022
Quantum Programming, by Outline Foundations: linear algebra; 100 minutes; Jan 11, 2022
Copyright By PowCoder代写 加微信 powcoder
Hook: The math that we need for quantum computing is linear algebra. The notation for vectors is from quantum mechanics and differs a bit from what we are used to in math, yet we can learn it. Most of the linear algebra that we need for quantum computing fits into a single lecture.
Purpose: Persuade you that the linear algebra is mostly stuff that you know already.
1. The basic concept is Hilbert spaces.
2. We can explain qubits, superposition, entanglement, and measurement. 3. The possibly unfamiliar stuff is Dirac notation and tensor products.
Transition to Body: First let me introduce the basic mathematical structure that we will use.
Main Point 1: The basic concept is Hilbert spaces.
[A Hilbert space is a set with some operations]
[The key operations that we need for quantum computing are unitary, linear functions] [The concept of a basis]
Transition to MP2: The concepts of quantum computing have mathematical counterparts.
Main Point 2: We can explain qubits, superposition, entanglement, and measurement. [Qubits and superposition]
[Measurement]
[Entanglement and quantum chess]
Transition to MP3: Now have covered the basic stuff and can move on to advanced topics.
Main Point 3: The possibly unfamiliar stuff is Dirac notation and tensor products. [Dirac notation]
[Tensor products] [Laws]
Transition to Close: So there you have it.
Review: Based on Hilbert spaces, we can explain all the concepts of quantum computing, and
when we use tensor products and Dirac notation, the notation is compact.
Strong finish: Now we are ready for quantum computing and we will get into it next lecture. Call to action: Brush up on basic linear algebra by reviewing the second half of Hidary’s book.
Detailed presentation
Hook: The math that we need for quantum computing is linear algebra. Some of the notation for vectors is from quantum mechanics, which differs a bit from what we are used to in math, yet we can learn it. All the linear algebra that we need for quantum computing fits into a single lecture.
Purpose: Persuade you that the linear algebra is mostly stuff that you know already.
1. The basic concept is Hilbert spaces.
2. We can explain qubits, superposition, entanglement, and measurement. 3. The possibly unfamiliar stuff is Dirac notation and tensor products.
Transition to Body: First let me introduce the basic mathematical structure that we will use. Main Point 1: The basic concept is Hilbert spaces.
[A Hilbert space is a set with some operations]
If z = a+bi, then the complex conjugate of z is z∗ = a−bi. The length |z| of z is a nonnegative real number given by |z|2 = zz∗ = (a+bi)(a−bi) = a2 +b2. Euler’s formula says that eiθ = cos θ+i sin θ, so we can represent any complex number as reiθ.
In quantum computing, the state of the system is a unit vector in a Hilbert space. A unit vector is a vector of length 1. A Hilbert space is a vector space with an inner product that satisfies some conditions. In our case, the Hilbert space consists of vectors of complex numbers and scalars that are also complex numbers. Vector addition and scalar multiplication work as usual, and for two vectors,
. . . . . .
the inner product is Σiαi∗βi. Notation: we write the inner product of |v⟩ and |w⟩ as ⟨v|w⟩, which is shorthand for ⟨v||w⟩, which itself is the matrix product of a row vector and column vector. Two vectors are orthogonal if their inner product is 0. Examples:
⟨v|w⟩ = |+⟩ =
|−⟩ = ⟨0|1⟩ =
a0|0⟩ + a1|1⟩ b0|0⟩ + b1|1⟩
(a∗0 a∗1) b0 = a∗0b0 + a∗1b1 b1
√1 (|0⟩+|1⟩) 2
√1 (|0⟩−|1⟩) 2()
(10) 01 = 1×0+0×1 = 0
11(√1) 11 ⟨+|−⟩=(√√)2 =−=0
22−√1 22 2
The outer product of two vectors is defined as follows:
α 1 ( α ∗ β ∗ ) = α 1 α 2∗ α 1 β 2∗ β 1 2 2 β 1 α 2∗ β 1 β 2∗
The outer product is the matrix product of a column vector and a row vector; the result is a matrix.
[The key operations that we need for quantum computing are unitary, linear functions]
A linear operation U is unitary iff UU† = U†U = I. Here U† is the conjugate transpose of U. We have U−1 = U†. Examples:
H = √1 1 1 Ry(θ) = cos(θ/2) −sin(θ/2) S = 1 0 2 1 −1 sin(θ/2) cos(θ/2) 0 i
NOT = X = 0 1 Y = 0 −i Z = 1 0 1 0 i 0 0 −1
The matrices X,Y,Z, are called the Pauli gates. Note that H† = H and H2 = I. Note that H|0⟩ = |+⟩ and H|1⟩ = |−⟩. Here are detailed calculations:
H|0⟩ = √1 1 1 1 = √1 1 = |+⟩ 21−10 21
H|1⟩ = √1 1 1 0 = √1 1 = |−⟩ 2 1 −1 1 2 −1
Note that Z|+⟩ = |−⟩ and Z|−⟩ = |+⟩.
Here is how to decompose H into a sum of outer products:
H = √1 1 1 = √1 1 (10)+√1 1 (01) = (|+⟩⟨0|)+(|−⟩⟨1|) 2 1 −1 2 1 2 −1
Let us check that NOT works like a classical Boolean negation operator. ()()()
NOT |1⟩ NOT (α|0⟩ + β|1⟩)
= 0 1 1 = 0 = |1⟩ 1001
= |0⟩ ()()()
= 0 1 α = β =β|0⟩+α|1⟩ 10βα
[The concept of a basis]
A generating set for a vector space is a finite set of vectors such that every vector in this space can be written as a linear combination of these vectors, that is, if {|ei⟩} is a generating set for a vector space, then every element of the vector space can be expressed as Σi vi|ei⟩. A set of vectors {|ei⟩} is linearly independent if Σi vi|ei⟩ = 0 if and only if vi = 0 for all i. A basis is a generating set of vectors that are all linearly independent. An orthonormal basis is a basis for which the basis vectors are unit vectors and are orthogonal to each other.
Note that {|0⟩,|1⟩} forms an orthonormal basis. Note that {|+⟩,|−⟩} forms an orthonormal basis. The Hadamard gate goes back and forth between the {|0⟩, |1⟩} basis and the {|+⟩, |−⟩}-basis.
Transition to MP2: The concepts of quantum computing have mathematical counterparts. Main Point 2: We can explain qubits, superposition, entanglement, and measurement.
[Qubits and superposition]
A qubit is a vector αβ , where α, β are complex numbers that satisfy |α|2 + |β|2 = 1. Here, α, β
are amplitudes (probabilities as complex numbers). Quantum mechanics people prefer to write α|0⟩ + β|1⟩. Here we see a linear combination, also known as a superposition: the qubit is 0 and 1 at the same time, with some amplitudes.
[Measurement]
We cannot measure the amplitudes in a qubit; this is enshrined in the measurement postulate of quantum mechanics. What we can do is to choose an orthonormal basis {|v⟩, |w⟩} and measure the qubit in that basis. For example, when we measure the qubit α|0⟩ + β|1⟩ in the basis {|0⟩, |1⟩}, we use the Born rule and get:
|0⟩ with probability |α|2
|1⟩ with probability |β|2
More generally, we can choose the orthonormal basis {|v⟩,|w⟩}, rewrite the qubit in that basis: α|0⟩ + β|1⟩ = α′|v⟩ + β′|w⟩, and now the outcome of the measurement is v with probability |α′|2, and w with probability |β′|2. The outcome of the measurement is also the new state of the qubit. We can wonder why measurement alters the state; researchers have proposed three interpretations.
The first is the Copenhagen interpretation ( ), which says that nature operates in a quantum world, but we live in a classical world. The idea that we get information from the quantum world via measurement is an axiom. Intuitively, asking in quantum mechanics “what is a measurement?” is equivalent to asking the axioms of euclidean geometry “what is a point?”.
The second is the many-world interpretation ( ), which says that every time one measures a quantum object, the universe branches into two equally real universes.
The third is the non-local hidden variables interpretation ( ), which says that both of the previous answers are unacceptable and that quantum mechanics is an incomplete theory. Non-local hidden variables is one among several proposals to fill the gap.
In general, for an orthogonal basis {|v⟩,|w⟩}, measurement of |ψ⟩ gives |v⟩ with probability |⟨v|ψ⟩|2, and gives |w⟩ with probability |⟨w|ψ⟩|2.
Suppose we have two qubits:
|ψ⟩ = α00|00⟩ + α01|01⟩ + α10|10⟩ + α11|11⟩ where Σij |αij|2 = 1
The probability that we measure |ij⟩, where i,j ∈ {0,1}2 is |αij|2. Additionally, after the measure- ment, the state of the two qubits is |ij⟩.
Suppose Alice measures the first qubit in the standard basis and observes |0⟩, which she will do with probability |α00|2 + |α01|2. After the measurement, the state of the two qubits is:
α00|00⟩ + α01|01⟩ α00|0⟩ + α01|1⟩ √|α00|2 + |α01|2 = |0⟩ ⊗ √|α00|2 + |α01|2
The probability rule for measuring the second qubit is now given by the rules of conditional prob- ability. Now a measurement of the second qubit in the standard basis will give:
|0⟩ with probability |α00 |2 |α00 |2 +|α01 |2
|1⟩ with probability |α01 |2 |α00 |2 +|α01 |2
Notice that once Alice made her first measurement, the probability of observing each of |10⟩ and |11⟩ becomes zero. Notice also that measuring the first qubit and then measuring the second qubit gives the same result as measuring both qubits at once.
Example of how measuring along way can change the computation. We have HH|0⟩ = |0⟩. In contrast, if we do H|0⟩, then measure, then apply H again, then half of the time we get |+⟩ and half of the time we get |−⟩.
[Entanglement and quantum chess] Suppose we have two qubits:
|ψ⟩ = α00|00⟩ + α01|01⟩ + α10|10⟩ + α11|11⟩ where Σij |αij|2 = 1 One of the possibilities here is a so-called Bell pair, which is an entangled state:
√1 |00⟩ + √1 |11⟩ 22
Notice that if we measure one of the qubits as zero, the other qubit has to measure zero as well. In general, we say that either a state is a tensor product or, otherwise, it is entangled.
Here is an example. Assume there are three characters, Alice, Bob and Charlie. Charlie has two pairs of gloves. Charlie decides based on a random coin flip whether to pick the left-hand gloves or the right-hand gloves. Then Charlie gives each of Alice and Bob a box with one of the picked gloves. Charlie keeps all this secret from Alice and Bob. Afterwards, Alice goes to Mars, while Bob stays on Earth. When Alice opens her box, she finds out she has a left glove, which means that she knows immediately that Bob has a left glove. Since Alice and Bob don’t communicate and thus information does not travel between them, this does not violate relativity theory.
This example doesn’t show the full power of quantum because Charlie picks the gloves before Alice goes to Mars. Thus, Alice is traveling with a classical glove rather than a quantum glove, but she won’t know which one until later. Thus, this example is more of a probabilistic computing example than a quantum computing example.
As an example that may help understand superposition and entanglement, I will discuss quan- tum chess. at USC developed quantum chess and he had the idea to add a layer of quantumness on top of chess. What did he do?
In quantum chess, a piece can exist in superposition. A quantum move consists of up to two standard moves that don’t capture anything. The chance that the piece moved is 50 percent, and the chance that it didn’t move is 50 percent. A measurement may find the piece on either square.
Above, we have a white king, a white pawn, and a white knight. We also have a black king and a black pawn. Now let us do a quantum move with the white knight.
Above, the quantum knight has done a double move, which means that now it is in the new square with 50 percent probability and in the old square with 50 percent probability. We can see this indicated with the two half circles.
Now let us move the black pawn two squares forward.
This moves depends on whether white knight is in the way so the move of the black pawn entangles the white knight and the black pawn. This means that the black pawn moved with 50 percent probability and stayed put with 50 percent probability.
Now let us try to move the white pawn one square forward. This triggers a measurement to see whether the white knight is there.
Above, the measurement gave that the white knight had moved so the white pawn could advance. Because the white knight did move, the black pawn was unable to move. So now we also know that the black pawn is on its original square, and all the probabilities are back to 100 percent.
In contrast, above, the measurement gave that the white knight didn’t move so the white pawn had to stay put. This means that the white knight was not blocking the black pawn, hence the black pawn advanced two squares. Notice that all the probabilities are back to 100 percent.
We saw that superposition is possible and we saw how pieces can get entangled. 8
Transition to MP3: Now have covered the basic stuff and can move on to advanced topics. Main Point 3: The possibly unfamiliar stuff is Dirac notation and tensor products.
[Dirac notation]
We will use Dirac’s ket notation, which is a compact way to write a column vector:
|0⟩=10 and|1⟩=01
Those vectors are pairwise orthogonal unit vectors so they form an orthonormal basis for the vector space; we call it the standard basis. Notice that:
The advantage of the ket notation is that the it labels the basis vectors explicitly.
Dirac’s word “ket” is part of the word bracket; he also has a “bra” notation for row vectors. ⟨0|=(1 0) and ⟨1|=(0 1)
Technically, ⟨i| is the conjugate transpose of |i⟩, so ⟨ψ| = |ψ⟩†.
|ψ⟩ = 21 ⟨ψ| = (1−i √1 )
0 otherwise
|φ⟩ = i |0⟩+1+i|1⟩ ⟨φ| = −i⟨0|+1−i⟨1| √22 √22
In ket notation, the outer product looks like |Ψ1⟩ ⟨Ψ2|. The matrix |Ψ⟩ ⟨Ψ| is called the density matrix of the quantum state Ψ.
[Tensor products]
The tensor product is also known as the Kronecker product; it is defined for two vectors as follows:
We can show that
|α1|2 + |β1|2 = 1 and |α2|2 + |β2|2 = 1
αα2 1 β2 ( )
βα2 1 β2
α1α2
α1β2 = β α
⇐⇒ |α1α2|2 + |α1β2|2 + |β1α2|2 + |β1β2|2 = 1 The above definition generalizes to a tensor product of two matrices.
A11B A12B . . . A1mB
A⊗B = A21B A22B … A2mB . . . .
An1B An2B . . . AnmB
We will write |ψ⟩|φ⟩ as an abbreviation for |ψ⟩ ⊗ |φ⟩. Additionally, we will often eliminate internal
brackets. Thus, |0⟩ ⊗ |1⟩ ⊗ |1⟩ and |0⟩|1⟩|1⟩ and |011⟩ all denote the same vector. 9
If s ∈ {0, 1}n, then |s⟩ denotes a column vector with 2n entries. If we think of s as a number in binary notation, then |s⟩ is a column vector that is 0 everywhere except that it is 1 in the position indexed by the number denoted by s.
(α1|0⟩ + β1|1⟩) ⊗ (α2|0⟩ + β2|1⟩) = α1α2|00⟩ + α1β2|01⟩ + β1α2|10⟩ + β1β2|11⟩
Or, in Dirac notation:
( ) ( ) 0011 NOT⊗H= 01 √1 11 =√1001−1 1 0 2 1 −1 21 1 0 0
√1 |000000⟩ + √1 |111111⟩ = . . . = √1 . 2 2 2 0
|0⟩|0⟩=|0⟩⊗|0⟩= 1⊗1 0 0
|0⟩|1⟩=|0⟩⊗|1⟩= 1⊗0 0 1
|1⟩|0⟩=|1⟩⊗|0⟩= 0⊗1 1 0
|1⟩|1⟩=|1⟩⊗|1⟩= 0⊗0 1 1
0 = 0 1
0 = 0 0
here we have 62
H⊗I = √1 0 1 0 1 21 0 −1 0
φ = √1 0 20
(H⊗I)φ = 211 1
φ = √1 |00⟩+ √1 |11⟩ = √1 |0⟩|0⟩+ √1 |1⟩|1⟩ = √1 (|0⟩⊗|0⟩+|1⟩⊗|1⟩) 22222
1|00⟩ + 1|01⟩ + 1|10⟩ − 1|11⟩ 222222
(H ⊗ I)(√1 |00⟩ + √1 |11⟩)
Now let us use properties of the tensor product to do the calculation.
1 −1 0 0
(H ⊗ I)(φ)
= (H ⊗I)(√1 (|0⟩⊗|0⟩+|1⟩⊗|1⟩)) 2
= √1 ((H|0⟩⊗I|0⟩)+(H|1⟩⊗I|1⟩)) 2
= √1 (((√1 |0⟩+ √1 |1⟩)⊗|0⟩)+((√1 |0⟩− √1 |1⟩)⊗|1⟩)) 22222
= ((12|0⟩ + 12|1⟩) ⊗ |0⟩) + ((12|0⟩ − 12|1⟩) ⊗ |1⟩)
= 12|00⟩ + 12|10⟩ + 12|01⟩ − 12|11⟩
= (I ⊗ X)(√1 (|00⟩ + |11⟩)) = √1 (|01⟩ + |10⟩)) 22
(I ⊗ X)(φ)
The tensor product of two unitary matrices is unitary. Tensor product is associative, distributes over matrix addition, can be applied to a tensor product, and satisfies a “floating scalars” law:
(A⊗B)⊗C = A⊗(B+C) = (A+B)⊗C =
(A⊗B)(C ⊗D) = (αA)⊗B =
A⊗(B⊗C) (A⊗B)+(A⊗C) (A⊗C)+(B⊗C) (AC) ⊗ (BD)
A⊗(αB) = α(A⊗B)
In particular, if |a⟩ = Σj αj|aj⟩ and |b⟩ = Σk βk|bk⟩, then
|a⟩ ⊗ |b⟩ = Σj Σk αjβk(|aj⟩ ⊗ |bk⟩) = Σj Σk αjβk|ajbk⟩
In general, the tensor product fails to be commutative: |0⟩ ⊗ |1⟩ = |01⟩ ̸= |10⟩ = |1⟩ ⊗ |0⟩. Laws about outer product:
|ψ⟩ ⟨φ| |γ⟩ = |ψ⟩ ⟨φ|γ⟩ = ⟨φ|γ⟩ |ψ⟩
(α|v⟩⟨w|M)† = M†(⟨w|)†(|v⟩)†(α)† = M†|w⟩⟨v|α∗ = α∗M†|w⟩⟨v|
We can express any matrix M as a sum of outer product terms:
M = M† = I = |v⟩ = M|v⟩ =
Σi,j Mij|i⟩⟨j| Σ M∗|i⟩⟨j|
Σi,j Mij|i⟩⟨j| Σk vk|k⟩ = Σi,j,k Mijvk|i⟩⟨j| |k⟩ = Σi,j,k Mijvk|i⟩⟨j|k⟩
= Σi,j Mij vj |i⟩
Transition to Close: So there you have it.
Review: Based on Hilbert spaces, we can explain all the concepts of quantum computing, and when we use tensor products and Dirac notation, the notation is compact.
Strong finish: Now we are ready for quantum computing and we will get into it next lecture. Call to action: Brush up on basic linear algebra by reviewing the second half of Hidary’s book.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com