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?

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

  • "Essentially the idea is that instead of just being in 0 or 1, we can be in some mix of the two. " What does that mean "we can be in some mix of the two"? Does it imply that the qubit can take on any value between 0 <= qubit <= 1? Where does alpha and beta come from? – Lee Cascio Dec 5 at 18:00
  • It means that you can have weighted sums of the two. A single qubit's state can be described using two numbers, these can be thought of angles (See the Bloch Sphere representation). A qubit in the state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$ has a $\alpha^2$ probability of being measured as 0 and $\beta^2 = 1-\alpha^2$ probability of being measured as 1. The relative phase between these two states is also physically/computationally significant, but not when measuring in the computational (0 vs 1) basis. – Dripto Debroy Dec 5 at 18:45
  • @LeeCascio $\alpha$ and $\beta$ are complex numbers. "Does it imply that the qubit can take on any value between 0 <= qubit <= 1" - no, that's a wrong way to think about it as the coefficients of 0 and 1 are not restricted to real numbers. $\alpha$ and $\beta$ can be derived by analyzing the set of operations on the initial state of the qubit (say, applying the Pauli-Y gate on a qubit can change its state from $|0\rangle$ to $i|1\rangle$, where $i$ is the complex number iota). You can't estimate the values of the complex numbers physically (but you can measure $|\alpha|^2$ and $|\beta|^2$). – Blue Dec 6 at 3:33
  • [cont.] It is important to note that any real number between $0$ and $1$ can be written as a weighted sum of $0$ and $1$. Say, $0.3$ can be written as $0.7\times 0 + 0.3\times 1$. But you don't have any number in between $0$ and $1$ which is equivalent to say $0.7\times 0 + 0.3i\times 1$. The set of complex numbers is strictly larger than the set of real numbers! For qubits there is the additional restriction that $|\alpha|^2+|\beta|^2=1$ since probabilities must add up to $1$. – Blue Dec 6 at 5:28
  • [cont.] If $\alpha,\beta$ are considered to be real, $|\alpha|^2+|\beta|^2 = 1$ would simply be a circle in the $\alpha, \beta$ plane. However, $|\alpha|^2+|\beta|^2=1$ needs a whole sphere to be represented mathematically i.e. the Bloch sphere, for complex $\alpha,\beta$. – Blue Dec 6 at 5:44

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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