What is the actual mechanism behind quantum computing?

Question

I was redirected from theoretical computing to quantum computing for this question. I've been mildly researching quantum computers to figure out how entanglement and superposition are utilized for higher performance. I understand what these are and I've gotten to the point where it looks like the key is in the logic gate but explanations are vague other than stating that simultaneous possible configurations of all 0s and 1s can be processed at the same time. But what is the actual mechanism involved?

I would like a condensed understanding of how the quantum effect is utilized for any particular function. Is this possible or is the explanation too complex for a simple description? My background is Aeronautical Engineering, then Math and Physics Education as a late second career (BA in Math Education, MA in Science Education).

Answer 1

A qbit is a two-element vector:

$|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$

where $\alpha, \beta \in \mathbb{C}$ and $|\alpha|^2 + |\beta|^2 = 1$, a property called the 2-norm.

We have two important qbit values which we associate with the classical bits 0 and 1:

$|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$

A qbit is in superposition when it is in any state other than $|0\rangle$ or $|1\rangle$. When people say superposition means the qbit "is both 0 and 1 at the same time", what they mean is it is a linear combination of 0 and 1:

$|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix} = \alpha\begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \alpha|0\rangle + \beta|1\rangle$

We operate on qbits with quantum logic gates, which must always be equivalent in action to unitary matrices. For example, here's the bitflip or "not" operator:

$X|0\rangle = \begin{bmatrix} 0 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} = |1\rangle$

We represent the state of multiple qbits through their tensor product:

$\begin{bmatrix} a \\ b \end{bmatrix} \otimes \begin{bmatrix} c \\ d \end{bmatrix} = \begin{bmatrix} ac \\ ad \\ bc \\ bd \end{bmatrix}$

Note that the size of the product state vector grows exponentially with the number of qbits:

$\begin{bmatrix} a \\ b \end{bmatrix} \otimes \begin{bmatrix} c \\ d \end{bmatrix} \otimes \begin{bmatrix} e \\ f \end{bmatrix} = \begin{bmatrix} ace \\ acf \\ ade \\ adf \\ bce \\ bcf \\ bde \\ bdf \end{bmatrix}$

Ordinarily this doesn't matter very much, but sometimes qbits become entangled, which means their product state cannot be factored into the tensor product of individual qbits:

$\begin{bmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}} \end{bmatrix} \ne \begin{bmatrix} a \\ b \end{bmatrix} \otimes \begin{bmatrix} c \\ d \end{bmatrix}$

When this happens, applying a quantum logic gate to $n$ qbits (which takes the form of a $2^n \times 2^n$ unitary matrix) can manipulate $2^n$ pieces of information (the elements of the product state, called amplitudes) in one shot. However, there's a bottleneck: you can only ever get $n$ bits of information out of an $n$-qbit system (through measurement), even though the $n$-qbit system contains $2^n$ pieces of information. This bottleneck means we cannot "solve problems by trying all possible solutions simultaneously" or some other such nonsense you might have read, and quantum computers can only provide speedup in very specific problem domains.

I gave a lecture where I expand on these concepts here.

Answer 2

Answering what the "actual mechanism" is, is a very difficult question. I don't think there is any widespread consensus as to exactly which aspect of quantum mechanics leads to quantum speed-ups. Or said differently, the answer to "what is the actual mechanism behind quantum computing" is arguably "quantum mechanics", although this is obviously not a very satisfactory answer.

Nonetheless, there are a few tricks that quantum computers exploit which can be considered among the main tricks at play in many quantum algorithms.

In particular, one of the main characteristics of quantum computers is that they can operate on a space that is much larger than the space of the possible classical states.

By this I mean that if, for example, you consider a computation on $n$ qubits, then the corresponding (pure) states correspond to unit vectors in a $2^n$-dimensional vector space, and quantum computers operate by rotating and moving around these vectors in this huge vector space. Whenever you actually get an output, you will still only get one of the possible "classical" outputs (a bit string in this case), but still to get to that output from the given input, the quantum computer is allowed to explore a vastly larger space of possibilities.

A case in which this is nicely seen is for example Grover's algorithm. Each step of Grover's algorithm can be directly visualized as a rotation of the initial state towards the target state (see e.g. this answer). Such rotations exist in a space that is quite simply not accessible to classical devices.

Another common argument is that quantum computers allow you to somehow probe the output of a function on many different inputs at the same time (assuming to be able to implement that function coherently as a unitary operation). This does not quite mean that one can "check many possibilities at the same time", but it does mean that one can use a function a single time and get an output which depends on the way that function operates on a whole lot of inputs.

Again, Grover's algorithm is a good example of this, but in this case Deutsch-Jozsa is probably an even better one, as it shows how one can use a function a single time and yet deterministically figure out how that function operates on different inputs (while classically there is simply no way to know how a function operates on two inputs without trying them both).