Course plan:
- Section "Programmer's model of quantum computers"
- look at a Qiskit hello world
- e.g. ours: qiskit/hello.py
- learn about quantum circuits.
- tensor product in quantum computing
- First we learn some quantum logic gates. This shows an alternative, and extremely important view of a quantum computer besides a matrix multiplication: as a circuit. Fundamental subsections:
- quantum algorithms
This is a quick tutorial on how a quantum computer programmer thinks about how a quantum computer works. If you know:a concrete and precise hello world operation can be understood in 30 minutes.
- what a complex number is
- how to do matrix multiplication
- what is a probability
Although there are several types of quantum computer under development, there exists a single high level model that represents what most of those computers can do, and we are going to explain that model here. This model is the is the digital quantum computer model, which uses a quantum circuit, that is made up of many quantum gates.
Beyond that basic model, programmers only may have to consider the imperfections of their hardware, but the starting point will almost always be this basic model, and tooling that automates mapping the high level model to real hardware considering those imperfections (i.e. quantum compilers) is already getting better and better.
This model is very simple to understand, being only marginally more complex than that of a classical computer, see also: quantumcomputing.stackexchange.com/questions/6639/is-my-background-sufficient-to-start-quantum-computing/14317#14317
The situation of quantum computers today in the 2020's is somewhat analogous to that of the early days of classical circuits and computers in the 1950's and 1960's, before CPU came along and software ate the world. Even though the exact physics of a classical computer might be hard to understand and vary across different types of integrated circuits, those early hardware pioneers (and to this day modern CPU designers), can usefully view circuits from a higher level point of view, thinking only about concepts such as:as modelled at the register transfer level, and only in a separate compilation step translated into actual chips. This high level understanding of how a classical computer works is what we can call "the programmer's model of a classical computer". So we are now going to describe the quantum analogue of it.
- logic gates like AND, NOR and NOT
- a clock + registers
The way quantum programmers think about a quantum computer in order to program can be described as follows:
- the input of a N qubit quantum computer is a vector of dimension N containing classic bits 0 and 1
- the quantum program, also known as circuit, is a unitary matrix of complex numbers that operates on the input to generate the output
- the output of a N qubit computer is also a vector of dimension N containing classic bits 0 and 1
To operate a quantum computer, you follow the step of operation of a quantum computer:
- set the input qubits to classic input bits (state initialization)
- press a big red "RUN" button
- read the classic output bits (readout)
Each time you do this, you are literally conducting a physical experiment of the specific physical implementation of the computer:and each run as the above can is simply called "an experiment" or "a measurement".
- setup your physical system to represent the classical 0/1 inputs
- let the state evolve for long enough
- measure the classical output back out
The output comes out "instantly" in the sense that it is physically impossible to observe any intermediate state of the system, i.e. there are no clocks like in classical computers, further discussion at: quantum circuits vs classical circuits. Setting up, running the experiment and taking the does take some time however, and this is important because you have to run the same experiment multiple times because results are probabilistic as mentioned below.
Unlike in a classical computer, the output of a quantum computer is not deterministic however.
But the each output is not equally likely either, otherwise the computer would be useless except as random number generator!
This is because the probabilities of each output for a given input depends on the program (unitary matrix) it went through.
Therefore, what we have to do is to design the quantum circuit in a way that the right or better answers will come out more likely than the bad answers.
We then calculate the error bound for our circuit based on its design, and then determine how many times we have to run the experiment to reach the desired accuracy.
The probability of each output of a quantum computer is derived from the input and the circuit as follows.
First we take the classic input vector of dimension N of 0's and 1's and convert it to a "quantum state vector" of dimension :
We are after all going to multiply it by the program matrix, as you would expect, and that has dimension !
Note that this initial transformation also transforms the discrete zeroes and ones into complex numbers.
For example, in a 3 qubit computer, the quantum state vector has dimension and the following shows all 8 possible conversions from the classic input to the quantum state vector:
000 -> 1000 0000 == (1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
001 -> 0100 0000 == (0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
010 -> 0010 0000 == (0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0)
011 -> 0001 0000 == (0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0)
100 -> 0000 1000 == (0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0)
101 -> 0000 0100 == (0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0)
110 -> 0000 0010 == (0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0)
111 -> 0000 0001 == (0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0)
This can be intuitively interpreted as:
- if the classic input is
000
, then we are certain that all three bits are 0.Therefore, the probability of all three 0's is 1.0, and all other possible combinations have 0 probability. - if the classic input is
001
, then we are certain that bit one and two are 0, and bit three is 1. The probability of that is 1.0, and all others are zero. - and so on
Now that we finally have our quantum state vector, we just multiply it by the unitary matrix of the quantum circuit, and obtain the dimensional output quantum state vector :
And at long last, the probability of each classical outcome of the measurement is proportional to the square of the length of each entry in the quantum vector, analogously to what is done in the Schrödinger equation.
For example, suppose that the 3 qubit output were:
Then, the probability of each possible outcomes would be the length of each component squared:i.e. 75% for the first, and 25% for the third outcomes, where just like for the input:
- first outcome means
000
: all output bits are zero - third outcome means
010
: the first and third bits are zero, but the second one is 1
All other outcomes have probability 0 and cannot occur, e.g.:
001
is impossible.Keep in mind that the quantum state vector can also contain complex numbers because we are doing quantum mechanics, but we just take their magnitude in that case, e.g. the following quantum state would lead to the same probabilities as the previous one:
This interpretation of the quantum state vector clarifies a few things:
- the input quantum state is just a simple state where we are certain of the value of each classic input bit
- the matrix has to be unitary because the total probability of all possible outcomes must be 1.0This is true for the input matrix, and unitary matrices have the probability of maintaining that property after multiplication.Unitary matrices are a bit analogous to self-adjoint operators in general quantum mechanics (self-adjoint in finite dimensions implies is stronger)This also allows us to understand intuitively why quantum computers may be capable of accelerating certain algorithms exponentially: that is because the quantum computer is able to quickly do an unitary matrix multiplication of a humongous sized matrix.If we are able to encode our algorithm in that matrix multiplication, considering the probabilistic interpretation of the output, then we stand a chance of getting that speedup.
Bibliography:
- arxiv.org/pdf/1804.03719.pdf Quantum Algorithm Implementations for Beginners by Abhijith et al. 2020
This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
Some candidates:
- Shor's algorithm: this one will actually make humanity worse off, as we will be forced into post-quantum cryptography that will likely be less efficient than existing classical cryptography to implement
- quantum algorithm for linear systems of equations, and related application of systems of linear equations
- Grover's algorithm: speedup not exponential. Still useful for anything?
- Quantum Fourier transform: TODO is the speedup exponential or not?
- Deutsch: solves an useless problem
- NISQ algorithms
Do you have proper optimization or quantum chemistry algorithms that will make trillions?
Maybe there is some room for doubt because some applications might be way better in some implementations, but we should at least have a good general idea.
However, clear information on this really hard to come by, not sure why.
Whenever asked e.g. at: physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on Physics Stack Exchange people say the infinite mantra:
Lists:
- Quantum Algorithm Zoo: the leading list as of 2020
- quantum computing computational chemistry algorithms is the area that Ciro and many people are te most excited about is
- cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions
- mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla
Software that maps higher level languages like Qiskit into actual quantum circuits.
It is hard to beat the lists present at: quantumcomputingreport.com (closed source unfortunately, no GitHub) in particular:
- quantumcomputingreport.com/scorecards/qubit-count/ lists what are the latest qubit counts and technologies that each player is using
- quantumcomputingreport.com/players/public-companies/ summarizes what each player has been doing in a few paragraphs
"Quantum interconnect" refers to methods for linking up smaller quantum processors into a larger system.
As of 2024, seemingly few organizations developing quantum hardware had actually integrated multiple chips in interconnects as part of their main current roadmap. But many acknowledged that this would be an essential step towards scalable compuation.
The name "quantum interconnect" is likely partly a throwback to classical computer's "chip interconnect".
Sample usages of the term:
- news.mit.edu/2023/quantum-interconnects-photon-emission-0105
Researchers have demonstrated directional photon emission, the first step toward extensible quantum interconnects
- qpl.ece.ucsb.edu/research/quantum-interconnects
Other good lists:
- quantumcomputingreport.com/resources/tools/ is hard to beat as usual.
- www.quantiki.org/wiki/list-qc-simulators
- JavaScript
- algassert.com/quirk demo: github.com/Strilanc/Quirk drag-and-drop, by a 2019-quantum-computing-Googler, impressive. You can create gates. State store in URL.
- github.com/stewdio/q.js/ demo: quantumjavascript.app/
Bibliography:
- www.epcc.ed.ac.uk/whats-happening/articles/energy-efficient-quantum-computing-simulations mentions two types of quantum computer simulation:
The most common approach to quantum simulations is to store the whole state in memory and to modify it with gates in a given order
However, there is a completely different approach that can sometimes eliminate this issue - tensor networks
In the context of quantum computing of the 2020's, a "classical computer" is a computer that is not "quantum", i.e., the then dominating CMOS computers.
As en.wikipedia.org/w/index.php?title=ZX-calculus&oldid=1071329204#Diagram_rewriting tries to explain but fails to deliver as usual consider the GHZ state represented as a quantum circuit.
How can we easily prove that that quantum circuit equals the state:?
The naive way would be to just do the matrix multiplication as explained at Section "Quantum computing is just matrix multiplication".
However, ZX-calculus provides a simpler way.
And even more importantly, sometimes it is the only way, because in a real circuit, we would not be able to do the matrix multiplication
What we do in ZX-calculus is we first transform the original quantum circuit into a ZX graph.
This is always possible, because we can describe how to do the conversion simply for any of the Clifford plus T gates, which is a set of universal quantum gates.
Then, after we do this transformation, we can start applying further transformations that simplify the circuit.
It has already been proven that there is no efficient algorithm for this (TODO source, someone said P-sharp complete best case)
But it has been proven in 2017 that any possible equivalence between quantum circuits can be reached by modifying ZX-calculus circuits.
There are only 7 transformation rules that we need, and all others can be derived from those, universality.
So, we can apply those rules to do the transformation shown in Wikipedia:
and one of those rules finally tells us that that last graph means our desired state:because it is a Z spider with and .
Bibliography:
- quantumcomputing.stackexchange.com/questions/9774/what-are-some-applications-of-the-zx-calculus
- github.com/zxcalc/book Picturing Quantum Software by Aleks Kissinger and John van de Wetering (2024), CC BY-NC-SA.
One important area of research and development of quantum computing is the development of benchmarks that allow us to compare different quantum computers to decide which one is more powerful than the other.
Ideally, we would like to be able to have a single number that predicts which computer is more powerful than the other for a wide range of algorithms.
However, much like in CPU benchmarking, this is a very complex problem, since different algorithms might perform differently in different architectures, making it very hard to sum up the architecture's capabilities to a single number as we would like.
The only thing that is directly comparable across computers is how two machines perform for a single algorithm, but we want a single number that is representative of many algorithms.
For example, the number of qubits would be a simple naive choice of such performance predictor number. But it is very imprecise, since other factors are also very important:
- qubit error rate
- coherence time, which determines the maximum circuit depth
- qubit connectivity. Can you only connect to 4 neighbouring qubits in a 2D plane? Or to every other qubit equally as well?
Quantum volume is another less naive attempt at such metric.
Encryption algorithms that run on classical computers that are expected to be resistant to quantum computers.
This is notably not the case of the dominant 2020 algorithms, RSA and elliptic curve cryptography, which are provably broken by Grover's algorithm.
However, as of 2020, we don't have any proof that any symmetric or public key algorithm is quantum resistant.
Post-quantum cryptography is the very first quantum computing thing at which people have to put money into.
The reason is that attackers would be able to store captured ciphertext, and then retroactively break them once and if quantum computing power becomes available in the future.
There isn't a shade of a doubt that intelligence agencies are actively doing this as of 2020. They must have a database of how interesting a given source is, and then store as much as they can given some ammount of storage budget they have available.
A good way to explain this to quantum computing skeptics is to ask them:Post-quantum cryptography is simply not a choice. It must be done now. Even if the risk is low, the cost would be way too great.
If I told you there is a 5% chance that I will be able to decrypt everything you write online starting today in 10 years. Would you give me a dollar to reduce that chance to 0.5%?