Quantum computer type

Table of contents
- Model of quantum computing
  - Measurement and circuit based quantum computers Model of quantum computing
    - Circuit-based quantum computer Measurement and circuit based quantum computers
    - Measurement-based quantum computer Measurement and circuit based quantum computers
  - Analog and digital quantum computers Model of quantum computing
    - Digital quantum computer Analog and digital quantum computers
      - Quantum circuit Digital quantum computer
        Quantum state vector Quantum circuit
        Tensor product in quantum computing Quantum circuit
        Quantum circuits vs classical circuits Quantum circuit
      - Quantum logic gate Digital quantum computer
        Quantum logic gates are needed because you can't compute the matrix explicitly as it grows exponentially Quantum logic gate
        Quantum logic gates are needed for physical implementation Quantum logic gate
        Universal quantum gates Quantum logic gate
        Single-qubit gate Quantum logic gate
        Hadamard gate Single-qubit gate
        Pauli gate Single-qubit gate
        Pauli-X gate Single-qubit gate
        Phase shift gate Single-qubit gate
        Multi-qubit gate Single-qubit gate
        Controlled quantum gate Multi-qubit gate
        Empty circle control qubit notation Controlled quantum gate
        CNOT gate Controlled quantum gate
        Toffoli gate Multi-qubit gate
        Clifford gates Quantum logic gate
        Clifford plus T Clifford gates
        Gottesman-Knill theorem Clifford gates
        List of quantum logic gates Quantum logic gate
    - Analog quantum computer Analog and digital quantum computers
      - Continuous-variable quantum information Analog quantum computer

Measurement and circuit based quantum computers

Circuit-based quantum computer

Synonym to gate-based quantum computer/digital quantum computer?

Measurement-based quantum computer (One-way quantum computer)

TODO confirm: apparently in the paradigm you can choose to measure only certain output qubits.

This makes things irreversible (TODO what does reversibility mean in this random context?), as opposed to Circuit-based quantum computer where you measure all output qubits at once.

TODO what is the advantage?

Analog and digital quantum computers

Digital quantum computer (Gate-based quantum computer)

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.

Quantum circuit

A quantum circuit is a graph of quantum logic gates.

Quantum circuits are the prevailing model of quantum computing as of the 2010's - 2020's

Tensor product in quantum computing

We don't need to understand a super generalized version of tensor products to know what they mean in basic quantum computing!

Intuitively, taking a tensor product of two qubits simply means putting them together on the same quantum system/computer.

When we write the bra-ket notation:

∣ 00 ⟩

that is the same as

∣ 0 ⟩ \otimes ∣ 0 ⟩

The tensor product is called a "product" because it distributes over addition.

E.g. consider:

(\frac{∣ 0 ⟩ + ∣ 1 ⟩}{2}) \otimes ∣ 0 ⟩ = \frac{∣ 0 ⟩ \otimes ∣ 0 ⟩ + ∣ 1 ⟩ \otimes ∣ 0 ⟩}{2} = \frac{∣ 0 0 ⟩ + ∣ 1 0 ⟩}{2}

(1)

Intuitively, in this operation we just put a Hadamard gate qubit together with a second pure

∣ 0 ⟩

qubit.

And the outcome still has the second qubit as always 0, because we haven't made them interact.

The quantum state

\frac{∣ 0 0 ⟩ + ∣ 1 0 ⟩}{2}

is called a separable state, because it can be written as a single product of two different qubits. We have simply brought two qubits together, without making them interact.

If we then add a CNOT gate to make a Bell state:

\frac{∣ 0 0 ⟩ + ∣ 1 1 ⟩}{2} = \frac{∣ 0 ⟩ \otimes ∣ 0 ⟩ + ∣ 1 ⟩ \otimes ∣ 1 ⟩}{2}

(2)

we can now see that the Bell state is non-separable: we've made the two qubits interact, and there is no way to write this state with a single tensor product. The qubits are fundamentally entangled.

Quantum circuits vs classical circuits

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.

Quantum logic gate

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.

The following are the main reasons for that:

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

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:

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

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:

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.

Bibliography:

quantumcomputing.stackexchange.com/questions/2299/how-to-interpret-a-quantum-circuit-as-a-matrix

Universal quantum gates

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.

Single-qubit gate

The first two that you should study are:

Hadamard gate

The Hadamard gate takes

∣ 0 ⟩

∣ 1 ⟩

(quantum states with probability 1.0 of measuring either 0 or 1), and produces states that have equal probability of 0 or 1.

H = \frac{1}{2} [11 1 - 1]

(1)

Equation 1. Hadamard gate matrix.

Pauli gate

Pauli-X gate (Quantum NOT gate)

The quantum NOT gate swaps the state of

∣ 0 ⟩

and

∣ 1 ⟩

, i.e. it maps:

x ∣ 0 ⟩ + y ∣ y ⟩ \to y ∣ 0 ⟩ + x ∣ y ⟩

