By Zhengda He in science — Nov 2, 2023

Quantum Computing/Computer (QC)

What is QC?

According to Wikipedia: "Quantum computing is the use of quantum phenomena such as superposition and entanglement to perform computation. Computers that perform quantum computations are known as quantum computers."

Ok, from this definition, we know if we want to really understand quantum computing, we need to understand: (1) what is "quantum phenomena"? (2) what is "computation"?

The first question ("what is quantum phenomena?") is rooted in the subject of Quantum Mechanics, which we do not have time to dig deep in here (but I will write about that in other post, since quantum mechanics is really interesting to talk about). The key idea of quantum mechanics is: (1) duality of particles (particles can be a wave and a particle at same time, but it really means is that the probability of finding a particle at a location in space is like a wave, in mathematical perspective, if I give you a wavefunction \(\Psi(\vec{r})\), then the probability that you can find this particle at the spherical region \(\vec{r}\rightarrow \vec{r}+d\vec{r}\) is \(|\Psi(\vec{r})|^2d\vec{r}\), really interesting right? 😏. The \(|\Psi(\vec{r})|^2\) is called the probability density. This is the Copenhagen interpretation of quantum mechanics, and there are also other versions. In here you can find more discussions about that.)

The second question ("what is computation?") is really important for understanding quantum computation. It was first illustrated in Alan Turing's seminal article "On Computable Numbers, with an Application to the Entscheidungsproblem" (link), he talked about the "Turing machine", which is considered as the foundation of computer science. Stephen Wolfram also had great ideas on "what is computation" in his famous book <A new kind of science> (online version). But in a very simple perspective, computation is just a transformation from state A to state B. For example, in density functional theory (or first-principle simulation), I give you the geometric coordinates of the system, and the code will calculate and get a number (e.g. the total energy), that is the output, without thinking about the inner working mechanism of the code, that simple "structure-to-energy" mapping is considered as a form of "computation".

What are the fundamental principles of QC?

The fundamental principles of QC is the same as the fundamental principles of Quantum Mechanics, which is often referred as "postulates of quantum mechanics" (actual contents may vary, the order may vary, but the ideas are the same):

The state of a quantum mechanical system is completely specified by the wavefunction \(\Psi(\vec{r},t)\).
To every observable in classical mechanics, there corresponds a linear, Hermitian operator in quantum mechanics. e.g. in cartesian coordination system, the momentum is actually an operator (\(-i\hbar\vec{\nabla}\))
The quantum state can be seen as the linear combination of other states: \(\Psi = c_1\psi_1+c_2\psi_2+c_3\psi_3 \cdots c_n\psi_n\). the meaning of this is: If I measure this state \(\Psi\), the probability that I will measure \(\psi_i\) state is: \(|c_i|^2/\sum_{i=1}^n|c_i|^2\). And the measurement can only have n possible states (from \(\psi_1\) to \(\psi_n\))
The time-evolution of the state can be written in Schrödinger equation: \(\hat{H}|\Psi\rangle=i\hbar\partial |\Psi\rangle/\partial t\)
The total wave function of a fermion system will change its sign if we interchange the location of two fermions. With boson system, the sign will remain the same. (Pauli's exclusion principles comes from the antisymmetry of wave function of fermion system)

What's the difference between QC and traditional computation?

Traditional computation: based on Boolean algebra (True/False, 0/1). It is actually very interesting to learn how to use boolean algebra to do the summation, subtraction, multiplication and division.

QC: based on the law of quantum mechanics, which is superposition, quantum entanglement, it is a brand new way to think about computation. A new foundation of computation (you can say), and that requires a whole new way of thinking about the problems and designing new architectures.

There are also similaries between traditional computing and quantum computing, for example, they can all be represented as the connection of different types of "gates":

For traditional computing:

Image from: https://en.m.wikibooks.org/wiki/Digital_Circuits/Logic_Operations

For quantum computing:

https://www.bsc.es/research-development/research-areas/quantum-information/quantum-algorithms

Actually, a quantum computing algorithm is often referred as "quantum circuit". Which means the algorithm is actually constructed by different gates (which has different purposes).

But since quantum computation is based on quantum mechanics, the "gate" in the QC sense is actually more complicated than in the traditional boolean algebra. We need to use more advanced concept (like matrix and tensor). But we will go into the detail later.

What does a QC algorithm look like?

As we have already discussed before, a QC algorithm can also be called as a "quantum circuit". So that it is very important in here to introduce differnet types of "gates" in quantum computation and their physical realization (the actual circuit in the quantum computer).

In below are the most widely used gates in quantum computation:

The figure comes from: https://en.wikipedia.org/wiki/Quantum_logic_gate

In here let me explain why the gates can be seen as a matrix. In quantum mechanics, there are three identical representation of the theory: (1) Schrödinger's wave mechanics (2) Heisenberg's matrix mechanics (3) Feynman's path integral. In Heisenberg's matrix mechanics, all wave function are just a vector in the Hilbert space (which is an infinite dimension complex functional space, where the basis are the complete eigenvectors of the operators), since the purpose of the quantum gate is to transfer this wave vector from one state to another state, which can be viewed as the transformation from one vector to another, then we can treat the quantum gate as a matrix.

As an example, we can see the quantum circuit of Shor's algorithm: