# 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}$

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.

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.

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,

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

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

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

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

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

2. Google quantum General web site.

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

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

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

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

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

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

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

### 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. Microsoft Quantum Documentation gateway to a lot of stuff.

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

### 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:

### 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.7 HHL algorithm to solve a linear system of equations

1. quick, deep, intro.

2. quite understandable.

3. IBM Quantum Algorithms for Applications from qiskit

E.g., Fourier transform and HHL.

4. HHL Algorithm

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

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

1. excellent videos from this Delft research group.

2. QCI

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

4. 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. Quantum Computing UK nice set of docs and examples.

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

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