1   This file is online

https://wrf.ecse.rpi.edu/Teaching/parallel-s2020/posts/quantum.html

though that might change.

2   Viewpoint of this presentation

1. I don't care how qbits are implemented. That's important, even necessary, but it's someone else's problem.

2. This recapitulates the development of quantum computing, where the theory was worked out starting in the 1980s, long before actual quantum computers were built.

   (Analogously, the theory for classical computers was worked out in the 1930s, long before real computers were built. Alan Turing contributed to both the theory and the practice.)

3. This presentation may have many errors, but I hope that the general tenor is not too misleading.

3   Entanglement

warmup

Classical metaphor for entanglement:

1. Start with a piece of paper.
2. Tear it into two halves.
3. Put each half into an envelope, seal them, and mix them up, so that you can't tell which half is in which envelope.
4. Address and mail one envelope to a friend in Australia, and the other to a friend in Greenland.
5. When the Australian opens his envelope, he knows what the Greenlander will find in his.
6. However that doesn't let the Australian send any info to the Greenlander, or vv.
7. This has been demonstrated with real qbits transported 1000 miles apart.

Technical details later.

4   Classical computation

1. Bit.
2. Its 2 possible values are 0 or 1.
3. Byte.
4. Has 8 bits.
5. It has 256 possible values.
6. Bits are transformed with gates, like nand, nor, and, or, xor, not, ...
7. They generally destroy info, and are not invertible.
8. More complex circuits, like adders, are formed from a combo of these gates.

5   Quantum computation

1. Qbit, $q$.

2. Its state is a linear combo of two basis states, $|0>$ and $|1>$:

   $q = a|0> + b|1>$ ,

   where $a$ and $b$ are complex numbers, and $ | a | ^2 + | b | ^2 = 1$.

3. IOW, its state is a superposition of those two basis states, with those weights.

4. It is wrong to think that $q$ is really in one of the two states, but you don't know which one. This is the hidden variable theory. It has been proved experimentally to be false.

5. $q$ is really in both states simultaneously.

   Alice laughed. "There's no use trying," she said: "one can't believe impossible things." "I daresay you haven't had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast." - Through the Looking-Glass, and What Alice Found There (1871), by Lewis Carroll (Charles Lutwidge Dodgson).

6. You cannot observe its state, unless it is $|0>$ and $|1>$, in which case you observe $0$ or $1$. This is the classical case.

7. Otherwise you observe it with a measurement operator that transforms it to either $|0>$ and $|1>$, with probabilities

   $| a | ^2$ and $| b | ^2 = 1$, respectively.

8. $a$ and $b$ are complex.

9. That measurement changes $q$; it no longer has its old value.

10. $q$, that is, $q$ 's value, can be considered to be a vector of length one: $$\begin{pmatrix} a | 0> \\ b | 1> \end{pmatrix} $$ or simply $$\begin{pmatrix}a\\b\end{pmatrix}$$.

11. You operate on $q$ with a matrix multiplication: $q_2 = M q$.

12. This changes $q$; the old value is no longer available.

13. No cloning: You cannot copy a qbit, but can move it.

14. The life cycle of a qbit:

    1. Create a qbit with a classical value, 0 or 1.
    2. Operate on it with matrices, which rotate it to have complex weights.
    3. Transform it back to 0 or 1 and read it.

15. So far, not very powerful.

16. Now, let $q$ be a system with two qbits, i.e., a 2-vector of qbits.

17. $q$ is now a linear combo of 4 basis values, $ | 00>$, $ | 01>$, $ | 10>$, $ | 11>$.

18. $q = a_0 | 00> + a_1 | 01> + a_2 | 10> + a_3 | 11> $

19. where $a_i$ are complex and $ \sum | a_i | ^2 = 1$.

20. $q$ exists in all 4 states simultaneously.

21. If $q$ is a vector with n component qbits, then it exists in $2^n$ states simultaneously.

22. This is part of the reason that quantum computation is powerful.

23. Measuring $q$ will collapse it to one of {00, 01, 10, 11} with probabilities $ | a_i | ^2$.

24. You operate on $q$ by multiplying it by a 4x4 matrix operator.

25. The matrices are all invertible, and all leave $ | q | = 1$.

26. You set the initial value of $q$ by setting its two qbits each to 0 or 1.

27. How this is done depends on the particular hw.

