Ciro Santilli $$Sponsor Ciro$$ 中国独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件 邓家贵、低端人口、西藏骚乱

# Quantum computing

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.

## Programmer's model of quantum computers (How to program a quantum computer, Quantum computing is just matrix multiplication)

split words: 1k
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.
Although there are several types of quantum computer under development, there exists a single high level model that represents what any of those computers can do, and we are going to explain that model here.
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:
• logic gates like AND, NOR and NOT
• a clock + registers
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.
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:
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: 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 : $$qin​​∈C2n (1)$$
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 : $$qout​​=Qqin​​ (2)$$
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: $$qout​​​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​23​​0.021​0.00.00.00.00.0​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​​ (3)$$
Then, the probability of the first and third possible outcomes would be the length of each component squared: $$∣∣∣∣∣∣​23​​∣∣∣∣∣∣​2∣∣∣∣∣​21​2∣∣∣∣∣​2​=23​​2=21​2​=43​=41​​ (4)$$ 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: $$∣∣∣∣∣∣​21+2​i​∣∣∣∣∣∣​2∣∣∣∣∣​2i​∣∣∣∣∣​2​=2212+22​​=2212​​=43​=41​​ (5)$$
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 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.
Consider reading the following next:
• Section "Quantum logic gate" shows an alternative, and extremely important view of a quantum computer besides a matrix multiplication: as a circuit. Fundamental subsections:
Bibliography:

## Quantum algorithm

split words: 315
This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
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:
• Grover: speedup not exponential
• Deutsch: solves an useless problem
• Shor: cryptography is boring, do you have proper optimization or quantum chemistry algorithms that will make trillions?
• Quantum Fourier transform: TODO is the speedup exponential or not?
Ciro Santilli wonders if there is any understandable algorithm that meets the above criteria.

split words: 7

### Quantum Algorithm Zoo

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

### List of quantum algorithms

split words: 150

#### Bernstein-Vazirani algorithm

split words: 3
Toy/test/tought experiment algorithm.

#### Schor's algorithm (1994)

split words: 147
##### Integer factorization algorithms better than Schor's algorithm
split words: 144
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

split words: 202
Software that maps higher level languages like Qiskit into actual quantum circuits.

### Quantum Intermediate Representation (QIR)

split words: 29
Used e.g. by Oxford Quantum Circuits, www.linkedin.com/in/john-dumbell-627454121/ mentions:
Using LLVM to consume QIR and run optimization, scheduling and then outputting hardware-specific instructions.
Presumably the point of it is to allow simulation in classical computers?

### Quantum error correction

split words: 162
Technique that uses multiple non-ideal qubits (physical qubits) to simulate/produce one perfect qubit (logical).
One is philosophically reminded of classical error correction codes, 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 quantum threshold theorem.
For example, when 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.

#### Quantum threshold theorem

split words: 60
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.
##### Noisy intermediate-scale quantum era (NISQ)
split words: 17
Era of quantum computing before we reach physical errors small enough to do perfect quantum error correction as demonstrated by the quantum threshold theorem.

## Quantum computing player

split words: 231
It is hard to beat the lists present at: quantumcomputingreport.com (closed source unfortunately, no GitHub) in particular:

split words: 162

### Quantum computing research institute

split words: 5

#### QuTech

split words: 5
split words: 5
The educational/outreach branch of QuTech.

split words: 1

split words: 1

### Organization developing quantum software

split words: 19

#### Quantum Computing Inc.

split words: 19
Publicly traded in 2007, but only pivoted to quantum computing much later.

## Quantum computing hardware

split words: 3k

### Step of operation of a quantum computer

split words: 18

#### Readout (quantum computing)

split words: 18
Lists of the most promising implementations:
As of 2020, the hottest by far are:

### Quantum computers as experiments that are hard to predict outcomes

split words: 189
One possibly interesting and possibly obvious point of view, is that a quantum computer is an experimental device that executes a quantum probabilistic experiment for which the probabilities cannot be calculated theoretically efficiently by a nuclear weapon.
This is how quantum computing was originally theorized by the likes of Richard Feynman: they noticed that "Hey, here's a well formulated quantum mechanics problem, which I know the algorithm to solve (calculate the probability of outcomes), but it would take exponential time on the problem size".
The converse is then of course that if you were able to encode useful problems in such an experiment, then you have a computer that allows for exponential speedups.
This can be seen very directly by studying one specific quantum computer implementation. E.g. if you take the simplest to understand one, photonic quantum computer, you can make systems for which you need exponential time to calculate the probabilities that photons will exit through certain holes and not others.
The obvious aspect of this idea is by coming from quantum logic gates are needed because you can't compute the matrix explicitly as it grows exponentially: knowing the full explicit matrix is impossible in practice, and knowing the matrix is equivalent to knowing the probabilities of every outcome.

### Quantum computing is hard because we want long coherence but fast control

split words: 29
Mentioned e.g. at:
These are two conflicting constraints:
• long coherence times: require isolation from external world, otherwise observation destroys quantum state
• fast control and readout: require coupling with external world

### Quantum computer type

split words: 3k

#### Analog and digital quantum computers

split words: 157
##### Digital quantum computer (Gate based quantum computer)
split words: 28
As of 2022, this tends to be the more "default" when you talk about a quantum computer.
But there are some serious analog quantum computer contestants in the field as well.
split words: 129

#### Diamond vacancy quantum computer

split words: 10
5 Companies Working With Diamond NV Quantum Computing Technology.

split words: 14
split words: 5
split words: 5
split words: 9

#### Superconducting quantum computer

split words: 969
Based on the Josephson effect. Yet another application of that phenomenal idea!
It is fun to see that the representation of information in the QC basically uses an LC circuit, which is a very classical resonator circuit.
As mentioned at en.wikipedia.org/wiki/Superconducting_quantum_computing#Qubit_archetypes there are actually a few different types of superconducting qubits:
• flux
• charge
• phase
and hybridizations of those such as:
Input:
• microwave radiation to excite circuit, or do nothing and wait for it to fall to 0 spontaneously
• interaction: TODO
##### Superconducting quantum computer need non-linear components
split words: 66
Non-linearity is needed otherwise the input energy would just make the state go to higher and higher energy levels, e.g. from 1 to 2. But we only want to use levels 0 and 1.
The way this is modelled in by starting from a pure LC circuit, which is an harmonic oscillator, see also quantum LC circuit, and then replacing the linear inductor with a SQUID device, e.g. mentioned at: youtu.be/eZJjQGu85Ps?t=1655 Video 8. "Superconducting Qubits I by Zlatko Minev (2020)".
##### Superconducting qubit
split words: 125
split words: 110
split words: 82
###### Superconducting qubits are bad because it is harder to ensure that they are all the same
split words: 18
This is unlike atomic systems like trapped ion quantum computers, where each atom is necessarily exactly the same as the other.
split words: 28
###### Superconducting qubits are good because superconductivity is macroscopic
split words: 28
Superconducting qubits are regarded as promising because superconductivity is a macroscopic quantum phenomena of Bose Einstein condensation, and so as a macroscopic phenomena, it is easier to control and observe.
split words: 15
###### Transmon
split words: 15
Used e.g. in the Sycamore processor.
##### Organization developing superconducting quantum computer
split words: 419
###### Alice&Bob
split words: 27
Funding rounds:
• March 2022: 27M Euros
###### Google Quantum AI
split words: 172
Google's quantum hardware/software effort.
The AI is just prerequisite buzzword of the era for any project.
According to job postings such as: archive.ph/wip/Fdgsv their center is in Goleta, California, near Santa Barbara. Though Google tends to promote it more as Santa Barbara, see e.g. Daniel's t-shirt at Video 6. "Building a quantum computer with superconducting qubits by Daniel Sank (2019)".
###### Daniel Sank
split words: 35
Started at Google Quantum AI in 2014.
Has his LaTeX notes at: github.com/DanielSank/theory. One day he will convert to OurBigBook.com. Interesting to see that he is able to continue his notes despite being at Google.
###### Sycamore processor
split words: 73
This is a good read: quantumai.google/hardware/datasheet/weber.pdf May 14, 2021. Their topology is so weird, not just a rectangle, one wonders why! You get different error rates in different qubits, it's mad.
###### IBM Quantum Computing (IBM Q)
split words: 36
The term "IBM Q" has been used in some promotional material as of 2020, e.g.: www.ibm.com/mysupport/s/topic/0TO50000000227pGAA/ibm-q-quantum-computing?language=en_US though the fuller form "IBM Quantum Computing" is somewhat more widely used.
They also internally named an division as "IBM Q": sg.news.yahoo.com/ibm-thinks-ready-turn-quantum-050100574.html
###### OpenSuperQ
split words: 13
Open source superconducting quantum computer hardware design!
###### Oxford Quantum Circuits (2017, OQC)
split words: 126
Their main innovation seems to be their 3D design which they call "Coaxmon".
###### Ilana Wisby
split words: 96
Founding CEO of Oxford Quantum Circuits.
As mentioned at www.investmentmonitor.ai/tech/innovation/in-conversation-with-oxford-quantum-circuits-ilana-wisby she is not the original tech person:
she was finally headhunted by Oxford Science and Innovation to become the founding CEO of OQC. The company was spun out of Oxford University's physics department in 2017, at which point Wisby was handed "a laptop and a patent".
Did they mean Oxford Sciences Enterprises? There's nothing called "Oxford Science and Innovation" on Google. Yes, it is just a typo oxfordscienceenterprises.com/news/meet-the-founder-ilana-wisby-ceo-of-oxford-quantum-circuits/ says it clearly:
I was headhunted by Oxford Sciences Enterprises to be the founding CEO of OQC.
oxfordquantumcircuits.com/story mentions that the core patent was by Dr. Peter Leek: www.linkedin.com/in/peter-leek-00954b62/
split words: 45

#### Trapped ion quantum computer

split words: 2k
TODO understand.
##### Modular trapped ion quantum computer
split words: 55
Trapped ion people acknowledge that they can't put a million qubits in on chip (TODO why) so they are already thinking of ways to entangle separate chips. Thinking is maybe the key word here. One of the propoesd approaches inolves optical links. Universal Quantum for example explicitly rejects that idea in favor of electric field link modularity.
##### Organization developing trapped ion quantum computer
split words: 1k
split words: 497
split words: 28
###### Oxford Ionics (2017, OQC)
split words: 21
This job announcement from 2022 gives a good idea about their tech stack: web.archive.org/web/20220920114810/https://oxfordionics.bamboohr.com/jobs/view.php?id=32&source=aWQ9MTA%3D. Notably, they use ARTIQ.
###### Quantinuum
split words: 58
Merger between Cambridge Quantum Computing, which does quantum software, and Honeywell Quantum Solutions, which does the hardware.
split words: 3
split words: 3
###### Cambridge Quantum Computing
split words: 43
In 2015, they got a 50 million investment from Grupo Arcano, led by Alberto Chang-Rajii, who is a really shady character who fled from justice for 2 years:
Merged into Quantinuum later on in 2021.
###### tket
split words: 5
TODO vs all the others?
###### Universal Quantum
split words: 546
As of 2021, their location is a small business park in Haywards Heath, about 15 minutes north of Brighton[ref]
Funding rounds:
Co-founders:
Homepage says only needs cooling to 70 K. So it doesn't work with liquid nitrogen which is 77 K?
Homepage points to foundational paper: www.science.org/doi/10.1126/sciadv.1601540

#### Neutral atom quantum computer

split words: 24
##### Organization developing neutral atom quantum computer
split words: 24
###### Atom Computing
split words: 21
These people are cool.
They use optical tweezers to place individual atoms floating in midair, and then do stuff to entangle their nuclear spins.
split words: 3

#### Photonic quantum computer (Linear optical quantum computing)

split words: 392
Uses photons!
The key experiment/phenomena that sets the basis for photonic quantum computing is the two photon interference experiment.
The physical representation of the information encoding is very easy to understand:
• input: we choose to put or not photons into certain wires or no
• interaction: two wires pass very nearby at some point, and photons travelling on either of them can jump to the other one and interact with the other photons
• output: the probabilities that photos photons will go out through one wire or another
##### Organization developing photonic quantum computer
split words: 263
split words: 9
###### PsiQuantum
split words: 228
Good talk by CEO before starting the company which gives insight on what they are very likely doing: Video 24. "Jeremy O'Brien: "Quantum Technologies" by GoogleTechTalks (2014)"
PsiQuantum appears to be particularly secretive, even more than other startups in the field.
They want to reuse classical semiconductor fabrication technologies, notably they have close ties to GlobalFoundries.
So he went to the US and raised N times more from the American military-industrial complex.
###### PsiQuantum founding myth
split words: 162
Once upon a time, the British Government decided to invest some 80 million into quantum computing.
Jeremy O'Brien told his peers that he had the best tech, and that he should get it all.
Some well connected peers from well known universities did not agree however, and also bid for the money, and won.
Jeremy was defeated. And pissed.
So he moved to Palo Alto and raised a total of \$665 million instead as of 2021. The end.
Makes for a reasonable the old man lost his horse.
www.ft.com/content/afc27836-9383-11e9-aea1-2b1d33ac3271 British quantum computing experts leave for Silicon Valley talks a little bit about them leaving, but nothing too juicy. They were called PsiQ previously apparently.
The departure of some of the UK’s leading experts in a potentially revolutionary new field of technology will raise fresh concerns over the country’s ability to develop industrial champions in the sector.
More interestingly, the article mentions that this was party advised by early investor Hermann Hauser, who is known to be preoccupied about UK's ability to create companies. Of course, European Tower of Babel.
###### Xanadu Quantum Technologies
split words: 26
www.youtube.com/watch?v=v7iAqcFCTQQ shows their base technology:

## Superconducting quantum computing

split words: 3
Dominant 2019 method.

## Quantum computer simulator

split words: 81
Krizhevsky et al., which won the ImageNet
Bibliography:
*
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

## Quantum software

split words: 157

### Quantum programming framework

split words: 9

#### Qiskit

split words: 9
Python library, claims multiple backends, including simulation a real IBM quantum computer.

### Quantum control system

split words: 148
Some people call it "operating System".
The main parts of those systems are:
• sending multiple signals at very precise times to the system
• reading out some quantum error correction bits and sending error correcting signals back in a control loop

#### Quantum control systems use FPGAs

split words: 39
It seems that all/almost all of them do. Quite cool.

#### Organization developing quantum control systems

split words: 72
##### Riverlane (2017)
split words: 72
When you fail a HR interview, then you know you've reached rock bottom.
###### Deltaflow.OS
split words: 16
A "quantum computer operating system".
uknqt.ukri.org/wp-content/uploads/2021/10/UKNQTP-Strategic-Intent-2020.pdf page 24 mentions UKNQTP investment and gives an overview of some layers.

## Classical computer

split words: 21
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.

## ZX-calculus

split words: 249
How can we easily prove that that quantum circuit equals the state: $$2​∣000>+∣111>​ (7)$$ ?
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: $$2​∣000>+∣111>​ (8)$$ because it is a Z spider with and .

## Quantum logic gate

split words: 1k
At Section "Quantum computing is just matrix multiplication" we saw that making a quantum circuit actually comes down to designing one big unitary matrix.
We have to say though that that was a bit of a lie.
Quantum programmers normally don't just produce those big matrices manually from scratch.
Instead, they use quantum logic gates.

### Quantum logic gates are needed because you can't compute the matrix explicitly as it grows exponentially