(1)

As a result, this gate also inverts the probability of measuring 0 or 1, e.g.

if the old probability of 0 was 0, then it becomes 1
if the old probability of 0 was 0.2, then it becomes 0.8

[0110]

(2)

Equation 2. Quantum NOT gate matrix.

Figure 1. Quantum NOT gate symbol. Source.

Phase shift gate

Multi-qubit gate

The most common way to construct multi-qubit gates is to use single-qubit gates as part of a controlled quantum gate.

Controlled quantum gate

Controlled quantum gates are gates that have two types of input qubits:

control qubits
operand qubits (terminology made up by Ciro Santilli just now)

These gates can be understood as doing a certain unitary operation only if the control qubits are enabled or disabled.

The first example to look at is the CNOT gate.

Figure 1. Generic controlled quantum gate symbol. Source.
The black dot means "control qubit", and "U" means an arbitrary Unitary operation.
When the operand has a conventional symbol, e.g. the Figure "Quantum NOT gate symbol" for the quantum NOT gate to form the CNOT gate, that symbol is used in the operand instead.

Empty circle control qubit notation

Some authors use the convention of:

filled black circle: conventional controlled quantum gate, i.e. operate if control qubit is active
empty (White) circle: operarate if control qubit is inactive

CNOT gate (Controlled NOT gate)

The CNOT gate is a controlled quantum gate that operates on two qubits, flipping the second (operand) qubit if the first (control) qubit is set.

This gate is the first example of a controlled quantum gate that you should study.

⎣ ⎢ ⎢ ⎢ ⎡ 1000010000010010 ⎦ ⎥ ⎥ ⎥ ⎤

(1)

Equation 1. CNOT gate matrix.

Figure 1. CNOT gate symbol. Source. The symbol follow the generic symbol convention for controlled quantum gates shown at Figure "Generic controlled quantum gate symbol", but replacing the generic "U" with the Figure "Quantum NOT gate symbol".

To understand why the gate is called a CNOT gate, you should think as follows.

First let's produce a generic quantum state vector where the control qubit is certain to be 0.

On the standard basis:

∣ 00 ⟩ ∣ 01 ⟩ ∣ 10 ⟩ ∣ 11 ⟩

(2)

we see that this means that only

∣ 00 ⟩

and

∣ 01 ⟩

should be possible. Therefore, the state must be of the form:

⎣ ⎢ ⎢ ⎢ ⎡ x y 00 ⎦ ⎥ ⎥ ⎥ ⎤

(3)

where

x

and

y

are two complex numbers such that

∣ x ∣ + ∣ y ∣ = 1.0

If we operate the CNOT gate on that state, we obtain:

⎣ ⎢ ⎢ ⎢ ⎡ 1000010000010010 ⎦ ⎥ ⎥ ⎥ ⎤ \times ⎣ ⎢ ⎢ ⎢ ⎡ x y 00 ⎦ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎡ x y 00 ⎦ ⎥ ⎥ ⎥ ⎤

(4)

and so the input is unchanged as desired, because the control qubit is 0.

If however we take only states where the control qubit is for sure 1:

⎣ ⎢ ⎢ ⎢ ⎡ 1000010000010010 ⎦ ⎥ ⎥ ⎥ ⎤ \times ⎣ ⎢ ⎢ ⎢ ⎡ 00 x y ⎦ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎡ 00 y x ⎦ ⎥ ⎥ ⎥ ⎤

(5)

Therefore, in that case, what happened is that the probabilities of

∣ 10 ⟩

and

∣ 11 ⟩

were swapped from

x

and

y

y

and

x

respectively, which is exactly what the quantum NOT gate does.

So from this we understand more concretelly what "the gate only operates if the first qubit is set to one" means.

Now go and study the Bell state and understand intuitively how this gate is used to produce it.

Toffoli gate

Clifford gates

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.

quantumtech.blog/2023/01/17/quantum-computing-with-neutral-atoms/ OK this one hits it:
As Alex Keesling, CEO of QuEra told me, "... whereas in gate-based [digital] quantum computing the focus is on the sequence of the gates, in analog quantum processing it's more about the position of the atoms and where you place them so they can mirror real life problems. We arrange the atoms and define the forces that drive them and then measure the result... so it’s a geometric encoding of the problem itself."
So we understand that it is truly like the classical computer analog vs digital case.
thequantuminsider.com/2022/06/28/why-analog-neutral-atoms-quantum-computing-is-a-promising-direction-for-early-quantum-advantage on The Quantum Insider useless article mostly by Pasqal

Video 1. TensorFlow quantum by Masoud Mohseni (2020) Source. At the timestamp, Masoud gives a thought experiment example of the perhaps simplest to understand analog quantum computer: chained double-slit experiments with carefully calculated distances between slits. Calulating the final propability distribution of that grows exponentially.