Skip to main content

Quantum Homework 14 - Final Project

Due Mon Dec 12, 900am

This is your final project, with paper, code, whatever. Upload a zip file or tarball with everything to gradescope.

If that fails, put it on your favorite cloud service and upload the link. If that's google, send me a link that lets anyone with that link read it; don't just authorize it to what you think is my google account.

This is a 2 day extension from Friday. However, this is the limit. I will grade whatever I have at that time.

Quantum Class 24, Thy 2022-12-08

1 Final project presentations, day 3

  1. Adam G

  2. Almed E

  3. Noah P

  4. Alice B

  5. Alex B

  6. Oliver S

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

2 Writing

  1. Example of a well written paper: https://wrfranklin.org/p/239-marcelo-gpu-predicates-2021.pdf

  2. How not to write: The Bulwer Lytton Fiction Contest has challenged participants to write an atrocious opening sentence to the worst novel never written.

  3. Paper format: one good idea is to use the IEEE conference format . It allows either latex or MS word. Submit the PDF paper to gradescope.

3 Prior work

If your final project is building on, or sharing with, another course or project (say on GitHub), then you must give the details, and say what's new for this course.

4 12 Ways to Fool the Masses with Irreproducible Results

If you're implementing something:

https://lorenabarba.com/news/keynote-at-the-35th-international-parallel-and-distributed-processing-symposium-ipdps/

Lorena Barba IPDPS21 keynote May 20, 2021 (37:11)

Keynote at the IEEE International Parallel and Distributed Processing Symposium, May 19, 2021

Abstract Thirty years ago, David Bailey published a humorous piece in the Supercomputing Review magazine, listing 12 ways of presenting results to artificially boost performance claims. That was at a time when the debate was between Cray "two-oxen" machines versus parallel "thousand-chickens" systems, when parallel standards (like MPI) were still unavailable, and the Top500 list didn't yet exist. In the years since, David and others updated the list of tricks a few times, notably in 2010–11 (when the marketing departments of Intel and Nvidia were really going at each other) Georg Hager in his blog and Scott Pakin in HPC Wire. Heterogeneity of computing systems has only escalated in the last decade, and many remiss reporting tactics continue unabated. Alas, two new ingredients have entered into the mix: wide adoption of machine learning techniques both in the science applications and systems research; and a swell of concern over reproducibility and replicability. My talk will be a new twist on the 12 ways to fool the masses, focusing on how researchers in computational science and high-performance computing miss the mark when conducting or reporting their results with poor reproducibility. By showcasing in a lighthearted manner a set of anti-patterns, I aim to encourage us to see the value and commit to adapting our practice to achieve more trustworthy scientific evidence with high-performance computing.

There's a link to the slides there.

5 After the semester

I'm open to questions and discussions about any legal ethical topic. Even after you graduate.

  • gs

Quantum Class 23, Mon 2022-12-05

1 Final project presentations, day 2

  1. Richard P

  2. Steve L

  3. Vansh RC

  4. Charles C and Sanghyun K

2 Microsoft quantum

  1. https://azure.microsoft.com/en-us/solutions/quantum-computing/#quantum-impact 1:15

  2. https://news.microsoft.com/features/new-microsoft-breakthroughs-general-purpose-quantum-computing-moves-closer-reality/ 3:00

  3. Microsoft Quantum Development Kit: Introduction and step-by-step demo 10:34 Dec 11, 2017

    "Krysta Svore, principal researcher at Microsoft, demonstrates the new Microsoft Quantum Development Kit, now in preview.

    The Quantum Development Kit makes it easy for you to start experimenting with quantum computing now and includes:

    · A native, quantum-focused programming language called Q# · Local and Azure-hosted simulators for you to test your Q# solution · And sample Q# code and libraries to help you get started

    In this demo, she walks through a few code examples and explains where quantum principles like superposition and entanglement apply. She explains how quantum communication works using teleportation as your first "Hello World" inspired program. And keep watching to see more complex computations with molecular hydrogen. ...

  4. A discussion with Sankar Das Sarma and Chetan Nayak 39:46

    "Dr. Sankar Das Sarma, a Distinguished University Professor of physics at University of Maryland joins Chetan Nayak, Distinguished Engineer of Quantum at Microsoft to discuss Microsoft’s unique approach to building a fully scalable quantum machine....

Quantum Class 22, Thurs 2022-12-01

1 Final project presentations, updated

  1. Everyone who requested a specific date, got it. I assigned the others to even out the calendar.

  2. No matter when you talk, you have until Fri Dec 9 to submit your project.

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

2 Quantum computing and Machine Learning

  1. Quantum Machine Learning vs. Machine Learning for Quantum Computing by Mats Granath 28:50 Apr 29, 2022

    "Machine learning and quantum computing are two expanding technologies with tremendous potential. What if they are combined, into quantum machine learning (QML)? I will give an overview of QML, pointing out that quantum mechanics makes it difficult to “quantize” classical ML algorithms such as artificial neural networks. Instead, existing QML algorithms are typically hybrid algorithms, part classical, part quantum. An alternative to making ML quantum is to use ML as part of the software required to operate a quantum computer. I will give some examples from my own research of both types of algorithms, using a hybrid QML approach to address a logistics problem and using deep reinforcement learning for compiling quantum code and for quantum error correction."

    The first 10 minutes is a very nice review, so we'll start after it.

  2. TensorFlow Quantum: A software platform for hybrid quantum-classical ML 27:15 Mar 11, 2020

    "We introduce TensorFlow Quantum, an open-source library for the rapid prototyping of novel hybrid quantum-classical ML algorithms. This library will extend the scope of current ML under TensorFlow and provides the necessary toolbox for bringing quantum computing and machine learning research communities together to control and model quantum data."

  3. Hybrid quantum-classical Neural Networks with PyTorch and Qiskit

  4. https://towardsdatascience.com/tensorflow-quantum-marrying-machine-learning-with-quantum-computing-84533757e07f?gi=43b0a70c9297

Quantum Class 21, Mon 2022-11-28

1 Quantum jokes

of varying quality... https://upjoke.com/quantum-jokes

2 Final project presentations

  1. Everyone who requested a specific date, got it. I assigned the others to even out the calendar.

  2. Do any of the Dec 1 people want to move to Dec 5? The first two who email me can do that.

  3. Other changes that don't overload particular days might be ok.

  4. No matter when you talk, you have until Fri Dec 9 to submit your project.

3 Final project presentations

  1. Everyone who requested a specific date, got it. I assigned the others to even out the calendar.

  2. Do any of the Dec 1 people want to move to Dec 5? The first two who email me can do that.

  3. Other changes that don't overload particular days might be ok.

  4. No matter when you talk, you have until Fri Dec 9 to submit your project.

  5. Updated list is on class 22.

4 Jochen Rao on Molecules

  1. This fits together with the variational quantum eigensolver talk.

  2. 22.Molecules 9:50 Dec 11, 2020

5 Measurement-based computation, aka One way quantum computation

This is an alternative to the quantum logic gate model that uses reversible unitary gates in a quantum circuit.

Since performing a measurement changes the measured qbits, use it.

  1. https://www.quantiki.org/wiki/one-way-computation :

    "One way quantum computation (1WQC) uses an initially highly entangled state (called a cluster state), and then a pattern of single qubit measurements along different directions, together with feed-forward based on the results, in order to drive a quantum computation. The final result of the computation is obtained by measuring the last remaining qubits in the computational basis..."

  2. https://en.wikipedia.org/wiki/One-way_quantum_computer

    1. This is a one-way computer.

    2. Operations:

      1. Supplement the input/output qbits with some auxillary qbits.

      2. Entangle some of them.

      3. Measure some of the auxillary qbits wrt some bases. This affects the output qbits since they are entangled.

      4. Depending on the measurement results, perform further operations on the output qbits. These are called corrections.

    3. Repeat.

  3. This has equivalent formal power to reversible gates.

  4. It may be better suited to certain HW.

  5. One-way Quantum Computation - a tutorial introduction Dan E. Browne, Hans J. Briegel.

  6. How the excellent Jochen Rau presents it:

    14. Measurement-based computation 36:44. Nov 27, 2020

  7. So now you've seen 3 models of quantum computation.

6 MaxCut

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

Rao again, since he's excellent.

21.Classical optimization: MaxCut problem 14:47

Quantum Class 20, Mon 2022-11-21

1 Final project presentations

  1. Presentations will be the last 3 classes: Dec 1, 5, 8. FCFS. Max 6 groups per day.

  2. Pick your date here: https://doodle.com/meeting/participate/id/egZG5Pjd

  3. When signing up, use enough of your name(s) that I can recognize you.

