= Quantum computing
{tag=Computer physical principle of operation}
{wiki}
= Quantum computer
{synonym}
= Quantum computation
{synonym}
Quantum is getting hot in 2019, and even got a bit excited: .
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 for hardware that doesn't/barely exists! https://quantumcomputingreport.com/players/privatestartup (https://web.archive.org/web/20191223175204/https://quantumcomputingreport.com/players/privatestartup/[archive]). Some feared we might be in a bubble:
To get a basic idea of what programming a quantum computer looks like start by reading: {full}.
Some people [have their doubts], and that is not unreasonable, it might truly not work out. We could be on the verge of an of quantum computing. But 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 .
= Introduction to quantum computing
{parent=Quantum computing}
Course plan:
* {full}
* look at a
* e.g. ours: {file}
* learn about .
*
* First we learn some . This shows an alternative, and extremely important view of a quantum computer besides a matrix multiplication: as a circuit. Fundamental subsections:
* {full}
* {full}
* {full}
* {full}
* Examples of specific gates:
* :
*
*
*
*
*
*
*
*
* {full}
* {full}
= Programmer's model of quantum computers
{parent=Quantum computing}
= How to program a quantum computer
{synonym}
{title2}
= Quantum computing is just matrix multiplication
{synonym}
{title2}
This is a quick tutorial on how a programmer thinks about how a quantum computer works. If you know:
* what a is
* how to do
* what is a
a concrete and precise operation can be understood in 30 minutes.
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 model, which uses a , that is made up of many .
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. ) 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: https://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 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 , 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:
* like AND, NOR and NOT
* a clock + registers
as modelled at the , 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.
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 $2^n \times 2^n$ of $Q \in \C^{2^n} \times \C^{2^n}$ 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 :
* set the input to classic input bits ()
* press a big red "RUN" button
* read the classic output bits ()
Each time you do this, you are literally conducting a physical experiment of the specific [physical implementation] of the computer:
* setup your physical system to represent the classical 0/1 inputs
* let the state evolve for long enough
* measure the classical output back out
and each run as the above can is simply called "an experiment" or "a measurement".
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: . 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 !
This is because the probabilities of each output for a given input depends on the program () 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 "" $\va{q_{in}}$ of dimension $2^n$:
$$
\va{q_{in}} \in \C^{2^n}
$$
We are after all going to multiply it by the program matrix, as you would expect, and that has dimension $2^n \times 2^n$!
Note that this initial transformation also transforms the discrete zeroes and ones into .
For example, in a 3 qubit computer, the quantum state vector has dimension $2^3 = 8$ 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 $Q$ of the quantum circuit, and obtain the $2^n$ dimensional output quantum state vector $\va{q_{out}}$:
$$
\va{q_{out}} = Q \: \va{q_{in}}
$$
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 .
For example, suppose that the 3 qubit output were:
$$
\begin{aligned}
\va{q_{out}} &=
\begin{bmatrix}
\frac{\sqrt{3}}{2} \\
0.0 \\
\frac{1}{2} \\
0.0 \\
0.0 \\
0.0 \\
0.0 \\
0.0
\end{bmatrix}
\end{aligned}
$$
Then, the probability of each possible outcomes would be the length of each component squared:
$$
\begin{aligned}
P(000) &= \left|\frac{\sqrt{3}}{2}\right|^2 &= \frac{\sqrt{3}}{2}^2 &= \frac{3}{4} \\
P(001) &= \left|0\right|^2 &= 0^2 &= 0 \\
P(010) &= \left|\frac{\sqrt{1}}{2}\right|^2 &= \frac{\sqrt{1}}{2}^2 &= \frac{1}{4} \\
P(011) &= \left|0\right|^2 &= 0^2 &= 0 \\
P(100) &= \left|0\right|^2 &= 0^2 &= 0 \\
P(101) &= \left|0\right|^2 &= 0^2 &= 0 \\
P(110) &= \left|0\right|^2 &= 0^2 &= 0 \\
P(111) &= \left|0\right|^2 &= 0^2 &= 0 \\
\end{aligned}
$$
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 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:
$$
\begin{aligned}
\abs{\frac{1 + \sqrt{2}i}{2}}^2 &= \frac{1^2 + \sqrt{2^2}}{2^2} &= \frac{3}{4} \\
\abs{\frac{i}{2}}^2 &= \frac{1^2}{2^2} &= \frac{1}{4}
\end{aligned}
$$
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.0
This 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 https://en.wikipedia.org/wiki/Self-adjoint_operator[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 $2^{N}$ 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:
* https://arxiv.org/pdf/1804.03719.pdf Quantum Algorithm Implementations for Beginners by Abhijith et al. 2020
= Timeline of quantum computing
{parent=Quantum computing}
{wiki}
= Quantum algorithm
{parent=Quantum computing}
{wiki}
This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
Some candidates:
* : this one will actually make humanity worse off, as we will be forced into that will likely be less efficient than existing classical to implement
* , and related
* : speedup not exponential. Still useful for anything?
* https://en.wikipedia.org/wiki/Quantum_Fourier_transform[Quantum Fourier transform]: TODO is the speedup exponential or not?
* Deutsch: solves an useless problem
*
Do you have proper optimization or 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: https://physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on people say the infinite mantra:
Lists:
* : the leading list as of 2020
* is the area that Ciro and many people are te most excited about is
* https://cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions
* https://mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla
= Quantum computers are not expected to solve NP-complete problems
{parent=Quantum algorithm}
Only , which includes notably :
* https://quantumcomputing.stackexchange.com/questions/16506/can-quantum-computer-solve-np-complete-problems
* https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf by
* https://cs.stackexchange.com/questions/130470/can-quantum-computing-help-solve-np-complete-problems
* https://www.quora.com/How-can-quantum-computing-help-to-solve-NP-hard-problems
= Quantum Algorithm Zoo
{c}
{parent=Quantum algorithm}
https://quantumalgorithmzoo.org/
Source on : https://github.com/stephenjordan/stephenjordan.github.io
The most comprehensive list is the amazing curated and commented list of as of 2020.
= Quantum algorithm vs quantum gate vs quantum circuit
{parent=Quantum algorithm}
There is no fundamental difference between them, a is a , which can be seen as a super complicated .
Perhaps the greats practical difference is that algorithms tend to be defined for an arbitrary number of N qubits, i.e. as a for that each N produces a specific with N solving the problem. Most named gates on the other hand have fixed small sizes.
= Quantum algorithm by problem
{parent=Quantum algorithm}
= Quantum matrix multiplication
{parent=Quantum algorithm by problem}
https://cstheory.stackexchange.com/questions/2951/quantum-matrix-multiplication
= Quantum algorithm for linear systems of equations
{parent=Quantum algorithm by problem}
{tag=System of linear equations algorithm}
= HHL algorithm
{c}
{parent=Quantum algorithm for linear systems of equations}
= List of quantum algorithms
{parent=Quantum algorithm}
= Bernstein-Vazirani algorithm
{c}
{parent=List of quantum algorithms}
{wiki=Bernstein–Vazirani algorithm}
Toy/test/tought experiment algorithm.
= Grover's algorithm
{c}
{parent=List of quantum algorithms}
{wiki}
= Hiden shift algorithm
{parent=List of quantum algorithms}
= Hidden shift problem
{parent=Hiden shift algorithm}
{wiki}
= Quantum Fourier transform
{c}
{parent=List of quantum algorithms}
{tag=Discrete Fourier transform}
{title2=QFT}
{wiki}
Sample implementations:
* : {file}
= Shor's algorithm
{c}
{parent=List of quantum algorithms}
{tag=Integer factorization algorithm}
{title2=1994}
{wiki}
\Video[https://www.youtube.com/watch?v=lvTqbM5Dq4Q]
{title= Explained by (2019)}
= How many logical qubits are needed to run Shor's algorithm?
{parent=Shor's algorithm}
https://quantumcomputing.stackexchange.com/questions/5048/how-many-logical-qubits-are-needed-to-run-shors-algorithm-efficiently-on-large
= Integer factorization algorithms better than Shor's algorithm
{parent=Shor's algorithm}
* 2023 https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html comments on "Factoring integers with sublinear resources on a superconducting quantum processor” https://arxiv.org/pdf/2212.12372.pdf
\Q[
A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.
We have long known from Shor’s algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what’s possible today. (The IBM Osprey is a 433-qbit quantum computer, for example. Others are on their way as well.)
]
= Quantum compilation
{parent=Quantum computing}
{wiki}
= Quantum compiler
{synonym}
Software that maps higher level languages like into actual quantum circuits.
= Quantum compiler benchmark
{parent=Quantum compilation}
These appear to be benchmarks that don't involve running anything concretely, just compiling and likely then counting [gates]:
* https://github.com/ArlineQ/arline_benchmarks
= Quantum Intermediate Representation
{parent=Quantum compilation}
{tag=LLVM Intermediate Representation}
{title2=QIR}
https://devblogs.microsoft.com/qsharp/introducing-quantum-intermediate-representation-qir/
Used e.g. by , https://www.linkedin.com/in/john-dumbell-627454121/ mentions:
\Q[Using to consume QIR and run optimization, scheduling and then outputting hardware-specific instructions.]
Presumably the point of it is to allow simulation in ?
= Quantum error correction
{parent=Quantum compilation}
{wiki}
Technique that uses multiple non- qubits (physical qubits) to simulate/produce one perfect qubit (logical).
One is philosophically reminded of classical , where we also have multiple input bits per actual information bit.
TODO understand in detail. This appears to be a fundamental technique since all physical systems we can manufacture are imperfect.
Part of the fundamental interest of this technique is due to the .
For example, when https://www.bloomberg.com/news/articles/2020-04-06/quantum-computing-startup-raises-215-million-for-faster-device[PsiQuantum raised 215M in 2020], they announced that they intended to reach 1 million physical qubits, which would achieve between 100 and 300 logical qubits.