Non-layperson explanation of why a qubit is more useful than a bit?

Question

I have a computer science and mathematics degree and am trying to wrap my head around quantum computing and it just doesn't seem to make sense from the very beginning. I think the problem is the definitions out there are generally watered down for lay-people to digest but don't really make sense.

For example, we often see a bit compared to a qubit and are told that an "old fashion digital bit" can only be in one of two states, 0 or 1. But qubits on the other hand can be in a state of 0, 1, or "superposition", presumably a third state that is both 0 AND 1. But how does being in a state of "both 0 and 1" deliver any value in computing as it is simply the same as "I don't know"? So for example, if a qubit represents the last binary digit of your checking account balance, how does a superimposed 0 and 1 deliver any useful information for that?

Worse you see these same articles say things like "and two qubits can be put together for a total of 4 states, three can make a total of 8 states" -- ok that's just $2^n$, the same capability that "old-fashioned bits" have.

Obviously there is great promise in quantum computing so I think its more a problem of messaging. Any suggestions for intro/primer literature that doesn't present the quantum computing basics in this oxymoronic way?

Answer 1

Qubits are more flexible than bits in a way that's difficult to summarize. But one key difference is that qubits support "phase kickback", and bits have no concept of phase kickback.

Here is a puzzle. Fill in the blanks to make these two circuits equal:

With bits, this is impossible. There is no single-input single-output process that can reverse the data-dependence direction.

With qubits, this is trivial. You just use Hadamard gates. You can confirm this identity for yourself by checking that conjugating a controlled-not gate's matrix with swaps is equivalent to conjugating it with the Hadamard transform:

The very first quantum speedups that were discovered were based on this identity. For example, all the Deutsch–Jozsa algorithm does is use this identity to turn an unknown all-to-one effect into a one-to-all effect, in order to figure out what that effect is in one query instead of many queries.

This identity is just the simplest example of phase kickback. Refinements of the idea led to Simon's algorithm and ultimately to Shor's algorithm. And none of it works with bits because bits have no phase kickback.

Answer 2

So there are two major advantages qubits have over classical bits: superposition and entanglement.

Superposition is the one more often discussed, and is the "0 or 1" phrase you always hear. Essentially the idea is that instead of just being in 0 or 1, we can be in some mix of the two. However quantum operators are linear, so if they are fed a superposition, they apply themselves to both parts separately:

$$A(\alpha |0\rangle + \beta |1\rangle ) = \alpha A |0\rangle + \beta A |1\rangle$$

This is essentially a system with built in parallelization, which is nice, as a blackbox can be queried multiple times at once. A common starting point for quantum algorithms is to apply the Hadamard operator (Which takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$) to each of a string of qubits in the $|0\rangle$ state. This leads to:

$$H^{\otimes N} |0\rangle^{\otimes N} = \sum_{k=0}^{2^N - 1}|k\rangle$$

where $|k\rangle$ is the state with it's qubits in the binary representation of $k$. Plugging this state into a quantum operator essentially gets every single possible input into said operator with one query, and if you can tease out the information you need with that one operator then you only need one attempt instead of $2^N$ queries. See the Deutsch-Jozsa algorithm for more details.

Entanglement is the second idea, and I would argue is much more powerful. The idea is that you can combine qubits in ways which are inseparable, meaning that they stop being objects with independent values. For example you can put two qubits into a state:

$$\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$

where the values are linked together. That means that when qubits are combined, the possible states they can occupy are far more varied. If I measure one of the qubits I affect the data stored in the other qubit because they were a linked object. Through this you can get cool interference effects by changing bases. I would also look at the quantum teleportation circuit to get an idea of how this can be useful for things that classical bits cannot do.

Answer 3

Adding to @Dripto's answer.

For example, we often see a bit compared to a qubit and are told that an "old fashion digital bit" can only be in one of two states, 0 or 1. But qubits on the other hand can be in a state of 0, 1, or "superposition", presumably a third state that is both 0 AND 1. But how does being in a state of "both 0 and 1" deliver any value in computing as it is simply the same as "I don't know"? So for example, if a qubit represents the last binary digit of your checking account balance, how does a superimposed 0 and 1 deliver any useful information for that?

In this context, 0 and 1 refer to orthogonal basis states of a Hilbert space (a complex vector space) representation of the states of physical objects like electrons (say spin states of an electron - "up" and "down"). It is more appropriate to denote them as $|0\rangle$ and $|1\rangle$, according to the Dirac notation. I've written about this previously, here. Just saying "superposition of state 0 and state 1" doesn't convey any useful information, yes. However specifying the superposition state like $\alpha|0\rangle+\beta|1\rangle$, where $\alpha,\beta\in \Bbb C$ and $|\alpha|^2+|\beta|^2=1$, makes complete sense mathematically and conveys useful information. By the way, $|\alpha|^2$ is the probability of the qubit collapsing to state $|0\rangle$ upon measurement and $|\beta|^2$ is the probability of it collapsing to state $|1\rangle$, upon measurement. You might say "superposition of state 0 and state 1" doesn't make physical or intuitive sense. Sure, quantum mechanics is simply a mathematical model that happens to give correct predictions about real world phenomena. It doesn't need to make physical or intuitive sense. It just needs to work.

Also, we would never use a qubit to represent the last binary digit of your account balance, in the first place. That would be silly. And even if we do, the qubit should be restricted to the computational basis states $|0\rangle$ or $|1\rangle$, and not their superposition states.

Worse you see these same articles say things like "and two qubits can be put together for a total of 4 states, three can make a total of 8 states" -- ok that's just $2^n$, the same capability that "old-fashioned bits" have.

Yes, that is nonsense. A single qubit can exist in any state one out of uncountably infinite number of states like $\alpha|0\rangle+\beta|1\rangle$ where $\alpha,\beta \in \Bbb C$ (simply because there are uncountably many complex numbers and $\alpha,\beta$ can take up any of those uncountably many values). And, by extension, any $n$-qubit system can exist in an uncountably infinite number of states. I guess by $2^n$ they just meant the number of basis of the Hilbert space in which the composite qubit system belongs, for instance, $|00\rangle, |01\rangle, |10\rangle$ and $|11\rangle$ form the computational basis set for a 2 qubit system. In general, a two qubit system can take up any state like $(\alpha|0\rangle+\beta|1\rangle)\otimes (\gamma |0\rangle + \delta |1\rangle)$ (a tensor product of the state of the two individual qubits which constitute the $2$-qubit system), where $\alpha,\beta, \gamma, \delta \in \Bbb C$ and $|\alpha|^2+|\beta|^2=1$ and $|\gamma|^2+|\delta|^2=1$. $$(\alpha|0\rangle+\beta|1\rangle)\otimes (\gamma |0\rangle + \delta |1\rangle)$$ can be expressed as a linear combination of the computational basis elements $|00\rangle, |01\rangle, |10\rangle$ and $|11\rangle$ i.e. $$\alpha\gamma |0\rangle \otimes |0\rangle + \alpha\delta |0\rangle \otimes |1\rangle + \beta\gamma |1\rangle \otimes |0\rangle + \beta\delta|1\rangle \otimes |1\rangle,$$ alternatively denoted as:

$$\alpha\gamma |00\rangle + \alpha\delta |01\rangle + \beta\gamma |10\rangle + \beta\delta|11\rangle.$$

From here you can say that a $n$-qubit system can store $2^n$ values(coefficients) in parallel, although there's always the restriction that the squared sum of the moduli of the coefficients of the computational basis states must add up to $1$.

Obviously there is great promise in quantum computing so I think its more a problem of messaging. Any suggestions for intro/primer literature that doesn't present the quantum computing basics in this oxymoronic way?

See my previous answers: this and this, for resource recommendations. As mentioned there, I'd recommend starting with Vazirani's lectures and then moving on to Nielsen and Chuang. I recently found the 2006 lecture notes by John Watrous which are also pretty great for beginners. It helps a lot to have a thorough grounding in linear algebra, while learning quantum computing, but I suspect you already have that, being a mathematics and computer science graduate.

As for how computation using qubits can be faster, in some cases, than using classical bits, I recommend carefully thumbing through the standard quantum algorithms like Deutsch-Jozsa, Shor's, Grover's among others. Here is a simple explanation of the Deutsch-Jozsa algorithm. It would be a bit difficult to summarize that in one answer. Please keep in mind that quantum computing cannot speed up all type of computations. It's applicable to only very specific problems.

Answer 4

SFAIK, and still have seen nothing to contradict this, the main use of qubits is in simulations where actual quantum elements replace faux stochastic elements from traditional modeling. Thus it's a very useful but also pretty narrow thing that is in no way comparable to ubiquitous modern digital computing elements and has absolutely no path to replacing them. Somehow in all the blather, promotional, stock prospecti, etc. this gets lost.

So at the end of the day when IBM or whoever has squeezed all they can get out of this and quantum computing is mature and has replaced the aformentioned psuedo random simulation elements, bits, outside those models, some crypto, etc., will still be the same ol ubiquitous bits and presumably by that time the information in this reply will be common knowledge to those capable of processing it.