2 NVIDIA Quantum Computing, 2

  1. NVIDIA (and other companies) sees a growth area in providing QODA, a layer of services on top of the quantum computing HW. The goal is to make that easier to use and more portable.

  2. The analogy is that CUDA hides some of the GPU complexity.

  3. QODA also permits various backends: simulators and eventually real HW.

  4. Nice intro: https://docs.nvidia.com/cuda/cuquantum/overview.html

  5. https://quantumzeitgeist.com/artificial-intelligence-giant-nvidia-creates-a-new-platform-for-hybrid-quantum-classical-computing-qoda/

  6. https://developer.nvidia.com/qoda

  7. https://nvidianews.nvidia.com/news/nvidia-announces-hybrid-quantum-classical-computing-platform

  8. NVIDIA Special Address at Q2B: Defining the Quantum Accelerated Supercomputing Platform 18:39. Jul 12, 2022

    Quantum computing has the potential to offer giant leaps in computational capabilities, impacting a range of industries from drug discovery to portfolio optimization. Realizing these benefits requires pushing the boundaries of quantum information science in the development of algorithms, research into more capable quantum processors, and the creation of tightly integrated quantum-classical systems and tools. We'll review these challenges facing #quantumcomputing, showcase how #GPUcomputing can help, and reveal exciting developments in tightly integrated quantum-classical computing. https://developer.nvidia.com/qoda

  9. Watch Nvidia Reveal Quantum Computing Platform, QODA 6:53 Jul 12, 2022

    At Q2B, Nvidia announces QODA, a new hybrid quantum-classical computing platform. See it explained here.

  10. https://developer.nvidia.com/blog/introducing-qoda-the-platform-for-hybrid-quantum-classical-computing/

  11. https://blogs.nvidia.com/blog/2022/07/12/quantum-qoda-julich/

  12. https://blogs.nvidia.com/blog/2022/07/29/what-is-a-qpu/

  13. https://blogs.nvidia.com/blog/2022/09/20/cuquantum-qoda-adoption-accelerates/

  14. https://www.hpcwire.com/2022/07/12/nvidia-dives-deeper-into-quantum-announces-qoda-programming-platform/

  15. Q2B 2021 | Accelerating Quantum Algorithm Research with cuQuantum | Harun Bayraktar 29:52. December 9, 2021. Excellent solid talk.

  16. I tried to get QODA running to show the class.

    1. However it is still a work in progress.

    2. You can (try to )install QODA from https://docs.nvidia.com/cuda/cuquantum/custatevec/getting_started.html

    3. The deb fails on my machine running Ubuntu 22.10 because of a cublas version clash.

    4. The tarball installs.

    5. Compiling fails because it doesn't support the latest g++.

    6. -allow-unsupported-compiler seems to override that.

    7. Several programs are supplied but all the programs just say 'passed' when executed.

3 Classiq - Quantum algorithm design platform

  1. Here's another company working on the layers above the HW.

  2. "Classiq is revolutionizing the process of developing quantum computing software.

    "Our platform helps you build complex, optimized and hardware-aware quantum circuits and algorithms that could not be created otherwise. "

  3. https://www.classiq.io/ Watch the short video.

  4. They use the Variational Quantum Eigensolver (VQE) as an example.

4 Variational Quantum Eigensolver (VQE)

  1. This is a big current class of applications for hybrid classic - quantum computers.

  2. I think it's not quite practical yet, but it's close.

  3. Say you want to know the lowest energy state of a molecule.

    1. It's the lowest eigenvalue of a Hamiltonian.

    2. However the Hamiltonian cannot be calculated explicitly but must be simulated.

    3. This is very expensive, but less so on a quantum computer (because it uses quantum physics).

    4. It depends on some parameters.

    5. Use a classical computer to run an optimization search on the parameters, calling a quantum computer to evaluate the function (the Hamiltonian).

  4. https://qiskit.org/textbook/ch-applications/vqe-molecules.html very good.

  5. 24. Variational quantum eigensolver (VQE) 19:12, Dec 18, 2020, Jochen Rau. very good.

  6. Variational Quantum Eigensolver (VQE) | PennyLane Tutorial 17:44

  7. VQE Zero to Hero 20:50 May 9, 2022

    "The Variational Quantum Eigensolver (VQE) is one of the most promising algorithms for near term quantum hardware, but how does it work? Rensselaer Polytechnic Institute student Owen Lockwood shows you how to get from the basics of quantum mechanics and the Schrödinger equation to the second quantized electronic hamiltonian and how this forms the basis of the VQE."

    Goes into the physics and chemistry.

5 My predictions for the winners

  1. If I had to pick a HW winner, I'd pick Intel. However it's early still.

  2. For the SW, perhaps NVIDIA, or Intel, Amazon, Microsoft.

  3. Dunno about the Itty Bitty Machine company. Their best product IMO is their Power architecture as used with NVIDIA in supercomputers.

Quantum Class 19, Thu 2022-11-17

1 ECSE Alumni

It is possible to succeed after RPI.

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 General programming tips

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.

3 Parallel computing summary

  1. Read https://computing.llnl.gov/tutorials/parallel_comp/ for an intro to parallel computing.

  2. Some points:

    1. Parallel computing is decades old; there were commercial machines in the 1980s. I directed two PhD theses in parallel geometry then. However, then, clock speeds were increasing so serial machines were more interesting.

    2. Now: physics limits to processor speed.

    3. History of Nvidia.

      1. Curtis R. Priem ’82, Secretary of the RPI Board had designed graphics HW for both IBM and Sun Microsystems.

      2. Priem was an undergrad in ECSE.

      3. For awhile Sun was THE Unix workstation company. They used open standards and had the best price / performance.

      4. Nvidia designed gaming graphics accelerators...

      5. that just happened to be parallel coprocessors...

      6. that started to be used for nongraphics parallel processing because of their value.

      7. Nvidia noticed that and added more capability, e.g., double precision IEEE floats, to serve that market.

      8. Currently, some of the highest performance Nvidia boards cannot even do graphics because they don't have video out ports.

    1. Intel CPUs vs Nvidia CUDA cores.

    2. Advantages and disadvantages of shared memory.

    3. OpenMP vs CUDA.

    4. Rate-limiting cost usually I/O not computation.

  3. NVIDIA's teaching material.

    Note: Rather than explicitly extracting large zip archives or tarballs in order to read files in them, I use archivemount to create a virtual file system. This saves disk space. It doesn't stress git as much (fewer files). When reading, the I/O time is insignificantly increased. For some formats, you can even write. You can have more confidence that the zip file wasn't changed, than in a directory with perhaps hundreds of files.

4 NVIDIA

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.6.1 Versions

  1. CUDA has a capability version, whose major number corresponds to the micro-architecture generation. Kepler is 3.x. The K20xm is 3.5. The GTX 1080 is 6.1. The RTX 8000 is 7.5. Here is a table of the properties of different compute capabilities. However, that table is not completely consistent with what deviceQuery shows, e.g., the shared memory size.

  2. nvcc, the CUDA compiler, can be told which capabilities (aka architectures) to compile for. They can be given as a real architecture, e.g., sm_61, or a virtual architecture. e.g., compute_61.

  3. The CUDA driver and runtime also have a software version, defining things like available C++ functions. The latest is 10.1. This is unrelated to the capability version.

4.6.2 Misc

  1. With CUDA, the dominant problem in program optimization is optimizing the data flow. Getting the data quickly to the cores is harder than processing it. It helps big to have regular arrays, where each core reads or writes a successive entry.

    This is analogous to the hardware fact that wires are bigger (hence, more expensive) than gates.

  2. That is the opposite optimization to OpenMP, where having different threads writing to adjacent addresses will cause the false sharing problem.

  3. Nvidia CUDA FAQ

    1. has links to other Nvidia docs.

    2. can be a little old.

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.

5 NVIDIA Quantum Computing

  1. Nice intro: https://docs.nvidia.com/cuda/cuquantum/overview.html

  2. https://quantumzeitgeist.com/artificial-intelligence-giant-nvidia-creates-a-new-platform-for-hybrid-quantum-classical-computing-qoda/

  3. https://developer.nvidia.com/qoda

  4. https://nvidianews.nvidia.com/news/nvidia-announces-hybrid-quantum-classical-computing-platform

  5. NVIDIA Special Address at Q2B: Defining the Quantum Accelerated Supercomputing Platform 18:39. Jul 12, 2022

    Quantum computing has the potential to offer giant leaps in computational capabilities, impacting a range of industries from drug discovery to portfolio optimization. Realizing these benefits requires pushing the boundaries of quantum information science in the development of algorithms, research into more capable quantum processors, and the creation of tightly integrated quantum-classical systems and tools. We'll review these challenges facing #quantumcomputing, showcase how #GPUcomputing can help, and reveal exciting developments in tightly integrated quantum-classical computing. https://developer.nvidia.com/qoda

  6. Watch Nvidia Reveal Quantum Computing Platform, QODA 6:53 Jul 12, 2022

    At Q2B, Nvidia announces QODA, a new hybrid quantum-classical computing platform. See it explained here.

  7. https://developer.nvidia.com/blog/introducing-qoda-the-platform-for-hybrid-quantum-classical-computing/

  8. https://blogs.nvidia.com/blog/2022/07/29/what-is-a-qpu/

  9. Q2B 2021 | Accelerating Quantum Algorithm Research with cuQuantum | Harun Bayraktar 29:52. December 9, 2021. Excellent solid talk.

Quantum Class 18, Mon 2022-11-14

1 Good general site

https://quantumzeitgeist.com/

2 Conference showing real world interest in quantum computing

https://q2b.qcware.com/2022-conferences/silicon-valley/december-6-detailed-program/

3 Intel Quantum Computing - 2

  1. They use hot (temp: 1K) silicon spin qbits.

  1. https://newsroom.intel.com/news/intel-qutech-demonstrate-high-fidelity-hot-qubits-practical-quantum-systems/#gs.iri5sn

  2. https://en.wikipedia.org/wiki/Spin_qubit_quantum_computer

  3. https://physicsworld.com/a/silicon-spin-qubits-manufactured-on-an-industrial-scale/

  1. https://quantumcomputingreport.com/intel-releases-their-own-quantum-sdk-for-beta-test-and-they-are-funding-universities-to-develop-curricula-using-it/

  2. https://download.intel.com/newsroom/2022/2022innovation/quantum-sdk-backgrounder.pdf

  3. An LLVM-based C++ Compiler Toolchain for Variational Hybrid Quantum-Classical Algorithms and Quantum Accelerators

    Variational algorithms are a representative class of quantum computing workloads that combine quantum and classical computing. This paper presents an LLVM-based C++ compiler toolchain to efficiently execute variational hybrid quantum-classical algorithms on a computational system in which the quantum device acts as an accelerator. We introduce a set of extensions to the C++ language for programming these algorithms. We define a novel Executable and Linking Format (ELF) for Quantum and create a quantum device compiler component in the LLVM framework to compile the quantum part of the C++ source and reuse the host compiler in the LLVM framework to compile the classical computing part of the C++ source. A variational algorithm runs a quantum circuit repeatedly, each time with different gate parameters. We add to the quantum runtime the capability to execute dynamically a quantum circuit with different parameters. Thus, programmers can call quantum routines the same way as classical routines. With these capabilities, a variational hybrid quantum-classical algorithm can be specified in a single-source code and only needs to be compiled once for all iterations. The single compilation significantly reduces the execution latency of variational algorithms. We evaluate the framework's performance by running quantum circuits that prepare Thermofield Double (TFD) states, a quantum-classical variational algorithm.

  4. https://www.hpcwire.com/off-the-wire/intel-labs-releases-beta-version-of-intel-quantum-software-development-kit/

  5. https://www.linkedin.com/pulse/writing-hybrid-quantum-algorithm-using-intel-sdk-beta-ibrahim

    We may cover this in class.

  6. qHiPSTER: The Quantum High Performance Software Testing Environment

    We present qHiPSTER, the Quantum High Performance Software Testing Environment. qHiPSTER is a distributed high-performance implementation of a quantum simulator on a classical computer, that can simulate general single-qubit gates and two-qubit controlled gates. We perform a number of single- and multi-node optimizations, including vectorization, multi-threading, cache blocking, as well as overlapping computation with communication. Using the TACC Stampede supercomputer, we simulate quantum circuits ("quantum software") of up to 40 qubits. We carry out a detailed performance analysis to show that our simulator achieves both high performance and high hardware efficiency, limited only by the sustainable memory and network bandwidth of the machine.

  7. Intel Quantum Simulator

    We'll download and install this.

  8. https://intel-qs.readthedocs.io/en/docs/get_started_examples.html

  9. https://quantumzeitgeist.com/intels-quantum-sdk-is-in-beta/

  10. https://quantumzeitgeist.com/intel-corporation-collaborates-with-qutech-to-build-worlds-first-industrially-manufactured-qubit-device/

Quantum Class 17, Thu 2022-11-10

1 No lecture today

Read these notes. The big topic is Intel Quantum Computing.

2 Final projects

Homework 10, due Mon, is for you to announce your team and topic.

Some successive homeworks will be for progress reports.

Deliverables will be a report, a talk, and if writing code, documentation.

If you're taking the 6000 version, make the report longer or add a 2nd paper. Include a note saying why your work deserves 6000-level credit.

Presentations will be the last 3 classes: Dec 1, 5, 8. I'll open a signup site later.

3 Xkcd on quantum

https://xkcd.com/1861/

4 Intel Quantum Computing - 1

  1. Watch Intel's Entire Quantum Computing Presentation (Innovation Event 2022) 5:54. Sep 28, 2022.

  2. Million-Qubit Quantum Computer from Intel 14:37. Apr 11, 2022.

    In this video I discuss Intel Quantum Computer based on Silicon Qubits. It is the first Silicon Qubits at Scale and based on this technology Intel is building a Million-Qubit Quantum Computer.

  3. Architecture All Access: Quantum Computing 13:33 Jun 23, 2021.

    Quantum Computing has the potential to change our lives and far exceed the capabilities of today’s supercomputers. Join James Clarke, Director of Quantum Computing at Intel Labs, as he runs through the basics of quantum mechanics, what components make up a quantum computer, when we’ll achieve quantum practicality, and more.

    During his 20 years at Intel James Clarke has been a process engineer, led advanced interconnect research, and launched Intel’s Quantum Computing efforts with a focus on leveraging our in-house transistor process and manufacturing capabilities to create scalable qubit arrays. He’s co-authored over 50 papers and holds multiple patents.

    Architecture All Access is a master class technology series featuring Senior Intel Technical Leaders taking an educational approach to the historical impact and future innovations of key architectures that will continue to be at the center of ‘world-changing technology that enriches the lives of every person on earth.’ If you are interested in CPUs, FPGAs, Quantum Computing and beyond, subscribe and hit the bell to get new episode notifications.

  4. Intel Innovation 2022 Day 1 Keynote Replay 1:10:30. Sep 27, 2022.

    Linus Torvolds appears an hour in.

  5. Intel Innovation 2022 Day 2 Keynote Replay 1:12:27. Sep 28, 2022.

    ... The new Intel #Quantum software development kit (SDK) is designed to help developers learn how to program quantum algorithms and interface with Intel’s quantum computing stack.

  6. Quantum Computing! See Google, IBM and Intel’s Labs (supercut) 12:43. Aug 6, 2021.

    IBM, Google and Intel research scientists discuss the current state of quantum computing, and how the emerging tech is evolving in its labs.

Quantum Class 15, Mon 2022-10-24

1 Student presentations, round 2

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?

2 Quantum computing and DoD research

  1. https://www.google.com/search?channel=fs&q=darpa+quantum+computing

  2. https://www.google.com/search?q=aro+quantum+computing

  3. https://www.google.com/search?q=afosr+quantum+computing

  4. https://www.google.com/search?q=nrl+quantum+computing

  5. BAA, STTR, SBIR, solicitation, white paper

3 Amazon Braket

https://docs.aws.amazon.com/braket/

Quantum Class 14, Thu 2022-10-20

1 Followup on free-ranging discussion time, 3

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 Student presentations, round 2

Pick your date (choices: next Mon or Thurs) and announce your topic here:

https://doodle.com/meeting/participate/id/dJqLVD2b

When signing up, use enough of your name(s) that I can recognize you, plus your topic.

3 News

  1. The Nobel Prize in Physics 2022

    https://www.nobelprize.org/prizes/physics/2022/press-release/

  2. New research suggests our brains use quantum computation

    https://phys.org/news/2022-10-brains-quantum.html

  3. https://quantumcomputingreport.com/news/

    Note Malta.

  4. https://news.mit.edu/topic/quantum-computing

  5. https://www.reddit.com/r/QuantumComputing/new/

    can be interesting

  6. https://www.reddit.com/r/dwave/new/

    has little traffic

4 Optimization problems doable with D-wave

  1. Max cut

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

  2. VLSI Circuit opt

    https://www.researchgate.net/publication/262162554_An_Application_of_Combinatorial_Optimization_to_Statistical_Physics_and_Circuit_Layout_Design

  3. Spin glass min energy

  4. A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems

    https://arxiv.org/abs/1406.7601v2

  5. https://docs.dwavesys.com/docs/latest/handbook_problems.html#cb-probs-scheduling