split words: 386
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 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 outputs for each of the 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 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:
000 -> 1000 0000 == (1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
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.

### Quantum logic gates are needed for physical implementation

split words: 376
One direct practical reason is that we need to map the matrix to real quantum hardware somehow, and all quantum hardware designs so far and likely in the future are gate-based: you manipulate a small number of qubits at a time (2) and add more and more of such operations.
While there are "quantum compilers" to increase the portability of quantum programs, it is to be expected that programs manually crafted for a specific hardware will be more efficient just like in classic computers.
TODO: is there any clear reason why computers can't beat humans in approximating any unitary matrix with a gate set?
This is analogous to what classic circuit programmers will do, by using smaller logic gates to create complex circuits, rather than directly creating one huge truth table.
The most commonly considered quantum gates take 1, 2, or 3 qubits as input.
The gates themselves are just unitary matrices that operate on the input qubits and produce the same number of output qubits.
For example, the matrix for the CNOT gate, which takes 2 qubits as input is:
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
The final question is then: if I have a 2 qubit gate but an input with more qubits, say 3 qubits, then what does the 2 qubit gate (4x4 matrix) do for the final big 3 qubit matrix (8x8)? In order words, how do we scale quantum gates up to match the total number of qubits?
The intuitive answer is simple: we "just" extend the small matrix with a larger identity matrix so that the sum of the probabilities third bit is unaffected.
More precisely, we likely have to extend the matrix in a way such that the partial measurement of the original small gate qubits leaves all other qubits unaffected.
For example, if the circuit were made up of a CNOT gate operating on the first and second qubits as in:
0 ----+----- 0
|
1 ---CNOT--- 1

2 ---------- 2
then we would just extend the 2x2 CNOT gate to:
TODO lazy to properly learn right now. Apparently you have to use the Kronecker product by the identity matrix. Also, zX-calculus appears to provide a powerful alternative method in some/all cases.

### Quantum circuits vs classical circuits

split words: 240
Just like a classic programmer does not need to understand the intricacies of how transistors are implemented and CMOS semiconductors, the quantum programmer does not understand physical intricacies of the underlying physical implementation.
The main difference to keep in mind is that quantum computers cannot save and observe intermediate quantum state, so programming a quantum computer is basically like programming a combinatorial-like circuit with gates that operate on (qu)bits:
For this reason programming a quantum computer is much like programming a classical combinatorial circuit as you would do with SPICE, verilog-or-vhdl, in which you are basically describing a graph of gates that goes from the input to the output
For this reason, we can use the words "program" and "circuit" interchangeably to refer to a quantum program
Also remember that and there is no no clocks in combinatorial circuits because there are no registers to drive; and so there is no analogue of clock in the quantum system either,
Another consequence of this is that programming quantum computers does not look like programming the more "common" procedural programming languages such as C or Python, since those fundamentally rely on processor register / memory state all the time.
Quantum programmers can however use classic languages to help describe their quantum programs more easily, for example this is what happens in Qiskit, where you write a Python program that makes Qiskit library calls that describe the quantum program.

### Universal quantum gates

split words: 117
Just like as for classic gates, we would like to be able to select quantum computer physical implementations that can represent one or a few gates that can be used to create any quantum circuit.
Unfortunately, in the case of quantum circuits this is obviously impossible, since the space of N x N unitary matrices is infinite and continuous.
Therefore, when we say that certain gates form a "set of universal quantum gates", we actually mean that "any unitary matrix can be approximated to arbitrary precision with enough of these gates".
Or if you like fancy Mathy words, you can say that the subgroup of the unitary group generated by our basic gate set is a dense subset of the unitary group.

### Clifford gates

split words: 89
This gate set alone is not a set of universal quantum gates.
Notably, circuits containing those gates alone can be fully simulated by classical computers according to the Gottesman-Knill theorem, so there's no way they could be universal.
This means that if we add any number of Clifford gates to a quantum circuit, we haven't really increased the complexity of the algorithm, which can be useful as a transformational device.
A popular set of universal quantum gates derived from Clifford gates is Clifford plus T.

#### Clifford plus T

split words: 14
Set of quantum logic gate composed of the Clifford gates plus the Toffoli gate. It forms a set of universal quantum gates.

split words: 3

## Quantum supremacy (2019)

split words: 36

split words: 36
Similar to quantum supremacy, but add the goal that the computation must be useful, i.e. make money or solve some open mathematical problem, Ciro Santilli's wife was quite excited about the possibility of finding some counter examples in number theory with quantum computers.

## Qubit

split words: 36

### Continuous-variable quantum information

split words: 36
It is also possible to carry out quantum computing without qubits using processes with a continuous spectrum of measurement.
As of 2020, these approaches seem less developed/promising, but who knows.
These computers can be seen as analogous to classical non-quantum analog computers.

## Quantum computer benchmark

split words: 217
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.

### Coherence time

split words: 21
It takes time for the quantum state to evolve. So in order to have a deep quantum circuit, we need longer coherence times.

## Post-quantum cryptography (PQC)

split words: 355
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.
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:
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%?
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.

### Post-quantum cryptography company

split words: 29

#### PQShield (2018)

split words: 29
They seem to be doing hardware acceleration for post-quantum cryptography algorithm.
One has to feel bad for them as they likely threw out entire chip designs over NIST Post-Quantum Cryptography Standardization algorithm breakeges.

### NIST Post-Quantum Cryptography Standardization (2017-)

split words: 111
This post-quantum cryptography competition by NIST is a huge milestone of the field.
It was mind blowing when in 2022, after several years of selection, one of the 7 finalists was broken on a classical computer, not even in a quantum computer! news.ycombinator.com/item?id=30466063 | eprint.iacr.org/2022/214 Breaking Rainbow Takes a Weekend on a Laptop by Ward Beullens. Dude announced he had a break a few days before submission: twitter.com/WardBeullens/status/1492780462028300290 On Twitter. He's so young. Epic.
Edit: and then, after the third round, things were a bit unclear, so they made a fourth round with 4 choices out of the 7 from round 3, and in August 2022 one of the four was broken again on a classic CPU!!! OMG: arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/

### Provably quantum secure encryption algorithm

split words: 5
None known as of 2020.

## Quantum computing bibliography

split words: 2

### Quantum computing news

split words: 2

#### The Quantum Insider (thequantuminsider.com)

split words: 2
Good publication.