8
$\begingroup$

Below is a figure from a TIME magazine edition. I have a few questions regarding this representation of quantum computing:

  1. Is saying "0 and 1 at the same time" a correct statement? Isn't the qubit just in a superposition of both states, not "both at the same time"? It is ultimately either 0 or 1 once observed, and it has a certain probability of being 0 or 1 once observed. Is it ever "0 and 1 at the same time"?

  2. "Perform multiple operations simultaneously" seems to imply that the benefit of quantum computers comes from their ability to do computations in paralell. How accurate is that statement? Are computations happening in parallel?

time magazine quantum computing

$\endgroup$
2

5 Answers 5

21
$\begingroup$

This figure is not accurate at all about quantum computers.

This "try-every-case" thing is the standard boilerplate everyone puts in their popsci articles. But it's not at all how quantum algorithms work, it doesn't give any sense of what quantum computers are actually good at, and it doesn't give any sense of what they're not good at. The way quantum computers do things like factor numbers is nothing at all like trying all the answers. It's quite frustrating; Scott Aaronson puts this in the header of his blog https://scottaaronson.blog/ because it's such a widespread misconception.

$\endgroup$
8
$\begingroup$

I might not express the sentiment quite as strongly as some of the other answers. It is attempting to convey something, and what it is saying is not completely untrue, but is certainly skipping over some very important details.

  1. Yes, the qubit is in a superposition. But how do you express this to someone who doesn't know what a superposition is? If you only talk about the post-measurement state, there's nothing different going on (because you've destroyed the superposition). You can't just talk about probabilities because that's classical too. So some sort of description about being simultaneously both being in 0 and 1 is an attempt to convey something about what it means to be in a superposition.

  2. Many quantum algorithms do have a step that they go through where they evaluate multiple computational paths simultaneously. However, this is not the end of the story. Those paths are in superposition (which is really not the same as parallel but, again, we're trying to use language that non-specialists can get some sort of understanding from), and if you were to simply measure the outcome again, you'd get a collapse onto a singular outcome that would be just like what you'd get if you did classical computation. So there has to be an extra step (whose existence is only known in a very limited handful of cases) where you interfere those different superposed paths in such a way that the answer to your computation pops out. Where does the power of the quantum computer come from then? It wouldn't happen if you couldn't do all those paths simultaneously, but perhaps more important is the insight about the cases when you can do that interference step.

$\endgroup$
6
  • 3
    $\begingroup$ I'm curious. How would you explain the superposition of a qubit other than it being 1 and zero at the same time? $\endgroup$ Feb 3, 2023 at 21:29
  • 1
    $\begingroup$ @AccidentalTaylorExpansion my answer below gives at least three different ways to "interpret" the qubit's situation before it's measured (i.e. before the wavefunction has collapsed). Also, do you have any relation to AccidentalFourierTransform? $\endgroup$ Feb 4, 2023 at 14:51
  • 2
    $\begingroup$ @user1271772 Thanks! I don't see though how "0 and 1 at the same time" is different from "neither 0 nor 1 until observed". For my username: I saw the username of AccidentalFourierTransform and I thought it was funny/interesting so I made a twist on it. Together we cover the entire mathematical toolbox of physicists. $\endgroup$ Feb 4, 2023 at 15:27
  • 1
    $\begingroup$ @AccidentalTaylorExpansion this is why my answer says that trying to interpret what the wavefunction is before it is observed (i.e. before wavefunction collapse) is more in the realm of philosophy or pedagogy (maybe even "semantics"). I would say "0 and 1 at the same time" would mean "yes its a 0 and also yes its a 1", whereas "neither 0 nor 1 until observed would mean "no its not a 0 and also no its not a 1" then after measurement it would be something like "yes its a 0, and no its not a 1". We could also imagine the qubit is flipping rapidly/randomly between 0/1 until observed. $\endgroup$ Feb 4, 2023 at 15:32
  • 1
    $\begingroup$ @AccidentalTaylorExpansion Frankly, I don't have a better way of explaining it if I'm not allowed to show what's going on with maths. I do like to refer people to the Terry Pratchett quote: "It’s very hard to talk quantum using a language originally designed to tell other monkeys where the ripe fruit is." Our language is set up to describe our everyday experience. Quantum is not in that experience so until you learn what the specialised language means, you're a bit stuck! $\endgroup$
    – DaftWullie
    Feb 6, 2023 at 7:39
7
$\begingroup$

Contrary to the answers by Craig Gidney and by Martin Vesely (the answer by DaftWullie is the most fair so far), nothing in the TIME magazine cartoon is wrong.

  1. "It is ultimately either 0 or 1 once observed, and it has a certain probability of being 0 or 1 once observed. Is it ever "0 and 1 at the same time"?"

The exact nature of the wavefunction before collapse (i.e. before "observation") is not something that we can know without collapsing it. Science tells us the probability of observing a 0 or 1, but what it is before is not falsifiable in a scientific experiment, and is more of a question for philosophy or pedagogy. Whether the system is in a state of "0 and 1 at the same time" or "neither 0 nor 1 until observed" or "switching between 0 and 1 at faster than the speed of any measurement device until observed" depends on which of the many interpretations of quantum mechanics you prefer: Copenhagen interpretation, Everett interpretation (many-worlds), Von Neumann interpretation, etc. If you disagree, and think some interpretation of the superposition is wrong, then I challenge you to describe an experiment that can falsify (prove wrong) that interpretation.

Saying that the wavefunction is in a state of 0 and 1 at the same time, is very common among the scientists that are experts in quantum mechanics, especially when teaching the subject to the public (i.e. the type of audience of TIME magazine). When I teach quantum computing, I start by explaining the Mach-Zehnder experiment, and I explain that when the photon goes through the first half-silvered mirror, it's now in both the 0 position and 1 position at the same time, which is possible because photons don't have to just be considered point-like, localized "particles", but can also be considered delocalized "waves" that are in more than 1 place at a time.

  1. ""Perform multiple operations simultaneously" seems to imply that the benefit of quantum computers comes from their ability to do computations in paralell. How accurate is that statement? Are computations happening in parallel?"

It's not wrong. When a quantum computer is used to solve the Deutsch-Jozsa problem with 1 function evaluation instead of 2^n, the quantum computer is basically evaluating the function for all inputs: 00000, 00001, 00010, ..., 11111 at the same time. That is how I teach it, and that's how it's explained by most quantum computing experts that are asked to teach it.

The part in Craig Gidney's answer with which I do agree, is that quantum computation can be much more complicated than just evaluating everything in parallel, and his example of factoring numbers is a perfect one. Shor's algorithm does not simply "try to multiply all possible factors in parallel". If that were the case, Shor's algorithm would be 1 step that's simply repeated in parallel. Instead there's actually 7 different steps that are done on a classical computer, followed by a "period-finding" procedure done on the quantum computer which involves iteratively completing 8 different steps until the factors are found. Unfortunately, "evaluating every possibility at the same time" isn't something that can be done for the integer factorization problem, so we need to resort to something far more sophisticated. But it is the way that the Deutsch-Jozsa problem is solved, because in this problem we're not trying to factor integers, we're just trying to evaluate a function for all possible inputs and check whether or not the outputs have certain properties.

$\endgroup$
1
  • $\begingroup$ Thank you for your view. Just to note, I did not say that the figure is wrong but at least it is inaccurate. Quantum computers do not do everything in parallel. DJ is a good example where this explanation works but what about Grover or quantum Monte Carlo? There are some subtleties that the figure ignores. Concerning the qubit to be simultaneously in both states, I agree with you that this is good way how to explain superposition to generál audience. But purely mathematical approach describing the superposition as a linear combination seems to be the best way. $\endgroup$ Feb 3, 2023 at 6:58
4
$\begingroup$

Just to add something to your second question. If a quantum computer carried out the computation in parallel, every calculation where more inputs are involved would be sped up exponentially. However, this is not the case. Although algorithms where Quantum Fourier Transform is involved, like HHL or Shor, offers exponential speed up, there are also algorithms like Grover or quantum Monte Carlo which brings about only quadratic speed up. Moreover, Grover algorithm was proved to be optimal, i.e. the quadratic speed up is the maximum.

What is more, if quantum computers were always able to carry out parallel calculation, it would probably mean that any NP task can be solved in polynomial time on quantum computer. However, this is also not the case.

To sum up, for sake of simplicity we can say that qubit can be simultaneously in 0 and 1 state to persons with little knowledge of quantum mechanics but at the same time we have to add disclaimer about the exponential speed up a discussed above.

$\endgroup$
2
  • $\begingroup$ Has it been proved that if NP contains problems that are not in P, then NP contains problems that are not in BQP? $\endgroup$ Feb 3, 2023 at 12:58
  • 3
    $\begingroup$ @TannerSwett: We do not know what is relationship between these two classes. We only know that both are subsets of PSPACE. $\endgroup$ Feb 3, 2023 at 15:51
2
$\begingroup$

As you can probably see from the existing answers, the answer to your question is quite subjective and essentially boils down to one's epistemological perspective on the word "accurate".

My take is that the answer to your question depends on who the intended audience is and what the author's goals are. If the intended audience is people who know absolutely nothing about quantum computing, then (in my personal opinion) this is a defensible (although highly simplified) presentation for a first pass.

I very respectfully disagree with Craig Gidney's claim that "try every case" is "not at all how quantum algorithms work". It is certainly not exactly how quantum algorithms work, but it is something like how quantum algorithms work. Whether the analogy is close enough to be useful again depends on what your goals are. For an expert like Craig Gidney who is actually trying to discover or improve specific quantum algorithms, it certainly is nowhere near a precise enough heuristic to be useful. But for someone trying to explain an exciting new technology to a totally non-expert audience, I think it's a decent heuristic.

Craig Gidney and Martin Vesely (and Scott Aaronson as well) also suggest a specific claim that I slightly disagree with, although probably in a direction that's mostly orthogonal to their thinking. That idea is Craig Gidney's claim that the massive-parallelism picture "doesn't give any sense of what quantum computers are actually good at, and it doesn't give any sense of what they're not good at", or Martin Vesely's more specific claim that it implies that quantum computers could efficiently solve NP-complete problems (which is believed not to be the case).

I very respectfully suggest that that claim assumes that the median person who reads these descriptions has more of a "theoretical computer science" mindset than is actually the case. I suspect - and this is just a suspicion, I could be wrong - that for the median person who reads that description, the main takeaway is closer to "There are some problems that quantum computers can solve very fast" than to the more specific claim that "Quantum computers can efficiently solve all problems that would benefit from massive classical parallelization." And the former takeaway is completely correct. Note that my disagreement is solely on sociological grounds, not on any grounds of either computer science or physics.

More concretely: suppose you took the average person with no background in quantum computing who read that figure and thought "Okay, I kinda get that", and you asked them "Would a quantum computer be able to efficiently find the shortest path through a complicated travel network that hits every city?" I don't think that the person would confidently reply "Yes - the quantum computer would calculate the length of every path in parallel and extract the shortest one" (which would be incorrect). I suspect that it's more likely that they'd say something like "I have absolutely no idea. But I guess maybe it could use this crazy superposition business to solve the problem faster than a regular computer could?" (which, in my opinion, is not a bad answer for someone who realistically probably doesn't really need to know many more details that that).

The problem is that there aren't any great pedagogical alternatives to the "massive parallelism" picture that are useful to someone with zero background in QC and little interest in studying it formally. Framing quantum computing as a modification to the usual rules of classical probability is absolutely the best way to go - if you want to actually teach someone how it really works. But I don't think that's the goal of the Time magazine article - and frankly, I don't think that necessarily should be the goal, either.

I think that the "massive parallelism" story would be inappropriate to present in an undergraduate intro to computer science course, or even in a general-interest science outlet like Scientific American - it just isn't accurate enough. But I think it would have been defensible for Time magazine to present it to the general public, if they had added in a footnote saying something like "This is a highly simplified explanation that glosses over many important subtleties."

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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