Quantum computing will not rescue Moore’s Law

I found this video on quantum computing educational.  It confirmed some things that I’ve been pondering about quantum computing for a while, notably its limitations, which are discussed after about the five minute mark.

The strength of quantum computing is that it makes use of superpositions, the fact that quantum particles can be in multiple states at the same time.  But it’s always bothered me that superpositions disappear as soon as we try to determine what they contain (or, if you’re an adherent of the many-world interpretation of quantum mechanics, they spread to us in such a way that “we” only have access to one of the superposition branches).

It was fellow blogger Disagreeable Me who explained to me, and this video confirmed, that the way to think of quantum computing is as of a type of double slit experiment, but in the shape of a logic circuit.  Quantum computing allows for much more complex logic circuits than classical computing.  But as soon as that circuit outputs its results, decoherence, the wave function collapse, the disappearance or spread of the superposition, or whatever we call it, happens, and all the data aside from that in the collapsed state, disappears.

This means that quantum computing is good for certain types of CPU bound processes, such as calculations, but not for I/O bound processes, which is most of computing.  It means that those who believe that Moore’s Law is some cosmic law of physics are going to be disappointed when classical computing eventually hits fundamental physical laws.  Science fiction authors and singularity enthusiasts shouldn’t expect quantum computing to ride in and provide infinite computing power.

Of course, no one knows when Moore’s Law is going to end.  Experts seem to place it somewhere between 5 and 30 years.  I suspect we’ll only know about the end in retrospect years after we’ve hit it.  It won’t mean the end of progress in computing power, but it will mean that future gains past that point will be much harder, requiring alternate architectures.

This entry was posted in Zeitgeist and tagged , , , , , , , . Bookmark the permalink.

