Ciro Santilli @cirosantilli 35

In order to make websites efficient and portable, a lot of transpilation is needed.

web.archive.org/web/20200621205928/https://courses.maths.ox.ac.uk/node/view_material/1720 also mentioned at math.stackexchange.com/questions/579453/real-world-application-of-fourier-series/3729366#3729366 from heat equation solution with Fourier series.

eigenvalue problem of Laplace's equation.

Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.

One of the four following states:

When unqualified as in "the Bell state", it generally just means $|{\Phi }^{+}⟩$.

The Bell states are entangled and non-separable. Intuitively, we can see that when we measure that state, the values of the first and second bit are strictly correlated. This is the hallmark of quantum computation: making up states where qubits are highly correlated to match a specific algorithmic answer, and opposed to uniformly random noise. For example, the Bell state circuit is a common hello world, e.g. it is used in the official Qiskit hello world.

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:

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:

TODO why is it so hard to find anything non perturbative :-(

On a quantum computer...:

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.

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.

Video "Jeremy O'Brien: "Quantum Technologies" by GoogleTechTalks (2014)" youtu.be/7wCBkAQYBZA?t=2778 describes an error correction approach for a photonic quantum computer.

Bibliography: