ClaytonB
Member
- Joined
- Oct 30, 2011
- Messages
- 10,796
Quantum Computing Is Total Bullshit
Before I jump into the topic, I want to make some clarifications. First, by "total bullshit", I don't mean any of the following:
(a) quantum physics is fake
(b) quantum computing has a flaw in its underlying mathematics
(c) no quantum computer could ever be useful for anything
... and so on. Rather, second, this post is meant to explain why the mindless hype about quantum computing is false and misleading on many dimensions.
Third, this post is going to be in a weird space between technical and non-technical. I want to help non-technical people understand why quantum computing is a lot of hype, but I don't want to lose people in technical details. So, I'm going to be discussing technical topics in largely non-technical language. The explanations I give here will not be completely technically accurate but, rather, are meant to motivate non-technical folks to understand the gist of the problems with quantum computing. The reason for this is that the actual reasoning mistakes that are being made by many popularizers of quantum computing are quite subtle, and require non-trivial mathematical and computational background to understand. If someone reads this post and would like further clarification on the exact nature of these underlying technical problems, feel free to respond here and I will follow up.
With those disclaimers out of the way, let's begin.
What is a superposition, anyway?
One of the most common quantum buzzwords you will run into is "superposition". Classical bits, the fairy-tale goes, can only be in "one state at a time, either 0 or 1", but quantum bits can be in a "superposition" of both 0 and 1. What, exactly does this mean?
Before examining the meaning of superposition of quantum states, let's look at the original meaning of the word "superposition" which comes from wave physics. Drop two pebbles into a pond in slightly different location -- what will happen? The rings from each pebble will spread and "cross" one another:
Notice that, from this top-down view, the waves from the pebbles are oblivious to one another. They do not "collide", as a child might naively expect if they are too young to have played with rocks in the water. The waves do not "push" each other laterally, they just pass through each other. This is one of the properties of superpositions of transverse waves (the waves created by a pebble are transverse, meaning, they only wave "up and down", not having enough pressure to displace the water laterally.)
In the following diagram are two mathematical waves. Their exact equation and shape are not important, I just created some interesting waves for the purpose of illustration. As shown by the equation at the top of the diagram, the green wave is the sum of the orange wave and the blue wave. In magenta, I have highlighted four illustrative regions of the diagram so that you can see how these waves are added together, or superposed.
Note that the dark horizontal line is vertical 0, so the portions of the wave above the dark horizontal line are positive, and the portions below it are negative.)
The mathematical properties of superposed waves explain why water waves created by pebbles do not distort each other's shape when viewed top-down. The waves are interfering with one another, but only in the vertical direction, not laterally.
The facts I have related here about superposed water waves and mathematical waves are all there is to the topic of "superposition." This is everything that the word "superposition" means -- it is just the summation of interfering waves, nothing more, nothing less.
What is a parallel digital computer?
Suppose I give you an unsorted list of words. I want you to find out if the word "farfignewton" appears in that list. Here's how you can compute it:
First, you check "is the first item of the list equal to 'farfignewton'?" that is, "wrap=farfignewton?" The answer is No, so you move to the next word. "indicative=farfignewton?" Nope. Move on to the next word. And so on. If there are no other properties of the computational problem which would allow you to speed up this computation, this is the best you can do. And the average time it will take you to search the list is N/2 where N is the length of the list (assuming the word being searched for is in the list, and the list is truly randomized).
We can speed things up by adding a second computing element, allowing us to compare two elements of the list simultaneously. I am showing an artistic depiction of this, but don't confuse it for an actual implementation, which would not be done this way:
Here, we are comparing two words simultaneously, allowing us to move through the list twice as fast. The purple compute-unit and the orange compute-unit are independent, and so this allows us to do comparisons in parallel. The average time to search the list is now approximately N/4, since we are moving through the list twice as fast as before, and the original average time was N/2.
It is easy to see that, for certain simple problems (like search), we can scale up the speed simply by throwing more compute units (or "threads") at the problem. To search 10 times as fast, we just use 10 compute units. To search 1,000 times as fast, we use 1,000 compute units. And so on. While linear speed-up is not the best case that can be achieved across all problems, it is generally a desirable speed-up.
However, some problems are so large that they dwarf the available compute resources, even if you have millions or billions of compute-units. On such problems, as you scale up to bigger and bigger problem instances, the advantage of parallelism dwindles, because the problem size itself dwarfs the available number of computing units we have:
In (a), we see that two threads are working through a problem instance at a pretty good clip. The gray boxes show the progress as the two threads progress through the problem. In (b), we see that the two threads have a lot more work cut out for them. In (c), even more since there are now thousands of cases to work through, and in (d) we have shown an all-white box to suggest the idea of an "ocean" of instances which must be processed by these two threads. (d) is so hard that having two threads is not any better than having just one thread -- the problem is too large to be solved in any reasonable amount of time whether you have 1, 2, 8, 16, etc. threads.
Parallelism and randomization
Consider the following diagrams:
In (a) and (b), we see that we have 8 threads. On each time step, we can process 8 boxes (8 instances of the problem). Notice that we need to keep track of which boxes have been processed and which have not, otherwise, we will end up duplicating effort which defeats the whole purpose of employing parallelism.
The problem with this tracking is that it may require communication between the threads (which introduces overhead and reduces the amount of achievable speed-up) or, at least, we must specially design the algorithm so that the threads will operate harmoniously.
For very large problems, however, this approach becomes a serious disadvantage so, if we can, we prefer to randomize the problem instances, as shown in (c) and (d). At each time step, each available thread simply chooses a random box and processes it. If there are a sufficiently large number of boxes, there will only be a modest amount of duplicated effort.. the losses from duplication may be significantly lower than the costs of coordination would be. (e) shows the result after many time steps of randomized processing... each of the available 8 threads will have processed some number of boxes in random order, as shown. The empty boxes show one of the drawbacks of randomization -- processing the last few items by random order is slow and inefficient, so randomization is best suited to problems where the solution is almost always found "early". Search, for example, is a problem that is well suited to randomization and this is one of the ways that large-scale search (such as web-search) is organized.
The conceptual quantum advantage
As you can see from the illustrations above, we haven't really reduced the amount of effort of computing that must be done to solve a problem. We have sped up the computation but only at the cost of throwing an equivalent duplication of resources at it. We can speed up the computation by a factor of 10... but that also requires us to build 10 computers and make them all work on that problem in parallel. We've identified some clever tricks, such as randomization, to reduce communication overhead in parallel systems, but we haven't actually reduced the raw amount of work that must be done. All the computation that would have to be done by one thread, had to be done by our 8 threads -- it just completed 8 times faster.
The idea of quantum computing is that we want to do "many things at once" where we mean truly "at once" by one thread or "one qubit", rather than by dividing the problem up into many small pieces and harnessing countless computing units to do exactly the same amount of work, in parallel, instead of serially.
Consider the following diagram:
Here, we have shown 8 classical threads on the left doing 8 units of work. On the right, we have shown 8 qubits but some kind of "spread out color pattern" surrounding those qubits. I want to emphasize this is a purely artistic depiction and does not correlate to the underlying reality of quantum computing. But it captures the essence of what we want to do. Instead of solving large-scale problems with large-scale amounts of computing resources, we want to solve large-scale problems using a modest amount of computing resources that are somehow "spread out" across the entire problem space, in a smart way. And, to an approximation, that is what quantum computers are doing. If we regard the grid in the diagram above as a map of the "state space" of our problem, the quantum computer is exploring through a broad portion of the entire state space, instead of just exploring 8 discrete points in the state-space at a time, as an 8-thread parallel computer would.
So, here's the punchline:
Nature computes in parallel -- everywhere, all the time
Consider this neat little demonstration:
Notice he says at one point, "It's like it's trying all possible paths at once, by air-pressure." This is the key insight that debunks 99+% of the claims being made about quantum computers. There's nothing super-duper-special about what a quantum computer is doing, versus other physical systems. Everything in our world is "trying all paths at once"! Classically!!
Notice that, if you were to physically build the system depicted here, the moment you release the weight and let it hang freely, the weight p (and all the intervening forces on the pulleys) will be computed effectively "instantly", and you could measure this by hooking up force meters to measure the various forces involved. Yes, the tension along the rope will propagate at something like the speed of sound but that's not the point, as far as we're concerned, that is instantaneous. Nature is computing in parallel, everywhere, all the time. Classically, as well as "quantumly". Quantum mechanics has no special, super-extra parallelism[1].
As per the disclaimers I gave in the opening, this doesn't mean there is no difference between classical and quantum systems. However, from a computational standpoint, we can absolutely think of qubits as a "limiting case" of analog computing systems that are trying "all possible paths at once". There are countless ways to build such systems and they do not have to be bespoke to every problem you want to solve (there are general-purpose models for analog computation, if you are sufficiently exact as to what you mean by "general-purpose".)
Quantum computing (hype) is total bullshit!
---
[1] - This claim, in particular, is where the topic becomes technical. For anyone interested, my argument to support this point is based on encoding computational states in an analog system and then using arbitrarily high-precision measurements (beyond what is physically attainable) to achieve the same kind of "exponential parallelism" that quantum theory achieves. Essentially, this is a reductio argument to show that quantum theory is cheating by simply positing these exponential number of parallel universes which it also explicitly tells us we can't observe. In other words, it's a mathematical swindle. This criticism has nothing to do with quantum physics itself, and has everything to do with the overlap of computation and quantum physics. If you can shuffle bits around into parallel universes simply by positing an exponential number of such unobservable universes, then so can I. I am just using a different encoding and a different physical substrate (classical, instead of quantum).
Before I jump into the topic, I want to make some clarifications. First, by "total bullshit", I don't mean any of the following:
(a) quantum physics is fake
(b) quantum computing has a flaw in its underlying mathematics
(c) no quantum computer could ever be useful for anything
... and so on. Rather, second, this post is meant to explain why the mindless hype about quantum computing is false and misleading on many dimensions.
Third, this post is going to be in a weird space between technical and non-technical. I want to help non-technical people understand why quantum computing is a lot of hype, but I don't want to lose people in technical details. So, I'm going to be discussing technical topics in largely non-technical language. The explanations I give here will not be completely technically accurate but, rather, are meant to motivate non-technical folks to understand the gist of the problems with quantum computing. The reason for this is that the actual reasoning mistakes that are being made by many popularizers of quantum computing are quite subtle, and require non-trivial mathematical and computational background to understand. If someone reads this post and would like further clarification on the exact nature of these underlying technical problems, feel free to respond here and I will follow up.
With those disclaimers out of the way, let's begin.
What is a superposition, anyway?
One of the most common quantum buzzwords you will run into is "superposition". Classical bits, the fairy-tale goes, can only be in "one state at a time, either 0 or 1", but quantum bits can be in a "superposition" of both 0 and 1. What, exactly does this mean?
Before examining the meaning of superposition of quantum states, let's look at the original meaning of the word "superposition" which comes from wave physics. Drop two pebbles into a pond in slightly different location -- what will happen? The rings from each pebble will spread and "cross" one another:
Notice that, from this top-down view, the waves from the pebbles are oblivious to one another. They do not "collide", as a child might naively expect if they are too young to have played with rocks in the water. The waves do not "push" each other laterally, they just pass through each other. This is one of the properties of superpositions of transverse waves (the waves created by a pebble are transverse, meaning, they only wave "up and down", not having enough pressure to displace the water laterally.)
In the following diagram are two mathematical waves. Their exact equation and shape are not important, I just created some interesting waves for the purpose of illustration. As shown by the equation at the top of the diagram, the green wave is the sum of the orange wave and the blue wave. In magenta, I have highlighted four illustrative regions of the diagram so that you can see how these waves are added together, or superposed.
Note that the dark horizontal line is vertical 0, so the portions of the wave above the dark horizontal line are positive, and the portions below it are negative.)
The mathematical properties of superposed waves explain why water waves created by pebbles do not distort each other's shape when viewed top-down. The waves are interfering with one another, but only in the vertical direction, not laterally.
The facts I have related here about superposed water waves and mathematical waves are all there is to the topic of "superposition." This is everything that the word "superposition" means -- it is just the summation of interfering waves, nothing more, nothing less.
What is a parallel digital computer?
Suppose I give you an unsorted list of words. I want you to find out if the word "farfignewton" appears in that list. Here's how you can compute it:
First, you check "is the first item of the list equal to 'farfignewton'?" that is, "wrap=farfignewton?" The answer is No, so you move to the next word. "indicative=farfignewton?" Nope. Move on to the next word. And so on. If there are no other properties of the computational problem which would allow you to speed up this computation, this is the best you can do. And the average time it will take you to search the list is N/2 where N is the length of the list (assuming the word being searched for is in the list, and the list is truly randomized).
We can speed things up by adding a second computing element, allowing us to compare two elements of the list simultaneously. I am showing an artistic depiction of this, but don't confuse it for an actual implementation, which would not be done this way:
Here, we are comparing two words simultaneously, allowing us to move through the list twice as fast. The purple compute-unit and the orange compute-unit are independent, and so this allows us to do comparisons in parallel. The average time to search the list is now approximately N/4, since we are moving through the list twice as fast as before, and the original average time was N/2.
It is easy to see that, for certain simple problems (like search), we can scale up the speed simply by throwing more compute units (or "threads") at the problem. To search 10 times as fast, we just use 10 compute units. To search 1,000 times as fast, we use 1,000 compute units. And so on. While linear speed-up is not the best case that can be achieved across all problems, it is generally a desirable speed-up.
However, some problems are so large that they dwarf the available compute resources, even if you have millions or billions of compute-units. On such problems, as you scale up to bigger and bigger problem instances, the advantage of parallelism dwindles, because the problem size itself dwarfs the available number of computing units we have:
In (a), we see that two threads are working through a problem instance at a pretty good clip. The gray boxes show the progress as the two threads progress through the problem. In (b), we see that the two threads have a lot more work cut out for them. In (c), even more since there are now thousands of cases to work through, and in (d) we have shown an all-white box to suggest the idea of an "ocean" of instances which must be processed by these two threads. (d) is so hard that having two threads is not any better than having just one thread -- the problem is too large to be solved in any reasonable amount of time whether you have 1, 2, 8, 16, etc. threads.
Parallelism and randomization
Consider the following diagrams:
In (a) and (b), we see that we have 8 threads. On each time step, we can process 8 boxes (8 instances of the problem). Notice that we need to keep track of which boxes have been processed and which have not, otherwise, we will end up duplicating effort which defeats the whole purpose of employing parallelism.
The problem with this tracking is that it may require communication between the threads (which introduces overhead and reduces the amount of achievable speed-up) or, at least, we must specially design the algorithm so that the threads will operate harmoniously.
For very large problems, however, this approach becomes a serious disadvantage so, if we can, we prefer to randomize the problem instances, as shown in (c) and (d). At each time step, each available thread simply chooses a random box and processes it. If there are a sufficiently large number of boxes, there will only be a modest amount of duplicated effort.. the losses from duplication may be significantly lower than the costs of coordination would be. (e) shows the result after many time steps of randomized processing... each of the available 8 threads will have processed some number of boxes in random order, as shown. The empty boxes show one of the drawbacks of randomization -- processing the last few items by random order is slow and inefficient, so randomization is best suited to problems where the solution is almost always found "early". Search, for example, is a problem that is well suited to randomization and this is one of the ways that large-scale search (such as web-search) is organized.
The conceptual quantum advantage
As you can see from the illustrations above, we haven't really reduced the amount of effort of computing that must be done to solve a problem. We have sped up the computation but only at the cost of throwing an equivalent duplication of resources at it. We can speed up the computation by a factor of 10... but that also requires us to build 10 computers and make them all work on that problem in parallel. We've identified some clever tricks, such as randomization, to reduce communication overhead in parallel systems, but we haven't actually reduced the raw amount of work that must be done. All the computation that would have to be done by one thread, had to be done by our 8 threads -- it just completed 8 times faster.
The idea of quantum computing is that we want to do "many things at once" where we mean truly "at once" by one thread or "one qubit", rather than by dividing the problem up into many small pieces and harnessing countless computing units to do exactly the same amount of work, in parallel, instead of serially.
Consider the following diagram:
Here, we have shown 8 classical threads on the left doing 8 units of work. On the right, we have shown 8 qubits but some kind of "spread out color pattern" surrounding those qubits. I want to emphasize this is a purely artistic depiction and does not correlate to the underlying reality of quantum computing. But it captures the essence of what we want to do. Instead of solving large-scale problems with large-scale amounts of computing resources, we want to solve large-scale problems using a modest amount of computing resources that are somehow "spread out" across the entire problem space, in a smart way. And, to an approximation, that is what quantum computers are doing. If we regard the grid in the diagram above as a map of the "state space" of our problem, the quantum computer is exploring through a broad portion of the entire state space, instead of just exploring 8 discrete points in the state-space at a time, as an 8-thread parallel computer would.
So, here's the punchline:
Nature computes in parallel -- everywhere, all the time
Consider this neat little demonstration:
Notice he says at one point, "It's like it's trying all possible paths at once, by air-pressure." This is the key insight that debunks 99+% of the claims being made about quantum computers. There's nothing super-duper-special about what a quantum computer is doing, versus other physical systems. Everything in our world is "trying all paths at once"! Classically!!
Notice that, if you were to physically build the system depicted here, the moment you release the weight and let it hang freely, the weight p (and all the intervening forces on the pulleys) will be computed effectively "instantly", and you could measure this by hooking up force meters to measure the various forces involved. Yes, the tension along the rope will propagate at something like the speed of sound but that's not the point, as far as we're concerned, that is instantaneous. Nature is computing in parallel, everywhere, all the time. Classically, as well as "quantumly". Quantum mechanics has no special, super-extra parallelism[1].
As per the disclaimers I gave in the opening, this doesn't mean there is no difference between classical and quantum systems. However, from a computational standpoint, we can absolutely think of qubits as a "limiting case" of analog computing systems that are trying "all possible paths at once". There are countless ways to build such systems and they do not have to be bespoke to every problem you want to solve (there are general-purpose models for analog computation, if you are sufficiently exact as to what you mean by "general-purpose".)
Quantum computing (hype) is total bullshit!
---
[1] - This claim, in particular, is where the topic becomes technical. For anyone interested, my argument to support this point is based on encoding computational states in an analog system and then using arbitrarily high-precision measurements (beyond what is physically attainable) to achieve the same kind of "exponential parallelism" that quantum theory achieves. Essentially, this is a reductio argument to show that quantum theory is cheating by simply positing these exponential number of parallel universes which it also explicitly tells us we can't observe. In other words, it's a mathematical swindle. This criticism has nothing to do with quantum physics itself, and has everything to do with the overlap of computation and quantum physics. If you can shuffle bits around into parallel universes simply by positing an exponential number of such unobservable universes, then so can I. I am just using a different encoding and a different physical substrate (classical, instead of quantum).
Last edited:
