1.1 Disclaimer

While abstracting this summary from a large collection of disparate info, I might have made errors. However I believe this to be an unbiased and accurate summary.

1.2 My Context

1. I'm developing and teaching a new course that I proposed, ECSE-4964-01 Quantum Computer Programming.

2. 19 students who seem to like it.

3. Several people in this meet are giving guest lectures (thanks!). Everyone here is welcome.

4. RPI paying me to learn (thanks!); however there's a lot I still don't know.

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

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

2.2 No Cloning

Cloning (copying) 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.

2.3 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

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

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

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

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

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

3.4 Photonics

1. Operates at room temperature.

2. See Xanadu below.

4.1 IBM

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

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

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

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

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

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

7.4 Grover's search

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

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

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

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

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

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

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