1 Homework 3

here, due Tues.

2 Singular value decomposition correction

The image of the circle or its higher dimensional analogues under any matrix mapping is an ellipse or the analogue of an ellipse in some other number of dimensions. The lengths of the principal axes of this ellipse give what are called the singular values of the matrix. Any matrix A can be written as $A = U S V^*$, where U and V are unitary and S is diagonal with its entries being the singular values. For a hermitian matrix, the SVD is also a eigenvalue decomposition (diagonalization). Thus we can apply the circle/ellipse visualization to the eigenvalues of hermitian matrices. For a unitary matrix, all of the singular values are 1. A unitary matrix only rotates the circle, and does not deform it.

-Richard McQueen

(to everyone: more suggestions and corrections are welcome.)

3 Entangling with Toffoli revisited

1. Here's another way to look at this. Review:

2. $x'=x \\ y'=y \\ z'= z \oplus xy$

3. Use those equations only with classical bits, otherwise use the matrix multiplication.

4. Let x=1, z=0. Then, x'= 1, y'= y, z'= y.

5. So if y=0, then x'= 1, y'= 0, z'= 0.

6. and if y=1, then x'= 1, y'= 1, z'= 1.

7. If y is a superposition of 0 and 1, then the output will be a superposition of the above 2 cases.

8. That is, 50% of the time, we measure y'= 0, z'= 0 and 50% of the time we measure y'= 1, z'= 1.

9. We always measure y' and z' the same.

10. Even if we transport z' a long distance away first.

4 Quantum parallel computation

1. The above is also a first glimpse into parallel computation.

2. You first create a superposition of states.

3. Then the quantum operators operate on all the states in parallel.

4. We haven't yet seen how to pick out the answer we want.

5 Complexity theory - Hidary chap 4

1. Problems vs algorithms.

2. Interesting types of resources: time, space, ...

3. Worst case time, best case time.

4. We want to group problems and algorithms into classes in a way that captures their important properties and ignores the others.

5. competing formal ways to describe algorithms: Turing machine, Church's lambda calculus, ...

   1. different ones had different power (could describe different classes).

   2. the ones listed above seemed to all have the same power.

6. Universal Turing machine.

7. Church-Turing Thesis (CTT): If an algorithm can be performed on any piece of hardware (say, a modern personal computer), then there is an equivalent algorithm for a Universal Turing Machine (UTM) which performs exactly the same algorithm [161, p. 5].

8. Strong Church-Turing Thesis (SCTT) Any algorithmic process can be simulated efficiently using a Universal Turing Machine (UTM)

9. randomness can sometimes lead to a faster algorithm.

10. Extended Church-Turing Thesis (ECTT) Any algorithmic process can be simulated efficiently using a Probabilistic Turing Machine (PTM) [161, p. 6].

11. Quantum Extended Church-Turing Thesis (QECTT) Any realistic physical computing device can be efficiently simulated by a fault-tolerant quantum computer.

6 Hardware implementations

1. Quantum computation was theoretically started decades before actual quantum computers were designed.

2. Many competing technologies.

3. Let the strongest win.