1.1 Submission mechanism

Submit material to Homework 14

The deadline is extended to 9am Mon. I will grade whatever has been submitted at that time.

1.2 Inspiration for finishing your term projects

1. The Underhanded C Contest

   "The goal of the contest is to write code that is as readable, clear, innocent and straightforward as possible, and yet it must fail to perform at its apparent function. To be more specific, it should do something subtly evil. Every year, we will propose a challenge to coders to solve a simple data processing problem, but with covert malicious behavior. Examples include miscounting votes, shaving money from financial transactions, or leaking information to an eavesdropper. The main goal, however, is to write source code that easily passes visual inspection by other programmers."

2. The International Obfuscated C Code Contest

3. https://www.awesomestories.com/asset/view/Space-Race-American-Rocket-Failures

   Moral: After early disasters, sometimes you can eventually get things to work.

4. The 'Wrong' Brothers Aviation's Failures (1920s)

5. Early U.S. rocket and space launch failures and explosion

1.1 Thurs, Dec 1

1. Denzell D

2. Paul R

1.2 Mon, Dec 5

1. Richard P

2. Steve L

3. Vansh RC

4. Charles C and Sanghyun K

1.3 Thurs, Dec 8

1. Adam G

2. Almed E

3. Noah P

4. Alice B

5. Alex B

6. Oliver S

1.1 Tony Tether

Tony Tether IIRC, the longest serving DARPA Director. He initiated the 2004 DARPA_Grand_Challenge that spurred the development of autonomous vehicles.

1.2 Curtis Priem

See below.

1.3 Ed Zander

COO Sun, CEO Motorola.

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

2.1 Unionfs

1. aka overlay FS, translucent FS.

2. If a, b are directories, and m is an empty directory, then

   unionfs -o cow a=RW:b m

   makes m to be a combo of a and b, with a being higher priority

3. Writing a file into m writes it in a.

4. Changing a file in b writes the new version into a

5. Deleting a file in b causes a white-out note to be stored in a.

6. Unmount it thus:

   fusermount -u m

7. None of this requires superuser.

8. Application: making a read-only directory into a read-write directory.

9. Note: IBM had a commercial version of this idea in its CP/CMS OS in the 1960s.

2.2 Types of virtualization

1. There are many possible levels of virtualization.

2. At a low level, one might emulate the HW. This is quite flexible but too slow.

3. At a higher level, a basic OS runs separate virtual machines, each with its own file system.

   1. Harmless machine instructions execute normally.

   2. Powerful ones are trapped and emulated.

   3. This requires a properly designed instruction set.

   4. IBM has been doing this commercially for 40 years, with something originally called CP/CMS.

      I think that IBM lucked out with their instruction set design, and didn't plan it.

   5. Well-behaved clients might have problematic code edited before running, to speed the execution.

      I think that Vmware does that.

   6. It seems that compute-intensive clients might have almost no overhead.

   7. However, the emulated file system can be pretty slow.

   8. With Vmware, several clients can all be different OSs, and the host can be any compatible OS.

   9. E.g., I've had a linux vmware host simultaneously running both linux and windows clients.

4. In linux, root no longer has infinite power.

5. The next level of virtualization has an nontrivial host OS, but separates the clients from each other.

   1. They see a private view of the process space, file system, and other resources.

   2. This is lighter weight, e.g., quicker to start a VM and less overhead.

   3. The host and client must be the same OS.

   4. This might be called paravirtualization.

   5. Linux supports this with things like namespace isolation and control groups (cgroups). Wikipedia et al describe this.

   6. Ubuntu snaps do something like this.

      E.g., firefox is distributed as a snap to increase isolation and security.

      However starting firefox now takes 15 sec.

6. The next level up is the normal linux security.

   1. You can see all the processes and similar resources.

   2. The file system has the usual protections.

   3. This is hard to make secure when doing something complicated.

   4. How do I protect myself from firefox going bad?

   5. It's easy to describe what it should be allowed to do, but almost impossible to implement.

   6. That includes using apparmor etc.

7. Who guards the guards? I get spammed at a unique address that I used only to register with apparmor.

8. In theory, packaging an app in a virtual machine has fewer dependencies and is more secure.

9. You can run the vm w/o changes on different hosts.

10. A Vmware client can run w/o change on both linux and windows hosts.

11. You can run a client on your own hardware, then spill over to a commercial cloudy platform when necessary.

2.3 Docker

1. Docker is a popular lightweight virtualization system, which Nvidia uses to distribute SW.

2. Docker runs images that define virtual machines.

3. Docker images share resources with the host, in a controlled manner.

4. For simple images, which is not nvidia/cuda, starting the image is so cheap that you can do it to run one command, and encapsulate the whole process in a shell function.

5. Docker is worth learning, apart from its use by Nvidia for parallel computing. You might also look up Kubernetes.

6. More info:

   1. https://www.docker.com/

   2. https://www.zdnet.com/article/what-is-docker-and-why-is-it-so-darn-popular/

   3. https://opensource.com/resources/what-docker

2.4 Several forms of C++ functions

1. Traditional top level function

   auto add(int a, int b) { return a+b;}

   You can pass this to a function. This really passes a pointer to the function. It doesn't optimize across the call.

   These have global scope.