23 Responses to Quantum computing will not rescue Moore’s Law

  1. Brett says:

    That’s why we’re seeing the trend towards greater Cloud Computing, isn’t it?. If you’ve got to experiment with new architectures and ever-increasing numbers of processors woven in parallelism, it makes sense to do that with massive server farms with greater budgets than your average PC owner – at least if you have the speed of connections to do so, and we do with broadband.

    Liked by 1 person

    • I agree that cloud computing offers a lot more opportunities for experimental architectures. It also is likely to be the only place we see quantum computing for a while.

      What’s interesting though, it that a lot of what is labelled “cloud computing” is actually better thought of as cloud distribution and activation. Adobe Cloud and Office 365 have users download applications to their local device for the best experience. And mobile apps still execute on the local device. In all these cases, the storage often gets synced up into the cloud, which gives the illusion that everything is happening there.

      It will be interesting to see how these architectures change once miniaturization hits its fundamental limits.

      Liked by 1 person

  2. Steve Morris says:

    Quantum computing has incredible potential for solving certain types of problems. But for other kinds of problems it doesn’t offer a way forward. Perhaps specialised forms of architecture for different kinds of computing will be the future. A current trend in mobile computing is an 8-core processor: 4 fast cores for hard work and 4 slower ones that use less battery power. The system can choose which assets to use to optimise performance.

    Like

    • Hmmm. I didn’t know that, but it makes sense.

      I could see us having, before we hit fundamental limits, chips with thousands of cores. We’ll have massive parallel clusters running inside our phones.

      Like

  3. bhatmahesht says:

    Quantum computing may not be useful in many normal uses but as they are good in handling complex logic they might be good with machine learning and artificial intelligence related computing. They might be good in dealing with large amounts of data which is read in large chunks at a time. I am just hoping quantum computing and cloud computing together will extend moore’ s law for more than next 5 years.

    Liked by 1 person

    • I’d be interested in knowing how it could deal with large amounts of data. That strikes me as something inherently likely to cause decoherence, since it usually involves a lot of I/O. Even if all the data is held in RAM, it would be I/O from the processor’s point of view. Maintaining superposition across all those sub-systems seems like a long shot.

      But maybe I’m missing something? (I did totally miss before that a logic circuit could exist entirely in superposition.)

      Like

      • Wyrd Smythe says:

        I seem to recall reading QC might have some utility in searching indexes quickly. The idea being to somehow load all the index records in superposition and have the waveform collapse on the record being searched for.

        I think it was highly speculative. 😀

        Liked by 1 person

  4. Wyrd Smythe says:

    Comparing a qubit to the two-slit experiment is a really good way to put it! I didn’t realize people thought quantum computing would get around Moore’s. It’s certainly never been put forth as such. (Although I have heard we need quantum-level devices to keep climbing the curve. We’re already using quantum effects in hard drives. They’re working on atom-sized transistors.)

    One thing I’ve read is that quantum computing can easily solve factoring problems (finding the factors of large numbers), and if so, QC would invalidate most of modern encryption, since the basis of most encryption is the difficulty of factoring large prime numbers. The common RSA public-key encryption standard could become trivially crackable.

    AIUI, QC will not solve NP problems any better than regular computers. Computational intractability is computational intractability, and quantum won’t help (just like massive parallelization doesn’t help). Nor, obviously, would they put a dent in Turing’s Halting Problem, since that’s another one of those “even in principle” things.

    OTOH, QC might be good at providing answers to problems that involve long series of convergent calculations (e.g. like calculating pi, maybe?). QC has the potential to “calculate” like mother nature does. Using digital computers, chaos theory makes it intractable to precisely solve orbital dynamics for more than two bodies, but the solar system itself does it with ease. (Well, actually I don’t know about the “with ease” part… maybe it finds it really hard.)

    QC might, similarly, behave more like an analog system seeking a least free energy level than an abacus device manipulating number strings. The idea, in all cases, being that the wave function collapses on the right answer given the full superposition of possible answers to consider.

    Like

    • Thanks Wyrd. I mostly agree across the board.

      I don’t know any computer scientists who assert that QC will rescue Moore’s Law, but some science fiction authors seem prone to use “quantum computing” as a card to imagine infinite computing. And I’ve read singularity proponents who cite it as rescuing Moore’s.

      I’m not sure about chaos theory and complex systems. It seems like you’d need a lot of I/O, with the associated wave function collapses, to successfully model them. Having quantum circuits might get you a lot closer, but I’m not sure we could eliminate the inherent chaos in those systems. But I’ll totally admit to not being an expert in this area.

      Like

      • Wyrd Smythe says:

        “It seems like you’d need a lot of I/O,…”

        If you mean that would be slow, I agree. It’s mentioned in the video that quantum computers wouldn’t have faster operations than digital — in fact, the individual operations will likely be slower. The power comes from what one operation can do. If you have a superposition that represents your entire answer domain, a single collapse to an answer represents tons of operations on a digital computer to calculate that answer.

        It’s true that chaos can’t be defeated at the input. Taking measurements and entering numbers into any computer introduces that tiny error that ends up screwing you. But in a digital computer, you’re also screwed at every calculation step along the way, since every answer you calculate has a finite length.

        QC allow the calculations to be effectively analog, as a superposition between two orthogonal states contains an infinite number states. The math describing what quantum computers do is in the real domain. Note, for example, your video at 1:42. Or the graphic at 3:00. It doesn’t make it clear, but alpha, beta, gamma, and delta, would all be real values. So there is some potential for QC to calculate at an analog level (like nature does, and QC has much more in common with nature than DC does).

        (Remember that chaotic systems are fully determined. They are only computationally intractable, and that comes from the need to enter data as, and to calculate using, finite numbers.)

        ((Not to overly defend QC’s ability to deal with chaos. I mainly raised chaos to contrast digital systems from natural analog systems. QC is more like — but not exactly like — the latter, and that offers opportunities DC doesn’t.))

        Like

        • By I/O, I was more meaning that the quantum logic circuit would have to interact with its environment, limiting how much can actually happen before things decohere. Of course, that circuit could still do things simultaneously in a way no classic circuit could.

          On the determinism of complex systems, I’m a bit more epistemically cautious. They may be deterministic in principle. (Although the phrase “deterministic in principle” is a bit too metaphysical for me.) Or it’s possible that quantum effects could “bleed” into what we think of as the deterministic layer of reality; if it happens within the uncertainty of our measurements, it seems difficult to rule out.

          No worries on QC and chaos theory. I’m really just thinking collaboratively rather than debating.

          Like

          • Wyrd Smythe says:

            “By I/O, I was more meaning that the quantum logic circuit would have to interact with its environment, limiting how much can actually happen before things decohere.”

            Oh, I see what you’re saying. You’re right, one of the problems they’re trying to solve in QC is maintaining coherence long enough for the computer to be useful. A lot of the speculation about what QC can do assumes we solve the coherence problems (and then figure out how to design logic circuits and write QC algorithms — QC is probably more in infancy than AI is).

            AIUI (and I certainly may not), the idea is to create a quantum state where the value domain is the problem domain. The quantum state contains all possible answers, and the trick is setting it up so it collapses on the one(s) sought.

            Imagine a quantum state containing all possible factors to some large number. For many numbers, there would be a number of high probability answers representing the various factors. But for a number that’s the product of two primes (such as used in encryption), there would be only two.

            Maybe the way this works practically is that the quantum state is prepared many times and its collapse is observed and recorded. (Think how the two-slit pattern builds as more and more particles are fired.) A pattern develops showing the high-probability answers.

            A number with many factors ends up with many “bright spots” whereas an encryption key would have only two.

            So instead of a run of unknown (unpredictable) billions of CPU cycles calculating with factorization numbers (the difficulty of which is exactly what makes encryption useful), you have a process of known (comparatively extremely short) time where the numbers pop out like water seeking a level (in a least-free energy process that’s similar).

            To your point on determinism, yeah, quantum uncertainty does throw a monkey wrench into the machinery. It’s one thing to say that the mathematical models of a system are fully deterministic, but the physical system itself has to be subject to uncertainty.

            When people say chaotic systems are fully determined they mean there is no randomness in the mathematical model, and I suspect that’s to counter a common popular misunderstanding that chaos theory involves randomness. It doesn’t. Chaos theory is about the intractable computational issues.

            To continue the collaboration, I’ve been saying for a long time that we don’t see quantum effects in the macro world, so it’s hard to see exactly where uncertainty actually affects anything. Chemical and mechanical processes seem fully determined. (Which poses a problem for dualists in theory of consciousness. Where does free will come from?)

            One response is that solar fusion requires quantum tunneling, so without quantum effects, stars wouldn’t work. I’ve hard a hard time connecting that to determinism in the general sense, though.

            But I never realized that magnetism is a quantum phenomenon. Magnetism is a place the quantum world shows itself in the macro world. And magnetism seems to affect a lot of things in life, so maybe that’s one place quantum weirdness enters the Big Leagues.

            You can read the linked article, but here’s the summation:

            “The existence of magnetism is a visible manifestation of quantum mechanics. It cannot be understood without the Pauli exclusion principle, or without thinking about the electron spin. So if magnets feel a little bit like magic, that’s partly because they are a startling manifestation of quantum mechanics on a human-sized scale.”

            Interesting food for thought!

            Liked by 1 person

          • Steve Morris says:

            Chemistry is a quantum phenomenon!

            Liked by 1 person

          • Wyrd Smythe says:

            My understanding is that while there is a quantum description of chemistry, there is also a classical one involving valence electron interaction — that QM isn’t required to describe chemical interactions. (Obviously QM underlies anything to do with matter or energy, so it’s part of the picture in some fashion.)

            I’d think that has to change when you get into nuclear chemistry. Radioactive decay seems pretty quantum to me! (I get a kick out of how so many science books, no matter how detailed their descriptions of the other forces, when it comes to the weak force just say, “it’s involved in radioactive decay,” and then move on hoping no one asks any questions. 🙂 )

            Liked by 1 person

          • Wyrd Smythe says:

            As usual, xkcd has a comic that nails it:
            http://xkcd.com/1489/

            Liked by 1 person

          • Things should be as simple as possible, but no simpler. –Einstein (paraphrased to make it simpler 🙂 )

            Liked by 1 person

          • Steve Morris says:

            The weak force is tricky! It challenges our classical idea of what a force is. We tend to think that a force is an invisible hand that pushes or pulls. In quantum field theory, a force is regarded as an interaction between two particles, mediated by a virtual particle. In the case of the weak force, it’s the W and Z bosons that are exchanged. Because the W has an electric charge, it changes a quark from one type to another when it is exchanged, and this is the mechanism responsible for radioactive beta decay. There is also a push/pull effect, but it is minuscule.

            Was that better than mumble mumble? 🙂

            Liked by 2 people

          • Steve Morris says:

            As for chemistry, I don’t think you can even have the concept of electrons in orbits without QM. Certainly, classical EM theory says that atoms are impossible. But I suspect that Mike is looking for an example of the randomness aspect of QM at work, rather than its quantized nature. For this, radioactive decay is an obvious example that can be observed in a macroscopic world. But there are many, many real-world objects that can only be explained by QM – transistors, for instance.

            Liked by 2 people

          • Wyrd Smythe says:

            @Steve Morris

            “Was that better than mumble mumble?”

            Definitely! One wonders why so many authors don’t go at least that far. Or mention how instrumental the weak force is in solar fusion!

            “As for chemistry, I don’t think you can even have the concept of electrons in orbits without QM.”

            Understood. Absolutely. But I believe (non-nuclear) chemical interactions can be fully described without QM. More to the point…

            “But I suspect that Mike is looking for an example of the randomness aspect of QM at work, rather than its quantized nature.”

            I think it’s me that you mean, and, yes, that’s exactly what I meant. I mentioned before that anything to do with matter or energy is quantized, but the question here is how QM’s collapsing wave function “randomness” (which we believe to be the only true randomness — at least from our perspective) connects with macro processes.

            There is pragmatically unpredictable (possible but extremely difficult), effectively unpredictable (possible only in principle, impossible in practice), and genuinely unpredictable (impossible even in principle).

            Chaotic systems are thought to be effectively unpredictable, but quantum systems are genuinely unpredictable. A question that fascinates me is whether the universe is genuinely unpredictable (per QM) or just effectively so due to being only classical behavior at the macro level.

            To mix metaphors, my Holy Grail is a smoking gun where QM clearly affects the macroverse making it genuinely unpredictable. I’ve never found anything convincing, but magnetism has some interesting possibilities.

            Liked by 1 person

          • Steve Morris says:

            I would say that the universe is practically predictable at large scales, and that uncertainty (of any type) arises only when we probe more deeply. Once we reach high energies or small length scales, then everything is genuinely unpredictable. I can’t think of any phenomenon where that unpredictability upscales, but that’s just off the top of my head.

            I’m not sure why you think magnetism is unpredictable.

            Like

          • Wyrd Smythe says:

            I don’t know that it is. It’s that magnetism requires me to modify a long-time statement to the effect that we don’t ever directly observe quantum effects.

            That’s a statement that’s been increasingly iffy, anyway. You mentioned transistors, and hard drives now use quantum effects to store data. We don’t exactly see the randomness (although, for example, which electrons “tunnel” is random).

            These all (including magnetism) seem to behave classically at the macro level. My search continues, but magnetism is interesting for being a macro quantum effect.

            Liked by 1 person

  5. Steve Morris says:

    OK, here’s a macro phenomenon that is definitely quantum mechanical at its roots – superfluids.

    Like

    • Hmmm. Isn’t that a phenomenon that only happens near 0 Kelvin? It reminds me of the current necessity that quantum logic gates operate at those temperatures. It makes sense if you think about it, since temperature is basically the sum kinetic energy of particles bouncing around, causing wave function collapses with every collision.

      Like

Your thoughts?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s