5 D-Wave

We'll go thru

https://docs.dwavesys.com/docs/latest/

Quantum Class 13, Mon 2022-10-17

1 Followup on free-ranging discussion time, 2

  1. Real world electrical engineering: I'll show different plug formats for charging a Tesla.

    1. Note CCS evolved by just grafting DC pins onto the existing AC plug.

      CCS is common; I have a converter.

    2. Tesla transmits data in addition to power. Similar to USC-C except 1000x power.

      Tesla, the best technical format will probably lose to CCS. This has happened before.

      I have a 240V 48A Tesla charger at home.

    3. Chademo is obsolete.

    4. J-1772 is common for level-2 chargers at hotels. I have a converter.

    5. There are several NEMA formats for home outlets.

    6. There are 3 charging levels.

      1. 120V 12A

      2. 240V up to 48A (approx)

      3. 400V DC up to 500A (approx)

  2. College accreditation:

    1. The US is different from other countries, with less central control.

    2. We have various overlapping accreditation agencies.

    3. As for RPI:

      1. The university is accredited by the regional Middle States Commission on Higher Education (the US is partitioned into 6 regions).

      2. Degrees are accredited by the University of the State of New York "the Regents" (quite different from the State University of NY),

      3. Many specific programs, like EE, CSYS, medicine, law are accredited by their field. Here, accreditation only cuts off the lower tail of the distribution.

        Many professions require graduation from an accredited program (and then passing an exam) to practice. E.g., medicine, civil engineering.

    4. Historically, accreditation often was instituted to clean up a mess of awful places. E.g. medicine. In a milder form, CS.

    5. Unusual types of colleges (= those that can't get the usual accreditation) can form their own accrediting agencies. However the regular agencies are themselves accredited, in a chain terminating at the US Dept of Ed.

    6. Students who don't understand this mess can be tricked.

2 D-wave

  1. Videos, each about 6 min.

    1. Quantum Annealing Explained

    2. How Quantum Annealing Works

    3. The Physics of Quantum Annealing — Hamiltonian and Eigenspectrum

    4. A Tour of D-Wave's Lab Part 1

    5. A Tour of D-Wave's Lab

#. Quantum Programming 101 Aug 30, 2022 51:46.

3 Homework

Homework 8 is online.

Quantum Class 12, Thu 2022-10-13

1 Followup on free-ranging discussion from last time

  1. What use is quantum computation?

    "What good is a newborn baby?" - attributed to Mike Faraday and Ben Franklin.

  2. Value of PhD

    1. I like the idea, but maybe it's obsolescent.

    2. It teaches stubbornness and how to accomplish a 4 year project, which is unusual in industry.

    3. It's required for academia, but universities are obsolescent.

    4. It can be a status symbol in government, military, business.

    5. It's required to manage technical people with PhDs. Otherwise they won't respect you and you'll have trouble making technical decisions. Similarly, effective hospital managers are MDs.

      The mushy degrees that combine management with a technical concentration, either in math or health, have been tried for decades and always fail. OK, them's fighting words, so bring it on.

    6. However, you won't live longer because of the time you spent as a grad student. Maybe there were better uses of those 4 years.

  3. Strategic career advice

    1. Work to stay current in your field. Your employer may oppose this. If so, do it on your own time.

    2. E.g., I'm 70 years old and I'm teaching quantum computing.

      I proposed this course to ECSE 3 years ago, created it, and spend a lot of time learning the material.

      The difference between you and me is that RPI pays me to learn this.

    3. If you don't stay current, you'll be laid off after 20 years as obsolescent.

    4. In this credentialed society, collect the pretty pieces of paper. It's easier now with all the online courses.

    5. Be prepared for big unexpected changes. Imaging describing today's world to someone from even 5 years ago....

    6. Finally, make contacts and be friendly. All of my jobs have been from people I knew. As my grandmother said, "Be nice to the people you meet on the way up. You may meet them again on the way down."

2 Shor's algorithm to factor an integer

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

4 HHL algorithm to solve a linear system of equations

  1. Quantum Machine Learning - 37 - Overview of the HHL Algorithm 5:48.

    quick, deep, intro.

  2. Quantum algorithm for solving linear equations 36:31.

    quite understandable.

  3. Quantum Algorithms for Systems of Linear Equations (Quantum Summer Symposium 2020) 19:22.

  4. IBM Quantum Algorithms for Applications from qiskit

    E.g., Fourier transform and HHL.

  5. HHL Algorithm

    This is in Huawei HiQ, an open-source software framework for quantum computing.

  6. https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations

5 Term project

Time to start thinking of a term project, on a topic at least vaguely related to the course. Teams of any size ok. For the grad version, also write a paper.

Quantum Class 11, Mon 2022-10-03

1 Another view of superposition

The quantum states of some system are solutions of a linear PDE. There is a basis set of solutions. Linear combos are also solutions. That's superposition.

2 Simon's periodicity

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

For some unknown $c$, $F(x\oplus c) = F(x)$.

Determine $c$.

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

3 Quantum Fourier Transform

https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html

4 Quantum Phase Estimation

https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html

5 Inauguration Day Oct 6

  1. There are student seats available at the investiture. See me if interested.

Quantum Class 10, Thu 2022-09-29

1 IEEE Quantum Week 2022

This conference was last week. It was expensive but you can get something for free thus. Look at https://qce.quantum.ieee.org/2022/home/program/keynotes/

to see current important topics. Then google the speakers and titles to look for free versions of their presentations.

You could also pay for virtual access for 3 months.

E.g. Fred Chong: Closing the Gap Between Quantum Algorithms and Hardware.

https://www.youtube.com/watch?v=VNX4RLtbFeA

https://people.cs.uchicago.edu/~ftchong/Chong-QC-UCLA19.pdf

They lead to https://nwquantum.com/events/

NQN Seminar Series – Hybrid Classical-Quantum Algorithms.

2 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

3 Deutsch Jozsa Algorithm, ctd

The problem is artificial and uninteresting by itself. Its importance is that it was the first problem with a faster quantum algorithm (than its classical algorithm). It's a proof of principle.

This is a nice detailed description:

https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm

We're following: https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html

Another view: Deutsch Jozsa Algorithm - Quantum Computer Programming w/ Qiskit p.3.

Then the next step is to find a more interesting problem that can be sped up.

4 Bernstein-Vazirani Algorithm

This would be that next step.

https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html

5 Simon's periodicity

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

For some unknown $c$, $F(x\oplus c) = F(x)$.

Determine $c$.

Quantum Homework 6, Thu 2022-09-29

Due next Thu Oct 6.

Groups of 2 are ok; submit one answer to gradescope.

Try the programming examples accompanying the algorithm descriptions and report. Indeally, install qiskit on your machine, and compare to running on the IBM cloud. Try the simulator and a real quantum computer.

Quantum Class 9, Mon 2022-09-26

1 Respite not so bad after all

It trapped a message from AEFIS.

2 Caltech - excellent quantum computing sites

Quantum Science and Engineering

Institute for Quantum Information and Matter, a National Science Foundation Physics Frontiers Center

Alliance for Quantum Technologies

https://scienceexchange.caltech.edu/topics/quantum-science-explained/quantum-computing-computers

https://www.quantamagazine.org/entanglement-made-simple-20160428/ - Frank Wilczek, the author, got a nice free meal with the King of Sweden in 2004.

https://www.science.org/content/article/einstein-s-spooky-action-distance-spotted-objects-almost-big-enough-see

https://www.space.com/31933-quantum-entanglement-action-at-a-distance.html

3 Entanglement

Some sites that might help understanding it.

https://magazine.caltech.edu/post/untangling-entanglement

4 Quantum algorithms

We'll learn some famous quantum algorithms from the old qiskit text, starting with

oracles .

Quantum Class 7, Mon 2022-09-19

1 Student presentations

Mon:

  1. Noah Prisament - Bose Einstein condensate quantum computing

  2. Alex Bozeat - NMR

  3. Ahmed Elmenshawi - Spin Qbit

  4. Adam Goines - Neural Atom Quantum Computers

  5. Sanghyun Kim & Charles Chae - Photonics & Orca computing

  6. Oliver Salvaterra - optical lattice

    Thurs:

  7. Richard Pawelkiewicz - Vibrating Atoms

  8. Denzell Dixon - Photonic quantum computing

  9. Steven Laverty - Diamond Quantum Computing

  10. Alice Bibaud - Topological photonic chips

  11. Vansh Reddy Cheguri - Bose Einstein

2 Homework 5 online

Here.

due next Mon.

Quantum Class 6, Thu 2022-09-15

1 Homework 4 ctd

You talk next Mon. See here.

Use https://doodle.com/meeting/participate/id/dBLvyWka

to sign up. Give your topic and enough of your name that I can id you.

There's only one time; the purpose of this is to state your topic in a way that other people can see.

(By posting the link, I'm opening myself to potential spamming, but so far, that hasn't happened.)

2 Old homeworks

To accommodate late adders (students not Viperidae), I've extended the late due dates for the homeworks. Anyone else may also update their answers.

However I'll probably grade quite easily so it isn't necessary.

3 My class conflicts

  1. To accommodate a presidential reception that I'm attending, today will end at 4:45. Last year, I asked Pres Jackson what to do about the conflict. She said to end class early.

  2. Still thinking about what to do for the presidential installation, which might overlap if it runs late.

    I recommend attending the presentations; I am. These are a benefit of being at RPI.

  3. There'll be no classes the first week of Nov because I'll be at ACM SIGSPATIAL. I'll probably assign outside reading and watching.

4 COVID

What shall we do about quarantined students? I could try to webex the class from my iphone. But that quality will probably be bad. So here's a suggestion:

Any quarantined student, and also nonquarantined ones, is welcome to personal webex calls with me to ask questions about quantum computing etc. We can call these office hours.

If you want one, email with some times; I'll reply. When we agree, I'll call then.

5 IBM Quantum

Continuing what was started last class with qiskit etc.

Quantum Class 5, Mon 2022-09-12

1 Homework 4

You talk next Mon. See here.

2 Quantum computing in the news

(or at least on Slashdot).

  1. https://yro.slashdot.org/story/21/09/04/2147245/americas-nsa-isnt-sure-quantum-computers-will-ever-break-public-key-encryption

3 Abstract computation models ctd

  1. Original motivation was to discover an algorithm for proving (or disproving) theorems.

  2. That can be done in some simple cases, like first order predicate calculus with addition over the integers.

    1. and first order predicate calculus with addition and multiplication over the rationals or reals.

  3. This goal failed because it was proved that it is undecidable in some cases.

    1. like first order predicate calculus with addition and multiplication over the integers.

    2. Some theorems truth or falsity depends on the allowable domain of their variables.

    3. in a deep sense, ints are harder than reals.

    4. Long time ago I wrote a paper on this, in the context of computer graphics. Problems with Raster Graphics Algorithms.

4 Complexity classes

  1. Group problems into broad classes of considerably differing difficulty.

  2. P vs NP.

  3. Steve Cooks's paper first describing this was rejected.

  4. Quantum complexity classes.

5 Hardware implementations

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

  2. Just like classical computers.

  3. Many competing technologies.

  4. Let the strongest win.

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.1.1 Transmon qubit

  1. Sutor: Under the hood of IBM Q

  2. The transmon qubit | QuTech Academy 6:03.

  3. Alexandre Blais - Quantum Computing with Superconducting Qubits (Part 1) - CSSQI 2012 45:11.

  4. Control of transmon qubits using a cryogenic CMOS integrated circuit (QuantumCasts) 35:47.

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.

Quantum Homework 4, Mon 2022-09-12

  1. Student presentation to class next Mon 2022-09-19.

  2. Pick an approach to building quantum computers that is not used by a major company like IBM, Google, Microsoft, Amazon, Rigetti or D-wave. Hidary Chapter 5 has lots of suggestions. Describe the idea, and its major advantages and disadvantages.

  3. About 5-7 minutes. I won't be using a stopwatch, but be respectful of the other students. How the Ig Nobel awards handles this.

  4. Suggestion: test your computer with the classroom setup in advance. The room is open.

Total: 10

Quantum Class 4, Thurs 2022-09-08

1 Scientifically literate people and quantum computing

About people who are generally scientifically aware, but not really practitioners of science. What do you think people like that would like to know about Quantum Computing? Many people have heard about it, but most people don’t know what it means. What do you think their “burning questions” about it might be?

2 Handwritten notes are online

here. The file name is the class number; last time was 03.pdf . These are not really intended to stand alone; my typed blog is primary.

However, would you like me to add more details as I write them in class?

3 Homework 3 is online

(I think).

due next time.

4 Questions on last videos

  1. IBM:

    1. What are the roles of the kernel, algorithm, and model developers?

    2. Tell me about error suppression.

  2. Google:

    1. What are they doing?

    2. How do they control a qbit?

    3. How to they manage errors?

5 Videos to watch for next time

  1. The Map of Quantum Computing | Quantum Computers Explained, 33:27,

  2. Quantum Entanglement: Spooky Action at a Distance 14:41. 2020-02-12

6 Bloch sphere

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

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

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

  4. Many operations are rotations.

  5. I don't think this idea is particularly big, but people like it.

  6. It does not extend to multiple qbits.

7 Matrices

  1. Quantum computing operators are unitary.

    The conjugate transpose is the inverse.

  2. Measurement operators are self-adjoint aka Hermetian.

    The conjugate transpose is the matrix itself.

8 Hidary Chapter 3: Qubits, Operators and Measurement

with additions from other sources.

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.

9 Quantum properties - No Cloning

I made some supplementary material on cloning (copying), which works in the classical world but not in the quantum world.

Classically, you can easily clone a bit. Consider a 2-bit system, $x, y$. Each bit can be 0 or 1. All 4 combos are possible. Represent the state with a 4-vector

$s=\begin{vmatrix} a_0\\a_1\\a_2\\a_3\end{vmatrix}$

where exactly one $a_i=1$ and the other three are 0. E.g., if $a_3=1$ then $x=y=1$.

Here's a 2-input, 2-output circuit that clones the first bit.

$x'=x\\y'=x$

Its truth table is

x y | x'y'
0 0 | 0 0
0 1 | 0 0
1 0 | 1 1
1 1 | 1 1

Represent the operation by a matrix multiplication on s. The matrix M is:

1 1 0 0
0 0 0 0
0 0 0 0
0 0 1 1

That is, the final state is $s'_i = \sum_j M_{ij} s_j$

However, M is singular. For quantum operations, M has to be unitary. So this is not a legal quantum circuit. Let's try again.

The better way is the 3-input Toffoli gate. The function is

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

The truth table is

x y z | x'y'z'
0 0 0 | 0 0 0
0 0 1 | 0 0 1
0 1 0 | 0 1 0
0 1 1 | 0 1 1
1 0 0 | 1 0 0
1 0 1 | 1 0 1
1 1 0 | 1 1 1
1 1 1 | 1 1 0

The matrix is Eqn 5.62 on page 155.:

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0

Let x=1, z=0. Then:

x'= 1
y'= y
z'= y

and we've cloned y in the classical case, where the inputs are each 0 or 1.

This matrix is nonsingular and so is also legal in a quantum circuit.

(Looking ahead a little), try $y= \frac{1}{\sqrt{2}} | 0> + \frac{1}{\sqrt{2}} | 1>$, which is an equal superposition of 0 and 1. Using x=1, z=0, the input will be

$\frac{ | 1, 0, 0> + | 1, 1, 0>}{\sqrt{2}}$

and the state is

$(0, 0, 0, 0, \frac{1}{\sqrt{2}} , 0, \frac{1}{\sqrt{2}} , 0)^T$

That's an equal superposition of 2 of the possible 8 classical input states.

Multiplying that by the matrix gives

$\frac{ | 1, 0, 0> + | 1, 1, 1>}{\sqrt{2}}$

Instead of cloning y into z, this entangled y and z.

An operation that is simple on classical input can be more complicated on quantum inputs.

This isn't new; we already know how to entangle two qbits.

Engangling isn't the same as cloning. The point of cloning is that we could operate on the two bits separately. If they're engangled, operating on one affects the other.

Quantum Homework 3, Thurs 2022-09-08

Due 2022-09-12 4pm in gradescope. Groups of 2 are ok; submit one answer set.

(These questions are from Hidary.)

  1. (10 points) Investigate the Stern-Gerlach experiment of 1921. What was the expectation from classical theory for the outcome and what actually occurred?

  2. (10 points) What does non-separable mean for two states and what does that tell us about these states?

  3. (10 points) For the CZ gate, does it matter which qubit is the control qubit and which is the target?

  4. (10 points) What is the final state of the following circuit, in Dirac notation?

/files/hidary-hw-3-1b.png

Total: 40

Quantum Misc notes, Thurs 2022-09-08

Misc notes that I draw from for lectures.

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

2 Hardware implementations

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

  2. Many competing technologies.

  3. Let the strongest win.

3 New material

Various things designed to solidify your understanding of the fundamentals.

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.

      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.

    14. p 91, Ex 3.2.2

    15. p 93 double slit experiment

    16. p 97 Section 3.4, Assembling systems

3.2 2 slit experiment compared with real vs complex transitions

4 Misc intro to quantum computing stuff

This is misc stuff that you might find interesting, which I'm drawing from.

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.

/files/ionq_hws.png

4.4.1 Transmon qubit

  1. Sutor: Under the hood of IBM Q

  2. The transmon qubit | QuTech Academy 6:03.

  3. Alexandre Blais - Quantum Computing with Superconducting Qubits (Part 1) - CSSQI 2012 45:11.

  4. Control of transmon qubits using a cryogenic CMOS integrated circuit (QuantumCasts) 35:47.

4.4.2 Trapped Ion

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

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

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

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

4.4.4 Photonics

  1. Operates at room temperature.

  2. See Xanadu below.

4.5 Companies - Primary

These companies have their own hardware.

4.5.1 IBM

4.5.1.1 Summary
  1. They have several quantum computers, up to 53 qbits.

  2. The older ones are freely available on the web; see https://quantum-computing.ibm.com/

  3. Note that you can put gates between only adjacent 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.

4.5.1.2 Sites
  1. IBM Introduces First Integrated Quantum Computing System for Commercial Use

  2. Go Behind-the-Scenes of a Quantum Experiment (2:10) https://quantumexperience.ng.bluemix.net/qx/community/question?questionId=5ae975690f020500399ed39a&channel=videos

    or

    https://www.youtube.com/watch?v=tfZpJLdkzRU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=7

  3. A Qubit in the Making (2:01)

    https://www.youtube.com/watch?v=2pB87H3_F_c&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10&t=0s

  4. Behold the Mighty Qubit (2:51) https://www.youtube.com/watch?v=_P7K8jUbLU0&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10

  5. Classical and Quantum Randomness (3:39) https://www.youtube.com/watch?v=8kyJfAC4VAo&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=6

  6. Quantum Entanglement (2:21) https://www.youtube.com/watch?v=RmXasxLm43k&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=5

  7. Benchmarking Quantum Systems (1:58) https://www.youtube.com/watch?v=-7L5o-mzLqU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=8

  8. Quantum Pong — Programming on Quantum Computers Season 1 Ep 1 3:54 by Abraham Asfaw.

  9. IBM’s Roadmap For Scaling Quantum Technology

  10. IBM publishes its quantum roadmap, says it will have a 1,000-qubit machine in 2023

  11. https://quantumcomputing.stackexchange.com/questions/tagged/ibm-q-experience

  12. https://quantumcomputing.stackexchange.com/questions/tagged/qiskit

4.5.1.3 Applications on the IBM Q
  1. Quantum Algorithms for Applications from qiskit

  2. HHL Algorithm

    This is in Huawei HiQ, an open-source software framework for quantum computing.

  3. https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations

4.5.1.4 IBM Quantum experience
  1. When you design a circuit here, you don't need to simulate it elsewhere. It shows you the probabilities.

  2. Dual view: you can see and edit both the circuit and the QASM code.

  3. There are some sample programs in https://github.com/Qiskit/openqasm.git

  4. Example circuits in https://quantum-computing.ibm.com/docs/iqx/example-circuits .

4.5.2 Intel

  1. Tangle Lake has 49 superconducting qbits.

  2. Produced in Oregon.

  3. Partners with QuTech in Netherlands.

  4. https://www.intel.com/content/www/us/en/research/quantum-computing.html

4.5.3 Google

  1. Sycamore has 54 (-> 53) transmon qbits in 9x6 array, each coupled to 4 neighbors.

    1. https://www.eenewseurope.com/news/googles-sycamore-quantum-processor-shows-supremacy

    2. https://www.nature.com/articles/d41586-019-03213-z

    3. https://jonathan-hui.medium.com/quantum-supremacy-google-sycamore-processor-6f30073a17fa - detailed. ¹

  2. Google quantum General web site.

  3. Day 1 opening keynote by Hartmut Neven (Quantum Summer Symposium 2020) 29:58.

  4. QuantumCasts link to some videos, including the following.

  5. Quantum supremacy explained (QuantumCasts) 4:26.

  6. Introduction to Quantum Chess (Quantum Summer Symposium 2020) 13:53.

  7. Quantum Money (Quantum Summer Symposium 2020) 15:56. Peter Shor. It's fun to see what Shor is thinking about now.

  8. QSI Seminar: Dr Marissa Giustina, Google Research, Building Google's Quantum Computer, 09/06/2020 55:52.

  9. The Man Who Will Build Google's Elusive Quantum Computer

  10. Programming a quantum computer with Cirq (QuantumCasts) 10:39.

4.5.4 D-Wave

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

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

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

  4. What is Quantum Annealing? 6:14.

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

  6. 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/ "

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

  8. D-Wave factoring tutorial and other demos

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

4.5.5 IonQ

  1. founders from Maryland/College Park and Duke.

  2. trapped ion

  3. 32 qbits.

  4. low error rate

  5. excellent quantum volume

  6. will be available from Microsoft Azure and Amazon AWS Braket.

  7. https://ionq.com/

  8. https://en.wikipedia.org/wiki/IonQ

  9. https://ionq.com/posts/october-01-2020-most-powerful-quantum-computer

4.5.6 Honeywell

  1. H1: trapped ion.

  2. 10 qbits,

    1. full connectivity,

    2. can read isolated qbits in mid-computation,

    3. hi-res rotations.

  3. JP Morgan experimenting with it.

4.5.6.1 Sites
  1. The World’s Highest Performing Quantum Computer is Here

  2. Details.

  3. Zdnet: Honeywell's System Model H1 quantum computer available to enterprises

  4. They partner with Microsoft,, Experience quantum impact with Azure Quantum, Cambridge Quantum Computing, Zapata Computing, etc.

4.5.7 Rigetti

  1. Berkeley-based

  2. founder is ex-IBM

  3. https://en.wikipedia.org/wiki/Rigetti_Computing

  4. https://www.rigetti.com/

  5. has lots of tools

  6. available via AWS etc

  7. technical details are sparse

  8. has been absorbing venture capital

  9. https://techcrunch.com/2020/03/05/rigetti-computing-took-a-71-million-down-round-because-quantum-computing-is-hard/

    "Recently, investors are gambling more on the middleware layer of a quantum computing stack. These are companies like Zapata, Q-CTRL, Quantum Machines and Aliro, which improve the performance of quantum computers and create an easier user experience"

  10. makes optimistic promises (8/8/18):

    https://medium.com/rigetti/the-rigetti-128-qubit-chip-and-what-it-means-for-quantum-df757d1b71ea

4.5.8 Xanadu

  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.

4.5.9 Others

  1. Alibaba

  2. 1QBit

  3. CQC

  4. QC Ware

  5. QSimulate

  6. Quantum Circuits

  7. Rahko

  8. Zapata

See https://www.explainingcomputers.com/quantum.html

4.6 Companies - Aggregators

These companies resell others' computers as a cloud service.

4.6.1 Amazon

  1. https://aws.amazon.com/braket/

    "Amazon Braket is a fully managed quantum computing service that helps researchers and developers get started with the technology to accelerate research and discovery. Amazon Braket provides a development environment for you to explore and build quantum algorithms, test them on quantum circuit simulators, and run them on different quantum hardware technologies."

    "...quantum annealers from D-Wave, and gate-based computers from Rigetti and IonQ."

4.6.2 Microsoft

  1. They offer a cloud service on 3 platforms: Honeywell, IonQ, QCI.

    Microsoft Is Taking Quantum Computers to the Cloud

  2. Microsoft Quantum

    A lot of stuff, with a low S/N.

  3. Microsoft quantum blog

  4. Azure Quantum Developer Workshop. 5:05:25.

    A little diffuse.

  5. For faster quantum computing, Microsoft builds a better qubit 11/7/2019.

  6. Microsoft Quantum Documentation gateway to a lot of stuff.

  7. Microsoft, e.g. Quantum Computing for Computer Scientists 1:28:22.

    This is the same viewpoint as the textbook, but the speaker is different.

    This talk discards hand-wavy pop-science metaphors and answers a simple question: from a computer science perspective, how can a quantum computer outperform a classical computer? Attendees will learn the following:

    • Representing computation with basic linear algebra (matrices and vectors)

    • The computational workings of qbits, superposition, and quantum logic gates

    • Solving the Deutsch oracle problem: the simplest problem where a quantum computer outperforms classical methods

    • Bonus topics: quantum entanglement and teleportation

    The talk concludes with a live demonstration of quantum entanglement on a real-world quantum computer, and a demo of the Deutsch oracle problem implemented in Q# with the Microsoft Quantum Development Kit. This talk assumes no prerequisite knowledge, although comfort with basic linear algebra (matrices, vectors, matrix multiplication) will ease understanding.

    See more at https://www.microsoft.com/en-us/research/video/quantum-computing-computer-scientists/

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.8.1 Deutsch

  1. We have a black box F(x) -> x'.

  2. We're told that F is either balanced or constant.

  3. How to determine which?

  4. We can input any x and see the result.

  5. Classically: eval F(0) and F(1).

  6. That took two evals and some comparisons.

  7. All that matters is the number of evals. We assume that they're slower than everything else.

  8. Quantumly (quantumicly?) we can determine which type F is with only one eval plus some extra matrices.

4.8.2 Deutsch - Jozsa

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

We're told that it's either constant or balanced. It's not neither.

Which is it?

Classically, we need n/2+1 evals of F.

Quantumly, we need only 1.

4.8.3 Simon's periodicity

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

For some unknown $c$, $F(x\oplus c) = F(x)$.

Determine $c$.

4.8.5 Deutsch-Jozsa

This algorithm is deterministic.

  1. https://www.quantiki.org/wiki/deutsch-jozsa-algorithm

    Quick summary; doesn't say why it works.

  2. https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html

    This is an intro to Qiskit. The terminology is confusing. E.g., Register 1 has q0 q1 q2. Register 2 has q3. The run buttons don't seem to work.

  3. https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm

    This is a nice detailed description.

4.8.6 Shor's algorithm

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

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

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

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

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

4.8.7 HHL algorithm to solve a linear system of equations

  1. Quantum Machine Learning - 37 - Overview of the HHL Algorithm 5:48.

    quick, deep, intro.

  2. Quantum algorithm for solving linear equations 36:31.

    quite understandable.

  3. Quantum Algorithms for Systems of Linear Equations (Quantum Summer Symposium 2020) 19:22.

  4. IBM Quantum Algorithms for Applications from qiskit

    E.g., Fourier transform and HHL.

  5. HHL Algorithm

    This is in Huawei HiQ, an open-source software framework for quantum computing.

  6. https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations

4.9 Software

4.9.1 General

  1. A difficulty is to compile to the limited connectivity of the machine

  2. Open-Source Quantum Software Projects

  3. ProjectQ open-source software framework for quantum computing.

  4. Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises . Tutorial given at a few conferences.

4.9.2 Middleware

  1. https://www.hpcwire.com/off-the-wire/quantum-computing-inc-releases-version-1-1-of-mukai-middleware/

  2. https://tbri.com/webinars/middleware-the-quantum-computing-differentiator/ "An integral piece of quantum computing’s success is the middleware bridging existing code and algorithms to the new logical circuitry being established that sits on top of the quantum circuits. This integration and abstraction will allow the technology to process complex algorithms to provide the outcomes the hardware enables."

4.10 More info

4.10.1 QuTech Academy

  1. excellent videos from this Delft research group.

  2. QCI

  3. Per Delsing: Superconducting qubits as artificial atoms 28:59.

    He's describing a different computer from IBM's.

  4. The Taming of the Superconducting Qubit: A Tale of Loss 35:47.

    Presenter: Conal Murray, Research Staff Member, IBM Research

    The potential of quantum computing to enable new ways of solving problems considered intractable on classical computing platforms relies on our understanding of how qubits operate. Qubit scaling follows different metrics than those associated with classical computing, driven by the requirement that the fragile states they possess can be retained for sufficiently long times. After a brief introduction into superconducting transmon qubits, I will discuss how dielectric loss impacts their relaxation times and how we can effectively model such behavior using analytical and computational approaches. The resulting analysis provides guidance into the design aspects associated with such qubits. A secondary issue that follows from manufacturing greater numbers of qubits involves unwanted communication among them. In particular, resonance modes generated in the substrate on which they reside can limit their operating frequencies. It is known that incorporating grounded, through-silicon vias can increase the corresponding cutoff frequency within the substrate. I will show how we can predict the resulting spectrum by considering the array of vias as an effective photonic crystal to arrive at a fundamental frequency dependent on the particulars of the via geometry.

    http://meetings.aps.org/Meeting/MAR20/Session/P28.2

4.10.2 Misc

  1. 8 Best New Quantum Computing Books To Read In 2020

  2. quantikz – Draw quantum circuit diagrams in latex.

  3. Quantum Computing UK nice set of docs and examples.

  4. Ricardo Diaz recommends this book: Something Deeply Hidden: Quantum Worlds and the Emergence of Spacetime .

  5. There are now several business reports on the industry.

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.

Quantum Class 3, Tues 2022-09-06

1 Action at a distance

  1. Two qbits can be entangled tho they are far apart.

  2. How can this be?

  3. Newton faced the same conceptual leap.

  4. How can the earth affect the moon's orbit?

  5. Some people posited invisible whirlpools in space that dragged the planets around.

  6. That was falsified by the existence of retrograde orbits.

  7. Now we say that it happens because, in general relativity, the earth's mass bends space-time, and the moon just follows a geodesic.

  8. My view is that if something is useful but inexplicable, then just use it.

  9. Or, do like Andreas Osiander, Copernicus's editor, "these hypotheses need not be true nor even probable. [I]f they provide a calculus consistent with the observations, that alone is enough." https://en.wikipedia.org/wiki/Nicolaus_Copernicus

    If Giordano Bruno had talked evasively like that, maybe he wouldn't have been burnt at the stake in 1600. However he may have been burnt for other reasons.

2 Questions from Quantum Computing 2022 Update

  1. big application.

  2. what is superposition?

  3. why is it powerful?

  4. change in IBM strategy, or, what is circuit knitting?

  5. What is IBM's quantum parallelization?

  6. What is NIST doing re quantum crypto?

  7. How is Intel advancing quantum HW?

  8. What have some other companies done?

3 Hidary, Quantum Computing: An Applied Approach, 2nd ed, chapter 1

  1. Companion site: https://github.com/jackhidary/quantumcomputingbook

  2. Quantum computer: uses properties of quantum mechanics to compute

    1. world is quantum.

    2. compare to classical computer.

  3. quantum properties

    1. superposition

    2. entanglement

  4. state: complete math description of state.

    1. a complex vector.

    2. classical analog: e.g., position of a particle.

  5. Schrodinger's equation computes future state as a function of current state and stuff.

  6. Compare to Newton: future position depends on force etc.

  7. Analogously to Newton, only simple cases have closed form solutions. 2 body not 3 body. hydrogen atom.

  8. Even if there's a closed form solution, it may be chaotic, and so not as useful.

  9. Must simulate when no closed solution. Unfortunately that's all the good cases. College classes use solvable examples, not realistic ones.

  10. See Wolfram, A New Kind of Science.

  11. superposition: linear combo of states is a legal state.

    1. the weights are complex numbers.

    2. everything in quantum mechanics uses complex numbers.

    3. superposition does not work classically.

  12. A qubit $q$ is a quantum analog to a classical bit.

  13. the quantum analog to classical bits 0 and 1 are $|0\!\!>$ and $|1\!\!>$.

  14. q's state is a superposition (linear combo) of those two basis states:

    1. $q = a|0\!\!> + b|1\!\!>$ ,

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

  15. Note the weird notation (Dirac notation). In $|0\!\!>$, $|$ is like a left bracket and $>$ like a right one.

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

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

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

  19. measurement of a state $\Psi$, and the Born rule (p 5):

    1. Measurement is an operator or matrix, M, applied to a state $\Psi$.

    2. M changes the qbit irreversibly, see the polarization example in the book.

    3. You cannot reclaim the old value.

    4. M has eigenvalues.

    5. Represent $\Psi$ as a linear combo of M's eigenvalues $\psi_i$, considered as a basis.

    6. $\Psi= \alpha\psi_1+\beta\psi_2$, where $\alpha^2+\beta^2=1$.

    7. you can use different basis systems to represent the same vector, and rotate between them.

    8. M changes $\Psi$ state randomly to one of the basis vectors.

    9. the probability of $\Psi$ changing to a particular basis vector is the modulus squared of the weight of that basis vector.

    10. define $z^c$ to be the complex conjugate of $z$.

    11. if $\Psi= \alpha\psi_1+\beta\psi_2$, where $\alpha^c\alpha+\beta^c\beta=1$ then the probability of $\Psi$ changing to $\psi_1$ is $\alpha^c\alpha$. (the Born rule)

    12. $\alpha^c\alpha$ is called the modulus squared.

  20. There are many possible measurement operators available.

    1. You can choose which to apply to $q$. Say, position.

    2. That prevents you from applying the others to $q$, say, momentum, because you don't have $q$ available any more.

    3. Heisenberg uncertainty: measuring, say, position, prevents you from accurately measuring momentum.

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

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

  23. Unless $M$ is a measurement operator, it is invertible, so you can go backwards.

  24. Contrast to classical operators like and and or.

  25. Examples of 1-qubit gates

    1. not, aka X. page 28.

    2. square root of not

    3. Y, Z

    4. S (rotation by $90^o$), T ($45^o$), phase shift

    5. Hadamark. "it enables us to take a qubit from a definite computational basis state into a superposition of two states"

  26. All operators used in quantum computation other than for measurement must be reversible. - textbook.

  27. No cloning: You cannot copy a qubit, but can move it.

  28. The life cycle of a qubit:

    1. Create a qubit with a classical value, 0 or 1.

    2. Operate on it with matrices, which rotate it to have complex weights.

    3. Measure it by randomly projecting it onto a basis vector.

  29. So far, not very powerful.

  30. a quantum state $\Psi$ usually has many qubits.

    compare to a classical byte with 8 classical bits.

  31. However the different qubits in $\Psi$$ might be entangled.

    1. This is very weird and powerful.

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

    3. Even if the two qubits are 1000 mi apart. This has been experimentally observed.

    4. However that does not let you communicate.

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.

4 Chapter 2: history

  1. Read it on your own, but here are some additions:

  2. The property list on p15 is controversial and seems designed to exclude D-Wave.

  3. Like for classical computation, the main ideas of quantum computing were proposed before actual machines could be built.

5 Videos to watch for next time

  1. IBM Quantum 2022 Updated Development Roadmap, 18:49, 2022-05-10

  2. Google Quantum AI Update 2022, 25:21, 2022-04-14

Quantum Class 2, Thurs 2022-09-01

1 Class 1

I edited the blog to show what we actually did.

2 Homework 2

is online, due Tues.

3 Theory vs Experiment

  1. Sometimes the theoreticians posit something new, then the experimentalists try to build it.

    1. atom bomb

    2. classical computer

    3. quantum computer

  2. Other times the experimentalists (aka hackers) build something new.

    1. bridges

    2. airplanes

    3. medieval cathedrals

    4. steam engines

    5. calculus

  3. Then those may become so successful that bigger and bigger ones are built until those collapse / crash / fall down / blow up / have paradoxes.

  4. Then the theoreticians have to come in and clean up the mess to allow more progress.

  5. They may look for unifying themes in apparently separate problems.

  6. Group theory in abstract (modern) algebra happened that way.

  7. Anything discovered about groups was then valid in all the applied areas.

  8. All theories have limits that may or may not be relevant.

  9. Paradoxes expose limits. "All triangles are isosceles" error exposes something not covered by Euclid's axioms.

  10. Physics Nobels tend to go to theoretical explanations of surprising experiments. Although, there is nothing in common among all Nobel winners, not even intelligence (according to Enrico Fermi).

  11. Very rarely, experimentalists do something that the theoreticians had proven was impossible.

    1. Galileo seeing sunspots.

    2. Marconi radioing across Atlantic.

    3. Michaelson-Morley. (However several other contemporaneous inexplicable observations all proved to have classical explanations.)

    and something new is discovered / invented. Unfortunately the crackpots then seize on these rare examples...

4 Video

  1. Quantum Computing in Under 11 Minutes daytonellwanger https://www.youtube.com/watch?v=TAzZKAdX2Tw 10:56 more technical

5 Intro to quantum computing

  1. This is from

    1. Yanofsky and Mannucci, Quantum Computing for Computer Scientists,

    2. Hidary, 2nd edition, and

    3. my opinions.

  2. Isomorphism between geometry and algebra. Work in whichever domain is easier. Results carry over.

    1. 2D: x+ij -> (x,y)

    2. 3D: quaternions. 3D rotations are not commutative, and so quaternions are not. There's a memorial on a bridge in Trinity College Dublin where William Rowan Hamilton thought of them. Quaternions are equivalent to 3D vector algebra.

    3. qbits - Bloch sphere.

  3. qbits vs qubits? Above my pay grade.

  4. Evidence for quanta:

    1. 1905 photo-electric effect explanation. Einstein Nobel.

    2. Ultraviolet catastrophe.

    3. 1922 Stern Gerlach experiment. Very influential.

      https://en.wikipedia.org/wiki/Stern%E2%80%93Gerlach_experiment

  5. Hidary 1.1 Quantum Computer Definition, p 3

    A quantum computer is a device that leverages specific properties de- scribed by quantum mechanics to perform computation.

  6. State vector

    1. completely describes a system

    2. cannot be directly observed, only measured...

    3. which changes it.

  7. Hidary 1.1 Superposition and Entanglement, p 4

    2 big properties.

  8. bra-ket notation.

  9. can rewrite a state vector in a different basis

  10. Hidary 1.3 The Superposition Principle, p 4

    1. "The linear combination of two or more state vectors is another state vector in the same Hilbert space and describes another state of the system."

    2. Generally false in classical domain.

      Particle can go thru only 1 of 2 slits.

      However vibration states in a string add.

  11. Hidary entanglement p 7

    description is confusing, defer till later.

  12. Yanovsky p 40, vector space review

    1. One qbit is a simple vector space.

    2. Can change basis, e.g., to Hadamard basis. p 51.

  13. Eigenvalues and eigenvectors, p 60

  14. Hermetian matrices, p 63

  15. Classical 2 slit experiment, p 86.

    Probabilities add.

  16. Quantum 2 slit experiment, p 93.

    Complex waves add.

    Probabilities might reduce.

6 Quantum properties - 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.

    7. This has been demonstrated with real qbits transported 1000 miles apart.

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

    9. However that does not let you communicate.

  3. The above metaphor is inaccurate in ways that don't affect us now. (It assumes a hidden variable, which is false.)

  4. Entanglement and superposition do funny things to operations. Consider the Controlled NOT gate. It has 2 inputs, x and y.

    1. Classically, y is negated iff x=1. x doesn't change.

    2. If x and y are superposed with a Hadamard basis, then y can affect x.

7 Video to watch on your own

  1. Quantum Computing 2022 Update, 15:12, July 24 2022.

  2. You prepare discussion points and questions for next class.

8 Misc intro to quantum computing stuff

This is misc stuff that you might find interesting, which I'm drawing from.

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

9 No new homework

Finish 1 and enjoy Labor Day.

10 Videos to watch for Tues

  1. Watch A Beginner’s Guide to Quantum Computing, 18 min, by Dr. Talia Gershon, IBM Research.

Quantum Homework 2, Thurs 2022-09-01

Due 2022-09-06 4pm in gradescope. Groups of 2 are ok; submit one answer set.

These are questions about the videos watched or assigned in class.

  1. (10 points) What are the 2 ways that Talia Gershon says that quantum is different?

  2. (10 points) According to David Deutsch, what is the quantum theory of computation?

Total: 20

Quantum Class 1, Mon 2022-08-29

1 Misc

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.7.1 Preferred text

  1. Jack D. Hidary. Quantum Computing: An Applied Approach, 3nd edition, 2021. @ Springer. Also on Amazon.

1.7.2 Optional extra texts

  1. Noson S. Yanofsky and Mirco A. Mannucci. Quantum Computing for Computer Scientists 1st Edition

    I used to use this. This is nice but is 20 years old, and so omits some things. However I'll refer to it a little.

    I encourage you to read several books, and pick and choose.

  2. Abraham Asfaw et al, Learn Quantum Computation using Qiskit, http://community.qiskit.org/textbook, 2020

    There's an old and a new version. The old version was more comprehensive.

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 Intro to quantum computing

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.

Quantum Homework 1, Mon 2022-08-29

Due 2022-09-01 4pm in gradescope.

  1. (5 points) Compute (5+2i)/(3+4i).

  2. (5 pts) Compute the eigenvalues of $\begin{vmatrix} 5&2\\3&4 \end{vmatrix}$.

  3. (5 pts) Considering complex numbers as points in the 2D plane, what is the geometric effect of multiplying a complex number by (.6-.8i) ?

  4. (5 pts) Let c = 1 + i. Convert it to polar coordinates, calculate its fifth power, and revert the answers to Cartesian coordinates.

  5. (5 pts) Find all the cube roots of c = 1 - i.

  6. (5 pts) Invert the Hadamard matrix $\frac{1}{\sqrt{2}} \begin{vmatrix} 1&1\\1&-1\end{vmatrix}$.

Total: 30