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).

  • 2
    $\begingroup$ Hi. Would this and this answer your question? It would be helpful if you could include your level of expertise (in mathematics/physics), so that other users can answer accordingly. $\endgroup$ – Blue Feb 5 at 20:00
  • $\begingroup$ Yes, this will give me some more focused material to study. Thanks for your revision to focus other users' responses. $\endgroup$ – Phil H Feb 6 at 4:20

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.

  • $\begingroup$ This is very good, it gets into the details and hence the logic of what a quantum computer can and cannot do and therefore a general understanding of why it can only speed up certain problem domains. I'll study the link content of your lecture concepts.. $\endgroup$ – Phil H Feb 6 at 17:49
  • $\begingroup$ I'd like to mention here that quantum computation does not necessarily require qubits. There are architectures which use qutrits and qudits too. And there's also continuous variable quantum computation. $\endgroup$ – Blue Feb 8 at 16:42

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).


protected by Blue Feb 5 at 20:03

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.