The promise of quantum computing?

Anyone who follows the computing industry knows that Moore’s Law, the observation that computing power doubles every couple of years, has been sputtering in recent years.  This isn’t unexpected.  Gordon Moore himself predicted that eventually the laws of physics would become a constraint.

One of the technological hopes for a revival is quantum computing.  Quantum computing depends on qubits, quantum bits, which like classical bits can be 1 or 0, but can also be in a quantum superposition of both 1 and 0 simultaneously.  When entangled with other qubits, the number of states a quantum system can hold increases exponentially, far in excess of what a classical system can hold.  In principle, a 300 qubit processor can hold more information than there are elementary particles in the observable universe.

When you read these types of projections, it’s easy to see why many people think quantum computing will have near infinite performance and capacity.  An array of qubits allows for an enormous range of possible answers to be computed in parallel.

That’s the common description you see in the popular press.  It used to leave me pretty confused, since it was clear that something was missing.  Eventually, for a computation to be of any use, you have to access the result, that is, perform a measurement on the qubit, and when you do, it randomly collapses into one classical state.  And under the rules of quantum physics, there’s no guarantee that the right answer will “win”.

As theoretical computer scientist Scott Aaronson makes clear in this podcast interview by Sean Carroll, you can’t just run a gigantic range of possible answers in parallel.  Your quantum circuitry has to find a way to promote the right answer, that is, make it the most probable one that will be the outcome of the measurement, and this has to be done without knowing in advance what that right answer will be.  A heavy burden that deflates things a bit.

He also makes it clear that while the range of problems quantum computing can solve is expected to be broader than what classical systems can solve (such as possibly using Shor’s algorithm to break RSA encryption), it doesn’t mean they will be able to solve every problem that a classic system can’t.  There remain a class of problems that are expected to be unsolvable, except through brute force methods that, in some cases, may take longer than the heat death of the universe.

There are also a host of implementation issues that complicate everything.  Quantum circuits must be kept isolated from the environment to keep them from decohering, which has turned out to be a major challenge.  And these systems are unavoidably more stochastic, and so have higher error rates, requiring a lot more error correction circuitry than classical systems.

Still, quantum computing does seem to hold a lot of promise.  For a long time, I was leery of those promises, not sure if it wouldn’t get stuck in the same development hell that fusion technology seems to be in.  But with Google’s recent success, it seems like there’s reason for cautious optimism, that the universe may actually allow us to do this.  It may open up new possibilities, ones that may be hard for us to imagine right now.

So, lots of potential, just not magical ones.

Unless of course I’m missing something.

