Tag: quantum computing

The minimal effort explanation of quantum computing

Quantum computing is really complicated, right? Far more complicated than conventional computing, surely. But, wait. Do I even understand how my laptop works? Probably not. I don’t even understand how a doorknob works. I mean, I can use a doorknob. But don’t ask me to design one, or even draw a picture of the inner mechanism.

We have this illusion (it has the technical name in the illusion of explanatory depth) that we understand things we know how to use. We don’t. Think about it. Do you know how a toilet works? A freezer? A goddamn doorknob? If you think you do, try to explain it. Try to explain how you would build it. Use pictures if you like. Change your mind about understanding it yet?

We don’t use quantum computers so we don’t have the illusion we understand how they work. This has two side effects: (1) we think conventional computing is generally well-understood or needs no explanation, and (2) we accept the idea that quantum computing is hard to explain. This, in turn, causes us to try way too hard at explaining it.

Perhaps by now you are thinking maybe I don’t know how my own computer works. Don’t worry, I googled it for you. This was the first hit.

Imagine if a computer were a person. Suppose you have a friend who’s really good at math. She is so good that everyone she knows posts their math problems to her. Each morning, she goes to her letterbox and finds a pile of new math problems waiting for her attention. She piles them up on her desk until she gets around to looking at them. Each afternoon, she takes a letter off the top of the pile, studies the problem, works out the solution, and scribbles the answer on the back. She puts this in an envelope addressed to the person who sent her the original problem and sticks it in her out tray, ready to post. Then she moves to the next letter in the pile. You can see that your friend is working just like a computer. Her letterbox is her input; the pile on her desk is her memory; her brain is the processor that works out the solutions to the problems; and the out tray on her desk is her output.

That’s all. That’s the basic first layer understanding of how this device you use everyday works. Now google “how does a quantum computer work” and you are met right out of the gate with an explanation of theoretical computer science, Moore’s law, the physical limits of simulation, and so on. And we haven’t even gotten to the quantum part yet. There we find qubits and parallel universes, spooky action at a distance, exponential growth, and, wow, holy shit, no wonder people are confused.

What is going on here? Why do we try so hard to explain every detail of quantum physics as if it is the only path to understanding quantum computation? I don’t know the answer to that question. Maybe we should ask a sociologist. But let me try something else. Let’s answer the question how does a quantum computer work at the same level as the answer above to how does a computer work. Here we go.

How does a quantum computer work?

Imagine if a quantum computer were a person. Suppose you have a friend who’s really good at developing film. She is so good that everyone she knows posts their undeveloped photos to her. Each morning, she goes to her letterbox and finds a pile of new film waiting for her attention. She piles them up on her desk until she gets around to looking at them. Each afternoon, she takes a photo off the top of the pile, enters a dark room where she works at her perfected craft of film development. She returns with the developed photo and puts this in an envelope addressed to the person who sent her the original film and sticks it in her out tray, ready to post. Then she moves to the next photo in the pile. You can’t watch your friend developing the photos because the light would spoil the process. Your friend is working just like a quantum computer. Her letterbox is her input; the pile on her desk is her classical memory; while the film is with her in the dark room it is her quantum memory; her brain and hands are the quantum processor that develops the film; and the out tray on her desk is her output.

The real magic of quantum computing

By now you have read many articles on quantum computing. Congratulations. You know nothing about quantum computing.

There is a magician on stage. It’s tense. Maybe it’s a primetime TV show and the production value is super high. The celebrity judges look nervous. There is epic build up music as the magician calls their assistant on stage. The assistant climbs into a box that is covered with a velvet blanket. Why a blanket? I mean, isn’t the box good enough? What a pretentious as… forget it, I’m ruining this for myself. OK, so the assistant is in the box with their head and legs sticking out. What the fuck? Who made this box, anyway? Damn it, I’m doing it again. Then—oh shit—is that a saw? What’s going to happen with that? Fuck! No! The assistant’s been cut in half! And then the quantum computer outputs the answer. Wait, what? Where did the quantum computer come from? I don’t know—quantum computing is magic like that.

By now you have read many articles on quantum computing. Congratulations. You know nothing about quantum computing. I know what you are thinking: Whoa, Chris, I wasn’t ready for these truth bombs. Take it easy on us. But I see a problem and I just need to fix it. Or, more likely, call the rental agent to fix it.

You probably think that a qubit can represent a 0 and a 1 at the same time. Or, that quantum computing takes advantage of the strange ability of subatomic particles to exist in more than one state at any time. I can hardly fault you for that. After all, we expect Scientific American and WIRED to be fairly reputable sources. And, I’m not cherry picking here—these were the first two hits after the Wikipedia entry on a Google search of “What is quantum computing?” Nearly every popular account of quantum computing has this “0 and 1 at the same time” metaphor.

I say metaphor because it is certainly not literally true that the things involved in quantum computing—those qubits mentioned above—are 0 and 1 at the same time. Why? Well, for starters, 0 and 1 are defined to be mutually exclusive (that means it’s either one OR the other). Logically, 0 is defined as [NOT 1]. Then 0 AND 1 is equal to [NOT 1] AND 1, which is a false statement. “0 and 1 at the same time” just doesn’t make sense, and it’s false anyway. Next.

OK, so what’s the big deal? We all play fast and loose with words. Surely this little… let me stop you right there, because it gets worse. Much worse.

The Scientific American article linked above then deduces that, “This lets qubits conduct vast numbers of calculations at once, massively increasing computing speed and capacity.” That’s a pretty big logical leap, but I’d say it’s a correct one. Let’s break it down. First, if a qubit can be 0 and 1 at the same time then two qubits can be 00 and 01 and 10 and 11 at the same time. And three qubits can be 000 and 001 and 010 and 011 and 100 and 101 and 110 and 111 at the same time. And… well, you get the picture. Like mold on that organic bread you bought, exponential growth!

The number of possible ways to set some number of bits, say n of them, is 2n—a big number. If n = 300, 2300 is more than the number of atoms in the universe! Think about that. Flip a coin just 300 times and the number of possible ways they could land is unfathomable. And 300 qubits could be all of them at the same time. If you believe that, then it is easy to believe that quantum computers will just calculate every possible solution to your problem at once and pick the right answer. That would be magic. Alas, this is not how quantum computers work.

Lesson 1: don’t take a bad metaphor and draw your own simplistic conclusions from it.

Try this one out from Forbes: “A bit can be at either of the two poles of the sphere, but a qubit can exist at any point on the sphere.” Spot on. This is 100% accurate. But, wait! “So, this means that a computer using qubits can store an enormous amount of information and uses less energy doing so than a classical computer.” The fuck? No. In fact, a qubit cannot be used to store and retrieve more than 1 bit of data. Again, magic, but not how quantum computers work.

Lesson 2: don’t reduce an entire field to one idea and draw your own simplistic conclusions from it.

I can just imagine what you are thinking right now. OK hotshot, how would you explain quantum computing? I’m glad you asked. After bashing a bad analogy, I’m going to use another, better analogy. I like analogies—they are my favorite method of learning. Teaching by analogy is kind of like being in two places at the same time.

Alright, I’m going to tell you the correct analogy between quantum physics and magic. Let’s think about what a magic trick looks like abstractly. The magician, who is highly trained, spends a huge amount of time choreographing a mechanism which is then hidden from the audience. The show begins, the “magic” happens, and we are returned to reality with bafflement. If you are under 20, then you also take a selfie for the Insta #fuckyeahmagic.

Now here is what happens in a quantum computation. A quantum engineer, who is highly trained, spends a huge amount of time choreographing a mechanism which is then hidden from the audience. The show begins, quantum computation happens, and we are returned the answer to our problem. Tada! Quantum computation is magic. Selfie, Insta, #fuckyeahquantum.

Let’s dig into this a bit deeper, though. Why not uncover the quantum computer—open the box—to reveal the mechanism? Well, we can’t. If we “watch” the computation happen, we expose the quantum computer to an environment and this will break the computation. The kind of things a quantum computer needs to do requires complete isolation from the environment. Just like a magician’s trick, if we reveal the mechanism, the magic doesn’t happen.

OK, fine. The “magic” will be lost, but at least I could understand the mechanism, right? Sure, that’s right. But here’s the catch: a magician spends countless hours training and preparing for the trick. Knowing the mechanism doesn’t help you understand how to actually perform the trick. Nor does seeing that the mechanism of quantum computing is some complicated math actually help you understand how it works. And don’t over simplify it—we already know that doesn’t work.

Let’s look at the example of a sword swallowing illusionist. If you don’t know what I’m talking about, it’s exactly how it sounds—a person puts a sword the length of their torso in their mouth down to the handle. How one figures out they have a proclivity for this talent, I don’t want to know. But what’s the explanation? Don’t worry, I already googled it for you, and it’s simple: “the illusionist positions their head up so that his throat and stomach make a straight line.” Oh, is that it? I’m suddenly unimpressed. So now that you too know how to swallow a sword are you going to go and do it? I fucking doubt it. That would be stupid—about as stupid as reading a few sentence description of some “explanation” of quantum computing and then declaring you understand it.

Lesson 3: don’t place your analogy at the level of explanation—place it at the level of the phenomenon. Let your analogy do the work of explanation for you.

If you like figures, I have prepared a lovely summary for you.

Well there you go. Quantum computing isn’t magic, but it can put on a good show. You can learn about how to do the tricks yourself and even perform a few with a little more effort. I suggest starting with the IBM Quantum Experience. Or, start where the real magicians do with Quantum Computing for Babies 😂

New papers dance!

Two new papers were recently posted on the arXiv with my first two official PhD students since becoming a faculty member! The earlier paper is titled Efficient online quantum state estimation using a matrix-exponentiated gradient method by Akram Youssry and the more recent paper is Minimax quantum state estimation under Bregman divergence by Maria Quadeer. Both papers are co-authored by Marco Tomamichel and are on the topic of quantum tomography. If you want an expert’s summary of each, look no further than the abstracts. Here, I want to give a slightly more popular summary of the work.

Efficient online quantum state estimation using a matrix-exponentiated gradient method

This work is about a practical algorithm for online quantum tomography. Let’s unpack that. First, the term work. Akram did most of that. Algorithm can be understood to be synonymous with method or approach. It’s just a way, among many possibilities, to do a thing. The thing is called quantum tomography. It’s online because it works on-the-fly as opposed to after-the-fact.

Quantum tomography refers to the problem of assigning a description to physical system that is consistent with the laws of quantum physics. The context of the problem is one of data analysis. It is assumed that experiments on this to-be-determine physical system will be made and the results of measurements are all that will be available. From those measurement results, one needs to assign a mathematical object to the physical system, called the quantum state. So, another phrase for quantum tomography is quantum state estimation.

The laws of quantum physics are painfully abstract and tricky to deal with. Usually, then, quantum state estimation proceeds in two steps: first, get a crude idea of what’s going on, and then find something nearby which satisfies the quantum constraints. The new method we propose automatically satisfies the quantum constraints and is thus more efficient. Akram proved this and performed many simulations of the algorithm doing its thing.

Minimax quantum state estimation under Bregman divergence

This work is more theoretical. You might call it mathematical quantum statistics… quantum mathematical statistics? It doesn’t yet have a name. Anyway, it definitely has those three things in it. The topic is quantum tomography again, but the focus is different. Whereas for the above paper the problem was to devise an algorithm that works fast, the goal here was to understand what the best algorithm can achieve (independent of how fast it might be).

Work along these lines in the past considered a single figure of merit, the thing the defines what “best” means. In this work Maria looked at general figures of merit called Bregman divergences. She proved several theorems about the optimal algorithm and the optimal measurement strategy. For the smallest quantum system, a qubit, a complete answer was worked out in concrete detail.

Both Maria and Akram are presenting their work next week at AQIS 2018 in Nagoya, Japan.

Quantum computing worst case scenario: we are Lovelace and Babbage

As we approach the peak of the second hype cycle of quantum computing, I thought it might be useful to consider the possible analogies to other technological timelines of the past. Here are three.

Considered Realism

We look most like Lovelace and Babbage, historical figures before their time. That is, many conceptual, technological, and societal shifts need to happen before—hundreds of years from now—future scientists say “hey, they were on to something”.

Charles Babbage is often described as the “father of the computer” and he is credited with inventing the digital computer. You might be forgiven, then, if you thought he actually built one. The Analytical Engine, Babbage’s proposed general purpose computer, was never built. Ada Lovelace is credited with creating the first computer program. But, again, the computer didn’t exist. So the program is not what you are currently imagining—probably, like, Microsoft Excel, but with parchment?

By the time computing began in earnest, Lovelace and Babbage were essentially forgotten. Eventually, historians restored them to their former glory—and rightfully so as they were indeed visionaries. Lovelace anticipated many ideas in theoretical computer science. However, the academic atmosphere at the time lacked the language and understanding to appreciate it.

Perhaps the same is true of quantum computation? After all, we love to tout the mystery of it all. Does this point to a lack of understanding comparable to that in computing 200 years ago?

This I see as the worst case scenario for quantum computation. We are missing several conceptual—and possibly societal—ideas to articulate this thing which obviously has merit. Eventually, humanity will have a quantum computer. But, will that future civilisation look at us as their contemporaries or a bunch of idiots mostly interested in killing each other while a few of our social elite played with ideas of quantum information?

Cautious Optimism

We are on the cusp off a quantum AI winter. We’re in for a long calm before any storm.

This is probably where most academic quantum scientists sit. We’ve seen 10-year roadmaps, 20-year roadmaps, even 50-year roadmaps. The truth is that every “scalable” proposal for quantum technology contains a little magic. We really don’t know what secret sauce is going to suddenly scale us up to a quantum computer.

On the other hand, very very few scientists believe quantum computing to be impossible—it’s going to happen eventually. At the same time, most would also not bet their own money on it happening any time soon. And, if most scientists are correct, the hype doesn’t match reality and we’re headed for a crash—a crash in funding, a crash in interest, and—worst of all—a crash in trust.

Some would argue that there are too many basic science questions unanswered before we harness the full potential of this theory that even its practitioners continue to call strange, weird, and counterintuitive. The science will march on anyway, though. Memes with truth and merit have a habit of slow and steady longevity. The ideas will evolve and—much like AI—eventually become mainstream, probably in our lifetime.

Unabated Opportunism

We will follow the same steady forward march that digital computers did the past 50 years.

If you are involved with a start-up company with an awkwardly placed “Q” in its name, this is where you sit. You believe our current devices are “quantum ENIAC machines”. Following the historical trajectory of classical computers, we just need some competitive players making a steady stream of breakthroughs and—voila!—quantum iPads for your alchemy simulations in no time. Along the way, we will reap continuing benefits from the spin-offs of quantum tech.

This is the quantum tech party line: quantum supremacy (yep, that’s a term of art now) is near. We are on the precipice of a technological—no, societal—revolution. It’s a new space race with equally high stakes. Get your Series A while the gettin’s good.

Like it or not, this is the best case scenario for the field. Scientists like to argue about what the “true” resource for quantum computation is. Turns out, it was money all along. Perhaps the hype will create a self-fulfilling prophecy that draws the the hobbyists and tinkerers that fueled much of the digital revolution. Can we engineer such a situation? I think we better find that out sooner rather than later.