2. Note auto. It's underused.

3. Overload operator() in a new class

   Each different variable of the class is a different function. The function can use the variable's value. This is a closure.

   This is local to the containing block.

   This form optimizes well.

4. Lambda, or anon function.

   auto add = [](int a, int b) { return a+b;};

   This is local to the containing block.

   This form optimizes well.

5. Placeholder notation.

   As an argument in, e.g., thrust transform, you can do this:

   transform(..., _1+_2);

   This is nice and short.

   As this is implemented by overloading the operators, the syntax of the expression is limited to what was overloaded.

4.1 NVIDIA GTC conference

1. https://www.nvidia.com/gtc/

2. mostly free.

4.2 Top500

Many of the top 500 supercomputers contain NVIDIA modules, often together with IBM Power Systems.

4.3 Nvidia primary documentation

Generally more up-to-date and accurate, but drier than the secondary docs. A little disorganized because it keeps growing. The root is here: https://docs.nvidia.com/

Two major relevant sets are:

1. https://docs.nvidia.com/hpc-sdk/index.html

2. https://docs.nvidia.com/cuda/index.html

4.4 Nvidia conceptual hierarchy

As always, this is as I understand it, and could be wrong. Nvidia uses their own terminology inconsistently. They may use one name for two things (E.g., Tesla and GPU), and may use two names for one thing (e.g., module and accelerator). As time progresses, they change their terminology.

1. At the bottom is the hardware micro-architecture. This is an API that defines things like the available operations. The last several Nvidia micro-architecture generations are, in order, Tesla (which introduced unified shaders), Fermi, Kepler, Maxwell (introduced in 2014), Pascal (2016), and Volta (2018).

2. Each micro-architecture is implemented in several different microprocessors. E.g., the Kepler micro-architecture is embodied in the GK107, GK110, etc. Pascal is GP104 etc. The second letter describes the micro-architecture. Different microprocessors with the same micro-architecture may have different amounts of various resources, like the number of processors and clock rate.

3. To be used, microprocessors are embedded in graphics cards, aka modules or accelerators, which are grouped into series such as GeForce, Quadro, etc. Confusingly, there is a Tesla computing module that may use any of the Tesla, Fermi, or Kepler micro-architectures. Two different modules using the same microprocessor may have different amounts of memory and other resources. These are the components that you buy and insert into a computer. A typical name is GeForce GTX1080.

4. There are many slightly different accelerators with the same architecture, but different clock speeds and memory, e.g. 1080, 1070, 1060, ...

5. The same accelerator may be manufactured by different vendors, as well as by Nvidia. These different versions may have slightly different parameters. Nvidia's reference version may be relatively low performance.

6. The term GPU sometimes refers to the microprocessor and sometimes to the module.

7. There are at least four families of modules: GeForce for gamers, Quadro for professionals, Tesla for computation, and Tegra for mobility.

8. Nvidia uses the term Tesla in two unrelated ways. It is an obsolete architecture generation and a module family.

9. Geoxeon has a (Maxwell) GeForce GTX Titan and a (Kepler) Tesla K20xm. Parallel has a (Volta) RTX 8000 and (Pascal) GeForce GTX 1080. We also have an unused (Kepler) Quadro K5000.

10. Since the highest-end (Tesla) modules don't have video out, they are also called something like compute modules.

4.5 GPU range of speeds

Here is an example of the wide range of Nvidia GPU speeds; all times are +-20%.

The Quadro RTX 8000 has 4608 CUDA cores @ 1.77GHz and 48GB of memory. matrixMulCUBLAS runs at 5310 GFlops. The specs claim 16 TFlops. However those numbers understate its capabilities because it also has 576 Tensor cores and 72 ray tracing cores to cast 11G rays/sec.

The GeForce GTX 1080 has 2560 CUDA cores @ 1.73GHz and 8GB of memory. matrixMulCUBLAS runs at 3136 GFlops. However the reported time (0.063 msec) is so small that it may be inaccurate. The quoted speed of the 1080 is about triple that. I'm impressed that the measured performance is so close.

The Quadro K2100M in my Lenovo W540 laptop has 576 CUDA cores @ 0.67 GHz and 2GB of memory. matrixMulCUBLAS runs at 320 GFlops. The time on the GPU was about .7 msec, and on the CPU 600 msec.

It's nice that the performance almost scaled with the number of cores and clock speed.

4.6 CUDA

4.7 Nvidia GPU summary

Here's a summary of the Nvidia Pascal GP104 GPU architecture as I understand it. It's more compact than I've found elsewhere. I'll add to it from time to time. Some numbers are probably wrong.

1. The host is the CPU.

2. The device is the GPU.

3. The device contains 20 streaming multiprocessors (SMs).

   Different GPU generations have used the terms SMX or SMM.

4. A thread is a sequential program with private and shared memory, program counter, etc.

5. Threads are grouped, 32 at a time, into warps.

6. Warps of threads are grouped into blocks.

   Often the warps are only implicit, and we consider that the threads are grouped directly into blocks.

   That abstract hides details that may be important; see below.

7. Blocks of threads are grouped into a grid, which is all the threads in the kernel.

8. A kernel is a parallel program executing on the device.

   1. The kernel runs potentially thousands of threads.

   2. A kernel can create other kernels and wait for their completion.

   3. There may be a limit, e.g., 5 seconds, on a kernel's run time.

9. Thread-level resources:

   1. Each thread can use up to 255 fast registers. Registers are private to the thread.

      All the threads in one block have their registers allocated from a fixed pool of 65536 registers. The more registers that each thread uses, the fewer warps in the block can run simultaneously.

   2. Each thread has 512KB slow local memory, allocated from the global memory.

   3. Local memory is used when not enough registers are available, and to store thread-local arrays.

10. Warp-level resources:

    1. Threads are grouped, 32 at a time, into warps.

    2. Each warp executes as a SIMD, with one instruction register. At each cycle, every thread in a warp is either executing the same instruction, or is disabled. If the 32 threads want to execute 32 different instructions, then they will execute one after the other, sequentially.

       If you read in some NVidia doc that threads in a warp run independently, then continue reading the next page to get the info mentioned in the previous paragraph.

    3. If successive instructions in a warp do not depend on each other, then, if there are enough warp schedulers available, they may be executed in parallel. This is called Instruction Level Parallelism (ILP).

    4. For an array in local memory, which means that each thread will have its private copy, the elements for all the threads in a warp are interleaved to potentially increase the I/O rate.

       Therefore your program should try to have successive threads read successive words of arrays.

    5. A thread can read variables from other threads in the same warp, with the shuffle instruction. Typical operation are to read from the K-th next thread, to do a butterfly permutation, or to do an indexed read. This happens in parallel for the whole warp, and does not use shared memory.

    6. A warp vote combines a bit computed by each thread to report results like all or any.

11. Block-level resources:

    1. A block may contain up to 1024 threads.

    2. Each block has access to 65536 fast 32-bit registers, for the use of its threads.

    3. Each block can use up to 49152 bytes of the SM's fast shared memory. The block's shared memory is shared by all the threads in the block, but is hidden from other blocks.

       Shared memory is basically a user-controllable cache of some global data. The saving comes from reusing that shared data several times after you loaded it from global memory once.

       Shared memory is interleaved in banks so that some access patterns are faster than others.

    4. Warps in a block run asynchronously and run different instructions. They are scheduled and executed as resources are available.

    5. However they are all running the same instruction sequence, perhaps at different points in it.

    6. That is call SPMD, single program multiple data.

    7. The threads in a block can be synchonized with __syncthreads().

       Because of how warps are scheduled, that can be slow.

    8. The threads in a block can be arranged into a 3D array, up to 1024x1024x64.

       That is for convenience, and does not increase performance (I think).

    9. I'll talk about textures later.

12. Streaming Multiprocessor (SM) - level resources:

    1. Each SM has 128 single-precision CUDA cores, 64 double-precision units, 32 special function units, and 32 load/store units.

    2. In total, the GPU has 2560 CUDA cores.

    3. A CUDA core is akin to an ALU. The cores, and all the units, are pipelined.

    4. A CUDA core is much less powerful than one core of an Intel Xeon. My guess is 1/20th.

    5. Beware that, in the CUDA C Programming Guide, NVidia sometimes calls an SM a core.

    6. The limited number of, e.g., double precision units means that an DP instruction will need to be scheduled several times for all the threads to execute it. That's why DP is slower.

    7. Each SM has 4 warp schedulers and 8 instruction dispatch units.

    8. 64 warps can simultaneously reside in an SM.

    9. Therefore up to 32x64=2048 threads can be executed in parallel by an SM.

    10. Up to 16 blocks that can simultaneously be resident in an SM.

        However, if each block uses too many resources, like shared memory, then this number is reduced.

        Each block sits on only one SM; no block is split. However a block's warps are executed asynchronously (until synced).

    11. Each SM has 64KiB (?) fast memory to be divided between shared memory and an L1 cache. Typically, 48KiB (96?) is used for the shared memory, to be divided among its resident blocks, but that can be changed.

    12. The 48KB L1 cache can cache local or global memory.

    13. Each SM has a read-only data cache of 48KB to cache the global constant memory.

    14. Each SM has 8 texture units, and many other graphics capabilities.

    15. Each SM has 256KB of L2 cache.

13. Grid-level resources:

    1. The blocks in a grid can be arranged into a 3D array. up to \((2^{31}-1, 2^{16}-1, 2^{16}-1)\).

    2. Blocks in a grid might run on different SMs.

    3. Blocks in a grid are queued and executed as resources are available, in an unpredictable parallel or serial order. Therefore they should be independent of each other.

    4. The number of instructions in a kernel is limited.

    5. Any thread can stop the kernel by calling assert.

14. Device-level resources:

    1. There is a large and slow 48GB global memory, which persists from kernel to kernel.

       Transactions to global memory are 128 bytes.

       Host memory can also be memory-mapped into global memory, although the I/O rate will be lower.

       Reading from global memory can take hundreds of cycles. A warp that does this will be paused and another warp started. Such context switching is very efficient. Therefore device throughput stays high, although there is a latency. This is called Thread Level Parallelism (TLP) and is a major reason for GPU performance.

       That assumes that an SM has enough active warps that there is always another warp available for execution. That is a reason for having warps that do not use all the resources (registers etc) that they're allowed to.

    2. There is a 2MB L2 cache, for sharing data between SMs.

    3. There is a 64KiB Small and fast global constant memory, , which also persists from kernel to kernel. It is implemented as a piece of the global memory, made fast with caches.

       (Again, I'm still resolving this apparent contradiction).

    4. Grid Management Unit (GMU) schedules (pauses, executes, etc) grids on the device. This is more important because grids can start other grids (Dynamic Parallelism).

    5. Hyper-Q: 32 simultaneous CPU tasks can launch kernels into the queue; they don't block each other. If one kernel is waiting, another runs.

    6. CUDA Work Distributor (CWD) dispatches 32 active grids at a time to the SMs. There may be 1000s of grids queued and waiting.

    7. GPU Direct: Other devices can DMA the GPU memory.

    8. The base clock is 1607MHz.

    9. GFLOPS: 8873.

    10. Memory bandwidth: 320GB/s

15. GPU-level resources:

    1. Being a Geforce product, there are many graphics facilities that we're not using.

    2. There are 4 Graphics processing clusters (GPCs) to do graphics stuff.

    3. Several perspective projections can be computed in parallel, for systems with several displays.

    4. There's HW for texture processing.

16. Generational changes:

    1. With each new version, Nvidia tweaks the numbers. Some get higher, others get lower.

       1. E.g., Maxwell had little HW for double precision, and so that was slow.

       2. Pascal's clock speed is much higher.

17. Refs:

    1. The CUDA program deviceDrv.

    2. http://developer.download.nvidia.com/compute/cuda/compute-docs/cuda-performance-report.pdf

    3. http://international.download.nvidia.com/geforce-com/international/pdfs/GeForce_GTX_1080_Whitepaper_FINAL.pdf

    4. Better Performance at Lower Occupancy, Vasily Volkov, UC Berkeley, 2010.

    5. https://www.pgroup.com/lit/articles/insider/v2n1a5.htm - well written but old.

    (I'll keep adding to this. Suggestions are welcome.)

4.8 More CUDA

1. CUDA function qualifiers:

   1. __global__ device function called from host, starting a kernel.

   2. __device__ device function called from device function.

   3. __host__ (default) host function called from host function.

2. CUDA variable qualifiers:

   1. __shared__

   2. __device__ global

   3. __device__ __managed__ automatically paged between host and device.

   4. __constant__

   5. (nothing) register if scalar, or local if array or if no more registers available.

3. If installing CUDA on your machine, this repository seems best:

   http://developer.download.nvidia.com/compute/cuda/repos/ubuntu1604/x86_64

   That includes the Thrust headers but not example programs.

4.9 Other Nvidia features

We've seen almost everything, except:

1. Texture and surface maps.

2. ML HW like A=BC+D for 4x4 matrices.

3. Ray tracing HW, to compute a ray's intersections with boxes.

4. Cooperative groups: with Ampere, subsets of a warp can synchronize.

5. Subsets of a GPU can be defined as virtual GPUS, which are walled off from each other.

6. Memory can be compressed when stored, making a space-time tradeff.

7. The terminology CUDA core is obsolete. Now, they say that an SM has, perhaps 32 single float units, 32 integer units, 32 CUDA instruction dispatchers, and 16 double float units, etc. Each unit operates independently.

1.1 Today

1. Adam G

2. Charles C, Sanghyun K - Trapped ion technology_IONQ

3. Vansh R C

4. Ahmed E

5. Oliver S - quantum memristors

1.1 Today

1. Richard P - Quantum Key Distribution

2. Noah and Alice - Quantum Walks

1.2 Thurs

1. Adam G and -

2. Charles C, Sanghyun K - Trapped ion technology_IONQ

3. Vansh R C

4. Ahmed E

5. Oliver S - quantum memristors

6. Denzel

1.3 Others?

not doing this homework?

present in 2 weeks?

1.1 Accreditation

Example of students who don't understand accreditation being tricked:

1. In Florida, non-accredited colleges say that their credits "may" transfer to the prestigious state colleges.

2. The credits do not transfer. There was no quality control or other standards for those credits.

1.2 Compiling quantum computer programs

1. Executing a Pascal-like program to an actual quantum computer has several steps.

2. The actual quantum computer has physical qbits.

3. Some (but usually not most) pairs of qbits are connected; see the graph description of the quantum computer.

4. A 2-qbit operation like CCNOT can happen only on a connected pair.

5. Not all the quantum operations that we've seen have physical realizations. Which do depends on the hardware. IBM is different from IONQ.

6. The user writing the program is properly unaware of any of this. S/he just uses meaningful variable names and useful ops.

7. Maybe s/he draws a qiskit diagram, which is basically equivalent to the program.

8. The compiler has to:

   1. Translate unrealizable operations into sequences of realizable operations.

   2. Decide how to optimally assign the variables to actual qbits.

   3. Remember that operations can occur only between adjacent qbits, so try to assign qbits to maximize this adjacency.

   4. To operate on other pairs of qbits, add swap operations to make them adjacent.

   5. These (and all) operations are noisy and take time.

   6. The quantum computer has a limit (the quantum volume) on how much it can do before accumulated noise etc destroys the results.

   7. Look for opportunities to optimize and reduce pairs of consecutive operations. This happens a lot.

9. Qiskit and its competitors do all this.

10. This is reminiscent of compiling onto a classical machine with limited registers.

11. Optimal solutions are NP, but good enough solutions are possible.

12. Someone is probably using a quantum computer to compile.

1.3 Being a grad student here at RPI

How might we help?

2.1 The problem

1. Factorize an integer.

2. in BQP.

3. almost exponentially faster than best classical algorithm.

4. Largest examples I can find: 56153 = 233 × 241.

2.2 Notes

1. This is the most famous quantum algorithm.

2. It's the one that has the potential to break much public key crypto.

3. This is the deepest topic of this course so far.

4. Takeaways from this algorithm are that some serious math is involved, and the quantum version is unlike the classical version.

5. If you don't absorb all the details, then absorb its flavor.

6. I sometimes show videos because they present the idea better than me.

7. OK to ask questions and make comments during the videos. I'll pause the video and try to answer.

2.3 Application: break RSA

1. Public-private key crypto.

2. Oversimpifying, RSA private key is a pair of large primes.

   Public key is their product.

3. Odd fact: if 2 public keys have a common factor, then you can easily factor both of them with gcd.

4. Publish the public key.

5. Use intended recipient's public key to encrypt message then send it.

   Recipient uses his private key to decrypt it.

6. Or, use private key to sign message then publish or send it.

   Anyone can use the public key to verify it.

7. Invented in 1970s, secretly before publicly.

8. Aside: visit the NSA's National Cryptologic Museum. Note how nothing there is under 50 years old.

9. All this assumes that you can reliably get someone's genuine public key.

   Some scams involve faking phone numbers, email addresses, etc.

10. Based on a function that's hard to invert, e.g., factoring.

11. RSA has competitors.

12. There are various ways to embed RSA or a competitor into an encryption program, with choices of algorithm, key length, etc.

13. On linux, you can encrypt a file with pgp, gnupg, LUKS, zip encryption, zfs encryption, truecrypt (suddenly discontinued w/o any stated reason in 2014), etc, etc.

14. At one time, there was no version of pgp that was legal both in the US and outside the US.

15. At one time, the US proposed that crypto must have a back door. However this was dropped.

16. A paranoid person might suspect that the chaos was deliberate to make it harder to use crypto. But that's just crazy talk.

17. RSA is slow, so it's used only to encrypt a session-specific symmetric key that is used for the rest of the message, ssh session, etc.

18. Gnupg et al do a 3rd level of encryption.

    The private key is encrypted with a passphrase.

    You use the passphrase to decrypt the file.

    The encrypted passphrase is stored ~/.gnupg .

    If you lose ~/.gnupg, you lose all your encrypted data.

    You can change the passphrase by re-encrypting the private key w/o re-encrypting the whole file.

    You can have multiple passphrases to give to different people.

    You can cancel a passphrase by deleting the version of the encrypted private key that was encrypted with it.

19. So, you need 3 things to access the encrypted file: the encrypted file, the encrypted secret key, and the passphrase.

2.4 Classical factoring

1. Efficient algorithms are complicated and use number theory.

2. Rational sieve is good first algorithm to study. It's simple and reasonably fast.

2.5 Videos

1. Shor on, what is Shor's factoring algorithm? (2:09)

   It's good to listen to the inventor of a big idea.

2. Umesh Vazirani's lecture, 2018.

   1. This jumps into the middle of things a little. However the alternatives are worse: not to show Vazirani at all, or to also show all the earlier videos.

   2. Lecture 10 1 Period Finding (19:27)

   3. Lecture 10 2 Shor's Factoring Algorithm (25:42)

3. Hacking at Quantum Speed with Shor's Algorithm (16:35). Optional to watch on your own.

4. The Story of Shor's Algorithm, Straight From the Source | Peter Shor (31:27) 2021-07-02 Gives the history. Optional to watch on your own.

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

6. Hacking at Quantum Speed with Shor's Algorithm (16:35)

7. Five lectures by Abraham Asfaw in Qiskit's Introduction to Quantum Computing and Quantum Hardware.

2.6 Vanished videos

1. 43 Quantum Mechanics - Quantum factoring Period finding (19:27)

2. 44 Quantum Mechanics - Quantum factoring Shor's factoring algorithm (25:42)

2.7 IBM Quantum

https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm

https://qiskit.org/textbook/ch-algorithms/shor.html

3.1 Problem

Blackbox $F: \{0,1\}^n \to \{0,1\}$

For only one x, F(x) = 1. Otherwise F(x)=0.

Determine x.

Classically: T(n)=O(n).

Quantumly: $T(n) = O(\sqrt{n})$.

3.2 Videos

1. Introduction to Quantum Computing (18) - Grover's Algorithm: Quantum Problem Statement (4:24)

2. Introduction to Quantum Computing (19) - Grover's Algorithm: Outline (16:09)

3. Introduction to Quantum Computing (20) - Grover's Algorithm: Subspace (7:42)

4. Introduction to Quantum Computing (21) - Grover's Algorithm: Geometric Interpretation

5. Introduction to Quantum Computing (23) - Grover's Algorithm: Implementation (9:33)

6. Introduction to Quantum Computing (24) - Grover's Algorithm: IBM Quantum Experience (11:39)

5.1 Superconducting qubits

1. Dilution fridge: cool by mixing He3 into He4.

2. Cooper pairs of electrons: pairs of electrons in a metal weakly attract each other. It's a quantum effect.

3. Josephson Junction.

4. good ref: A Quantum Engineer's Guide to Superconducting Qubits

5.2 Trapped Ion

1. https://en.wikipedia.org/wiki/Trapped_ion_quantum_computer

2. Proponents say that it's better than transmon qbits.

3. Trapped-ion qubit, the maglev train of a quantum computer, 9:34, 2021-08-24.

4. https://ionq.com/technology

   "To date, we’ve run single-qubit gates on a 79 ion chain, and complex algorithms on chains of up to 11 ions."

5.3 Quantum annealing

1. This is not comparable to quantum gates and circuits like IBM has.

2. It minimizes a function by testing many solutions in parallel.

3. See details in the D-Wave section.

4. Qbit count is not comparable to gate models.

5. https://en.wikipedia.org/wiki/D-Wave_Systems

6. They make a different type of quantum computer, called a quantum annealer. They have been in the news lately, e.g.,

7. https://arstechnica.com/science/2020/09/d-wave-releases-its-next-generation-quantum-annealing-chip/

8. What is Quantum Annealing? 6:14.

9. How The Quantum Annealing Process Works 6:09.

10. Quantum Programming 101: Solving a Problem From End to End | D-Wave Webinar 54:25.

    "Want to learn how to program a quantum computer? In this webinar, we explain how to do so by running through a complete, simple example. We explain how to formulate the problem, how to write it, and how to tune it for best results. "

    "This webinar is intended for those with little or no experience programming on a D-Wave quantum computer. After watching, get free time on Leap, the quantum cloud service at https://cloud.dwavesys.com/leap/signup/ "

11. Slides from Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises by Frank Mueller, Patrick Dreher, Greg Byrd held at PPoPP (Feb 2019) ASPLOS'19 (Apr 2019),

    Part 3: D-Wave -- Adiabatic Quantum Programming

12. D-Wave factoring tutorial and other demos

    including Jupyter notebooks (you have to login for them).

5.4 Photonics

1. Xanadu Quantum Cloud

2. https://venturebeat.com/2020/09/02/xanadu-photonics-quantum-cloud-platform/

3. Uses photonics.

4. Operates primarily at room temperature.

5. Up to 24 qbits, gate depth of 12.

6. Has free SW tools, some of which can compile to other quantum technologies.

7. Expected good applications: graphs and networks, machine learning, and quantum chemistry.

8. They expect to scale up better than competing technologies.

9. Operates at room temperature.

8.1 Two qubit operators

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

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

3. $q = a_0 | 00\!\!> + a_1 | 01\!\!> + a_2 | 10\!\!> + a_3 | 11\!\!> $

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

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

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

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

8. A measurement operator applied to $q$ will rotate it to a basis {00, 01, 10, 11}, so that it will be observed in one of those four cases, with probabilities $ | a_i | ^2$.

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

10. The matrices are all invertible (except for measurement matrices), and all leave $ | q | = 1$.

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

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

13. 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}$$.

14. The combined state is the tensor product of the individual qubits.

15. In this case, you could separate out the individual qubits again.

16. However, sometimes after operating on the combo (i.e., multiplying by a matrix), you cannot any more separate out the result into a tensor product of individual qubits.

17. For $n$ qubits, the tensor product is a vector with $2^n$ elements, one element for each possible value of each qubit.

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

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

20. The matrix is invertible.

21. The transformation doesn't destroy information.

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

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

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

25. However that does not let you communicate.

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

8.2 Common operators

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

2. Bell state

   1. Maximally entangled.

   2. Hadamard then CNOT.

8.3 Entanglement of 2-qbit system

State is a 4-vector of length 1.

It was originally created as the exterior product of two 2-vectors, the states of two separate 1-qbit systems.

Originally the separate 1-qbit systems didn't affect each other. Either could be transformed and measured.

Then 2-qbit system was rotated with a transformation matrix.

Now, perhaps it can be decomposed into the exterior product of two 2-vectors. Perhaps not.

1. Case 1: The 4-vector representing the new state can be decomposed.

   1. Then it's still really two separate 1-qbit systems.

   2. They can still either be transformed and measured.

   3. Measuring one qbit does not affect the other qbit.

2. Case 2: The 4-vector representing the new state cannot be decomposed.

   1. So the 2 qbits are now entangled.

   2. That means that measuring one qbit affects what you will see when you measure the other.

   3. It might just bias the probabilities of measuring the other qbit as 0 or 1.

   4. Or, it might totally control what you will see.

8.4 Entangling with Toffoli

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.

3.1 Math review from Quantum Computing for Computer Scientists

1. Chapter 2:

   1. Complex vector space, page 34.

      1. n-dim vector $\begin{vmatrix} c_0 \\ \cdots \\ c_{n-1}\end{vmatrix}$

      2. Add 2 vectors.

      3. Multiply vector by scalar.

      4. etc.

   2. Set of $m\times n$ complex matrices, $\mathbb{C}^{m\times n}$, is also a complex vector space.

      1. Transpose, conjugate, adjoint.

      2. Matrix mult is $\star$ in book.

   3. $\mathbb{C}^{m\times n}$ is a complex algebra.

   4. Set of polynomials in one variable of degree $le n$ is a complex vector space.

   5. State of a quantum system is a complex vector.

   6. You can make new vector spaces from combos of old ones.

      1. Cartesian product or direct sum.

      2. Just an ordered pair.

      3. $(v_1, v_2)$.

   7. Set of basis vectors for the vector space.

      1. Every vector $v$ in the space is a linear combo of the basis vectors.

      2. Represent $v$ as the list of weights.

      3. There are many possible basis sets.

      4. Each different basis set causes a different representation for the vectors.

      5. Convert: change of basis.

      6. Cartography example: NAD27, WGS84.

         A bridge between Switzerland and Germany across the Rhine River at Laufenberg had its two ends at different elevations because of a conversion error between two different basis systems.

         https://www.science20.com/news_articles/what_happens_bridge_when_one_side_uses_mediterranean_sea_level_and_another_north_sea-121600

      7. Hadamard matrix is an example.

   8. Section 2.4 Inner product, etc, p 53

   9. Section 2.7 Tensor product of vector spaces, p 66.

      1. $\mathbb{V} \otimes \mathbb{V'}$.

      2. Let $dim(\mathbb{V})=p$ and $dim(\mathbb{V'})=q$ . Then $dim(\mathbb{V} \otimes \mathbb{V'}) = pq$.

      3. This is how quantum systems combine.

      4. Example 2.7.2 p 70.

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

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

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

   3. Norm, aka length.

   4. We won't need limits etc.

   5. Section 2.5 Eigenvalues and eigenvectors

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

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

   6. Section 2.6 Hermitian and unitary matrices

   7. P 39. Adjoint: conjugate transpose of matrix.

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

   9. P 62. Hermitian matrix: it is its adjoint.

   10. Unitary: its inverse is its adjoint.

   11. Geometrically, they are rotations since they preserve distances.

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

   13. P 71, tensor product of matrices.

   14. 1. Chapter 3 through 3.2, p 74-88.

       1. p 80, doubly stochastic matrix.

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

       3. P 88, Chapter 3, section 3.3 Quantum systems,

       4. Real probabilities add.

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

   15. p 91, Ex 3.2.2

   16. p 93 double slit experiment

   17. p 97 Section 3.4, Assembling systems

3.2 2 slit experiment compared with real vs complex transitions

4.1 Quantum properties - Phase

1. You cannot measure the phase of qbit.

2. You can measure the relative phase of 2 qbits.

3. Many algorithms encode the answer as a phase shift of a qbit.

4. Phase kickback means that a gate that runs one way, e.g., the control bit affects an output bit, can be made to run the other way, e.g., the control bit is changed, by making the other bit a Hadamad basis.

5. Phase Kickback V Abhijith Rao

6. Qiskit Phase Kickback

4.2 Quantum supremacy

1. Coined by Preskill in 2012.

2. Google claimed this in Oct 2019 on a specific (artificial?) problem; see Google section.

3. IBM disagrees.

4.3 Cloud-based computing

1. IBM started this.

2. Alibaba followed.

3. Then D-Wave Leap, Rigetti, Amazon AWS Braket and Quantum solutions lab, Microsoft Azure.

4. IBM's intent is to entangle their computers in different sites; exponentially increasing power.

4.4 Technologies

1. Quantum Materials | QuTech Academy 8:57.

4.5 Companies - Primary

These companies have their own hardware.

4.6 Companies - Aggregators

These companies resell others' computers as a cloud service.

4.7 Algorithms

1. Good ref is Chapter 6, Algorithms of Quantum Computing for Computer Scientists, published in 2000. Algorithms don't change fast. It does omit new things like HHL.

2. For these examples, the quantum algorithm is quite different from the classical algorithm, and is asymptotically faster.

3. Current research is deciding what algorithms can be made faster.

4. p 172: Any function can be made invertible by adding a control bit.

5. Major categories:

   1. Cryptography

   2. Quantum search

   3. Quantum simulation

   4. Quantum annealing and adiabatic optimization

   Nice summary: https://en.wikipedia.org/wiki/Quantum_computing

6. Algorithm summary:

   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

4.8 Algorithm details

4.9 Software

4.10 More info

4.11 Summary

1. Quantum computing hasn't solidly proved itself yet. However it's now in the engineering phase - realizing what we basically know how to do.

2. IMO the physicists have done it again (last time was atomic energy). This will be a fundamental transformation of computing.

3. Certain searching algorithms will be exponentially faster.

4. Algorithm design still needs research. Algorithms are quite complex.

5. Major application areas like drug design.

6. Several viable technologies competing.

7. Several HW companies.

8. Competing toolsets being developed.

9. Various service platforms to provide simulators and the HW.

10. Recommendation (remember I'm SW):

    1. Be agnostic wrt platform (we don't know who will win).

    2. Have people use AWS etc to learn and develop apps. No capital investment needed.

    3. Work developing and/or using middleware, which is newer area.

    4. RPI-specific:

       1. Merely playing catchup is a losing game. Need something new.

       2. Assume that IBM etc will make the computers. The big problem with new HW is always how to use it. The ability of customers to use a new tool can determine whether it succeeds.

       3. Include other RPI programs?

          1. Gamify this using Game and Sim?

          2. Work with tetherless world?

       4. I'm still thinking.

3.1 Entanglement

1. Crazy counterintuitive idea that's the basis for quantum speedup.

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

3. This has been demonstrated with real qubits transported 1000 miles apart.

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

5. However that does not let you communicate.

6. The preceding metaphor is wrong in that it has a hidden variable, the unobserved half-paper state. That does not happen in quantum physics. With qubits, the states are not fixed until one is observed. I'm trying to get the idea across.

8.1 Intro sites - 2

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

2. A beginner's guide to quantum computing | Shohini Ghose https://www.youtube.com/watch?v=QuR969uMICM 10:04

3. https://towardsdatascience.com/introduction-to-quantum-programming-a19aa0b923a9?gi=69d861e26d80

4. https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-8996b667d256

5. https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-2-qubit-operator-871528d136db

6. https://www.cl.cam.ac.uk/teaching/0910/QuantComp/notes.pdf

   1. They have a nice description of measurement starting at slide 10.

   2. Each measurement operator has a basis vector set.

   3. The operator represents the qbit as a linear combo of the basis vectors.

   4. Then it projects the qbit onto one of the basis vectors, with probability being the length of that component.

   5. It is possible for two different qbits to measure the same in some basis, but measure different in a different basis.

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

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

9. Experiment with Basic Quantum Algorithms (Ali Javadi-Abhari, ISCA 2018) (19:05)

10. Quantum Computing for Babies

8.2 Current status sites

1. https://www.telegraph.co.uk/technology/2020/09/02/britain-must-act-fast-prevent-brain-drain-quantum-computing/ - good summary of programs around the world.

2. Quantum startup CEO suggests we are only five years away from a quantum desktop computer

1.1 Syllabus

Read the syllabus, accessible from the top bar.

1.2 Gradescope

We'll use Gradescope for submitting homeworks and possibly projects. Use the entry code that I'll give in class to add yourself.

"If you already have a Gradescope account, log into that account and navigate to your Account Dashboard by clicking the Gradescope logo in the top left, and click Add Course in the bottom right corner. Then enter your course code."

Then, the quick link to the course should be https://www.gradescope.com/courses/432866 . It is available in the top bar of this page.

1.3 My research

I do parallel geometry algorithms on large problems for CAD and GIS. See my home page. I will be retiring this year after 45 years at RPI (including several years at places like the National Science Foundation and UC Berkeley).

1.4 Changes from last year

1. New textbooks.

2. More non-IBM material.

3. No piazza.

4. Class is in person.

5. Switch to the new edition of Hidary (2nd ed, 2021).

1.5 My role

1. My main job is to be a curator selecting the best material for the class.

2. I try to show the principals themselves describing their work and their opinions. E.g., Peter Shor talking about his algorithm and about quantum computing in general.

3. I try to leave you wanting to learn more.

4. There's a lot that I still have to learn about quantum computing. For some specific topics, some of you may know more than me.

1.6 Office hours

1. After most classes for an hour.

2. By webex at mutually agreeable times; email me.

1.7 Textbooks

1.8 Web sites

1. IBM's detailed online stuff. Not just qiskit but algorithms etc.

2. Other universities provided inspiration.

3. Misc quantum research centers, like Delft

4. Many videos.

1.9 Course blog

1. https://wrfranklin.org/Teaching/quantum-f2022

2. My former web site, wrf.ecse.rpi.edu, now redirects to wrfranklin.org .

1.10 Learning Outcomes

1. Demonstrate proficiency with the mathematics behind quantum computing.

2. Understand important quantum computing algorithms.

3. Understand the three main quantum platforms: transmon qubit, trapped ion, and quantum annealing.

4. Apply that to write and run programs on those platforms.

2.1 Intro

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

2.2 Brief History

The WIRED Guide to Quantum Computing 08.24.2018. Nice non-too-technical summary of the history. The theory preceded the realization. This happens sometimes, e.g., with atomic energy. From there:

1980

Physicist Paul Benioff suggests quantum mechanics could be used for computation.

1981

Nobel-winning physicist Richard Feynman, at Caltech, coins the term quantum computer.

1985

Physicist David Deutsch, at Oxford, maps out how a quantum computer would operate, a blueprint that underpins the nascent industry of today.

1994

Mathematician Peter Shor, at Bell Labs, writes an algorithm that could tap a quantum computer’s power to break widely used forms of encryption.

2007

D-Wave, a Canadian startup, announces a quantum computing chip it says can solve Sudoku puzzles, triggering years of debate over whether the company’s technology really works.

2013 Google teams up with NASA to fund a lab to try out D-Wave’s hardware.

2014

Google hires the professor behind some of the best quantum computer hardware yet to lead its new quantum hardware lab.

2016

IBM puts some of its prototype quantum processors on the internet for anyone to experiment with, saying programmers need to get ready to write quantum code.

2017

Startup Rigetti opens its own quantum computer fabrication facility to build prototype hardware and compete with Google and IBM.

2.3 Intro sites

1. Feynman was the first to propose the theoretical idea of a quantum computer.

   Richard Feynman - Quantum Mechanics 4:01.

   Extracted from HD Feynman: FUN TO IMAGINE complete 1080p 1:06:49. Recorded in 1983.

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

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