Ciro Santilli @cirosantilli 35

Course plan:

A quantum algorithm that is thought to be more likely to be useful in the NISQ era of quantum computing.

There is no fundamental difference between them, a quantum algorithm is a quantum circuit, which can be seen as a super complicated quantum gate.

Perhaps the greats practical difference is that algorithms tend to be defined for an arbitrary number of N qubits, i.e. as a function for that each N produces a specific quantum circuit with N qubits solving the problem. Most named gates on the other hand have fixed small sizes.

Source on GitHub: github.com/stephenjordan/stephenjordan.github.io

The most comprehensive list is the amazing curated and commented list of quantum algorithms as of 2020.

Ah, the jewel of computational physics.

Also known as an ab initio method: no experimental measurement is taken as input, QED is all you need.

But since QED is thought to fully describe all relevant aspects molecules, it could be called "the" ab initio method.

For one, if we were able to predict protein molecule interactions, our understanding of molecular biology technologies would be solved.

No more ultra expensive and complicated X-ray crystallography or cryogenic electron microscopy.

And the fact that quantum computers are one of the most promising advances to this field, is also very very exciting: Section "Quantum algorithm".

Quantum is getting hot in 2019, and even Ciro Santilli got a bit excited: quantum computing could be the next big thing.

No useful algorithm has been economically accelerated by quantum yet as of 2019, only useless ones, but the bets are on, big time.

To get a feeling of this, just have a look at the insane number of startups that are already developing quantum algorithms for hardware that doesn't/barely exists! quantumcomputingreport.com/players/privatestartup (archive). Some feared we might be in a bubble: Are we in a quantum computing bubble?

To get a basic idea of what programming a quantum computer looks like start by reading: Section "Quantum computing is just matrix multiplication".

Some people have their doubts, and that is not unreasonable, it might truly not work out. We could be on the verge of an AI winter of quantum computing. But Ciro Santilli feels that it is genuinely impossible to tell as of 2020 if something will work out or not. We really just have to try it out and see. There must have been skeptics before every single next big thing.

One key insight, is that the matrix of a non-trivial quantum circuit is going to be huge, and won't fit into any amount classical memory that can be present in this universe.

This is because the matrix is exponential in the number qubits, and $2^{100}$ is more than the number of atoms in the universe!

Therefore, off the bat we know that we cannot possibly describe those matrices in an explicit form, but rather must use some kind of shorthand.

But it gets worse.

Even if we had enough memory, the act of explicitly computing the matrix is not generally possible.

This is because knowing the matrix, basically means knowing the probability result for all possible $2^N$ outputs for each of the $2^N$ possible inputs.

But if we had those probabilities, our algorithmic problem would already be solved in the first place! We would "just" go over each of those output probabilities (OK, there are $2^N$ of those, which is also an insurmountable problem in itself), and the largest probability would be the answer.

So if we could calculate those probabilities on a classical machine, we would also be able to simulate the quantum computer on the classical machine, and quantum computing would not be able to give exponential speedups, which we know it does.

To see this, consider that for a given input, say 000 on a 3 qubit machine, the corresponding 8-sized quantum state looks like:and therefore when you multiply it by the unitary matrix of the quantum circuit, what you get is the first column of the unitary matrix of the quantum circuit. And 001, gives the second column and so on.

As a result, to prove that a quantum algorithm is correct, we need to be a bit smarter than "just calculate the full matrix".

Which is why you should now go and read: Section "Quantum algorithm".

This type of thinking links back to how physical experiments relate to quantum computing: a quantum computer realizes a physical experiment to which we cannot calculate the probabilities of outcomes without exponential time.

So for example in the case of a photonic quantum computer, you are not able to calculate from theory the probability that photons will show up on certain wires or not.

This theorem roughly states that states that for every quantum algorithm, once we reach a certain level of physical error rate small enough (where small enough is algorithm dependant), then we can perfectly error correct.

This algorithm provides the conceptual division between noisy intermediate-scale quantum era and post-NISQ.