28. I.e., initially, $q_1 = \begin{pmatrix}a_1 | 0> \\b_1 | 1> \end{pmatrix}$ and $q_2 = \begin{pmatrix}a_2 | 0> \\b_2 | 1> \end{pmatrix}$, and so

    $$q = \begin{pmatrix} q_1 \\ q_2 \end{pmatrix} = \begin{pmatrix} a_1 a_2 | 00 > \\ a_1 b_2 | 01 > \\ a_2 b_1 | 10 > \\ b_1 b_2 | 11 > \end{pmatrix}$$.

29. Here, the combined state is the tensor product of the individual qbits.

30. For $n$ qbits, the tensor product is a vector with $2^n$ elements, one element for each possible value of each qbit.

31. Each element of the tensor product has a complex weight.

32. You transform a state by multiplying it by a matrix.

33. The matrix is invertible.

34. The transformation doesn't destroy information.

35. When you measure a state, it collapses into one of the component states. (This may be inaccurate.)

36. You don't need to bring in consciousness etc. The collapse happens because the measurement causes the state to interact with the outside world.

37. The probability of collapsing into a particular state is the squared magnitude of its complex weight.

38. For some sets of weights, particularly after a transformation, the combined state cannot be separated into a tensor product of individual qbits. In this case, the individual qbits are entangled.

39. That is the next part of why quantum computation is powerful.

40. Entanglement means that if you measure one qbit then what you observe restricts what would be observed when you measure the other qbit.

41. However that does not let you communicate.

42. From page 171 of

    Quantum Computing for Computer Scientists 1st Edition

    All quantum algorithms work with the following basic framework:

    1. The system will start with the qubits in a particular classical state.
    2. From there the system is put into a superposition of many states.
    3. This is followed by acting on this superposition with several unitary operations.
    4. And finally, a measurement of the qubits.

    1. Ways to look at measurement:
       1. Converts qbit to classical bit.
       2. Is an interaction with the external world.
       3. Information is not lost, but leaks into the external world.
       4. Is an operator represented by a matrix.
       5. that is Hermitian, i.e., it's equal to its complex transpose.
       6. For physical systems, some operators compute the system's momentum, position, or energy.
       7. The matrix's eigenvalues are real.
       8. The result of the operation is one of the eigenvalues.

43. More from

    Quantum Computing for Computer Scientists 1st Edition

    1. Compare byte with qbyte.
    2. State of byte is 8 bits.
    3. State of qbyte is 256 complex weights.
    4. They all get modified by each operation (aka matrix multiply).
    5. That is the power of quantum computing.

44. The current limitations are that IBM does only a few qbits and that the operation is noisy.

45. 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.

46. Common operations (aka gates):

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

    1. Hadamard.

       Creates a superposition.

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

    2. 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

    3. 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.

47. 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

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

6   My RPI course

I've created ECSE-4964 Quantum Computer Programming, CRN 30195. Preliminary syllabus.

This will force me to learn the material.

As of 3/25/2020, 17 students have preregistered.

7   IBM quantum computing

1. They have several quantum computers.

2. The older ones are freely available on the web.

3. Those have 5 and 14 qbits.

4. You submit a batch job and get emailed when it runs.

5. IBM github site: https://github.com/Qiskit with

   1. a free simulator.

      It doesn't match all the physical complexity of the real computer, but it's a good start.

   2. and tutorials and presentations:

6. and a SW development framework. https://qiskit.org/

7. You can create a quantum computation program either by

1. designing a circuit, or
2. using a programming language.

8   Quantum computing on youtube

1. Quantum Algorithms (2:52)

   Which problems can quantum computers solve exponentially faster than classical computers? David Gosset, IBM quantum computing research scientist, explains why algorithms are key to finding out.

2. David Deutsch - Why is the Quantum so Strange? (8:43)

3. Grover's Algorithm (9:57)

   An overview of Grover's Algorithm. An unstructured search algorithm that can find an item in a list much faster than a classical computer can. Several sources are listed.

4. Bob Sutor demonstrates the IBM Q quantum computer (6:53)

5. Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19)

6. "Spooky" physics | Leo Kouwenhoven | TEDxDelft (18:00)

7. David Deutsch - Why is the Quantum so Strange? (8:43)

8. Quantum Computing Concepts – Quantum Hardware (3:22)

9. IBM Introduces First Integrated Quantum Computing System for Commercial Use

10. The World’s First Integrated Quantum Computing System (1:06)