1 Lecture video quality

Did anyone have a problem with the resolution of the lecture 3 video being scaled down to 960x540 instead of the original 1920x1080? That cut the file size from 298MB to 145MB. It's annoying that Mediasite doesn't support H.265, so the codec has to be H.264. In future, I might increase the compression until people start objecting. The main effect of that would be motion artifacts; still images should be the same.

FYI, so far, a CLI is easier than an interactive tool.:

ffmpeg -i c03.mp4 -ss 1:00 -b:a 20k -vf "scale=iw/2:ih/2" c03s.mp4

This is being computed on my P73 laptop with a 6-core Xeon E-2276M CPU @ 2.80GHz (up to 4.70 GHz with Turbo Boost), 128GB of ECC memory, and Quadro RTX 5000 with 16GB. (The only problem with the laptop is it weighs 8 lb.)

2 Quantum Computing for Computer Scientists, ctd.

(I wanted to mix up the math with less mathy stuff).

From end of section 2.3, p.52 to 2.6.

P 52. Transition matrix to convert a vector representation from the canonical basis this another basis is the Hadamark matrix.

Section 2.4. Add an inner product operator to the complex vector space. Note the conjugates in the rules; you don't see them with a real vector space.

Norm, aka length.

We won't need limits etc.

Section 2.5 Eigenvalues and eigenvectors

Eigenvalues don't depend on the representation. Converting to a new basis set doesn't change them.

Geometrically, in 2D, in you transform a circle centered at origin, eigenvalues are lengths of the axes. Eigenvectors are the axes.

Section 2.6 Hermitian and unitary matrices

P 39. Adjoint: conjugate transpose of matrix.

If you use its eigenvectors as a basis, then the matrix diagonalizes to a list of its eigenvalues.

P 62. Hermitian matrix: it is its adjoint.

Unitary: its inverse is its adjoint.

Geometrically, they are rotations since they preserve distances.

Notation confusion: the books uses capital letters both for matrices and vectors.

P 71, tensor product of matrices.

p 80, doubly stochastic matrix.

Multiplying it by a vector of probabilities gives a vector of probabilities (i.e., they sum to 1 and $0\le a_i \le 1$ ).

P 88, Chapter 3, section 3.3 Quantum systems,

Real probabilities add.

When probabilities are norms of complex numbers, they might cancel.

p 91, Ex 3.2.2

p 93 double slit experiment

p 97 Section 3.4, Assembling systems

p 103 Chap Basic quantum theory

Feel free to read ahead.

3 Two qbit operators, ctd

1. https://en.m.wikipedia.org/wiki/Bloch_sphere:

   1. The state of a qbit can be represented as a point on or in a sphere of radius 1.

   2. E.g., |1> is the north pole, |0> the south pole.

   3. Many operations are rotations.

2. Common operations (aka gates):

   https://en.wikipedia.org/wiki/Quantum_logic_gate

   1. Swap

   2. controlled not CNOT cX

      When input is general, it's more sophisticated that it looks.

   3. Hadamard.

      1-qbit creates a superposition.

      https://cs.stackexchange.com/questions/63859/intuition-behind-the-hadamard-gate

      2-qbit creates a uniform superposition

      https://en.wikipedia.org/wiki/Quantum_logic_gate

   4. Toffoli, aka CCNOT.

      Universal for classical boolean functions.

      (a,b,c) -> (a,b, c xor (a and b))

      https://en.wikipedia.org/wiki/Toffoli_gate

   5. Fredkin, aka CSWAP.

      https://en.wikipedia.org/wiki/Fredkin_gate

      3 inputs. Swaps last 2 if first is true.

      sample app: 5 gates make a 3-bit full adder.

3. Bell state

   1. Maximally entangled.

   2. Hadamard then CNOT.

4. Algorithms:

   1. Some, but not all, are faster.

   2. Bounded-error quantum polynomial time (BQP)

      1. "is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances" - https://en.wikipedia.org/wiki/BQP

      2. Includes integer factorization and discrete log.

      3. Relation to NP is unknown (big unsolved problem).

   3. Searching problems:

      1. Find the answer to a puzzle.

      2. Math examples: factor an integer, solve a polynonial equation.

      3. Testing validity of a putative solution is easy.

      4. Finding that putative solution, naively, requires testing all possibilities.

      5. Quantum computation can solve some searching problems faster.

      6. This is probabilistic or noisy; often the found solution is wrong.

      7. So you repeat the computation enough times that the error rate is acceptably low.

      8. Some classical algorithms are similar. There is an excellent probabilistic primality algorithm.

      9. The quantum algorithms are quite complex. (i.e., I'm still learning them.)

   4. Algorithms, another view

      1. Hadamard matrix rotates the pure state to an entangled superposition.

      2. Then we operate in parallel on each state in the superposition.

      3. Finally we separate out the desired answer.

   5. Grover's algorithm:

      1. https://en.wikipedia.org/wiki/Grover%27s_algorithm

      2. Given a black box with N inputs and 1 output.

      3. Exactly one input makes the output 1.

      4. Problem: which one?

      5. Classical solution: Try each input, T=N.

      6. Quantum: $T=\sqrt(N)$.

      7. Probabilistic.

      8. Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.

      9. Can extend to quantum partial search.

      10. Grover's algorithm is optimal.

      11. This suggests that NP is not in BQP .

   6. Shor's algorithm:

      1. Factorize an integer.

      2. in BQP.

      3. almost exponentially faster than best classical algorithm.

      4. Largest examples I can find:

         1. 56153 = 233 × 241.

         2. https://medium.com/@aditya.yadav/rsa-2048-cracked-using-shors-algorithm-on-a-quantum-computer-660cb2297a95

5. https://quantumexperience.ng.bluemix.net/qx/tutorial ctd.