25 thoughts on “The promise of quantum computing?

  1. I would bet that once a few pretty-versatile quantum computers are built, scientists and engineers will find more uses for them. They can be pretty clever about matching the available tools to the outstanding problems. In this case, finding ways to structure the computation so that right answers will survive the process(ing) while wrong ones are filtered out.

    Liked by 2 people

    1. Oh, I don’t doubt it. That’s why I said the technology does have a lot of potential. If they ever figure out a way to do it at room temperature, I can imagine all of our phones and other computers eventually having a quantum sub-processor, which handles tasks conducive to its advantages, speeding up the whole system.

      Liked by 1 person

    1. I can’t claim my own grasp is rock solid, but someone once told me to think of it as using a series of double slit experiments in a sequence.

      So, imagine a regular double slit experiment. We shoot the particle at the slits. It can take one of two possible paths. (Let’s ignore the ones that crash into the barrier.) Now, instead of having a screen at the back, let’s set up another double slit, so two in a row. The particle can now take 4 possible paths (2^2). If we put ten of these in a role, then the particle can take (2^10) possible paths. And remember, until it hits the final back screen and decoheres / collapses, it takes all the paths; it just collapses to one at the end.

      Now, instead of double slits, let’s imagine a series of particles held in some kind of matrix. We perturb the first, which has a chance of going into spin up or spin down. It then perturbs the next, with a dynamic very similar to the series of double slits.

      Finally, let’s arrange these particles in such a way that they form logic gates. Now we have multiple paths of logic, all happening concurrently.

      As I noted in the post, that’s the easy part. The problem is that all of these paths are being taken, but which is the right one? The circuitry need to promote the final correct answer. I won’t claim to understand how that’s done, but I can imagine it being doable, at least for predefined logic patterns, which is what most logic circuits are. It’s just the combinations we use them in that give us flexibility.

      I don’t know if any of that helps. I’m sporadically doing my own reading on this, but it requires linear algebra, and math isn’t my strong suit. But I’m hoping to eventually have a firmer grasp.

      Liked by 2 people

  2. My uneducated impression was that quantum computers were going to be awesome for certain classes of problems, like encryption/encryption breaking, as opposed to general purpose computing. While it’s possible that the tech will eventually get into phones, I think that’s farther off than my bet for the next thing that will continue the acceleration of computing power, which is the memristor and neuromorphic chips.

    *

    Liked by 4 people

    1. Could be. I can see neuromorphic computing helping, but similar to quantum computing, there will be things it’s good at and things it isn’t. The nice things about it is that it holds the promise of far more efficient power usage, and higher data density, both which may open a lot of doors.

      Liked by 2 people

  3. I think you covered it pretty good. It’s not computational magic; some problems are still out of reach or even undecidable even in principle.

    Once QC gets working, it’s main value is likely to be simulations of quantum, atomic, or molecular, systems. That’s a particular bailiwick for it.

    There’s Shor’s algorithm, which will kill RSA, but we have other encryption that doesn’t depend on factoring large numbers. I’m not sure how much other value the factoring trick has. There’s also Grover’s algorithm which is essentially a search algorithm. The potential is being able to search lots of indexes in parallel.

    As you say, quantum computing is (only) good for problems that can be stated in terms of superposition, and for which one can develop a way to amplify the desired solution. It often requires multiple runs of the same problem to develop the most probabilistic answer.

    Liked by 1 person

    1. Thanks Wyrd. I do tend to think that innovative use of quantum algorithms, in a specialized processor within an otherwise classical system, could provide a substantial performance boost.

      But only if they can figure out a way for it to work at normal temperature ranges. It’s hard to see a near 0 Kelvin processor working in our cell phones.

      Like

      1. Do you have a class of computational problems on cell phones you feel QC would provide a substantial performance boost for? My understanding is that it provides no benefit for most conventional computing (browsing, watching videos, writing a post, etc). It’s only where the problem can be expressed as a superposition of possible answers that it shines (e.g. factoring numbers where it considers all possible numbers at once). (I think it might actually be slower for some forms of conventional computing.)

        One thing that strikes me is the possibility of quantum encryption. Either for secure communication or for data protection. Other than that,… hard to guess. Maybe something to do with very sensitive sensors?

        Like

        1. I don’t, and my understanding is very similar to yours. Most everyday computing is I/O bound, which doesn’t seem conducive to quantum computing.

          But I’m open to the possibility that it’s a failure of imagination on my part, not to mention lack of knowledge of all the ways the quantum algorithms we do know about might be worked in to various operations.

          I agree that encryption seems like a good candidate. There may be other CPU bound processes where a parallel approach, particularly a massively parallel approach, might provide a performance boost. Maybe.

          Like

          1. Yeah, I/O bound or just serial in nature. Only certain kinds of problems lend themselves to a parallel architecture, in large part due to their serial nature. “A” has to be calculated before “B” can, and “C” requires “B” and so on.

            Even highly parallel tasks (I’ve been thinking about the Mandelbrot wrt QC) don’t seem to lend themselves to the superposition parallelization of QC. The individual points aren’t related, which makes the problem trivially parallel, but which also means there’s no benefit to superposition. The calculations on each point are serial, so no benefit on a per-point basis.

            One should never second-guess the future, but it doesn’t seem like that much of a failure of imagination to think QC might have a restricted domain. A very important one for medical drug designers and quark physicists, but maybe not something that’s going to change our world.

            Unless QC turns out to be instrumental in computing consciousness! I think there is some chance of that, mainly in the fully simulating reality sense.

            Like

          2. Agreed on the future.

            The biggest issue I have with quantum consciousness is there’s nothing in the data motivating it. Along the lines of the post I did the other day, for me, that puts it in the loose speculation category. We can’t completely rule it out, but coupled with the warm wet noisy relatively unisolated environment of the brain, it doesn’t seem likely.

            Not that quantum computation happening in the brain wouldn’t be very interesting if it were found to happen in some way. It might provide crucial clues on how to do quantum computing at room temperature without expensive crystals.

            Like

          3. Crystals?

            When I wrote “mainly in the fully simulating reality sense,” I meant to go on to mention Stephenson’s novel Fall, in which quantum computers are used to simulate the entire virtual reality, including the brains.

            In this sense a brain, a tree, and a rock, are all quantum systems. They’re made from quantum stuff. Quantum computers will be able to simulate quantum systems, such as rocks, trees, and brains, just as quantum systems.

            It’s the ultimate reduction. Everything ultimately is quantum (or so our provisional theory goes). If one can simulate reality at the quantum level, one can simulate anything.

            If QC becomes as common as in Fall, simulations could include scanned brains (if we can scan brains at the quantum level) or constructed new brains built on principles we discover. This would be without reference to putative “quantum computing of consciousness” — no more so than for a rock or tree.

            Whether consciousness uses a form of computing that involves superposition and measurement exists at two levels: Firstly, in the direct computational sense that consciousness depends on the function of recognizable qbits. I agree no data suggests this.

            The second level is quantum effects contributing more subtly to consciousness. (This is kind of the Penrose-Hammeroff level, AIUI.)

            Along the lines of not second-guessing the future, we’re finding evidence of quantum effects in hot messy environments. I read recently about spin coupling among atoms in a hot gas. There is also a potassium molecule that apparently can remain coherent for a surprisingly long time in a biological environment. Photosynthesis is a quantum system. Even the behavior of water appears to depend on quantum effects.

            (Beyond just chemistry, I mean. All chemistry is quantum, but we’re so used to chemistry that no one really thinks about that anymore. The full behavior of water depends on quantum effects above and beyond the chemical quantum interactions of the electrons.)

            Keep in mind that an incoherent quantum environment is just incoherent to us trying to look at parts of it. The particles all interact at the quantum level. Their activity averages to a persistent macro object with no apparent wave behavior.

            We may not yet be able to recognize the quantum behavior lurking inside a collective object, but we’re starting to see signs that it might matter. To me it makes sense. If the world is ultimately quantum, why wouldn’t quantum effects matter?

            Like

          4. Certain types of crystals might be a substrate that could enable room temperature quantum computing, at least according to this study.
            https://www.sciencedaily.com/releases/2020/05/200501184307.htm

            The Stephenson scenario, which does seem to be a fairly common occurrence in science fiction, strikes me as being in the magical category. It’s similar to the conception used in Devs, which I enjoyed immensely, although not because I thought it was plausible. Although again, I’m open to there being a failure of imagination here on my part. Maybe we will be simulating entire universes in a few years. (Which seems like it would increase the probability that we ourselves are in one.)

            I’m becoming skeptical of quantum biology. All of the claims appear to be speculative. And what had seemed to be the most plausible, what in fact was often presented as fact in the popular press: photosynthesis, now seems questionable.
            https://gizmodo.com/are-plants-quantum-1842734189
            It seems like we need a lot stronger evidence.

            Like

          5. “The Stephenson scenario […] strikes me as being in the magical category.”

            I haven’t seen Devs but have heard it links to MWI. Fall doesn’t; it’s strictly a simulation of a (limited) virtual reality (an “island” surrounded by “ocean”).

            The only “magic” I’m aware of in the Stephenson scenario is that we don’t have large quantum computers, yet, and that defining the Hamiltonian for a virtual reality is probably beyond us for now. The idea that quantum computers can simulate reality is part of what makes them a big deal. Near term it’ll be limited to protons, atoms, molecules, but large scale simulations are mostly a matter of scope.

            “I’m becoming skeptical of quantum biology.”

            Becoming? 😀 😀

            As I said, chemistry is quantum, but we’re so used to chemistry we don’t think about it as quantum. Photosynthesis, in particular, is an electron transport mechanism, that is decided quantum in its behavior. (It used to amuse me to sit and look out over a field of peaceful sunlit grass and think about all the furious buzzing of electrons going on, if we could only see it.)

            Usually when people talk about “quantum whatever” they’re actually talking about explicit superposition/measurement behavior (which, at some level, is going on constantly in everything, but as the gizmodo article mentions, really, really fast). Usually people mean qbit behavior.

            There are quantum behaviors beyond superposition. Ultimately, everything is quantum. The interesting question is to what degree that behavior is responsible for the macro level. On some level, the answer has to be “entirely.”

            Like

          6. I’ll admit my earliest reactions were skeptical. I became less skeptical with the widespread reports implying it was a certainty in some areas. Jim Al-Khalili’s advocacy of it also somewhat eased that skepticism. But it’s increasing again.

            Certainly quantum mechanics is part of everything, from making a cup of coffee to how stars work. The macro level emerges from the quantum one, the more fundamental reality.

            What behavior beyond superpositions (and associated issues) are you interested in?

            Like

          7. I’m interested in how what we blithely refer to as the “macro” world emerges.

            If one discounts ontological emergence, then the macro world is something we perceive epistemologically. There actually is no such thing as the “macro” world any more than there’s really a “picture” on a computer monitor (rather than just a bunch of glowing RGB dots).

            I’m fascinated by how a macro world emerges from the quantum one.

            My thesis here is essentially a perception Nature has the full toolkit from quantum on up through all the emergent layers (atoms, molecules, chemistry, biology). To me the likely bet is She would use all the tools at Her disposal, especially when it comes to something as complicated as a brain.

            😀 I guess I’m the one being reductive here. I figure it’s always been quantum, so it must be, at least in part, still quantum (esp. in such a complex system). Everything on top of that is emergent, and where I think that might matter is in terms of simulations.

            It might not be possible to drive a consciousness simulation through new states without full knowledge of what’s going on at the quantum level. We can observe things at a higher level and try to derive laws regarding the behavior we see, but it’s possible we’ll find those laws inadequate when it comes to generating new mental states. (Kind of along the Westworld idea of a re-created consciousness decaying over time. New mental states over time, due to not including the low-level, will diverge from what’s intended. Essentially would diverge from coherent thought.)

            It’s similar to solving orbital problems. We start by reducing the problem to just the main bodies involved, and we reduce those to a series of two-body problems that we can solve. Then we converge on an answer. We end up with a really good approximation, but it’s just that, an approximation.

            So the question is whether an approximation works in a simulation. Knowing exactly how the “macro” world emerges would be important in figuring that out.

            Like

          8. I definitely think the universe is quantum. But as to exactly what that means for the macro world, it seems like decoherence theory is an important framework, but it may ultimately come down to which interpretation of QM you favor.

            For the brain and consciousness, for me, it comes down to what the data are currently telling us. Right now, I’m not seeing indications from even the most liberal neuroscientists in terms of consciousness theory, that quantum physics plays any role. (At least aside from the role it plans in all physics, both inside and outside of the brain.)

            On simulations, it seems clear that no simulation would do exactly what the original would do. The question is whether the variations can be reduced to the range of variations that already show up in the original.

            Like

          9. What is this “macro world” of which you speak? 😀

            Seriously, I do think understanding “decoherence” is the key to explaining how quantum behavior vanishes. I’ll reiterate that decoherence is relative to our desire to treat a system as a qbit. The phase information of the qbit is swamped by merging with phases of particles it interacts with, and the original phase of the qbit, which is also merged into all those interacting particles, is distributed. End result, it “vanishes” from our eyes.

            A drop of water in a bucket of water does change both the bucket water and the drop. But not much on either part.

            “The question is whether the variations can be reduced to the range of variations that already show up in the original.”

            I agree. I’m suggesting it’s possible they cannot be without reference to the lowest levels of the system.

            For instance, we know the myelin sheathing and glial cells play a role, so a model based just on neurons and synapses probably isn’t enough. Maybe the model needs more details about neurotransmitters or needs to account for the coupling of nearby neurons. Maybe aspects of blood flow are important.

            We don’t know how far down a simulation needs to go to keep it correct. Can we accurately model a plant without modeling photosynthesis? Can we model the brain accurately without reference to the molecular level? I seriously wonder.

            I do agree it doesn’t seem likely we’d need the atomic, let alone quantum, level, but I can see it’s possible. There are potential EMF considerations. There could be spin coupings between neurons… 🤷🏼‍♂️

            And I know everyone hates the idea, but maybe Hameroff and Penrose aren’t crazy and quantum behavior does have something to do with neuron signaling. (I read an article about a new understanding of how anesthetics work, and I wondered what impact that might have on Hameroff. Part of his foot in the door, so to speak, is the idea that we don’t really understand anesthetics, yet.)

            Like

          10. I think to build a successful simulation, we’d need to understand things at the molecular, genetic, protein, cellular, neural circuitry, and overall architectural levels. Those understandings would allow us to know where we can get by with a coarser grained treatment, where we have to go down lower, and where we might be able to substitute alternate mechanisms to produce equivalent effects.

            On Hammeroff and Penrose, actually a lot of people seem quite taken with their ideas. (I have a standing Google search for consciousness science, but had to explicitly exclude the word “quantum” from it because otherwise I get flooded with quantum consciousness hits.) What they lack isn’t popularity, but evidence, or even data to motivate their assumptions, which is why cognitive scientists generally don’t take them seriously.

            Like

          11. Heh, yes. By “everyone” I did mean cognitive scientists. 🙂

            If measuring a single photon can create new worlds, is it really that much of a stretch to think lots of quantum events in the brain might have some effect on its operation?

            Liked by 1 person

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.