From First Principles - How Quantum Computing Actually Works (Part 1) (EP 54)

Episode Date: August 20, 2026

Quantum computers do not simply “try every answer at once.” So what do they actually do—and why have governments and technology companies spent billions trying to build them?In Part 1 of our two-part quantum computing deep dive, Lester Nare and Krishna Choudhary build the field from first principles.The series was prompted by a new Nature cover paper, A digitally controlled silicon quantum processing unit, co-authored by Krishna and members of the HRL Quantum Team and collaborators. Before getting into that hardware in Part 2, we first need to understand why anyone wanted to build a quantum computer in the first place.We begin with Bell’s theorem and the failure of local hidden-variable explanations of quantum mechanics. From there, we follow the realization that information is fundamentally physical through Rolf Landauer, reversible computation, Charles Bennett, Tommaso Toffoli, Paul Benioff, and the origins of quantum information science.Then Richard Feynman changes the question. Straightforward classical simulation of an interacting quantum system requires tracking a state space that grows exponentially with the number of particles. If nature itself is quantum mechanical, Feynman asks, why not build a computer that is quantum mechanical too?David Deutsch formalizes the universal quantum computer and introduces the first quantum algorithm. Using the Deutsch–Jozsa problem, the double-slit experiment, and Feynman’s path-integral intuition, we explain what a quantum algorithm is actually exploiting: carefully engineered constructive and destructive interference.Finally, we reach the discoveries that turned quantum computing from an academic curiosity into a strategic technology. Daniel Simon develops an early exponential quantum speedup. Peter Shor recognizes how the underlying mathematics can be used to attack problems central to public-key cryptography. Lov Grover follows with a quantum search algorithm—and suddenly governments have a very different reason to care about quantum machines.We also explore quantum money, quantum cryptography, the many-worlds interpretation, Google Willow and parallel-universe headlines, post-quantum security, and what useful quantum computers may ultimately be good for.Part 2: How do you actually build one?Nature paper:A digitally controlled silicon quantum processing unitDOI: 10.1038/s41586-026-10754-7Link: https://www.nature.com/articles/s41586-026-10754-7Explore the FFP science funding tracker:ffppod.com/fundingSupport the show:ffppod.com.com/donateFollow:@FFPPod on X / Instagram / TikTok / Facebook

There's a common phrase that's used. Quantum computing tries every solution in parallel, and it finds the right answer. And I mean, like, kind of, but like, honestly, not really. Because if that were actually true, then every single problem ever could just be done on a quantum computer in parallel. This is a big argument when people talk about, like, encryption. And encryption is maybe the only thing. Where it's true. Where it's actually true.

Everything else, though, maybe not. What ends up happening is there's only very specific types of questions. where you can exploit the properties of quantum mechanics. Okay. Hello, Internet. This is your captain speaking. Lester Nare, joined as always by my co-host and our resident PhD Krishna Chowdery. We are excited to start part one of what will be a two-part deep dive on quantum computing,

covering the recent cover story in nature, volume 655, issue 8,000. 8125 released on July 30th, 2026th, featuring our resident physicist Krishna as a co-author on the cover paper of nature. We are very excited about this. This is going to be right in the wheelhouse of the show. And there was so much to talk about. We're going to spread it over two episodes. As always, we are going to talk about the science from the ground up today, because this

is from first principles. Those of you who keep up with us on Instagram and watch our stories there will know that I'm co-author on a paper that was recently published in nature. And not only was it published, it was featured on the cover. And I have to say when I was a PhD student at UCLA and I was in the intersection of neuroscience and physics, I definitely dream about this day, right? every PhD student dreams about the day that maybe one of their papers is going to be featured on the cover of nature, science, cell, things like that.

I wouldn't have guessed that it would have been a quantum computing story, though. And I think if you ask a PhD Krishna about it, he'd be like, wait, what happened to the original plot of the movie? And also, why are you in a podcast studio? Anyways, so here's the paper itself. it's called a digitally controlled silicon quantum processing unit.

There are a lot of authors. The official author that's like under the tagline there is members of the HRL quantum team and collaborators. HRL Labs is my former workplace and something like 250 authors are on this thing. And right there on the list in the blue, that's me highlighted. It's in alphabetical order. So, you know, chattery, C.H comes up. maybe 20% down. If they actually did it in order of importance, I think I'd be somewhere in the bottom line there. Nobody has to know. Yeah, it still counts. It still counts. And there's a good

reason why there are so many authors, because I think what we accomplished required a lot of manpower and a lot of resources. We've covered stories before that have a lot of big groups. So this isn't like totally out of the ordinary for physics papers. For example, we've covered the Brookhaven's Star Collaboration when they were doing like some weird quark physics or the Event Horizon Telescope. That thing has 300 authors in all of its papers. That's the, you know, collaboration that images the black hole of M87. Even when you did the interview with Dr. Michael Blanton at Carnegie, he had mentioned this transition from individual name papers to to sort of this idea of big science.

Exactly. And he kind of lived through that transition. Yes, exactly. And to build a quantum computer, it requires big science. Right. Now, I was planning to cover that paper. And then as I was cramming everything and doing all of my background research, I started realizing that, you know, in order to talk about that paper and put it into context,

a single episode is going to leave me unsatisfied. And more importantly, it's going to leave our audience unsatisfied. satisfied because we have spoiled our audience with the history of the thing and then the contextualizing of the thing and then what the paper is and putting it in context with the broader world and blah blah blah there's a lot that goes on in the quantum computing world right it's a it's a whole new paradigm of computing so you can imagine there's a theoretical side there's a software side and there's a hardware side the paper that i'm co-author on is a mostly a hardware paper. But in order to really understand why it's such a big deal and why it's

on the cover of nature, I think, you know, we need to put it into the context of this larger quantum computing ecosystem. I mean, there's so many competing technologies that are out there. There's trapped ions. There's neutral atoms. There's superconducting cubits. There's spins. That's the one that we're going to talk about. There's myerana modes. from Microsoft, I don't know why that's on there, to be honest. But we'll get into that a little bit later. So there's all these storylines, and to really appreciate it, you need a lot of context. First, you need the context about what quantum computing is in general and why people should care.

I hear about quantum. You know, there's Marvel movies that use the word quantum. Yeah. It was one of the worst Marvel movies, I think, the Ant-Men one, quantum something, literally one of the worst. It's used as this rhetorical device for a lot of different ideas that are totally unrelated to the actual scientific study. And so I think this was going to be really interesting. I see the quantum supremacy stuff from Google, all these headlines all the time. I don't know how to parse.

I didn't even know that there were different types. Right. I thought it was just all the same quantum. Yeah, yeah, yeah. And so this is, I think, it's going to be interesting in helping to really distill down, like, what are we actually talking about? Exactly. Yeah. And so that's what today's episode is about. We're going to talk about the history of the field from a theory perspective. The next episode that's going to happen next week is when we're going to go into the hardware modalities and talk about how to actually build a working scalable quantum computer. So the paper is actually going to be next episode. This episode is the theoretical foundations and the setup for why we would even want to build something like this. If it's so hard, hard, there better be a good reason for why we're building it, right? So the questions that we're

going to answer here are things like, what is a qubit? What is a quantum algorithm? Right? And I want to contrast today's multi-billion dollar technologies. I think now it's like in the trillions, to be honest, against the humble beginnings of this field. It's like countercultural beginnings in the 1960s, 70s, and 80s. We're going to focus a lot on some of the human stories behind it. Because at the time, people were thinking about quantum computing in their spare time. There was no research program when this thing started about quantum computing. Now there's like entire half of a department of physics that will just be doing quantum

computing at certain universities. Right. So from humble beginnings to where we are now, it's an incredible story. I want to give our audience a sense of why everyone is so obsessed with building one. and I want to dismantle the hype is another big thing that I want to do here because we hear a lot of hype about quantum as you mentioned it's in every Marvel movie whenever they need some gimmick to like time travel or like teleport

multiverse like everything has a quantum nexus yeah like erase memories that the new Spider-Man movie I haven't watched it yet I want to but there's probably some quantum quantum nonsense in there. So if you're not careful, you can get it wrong, right? The hype is definitely real and it's definitely there. There's a common phrase that's used that,

you know, quantum computing tries every solution in parallel and it finds the right answer. And I mean, like, kind of, but like honestly, not really. Okay? Because if that were actually true, if quantum computing was just like finding, was like doing all of the solutions in parallel, then every single problem ever could just be done on a quantum computer in parallel, right?

Like every problem has a myriad of possible solutions. Okay, just try all of them in parallel and then what? You just solve everything. So what p doesn't equal np equals constant, right? Just constant time. You press it on a quantum computer. You're done. This is a big argument when people talk about like encryption specifically.

Yeah. And it's like, oh, what would take a trillion years can be run in parallel on a quantum computer? computer and can be done in seconds. And encryption is maybe the only thing where it's true. Where it's actually true. Everything else, though, maybe not, right? So that's kind of what I'm trying to get into. What ends up happening is there's only very specific types of

questions where you can exploit the properties of quantum mechanics. Okay. And in this episode, we're going to explore one of the famous algorithms called the Deutsche Jose algorithm. It's probably the simplest algorithm to understand. I don't think it's very useful, except as a teaching tool, to understand how quantum algorithms actually work. Okay?

It's simple enough that I think I could do a good job on this podcast to explain at least some of the magic behind what's actually happening. And we will talk about Shores algorithm. Don't worry about it. But we're not going to, like, go into detail because that's going to require another full deep dive. I just have to say, Deutsche Jose sounds like a starter for Liverpool. It totally does. Yeah. So that's the preview. Yep.

All right. And now let's get into it. We begin in 1964 with the formulation of Bell's theorem. This is a photo of our America 250 timeline that we had prepared for the celebration of America's 250th birthday. We had done a giant timeline of some 400 accomplishments that America was responsible. responsible for. A lot of people think that John Bell was mostly at CERN, but actually he took a one-year sabbatical and he came to the United States in 1964. He visited Stanford University and the University of Wisconsin, and during that sabbatical is when he wrote the seminal paper that he is most well known for. It showed definitively that local hidden variables cannot account for the richness of the observed phenomenon that we see in quantum mechanics. So I want to dive a little bit into that because I think

that is going to be the foundation for understanding why Feynman got into it. A lot of people just start with Feynman. There's a lot of stuff that happened before Feynman. Okay. And I don't want to be a podcast that is the cult of Feynman. There's plenty out there. Feynman is a great man, as we will see in the talk that he gives. But there was a lot of stuff that happened before then that enabled him to think about those problems. And for anyone who actually is interested in checking out that America 250, you can go to FFPod.com backslash America 250. It's an interactive timeline

that covers some of the stuff you just mentioned. That's pre-Findman, as well as many of the other great discoveries in our history. And it's, I think, a really humbling experience to go through it in that format. Yeah. And Feynman has mentioned a lot on that timeline because he did a lot of really cool things.

So let's start with our entanglement experiment that, everyone gets to know. Alice and Bob, okay? They always use Allison Bob. I don't know why. I think it's because A and B, maybe if somebody has an idea of historically why we always use Alice and Bob in these entanglement thought experiments, please let us know. So here's the idea. Suppose I create two particles with spin and they're entangled. So I don't know. Maybe like a photon goes through a crystal and then it splits into two. So then the two photons that were created were created from the same

quantum state. So they're going to have an entangled quantum state. Okay. Now by conservation of angular momentum, if Alice gets one of these particles and Bob gets another one of these particles and Alice observes her particle spinning one way, then by conservation of angular momentum, Bob should see his particle spinning the other direction, right? Because then the two spins cancel out. But according to quantum mechanics, there's a probability that Alice is going to see the spin going one way and the other way, and then a probability that Bob is going to see it going the other way. It's just that the two probabilities are correlated and that they always have to be opposite. Now, that begs the question, is there a spin to begin with? Right.

Okay? That was like made in the entanglement state and then got split up. Okay? Or the alternative being, or is it only existent once it's been, quote, absorb? Exactly. That's Neil's bore. Which is a complex. What is it? Yeah. What does that even mean? Right. So Neil's bore is like, no, that second thing. No, that's it. Right. There's no well-defined spin. And then only when you observe it, the wave function collapses.

And then you get one direction or the other. Right. And Einstein's like, this is nonsense. This doesn't make any sense. He insisted on something called local realism because he, one, he liked local. because local means that nothing travels faster than speed of light, which makes sense. And the physical objects possess definite properties that are independent of observation. Okay, so that's like the realism part. And they can't propagate faster than speed of light. There's no communication. Okay. So effectively, if you've seen the Denzel Washington movie, DeJavu, he's effectively

Denzel Washington. Okay? there's that really funny scene where like he's looking through a wormhole or something and he's asking if the person is alive. And one of the scientists is like, well, time is not a local variable. And then he's like, it's so funny. He's like, let me let me say it slow so you PhDs can understand. Right. And then he takes a chair and destroys a monitor.

And he's like, this monitor is now dead. It is not in a superposition of different entropy. And that's Einstein. It's such a classic scene and it's a great movie. It is really good. And it touches on some of these subjects maybe some ways great and some ways not so great. But it gives a real lived human experience to these theoretical questions in a way that you could try to kind of visualize. Yeah.

And honestly, I was Denzel Washington before I just sort of succumb to my fate and was like, okay, just shut up. and calculate. But when you're first learning it, everyone is Denzel Washington. What are you talking about? Right. Right. So effectively, under local realism, any correlation that's observed between Alice and Bob have to do with some kind of hidden variable. This is the famous EPR Einstein Podolsky Rosen paper that Einstein published in 1935. And he showed that, you know, if you have some kind of local hidden variable, then you can perhaps account for, you know, the, you know, it could kind of make sense, right? And for the longest time, it was like, okay, fine, whatever. The local hidden variable takes place of the wave function collapsing

during observation. Yeah, yeah. It's like there's something that's saved. Right. There's like a saved attribute in the two particles that then we observe on either side. Now, crucially, when we only observe like the spin in one direction, both the classical interpretation and the quantum interpretation are the same. Fine. Right? Because we're going to observe them in the opposite directions. And so for the longest time, it was like, oh, this is just like a philosophical argument. There's no way to prove it one way or the other. Who cares? Along comes John Graham Bell. Okay. John Graham Bell has the crucial insight in this particular paper. I mean, it's literally called on the Einstein-Padolski Rosen Paradox. And crucially, the affiliation there is University

of Wisconsin-Madison. So this is the paper. for Bell's Inequality, and it's in America. And that's why it's on our America 250, you know? It's like, hey, that one year, that one year was everything. So he realizes that we can actually expand the Alice and Bob experiment to give Alice and Bob a choice. Instead of them only observing a single direction, right, we can maybe have a filter where they can observe the spin

in the in the in the in the z direction up and down or in the x direction sideways okay so like when the when the light particle comes in i can adjust my filter my polarizer or whatever to to say okay what is the spin in the x direction what is the spin in the in the z direction right now i've got two choices alice has the same choice and bob has the same choice and alice is going to observe up and down in z if she chose z or up and down in x if she chose x and similarly bob has two choices as well now Now we sort of have this matrix of options. Exactly. Based on...

Yes. Now we have a matrix of options. And now we can actually disentangle. Is there a hidden variable? Or is the quantum mechanics doing crazy nonsense? Okay? Bell shows that in the local realism world, Einstein's world, the joint conditional probability distributions of all of these outcomes,

like the probability distribution of Alice observing this way, given that, and Bob observing this way, given his choice, it can factor out into two independent components that are local. Okay? If there's a hidden variable, I can factor it out into like this particle in Bob and that particle in Alice. Okay? On the other hand, quantum mechanics predicts that there is going to be certain settings where the correlation is going to exceed that bound.

If you could factor, the correlation can only go up a certain. amount. But for certain angles, the correlation is actually going to exceed. So now you've got a way to prove one way or the other, is there a hidden variable or not. Okay? John Klausor very famously did this at Berkeley, another one in our America 250 timeline. And he showed that, in fact, there is a violation. Right. There's a violation of Bell's inequality, and you cannot factor this probability distribution. Okay. There's no separate component. You have to consider the entire thing in this giant, no matter how far apart Alison Babar. John Klauser did this in the, he won the 2022 Nobel Prize in Physics, along with Alain Aspect and Anton Zylinger.

These guys were instrumental at taking bells inequality to the absolute limit. John Klauser was the first guy to do it. And these other two started considering very, very, like, you know, whenever, whenever, Whenever John Clouser did that, there's people that'll come up and be like, well, maybe the hidden variable is like in the lab, right? In the giant room that John Clouser is in. Because he's making these particles and then making it go to one end of the lab and the other end of the lab. His experiment was still kind of local, right? And then he's making choices that are local to him.

He's like choosing when to put the polarizers in one direction or the other. Is the argument basically like the scope of what you're accounting for is... Is like still kind of local. Right. Right. It's still kind of local. When does it not become? Yeah.

Yeah. So then Alan Aspect, Alan Aspect, I think one of his amazing experiments he did actually, I believe it was at Tenerife in the observatories there. Tenor reef has these amazing observatories. Optical telescopes that are across the mountain, right? So now what you can do, the main problem with the, with, um, John Klauser's experiment was that he was kind of choosing, even with a random number generator, he was kind of choosing himself which way to set the polarizers, what choice to make for his

Alice and his Bob. Alan Aspect said, okay, I'm going to point telescopes in opposite directions of the universe. Okay, one is going to point at a quasar that's like billions of light years this way, and one is going to point at a quasar, a billion light years that way. And depending on the light from the quasars, the quasars are going to make the choice on which direction my polarizing filter is going to be. Okay? Bell's inequality is still violated.

So that means that whatever local variable has to be like the size of the universe. At that point, it's like what is the hell are you? What is local, right? And so just to say this back to you, the idea is like, who decides the position of the filter initially was not considered sufficient to say that the hidden variable is not a thing? Yeah. because the idea was the decider of that was still too local to the system of observation.

And so now when we utilize these distant celestial objects as the variable that decides what direction the filters in in this matrix of options. Now our experimental design is billions of light years across versus just whatever, a couple tens of yards or whatever. And then the argument that this hidden variable can exist in this billion light years across. experimental apparatus can no longer be considered reasonable. Yeah. And now we are able to we still violate Bell's theorem.

And so the realists, sorry. Yeah, sorry. I mean, unless you're really like doubling down and you're saying there's just a universe wide local variable or something, you know, it's getting tenuous now. Right? Because now we're arguing over the definition

of local. Yeah, yeah, yeah. Exactly. Right. So the key thing here that I want you to take away is that factoring capability. Okay. Okay. It means that you cannot factor the physics into separate components, one for Alice and her particle and one for Bob and his particle. Okay. That's the key thing that establishes that quantum mechanics is very, very weird. And that's the insight that Feynman uses in his 1981 talk. Can you maybe phrase it in a slightly different way? because I think I understand what you're saying. When you say you can't factor it independently for both,

are you trying to say that there's a rule set above when either of them observed or act in a system that is not independent of each other? Like, I'm just trying. So there's like, in order to really try and understand what is happening in this experiment, we have to consider the entire system at once. We cannot consider the systems separate.

The particles cannot be considered in any mathematical form to be separate from one another. I see. They are connected by a single wave function is one way of putting it, right? Like the mathematics is inherently tied. It is one block. Yes. Right? It is a singular Lego block.

You can't break it down into subsequent smaller Lego blocks. No. The whole system that you're observing at whatever scale has to be considered a singular Lego block in this analogy. Yeah, yeah. In order to really capture all of the quantum mechanics that have. happening. Okay. There's no way to be like there's Aden Variable. And so, you know, this guy has this thing saved. That guy has that thing saved. And so, okay. You know what I mean? Yeah, yeah, yeah, yeah. So that's the key insight that Feynman is going to use later in 1981. Okay. Now, this is in the 1960s,

and we've got a long way to go before 1981. Okay. Because there's a lot more stuff that happens. In parallel, people are working on computation and trying to understand computation, right? In the early decades of the digital revolution where you've got these vacuum tubes and you're trying to understand, mathematical abstraction. Computation is simply that. It's just a mathematical abstraction. Okay. It's divorced from like physical substrates. Claude Shannon, very famously in 1948, he shows that information is the same as entropy, but it's still this mathematical abstraction. Okay. Rolf Landauer, he's actually at IBM Research, which we might hear a lot more about in this episode and in the next episode. More on that later. But Rolf Landauer, in 1969,

he establishes that information is actually inherently physical. Okay? And he demonstrates this by saying that any logically irreversible operation, meaning something that destroys information is going to cost you heat. Okay? Here's what I mean by that. Like, there's a fundamental minimum amount of thermal energy

that needs to be dissipated into an environment. and the amount of energy for erasing a bit, and I'll tell you what that means. Like, what does erasing a bit mean? But in any case, the fundamental amount of energy that you need to erase a bit and to let go of that heat is the temperature, multiplied by Boltzman constant,

multiplied by log of 2. The KBT is like the amount of jiggle that you have for everything that can jiggle, every degree of freedom, and the log 2 is like, it reminds you of like entropy is the log of the number of microstates. In this case, the number of microstates is two because it's a zero or a one. Okay?

So that's the amount of heat that you have to put out. Now, for normal computers, that's fine because we actually use reversible gates in our logic all the time. Our computers, the algorithms, and our phones. Everything uses like and gates or gates, things like that. If we just look at an and gate, for example, let me show you how this thing erases information. Okay? An and gate takes your inputs. There's two inputs that are either zero or one.

and only if they're both one, does the output become one, right? Now, what that means is there's four different possibilities, right? 0-0-1-1-0-1. But they get mapped to only two, right? The first three get mapped to zero because at least one of them is zero. And only the last one, the one-one,

the one gets mapped to a one. Now, this is irreversible because if I were to give you the output, the table in C, you could not tell me the input, the A and B, right? because there's redundancy. Yes. Like if I gave you the output is one,

then of course you could tell me it's one one. But if the output is zero, then you couldn't tell me which of the three it came from. So that's an erasure of information because you lost a bit of information. Before you had two bits, now you've only got one bit. Okay?

So whenever you implement an and gate, Landauer's principle comes in and you're going to have to release some amount of heat. Okay? And like the ability to go back is what's being released in the heat. Yes. The degradation of like understanding what your previous state was.

Exactly, exactly. It's kind of like an arrow of time argument that you're making. The TVA from Loki season one. Yeah. And this is totally okay for classical computing. Okay, we use so many end gates and or gates in our classical laptops, right? Fine. In quantum mechanics, this is not okay.

There's two reasons. The first one is kind of simple, right? If we want to use quantum mechanics to do computation, we want to work with the quantum magic that happens with the entangling that stuff that I was talking about with Bell's theorem and like you know these two states are entangled

now in order to keep the quantum state sort of happy you better not heat it up you better not let random other crap go in but if you're dissipating heat in the middle of your computation that is going to destroy all of the quantum mechanics of your system right

because your quantum system almost has to maintain this single Lego block state. And it can't be messed around with, because then that fundamentally changes the quantum magic of the system. Exactly, yeah. It's like the only part, and this is the next fundamental thing, the only part of quantum mechanics that is irreversible, meaning you can't go backwards,

is the opening of the box or the measurement, the observation. The observation. Right? The observation is the thing where you can't go back. before observing, quantum mechanics is like kind of deterministic because Schrodinger's equation just like tells you how the quantum states are going to evolve. It's only when you open the box and find out if the cat is dead or alive, is the cat dead or alive? Otherwise, there's like, you know, states where the cat is dead and the cat is alive and there's a complex amplitude

that is attached to both and they both go forward like Schrodinger's equations. This means that quantum mechanics has unitary evolution. And so if I want to do computation, with quantum mechanics, I cannot have reversible logic, which is kind of key. Okay? You cannot have reversible logic. Yeah. Wait, did I say that right? No, you can only have reversible logic.

Yeah, good, good guess. Right. Because the point is the system has to basically continuously maintain, like basically until the point of observation, which you want to be able to decide when that happens. Yeah. You want to just be able to have this system operate. in this state, which means it needs to be able to traverse between all of the quantum, possible quantum states.

Yeah, yeah. And I need to be able to save all of my progress in some sense. Okay. Okay. Yeah, yeah. I get the point that you're saying, which is like the benefit of a quantum system is that... You don't mess with it until the end. Right.

Everything is reversible. Yeah. Yeah. You know, yeah, all of the quantum magic stays quantum magic and you're like messing with the quantum magic, but now you have to do it in a irreversible way. Right. Right. You have to obey the laws of Schrodinger's equations and, like, unitary dynamics.

Yes. And, like, poke it in a very specific way that you're not, like, destroying the thing that is giving you all the magic. We have a little poached egg. We don't want to poke the yolk. Yes. While it's cooking. Right? And then ruin our poached egg or souffle or any other kind of cooking analogy.

I think that's a really interesting point, though, because now we're sort of helping to define the fundamentals differences between a classical and classical. classical and quantum systems, such that we are going to build to this reason of why quantum systems give us these interesting other things we can do. Yeah. That fundamentally because classical systems are irreversible, you cannot get out of a classical system, no matter how much power, compute, how well you dissipate the heat. None of that matters. Yeah, none of that matters.

Okay. In order to work with the quantum magic, you got to work in the constraints of quantum mechanics. and Schrodinger's equations. Very interesting. Or Heisenberg if you're in that camp, right? So it's unclear whether this is even possible, though. Right. Like, can you compute with reversible logic, right?

Because we're used to and gates and orgates and those are, those are, and we got algorithms galore for days for that kind of stuff, right? 1973, Charles Bennett demonstrates that you can actually use universal reversible computation. and along with him, Edward Fredkin and Tomaso Tofoli, who's over here, Tomaso Tofoli invents something called a Toffoli gate, which is a controlled, controlled, not gate. Okay? I don't want to get into all of that,

but it's effectively a logic gate that is reversible, meaning I can always go backwards. The logic, the truth table is unique because my three inputs give me three outputs. So from those three outputs, I can always reconstruct my three inputs. But crucially, this gate is something that I can use for universal computation. I can build any other gate from these gates. Okay?

So now it's possible. There's a chance. This makes sense. Unlike our previous and gate, where three out of the four outputs you could not go back from. Because it went two to one, right? So it's like, yeah, you lost some. Here it's three to three. three or three.

So you basically retain all the degrees of information necessary to go backwards. And that's a fundamental building block to now be able to potentially do the type of computation that you would, you have an enabling layer to potentially now think about the idea of quantum computing. Yes. Yes. You've got like a substrate that I can start building an algorithm. Maybe. Maybe.

Maybe. Maybe. And Tofoli, for those that are like well versed, in quantum computing or like just starting to learn about it, you'll hear a lot about Tofoli Gates. That's where the, that's who it's named after, right? And it's because it's this like first idea of like a gate that can make up universal logic in some sense. So following this, Paul Benioff at the Argonne National Lab, he creates a quantum mechanics version of the state transitions in Turing machines. Alan Turing in Church, who we talked about again on our America

250. I keep pitching this thing. But they demonstrated at Princeton that, you know, any computable algorithm can be computed on a Turing machine using these like state transitions and very simple logic. He showed that, you know, there's a version of that that I can do in quantum mechanics. Okay. Side note, Charles Bennett, who's the guy who demonstrated that first reversible computation, he was involved in the early days of quantum cryptography. So his undergrad friend, Stephen Wiesner, at Columbia.

they had an idea to use Heisenberg's uncertainty principle to create unforgeable money. So this is before Bitcoin was a thing, before the blockchain was a thing. They were trying to use quantum mechanics to create money that you couldn't fake. There's a funny story where Bennett attended the I-Triplee conference on Foundations of Computer Science in Puerto Rico. And on one of these afternoons, this cryptographer, Jill is Brassard. he was swimming out in the beachfront hotel in San Juan and Bennett just swims up to him in the ocean and just starts ranting at him about this idea of quantum money.

Okay, and the quote we have from Brassard is like, I was trapped so I listened politely because they're in the middle of the ocean. Brassar is just trying to have a good time before his talk about like cryptography or whatever. In Puerto Rico, who's not trying to have a good time. Yeah, he's trying to have a good time. And Bennett just swims up to him. is like, yo, quantum money. I got this idea.

I got this idea. It's going to make us rich, probably. I don't know what he said, right? But soon as he's listening to this thing, it's like doubt turns into fascination and he realizes, like, this could actually be some serious science. And the two of them form a collaboration that starts a whole new field of quantum information science. They win the Turing Prize together. And there's, you know, this discovery of a fundamental connection between, physics and information, quantum teleportation, if you've ever heard of.

That's these guys. So they won the Turing Prize together. But all from a serendipitous meeting in Puerto Rico, in the ocean, right, where Bennett just like accosted this guy. The only context I have recently of this idea of quantum teleportation was a new story, maybe from a year or two ago, where the Chinese apparently were able to, that they had the maximum distance of quantum teleportation of information. They had like a satellite in orbit. Oh, dude, I heard about that.

And something on the ground. And when I heard that, because like the idea is like it is, you cannot hack that information transfer in the way you would, with normal signals, intelligence. Yeah, that's like getting into quantum cryptography and stuff like that. Again, this is the stuff that these guys are doing. Wait, so it starts here on a beach in Puerto Rico. Yeah, yeah. And now it's an orbit.

Yeah. But that's, we're going to get there, I think, in terms of being able to better understand. what that means. But this is what we talk about when we say, like there are all these stories and headlines and tech blogs and whatever. Oh, quantum teleportation. Everything is going to be whatever. Yeah, but it starts with these small meetings between human beings, right, at conferences, crucially. Yes. So when people say that they don't want to fund conferences, conferences is where ideas come together. Osmosis. You know, like, it's very important to bring human beings together. So this is the status in the early

1980s. Okay. We've got some indication that quantum computing could work, right? Like Landauer's principle is not a no-go that we thought. There's ways to get around heat dissipation. There's also this fundamental advantage that Bell gives you with quantum mechanics, where he says that quantum mechanics is certainly very different from classical mechanics, right? And there is some magic there. Feynman comes in over here. Okay. So this is where Feynman enters the fray. He visits his old alma mater, MIT. We make fun of MIT a lot on this podcast. In this one, I'll have to give him credit.

MIT and IBM, in May 1981, they sponsored the Physics of Computation Conference at MIT's Endicott House. It's kind of like their Camp David for, like, conferences. It's like out in the outskirts of Boston, surrounded by the woods, this old, old, like, mansion out in the woods. Princeton has something similar, like with Prospect House, you know, in the middle of, but ours is on campus, in the middle of campus.

UCLA has something that's similar out in Lake Arrowhead, actually. That's nice. I had the pleasure of attending like a neuroscience workshop there. It's really nice. That's really nice. So, you know, universities have these like retreats. And MIT sponsored this at Endicott House. And this conference was attended by a who's who, okay, of quantum computing people or just computing people in general.

This is a photo that was to. taken by Charles Bennett, the guy who went into the ocean and tried to pitch this quantum money thing. So Charles Bennett was there. Okay. Along with, you've got Freeman Dyson on the left. Paul Benioff, Paul Benioff's the Turing Machine guy. Yes. You've got Rolf Landauer.

That's the Landauer limit thing. John Wheeler. Wheeler's just there and all of it. Wheeler's everywhere. He's like a Nick Fury and Marvel. Yeah, yeah. Dude, oh, my God. That's such a good analogy.

Yeah, Wheeler is the Nick Fury of 20th century physics. Yeah, and then, of course, Richard Feynman and Tom Toffoli. So all of the guys that we just talk about, they're at this conference, right? Feynman gives the keynote address. It's titled Simulating Physics with Computers. It's published in 1982 in the International Journal of Theoretical Physics. This is the paper that came out of it. And this is where he reframes quantum properties from the computational obstacles

into fundamental assets. And here's what I mean by that. Prior to this talk, everyone thought of quantum mechanics as a nuisance. Because when you're trying to make semiconductors into chips, quantum mechanics is a nuisance. Stuff is moving around, right? There's like, you got to worry about the band structure,

but if your growth is not great, then the electrons are going to hop everywhere. There's all sorts of noise. And quantum mechanics is primarily that source of noise, right? you got quantum tunneling, the thermal fluctuations, it limits how small you can make your transistors, things like that. Feynman inverted this perspective, and he analyzed,

what if you could create computational complexity by simulating quantum mechanics using a quantum computer, a computer that uses quantum mechanics? Now, why would we want to do that? Well, literally, reality is an interacting quantum system of particles, right? like quantum mechanics is the reality. And even if you talk about the 10 to the 80 atoms in the universe or like water having the 10 interacting electrons, it's still quantum mechanical. So it certainly makes sense.

So here's what Feynman said. He said, suppose I want to simulate the physics of these interacting particles, right? How much stuff would I need to store in my classical computer? This is where Bell's theorem came in. Okay? Remember, I was harping on earlier this idea that the physics of two particles cannot be factored into two independent mathematical probabilities. We have to look at it as one Lego block. About two smaller Lego blocks that make up this bigger Lego block.

Yeah, yeah. You can't say that this is what the stuff on the left with Alice is doing and this is what the stuff on the right with Bob is doing. Right. Instead, there's no way to combine them later on, right? if you could, then simulating an N-particle quantum system where the classical computer would be pretty straightforward. You just create some kind of software program that assigns like N-independent data tables or subroutines for all of the N-independent particles.

You look them up, each is tracking some kind of isolated local state, and then your memory and processing time scales linearly, like the order of N, like however many particles you have, that's about how it's going to scale. The point being it just becomes a compute and power. Yeah, yeah. And you just make a bigger computer, right?

And it's fine. Right. You could infinitely, you could scale up to some upper bound that then covers all the types of simulations you're trying to do. And you just have like one subroutine for each particle and you're fine. And you're fine. Right.

But quantum probability distributions do not factor. That's what Bell showed. Right. Right. If you want to talk about reality, the experiments show this, right? This is no longer in our head, right? For an N particle system, you can't decompose it into N different things. Instead, you have to worry about all of them combined.

It depends globally on the fully entangled configuration of your particles, right? So even if you imagine like a two-state particle, like the one that we talked about with Alice and Bob, right? You've got a two-state particle of spins that can be like, you know, spin up or spin down. a classical computer would be forced to store and update a joint probability like vector, tensor, or like set of numbers across all two to the n computational states. For Alice and Bob, for example, right?

You could have up, up, you could have down, down, you could have up down, or down. And those are different. across both the Z and the X? Well, here I'm just saying like just... Even if you keep it... Yeah, yeah, yeah. Yeah, even if we just keep it that simple.

Yeah, even if we just keep it that simple, right? Okay. Right. Which, like, the point being it's not... Yeah. Anyway. Yeah, the Z and the X comes in like a bit later and I'll have to get in, you know... Let's not go there.

Because they're all like, like, yeah, whatever. In any case, like, let's just say two particle states, right? Two state systems, right? Those two states can actually go in Z and X is the point that I was trying to make. But what you need to do is for Alice and Bob, you need to keep track of four possibilities. The up, up, the down, down, the down, the down, and the up down. Really, you got to take care of like the sum of this and the difference of this. Because, like, you know, what does it mean to be like the electron one is up and electron two is down?

There's no sticker on an electron saying this is one and two. They're indistinguishable particles. So you have to worry about, like, you know, combine linear combinations of them. But in any case, it's always two to the end is the idea. Now, this becomes insurmountable very, very quickly, very quickly. Okay, if you want 50 entangled two state particles, that's two to the 50 complex numbers that you have to take care of, right? Two to the 50 hack for students that are listening.

Two to the ten is like ten to the three, because two to the ten is ten twenty four, which is ten to the three. So if you ever want to go into base 10, 2 to the 50 is like 10 to the 3 to the 5, which is 10 to the 15. So you got to take care of 10 to the 15 complex numbers. If you're trying to simulate 300 two-state particles, which like any, there's so many compounds where there's 300 electrons that are moving around, proteins, for example. That's going to be 2 to the 300, which is 2 to the 10 to the 30, which is 10 to the 30, which is 10 to the 90 numbers. that exceeds the number of elementary particles in our observable universe. There's estimates out there that there are only 10 to the 80 atoms, right?

So just to simulate 300 two-state particles, I need 10 to the 90 numbers. And it's kind of crazy. Part of the point you're bringing up here is that it is just wholly inefficient because the type of systems we would be able to simulate are exceedingly small, effectively a protein. that only had two states, which is not real. It's not practical in real life.

Yeah. No, I'm saying a protein would be crazy. I mean, maybe you could simulate if you had all the time in the universe, like a water molecule with 10 electrons, right? There's no amount of brute force around compute and scaling up that would make it even tenable because the amount of variables when we have to account for the entire system as a whole. whole because you can't factor it.

It means that the amount of variables and interactions you're tracking continuously is just. It's just insane. Yeah. And also as an aside, I think it's kind of cool to think about that like somehow the universe is keeping track of what, so there's 10 to the 80 particles, right? even if all of those particles are two state systems, there's two to the 10 to the 80 complex amplitudes that the universe is keeping track.

I don't even know how big that number is, right? That might be, I don't know if that's the big, no, I'm sure there's mathematicians that have come up with bigger numbers than two to the 10 to the 80. But I'm just saying like it's kind of crazy that the universe is keeping track of all of those complex amplitudes to give us like the world. Is that how it works, really?

Is that really how it works? Sometimes I'm thinking about this stuff and I'm like, mate, is this really how it works? It's because it's hard to even And like where anyway. Yeah, but that's an aside about like just like the nature of reality. Totally totally totally totally. Why quantum mechanics is weird.

But in any case, right, this is what Feynman is talking about. And he says instead of classical bits where we'd have to, we'd have to create 10 to the 90 bits to keep track of 300 thingies, instead, what if we use a quantum version of a bit? What if we create a computer where the bit is a two-state quantum system? And then we bake into the computer the interaction that we're trying to study, right? Then the quantum mechanics inside the computer is going to take care of all of the superposition, and all of the blow-up of complex numbers, right?

Because we're just harnessing the quantum mechanics that we're trying to study. And at the foundational layer of where the compute happens. Yeah, hardware is king. Versus after the fact at the software level or at the systems level. Yes, exactly. And so he ends his talk with a very famous line that rings across a lot of quantum computing literature and a lot of quantum computing deep dives. He says, nature isn't classical.

Damn it. And if you want to take a simulation of nature, you'd better make it quantum mechanical. and by golly, it's a wonderful problem because it doesn't look so easy. No, it certainly doesn't. It certainly does not look so easy. 46 years later, we're still trying to make one. I think this is a really great starting point

because what we've done so far is we've sort of created this understanding of the difference between classical systems versus quantum mechanical systems at a theoretical level. how that informed the early countercultural era of computing in general, how this idea then moved to this point of there is actually quantum computing as a competing way to solve certain types of problems,

as opposed to classical computing, because there are fundamental limitations because we've found violations of Bell's theorem that mean that the hidden variable thing and the realists sorry. Yeah. And if we really want to create simulations that are true to are lived four-dimensional time space. Yeah, whatever. Yeah. Right. This magical thingy. We're going to need the compute layer to reflect the same quantum mechanical attributes that our theoretical frameworks currently suggest exists. Yes. Is that a fair summary? That's exactly right. And that talk happened in 1981, and he mentions all of the priors that I've been talking about.

He mentions Bell's theorem. He mentions Tifoli and Benioff and all these people who said, hey, quantum computing is a possibility, right? We have reversible logic. Right. We have a paradigm where we can manipulate a quantum state, right, even theoretically. And Bell shows that there's this rich underlying layer that we can actually exploit if we want to, right? Feynman's argument about fundamental science and like, you know, this becomes something that is a polynomial time simulation tool for chemistry, condensed matter physics, material science, everything.

But that's really not the reason why quantum computing is a trillion dollar industry. I don't think a trillion dollars would have gone into quantum computing if all it was doing was trying to find the next room temperature superconductor. Okay. Okay. The reason it is a trillion dollar computing industry is because of the stuff that we are getting into after our break, namely Shores algorithm and Bitcoin going to zero. And so with that, let's do some housekeeping. So for those of you watching us on YouTube or Spotify, welcome.

As always, watching the pod is one of the best ways to capture all of the overlaught. and graphics we talk about, be sure to like, share, comment, and subscribe. It helps us in our battle against the billionaire algorithm. For those listening on Apple Podcasts, it is out of our hands, but we are awaiting the announcement for Spotify creator videos to be available as video on Apple Podcasts. Allegedly, Apple and Spotify are collaborating on this launching late 2026, so keep an eye out for that. those who catch our clips on TikTok and Instagram on a regular basis, put them in those group DMs, share the best science show on the planet with your friends, coworkers, bring it to Journal

Club. If you are watching this full episode for the first time from our clips, welcome. Every episode is like this. And so we are super excited to continue to have you all today. A couple of announcements or housekeeping notes. For our merch giveaway, we are going to be. sending out the emails to the winners over the next week here. So keep an eye out on your email. Thank you for everyone for submitting for our one year anniversary. You may have noticed behind us

there are gold balloons representing 250. And while we talked a lot about America 250, the gold balloons are not necessarily here to celebrate our America 250 episode, but they are here thanks to the loving wives Anna and Joni who've provided us a way to celebrate our 250 Instagram followers, which is already now at 267. So we are just growing unbelievably fast. We want to thank the upcoming cast of the Real Housewives of FFP for supporting us so greatly. We love you both so much. And I'm just going to hit one last note before we get into some quick, headlines as a palette cleanser before we dive back into our quantum episodes.

If you would like to support the show, five-star reviews, like, comment, share, subscribe. If you would like to donate to the show, you can head to fppod.com backslash donate. Again, we are on all platforms. Our website has a great way to watch the videos, chapters, full transcripts, links to all the research papers we talk about are all available there. But now we want to quickly just get into. some of the top news stories from the week just to give you an idea of what's going on out there in the world of science.

Our first story came out breaking today. It's been all over the news related to pharmaceutical giants, Moderna and Merck, saying today, Wednesday, which will be likely a day before you all watch this podcast, that an experimental vaccine treatment has shown signs of preventing cancer from returning. or spreading in a study of high-risk melanoma patients. This was a combination of Moderna bringing their MRNA vaccine structure and Merck bringing their Ktruda. And the idea is they, you know, we've talked about the immune system in the past on the pod.

And part of the tough part about cancer cells is our immune system is not really able to identify them. So it's like our police, our immune system is looking for the criminals and the criminals are kind of invisible. apparently the combination of these two things makes it able, the immune system able to identify what was previously not visible to them. However, they've not published their results in a peer-reviewed journal or released the new data, saying instead they will be presented at an upcoming medical meeting and shared with regulators. Oh, okay. However, there does seem to be some real, there does seem to be a there there. Okay. And so according to their news release, the MRNA-based vaccine was tested in a late-stage trial involving people who had had surgery to remove a melanoma, one of the deadliest forms of skin cancer.

Apparently, this same methodology is also being applied to a few other types of cancer, and there's potential that it generalizes. Interesting. So their stock price, both of them went through the roof. Oh, I bet. Around that. So we'll see. A cancer vaccine? The data, we'll see when the data comes in, and we'll keep an eye on that.

That's pretty good. But that's an interesting first story from us that's out today. Our second story in the news headlines that was interesting. This is from UC Berkeley, this idea of a new technique called Trace that pinpoints human DNA inherited from ghost ancestors. There have been a lot of videos and hype things about, oh, the missing link to humanity's ancestry. So the idea here is that, and we've talked about some of these stories. stories before previously as well. Neanderthals and Denisovans interbred with modern human ancestors leaving behind a telltale DNA in our genomes. And so if you do 23andMe or Ancestry.com, you can

kind of know and see where those trace ancestries from. But now the researchers at UC Berkeley have found out that we may actually have evidence for modern human interbreeding with too much older unknown ancestors that have not yet been recorded in any of the genomic record specifically. Wow. And the time period in which the interbreeding started was prior to the sort of the migration out of Africa, which I believe was about 800,000 years ago. And so this is a very big, it would be a very big deal in terms of the... Yeah.

Yeah. If it happens before the out of Africa event, then it's much more widespread, right? Right? Yes. Yeah. Then it's like literally everyone who's not in Africa and maybe some in Africa. It appears that I believe the data point was 0.5 to 1%. They found traces of these two ancestral lines across every, the Eurasian, the like Denisovan Neanderthal. It's present across everybody. Oh, okay. And so now there's obviously going to be follow up around this, but it isn't interesting. And the thing is it started, there was this breakoff. It started prior, and then there was apparently a reconnection right before the rise of Homo sapien. And so there seems to be some interesting, there's some interesting genetic history to come out of that story. So interesting, fascinating.

If you would like us to cover that in more detail, let us know. Our last quick story reference point here, we are always going to talk about funding. Yesterday, the NSF announced $1.5 billion of the foundational research. this is the idea that every year or a couple of different times, they will have their new notices for funding opportunities, which define what they're funding under what dynamics and the requirements to submit your proposals. There's a lot of kerfuffle right now around funding because there's significant cuts that the current Trump administration is trying to make around funding generally, as well as changes to how grants are actually, how grants are awarded. themselves, which currently has expert review panels, they want to move it into being more aligned with whatever the agenda of the administration, the political administration of the time is. Which we covered in a previous episode about how politics is now getting intertwined into, yeah, the peer review panel of experts and scientists no longer have final say. It's just an

opinion. Which, again, we can talk about iterating on the process, but I think this is a hammer approach to something that requires a scalpel. The $1.5 billion new proposals that were announced across all of the fundamental hard sciences. Okay. So this is not the social sciences per se. We're talking about things like biological science, expeditions and computing, electrical communications, bioengineering, manufacturing.

One new area that I think was allocated about $30 million was emerging frontiers in wave-based computing, which has maybe some kind of tangential relation to what we're talking about. And so one of the issues people have about this is a lot of this is being framed around the golden age of X that is the overarching political narrative that is trying to be applied to a lot of research and development. And the emphasis on the technological bolstering from a geopolitical perspective, obviously we want to be able to do fundamental research, as we've talked about a lot, that

not necessarily have a direct through line to a practical commercial application because some of the biggest things we have discovered in the U.S. that have had the biggest financial impact were not decided at the point of research. It was figured out after the fact. And if you are curious about learning more about the history of funding in general in the U.S., we have an incredible interactive explorer for funding over the last 60 years in the U.S. United States. You can understand how research and development funding has been allocated across agencies, even including last year's FY2026 and this year's still ongoing FY27 funding debate

looks like. Instead of just talking about things without knowing the information, we've given a very easy way to look at what money has actually been allocated to science and where. And Big shout out to AAAS, who've provided the historical data sets that we've been able to build that off of. Now, last quick note in our break before we return to our quantum fantasticness. What is the, I can't remember the Marvel movie, Quantum. There it is. And that's the one that I didn't see. And it was apparently terrible.

So we don't care about that. But we have one correction from our previous episode, which was on the Riemann hypothesis. Yes. So the previous episode, a lot of you saw it, and most of it I'm very proud of. There's one segment where I think I could have done better. And it was when we were discussing some of Claude's results. And specifically this particular graphic came up. As background, Claude made some progress in a related problem to the Remod hypothesis,

where the remand hypothesis is, where are the zeros? of the Riemann's Zeta function, are they all on the critical line where the real part of the zeros is one half? Now, Claude showed that the previous bound of something like 44% had gone up to 67%, which means that 67% of all of the non-trivial zeros are on the, on that line. Critical line. Right? And I mistakenly said that if we get to 100%, that's going to be the remand hypothesis. And it's because that graphic showed 100% line over there, and it said remand hypothesis,

and I just wasn't really thinking, it's a lot richer than that, because this is a statistical argument, right? And you actually brought it up earlier when you said that, you know, with infinities, it's hard to talk about percentages. Like when we say that 67%, or let's say two-thirds,

Let's say two thirds of all zeros are on the critical line. G.H. Hardy had already proved that there are an infinite number of zeros on the critical line. So what does it mean for the infinite number of zeros to only at least be two thirds? Well, what that means is two out of three in that infinite set are on the line. That's what Claude is saying, right? There's an infinite set. And just like how one out of two of the infinite set of natural numbers are even numbers, one can say, or two out of three of all of the numbers are not multiples of three.

That's another way of saying it. That's another way of saying like in the infinite set, two out of three of all of the elements are going to be on that line, right? And then I mistakenly said that if we get to 100, that'll mean the remand hypothesis is true. That's not the case, right? Because of infinities. So you could have, for example,

an infinite number of zeros on the critical line, and then a single zero somewhere else. That would still give you 100% on the critical line, but the remand hypothesis would still be false because not every zero is on the critical line. Statistically, we can reach 100, and you still haven't proven the remand hypothesis. That's the point.

And so AI, you're still not there. There's a song. If I find it, I'll play it in the next episode because now there's like counterculture rap music about like wanting data centers in your neighborhood. No way. But it's like they don't really want a data center

in the neighborhood. But some people will know what I'm talking about is like, I want a data center in my neighborhood. I need a data center in my neighborhood. I want a data center in my town. Please put a data center in my neighborhood. That way,

my ramp might actually go down. I don't care if I lose my hearing. Like, I don't care if my water. Like, you know, and it's like obviously satire. Satire around it. But it's funny how culture and these issues related to AI are so intertwined. But we, after quite a fun break, again, the best show in science.

Not only do you get a deep dive, you get some background context on the latest happenings at the frontier. No other show provides you the best frontier breaking news science experience with a depth of understanding where you're going to walk away. not only learning something, but understanding the context in which these discoveries were made. And so we're going to jump back now into our breakdown of quantum computing in our part one of our two-part deep dive. So we left off with Feynman's keynote address at that conference. And as I said, you know, Feynman's keynote address was amazing, but that's not really why we have a trillion dollar ecosystem now.

he approached quantum computing from this physical modeling perspective. At the same time, David Deutsch in England, he formalized the mathematics of quantum computational complexity in a 1985 paper, quantum theory and the church-turing principle and the universal quantum computer. If you notice, it is communicated by Roger Penrose, fellow of the Royal Society, to the proceedings of the Royal Society.

So Roger Penrose is also in this story, the great mathematician and physicist who won the Nobel Prize for his proof that black holes are definitely a reality. So he shows, David Deutsch in this paper, he defines the universal quantum Turing machine. Okay. And that establishes the kind of quantum circuit model that we see today. When we look at like quantum algorithms and you have like these blocks, we're going to see. some of these later on. The logic operations are now represented by unitary matrices, the kinds of tofoli gates and things like that that we were talking about earlier. These are reversible logic gates, and they can act on a register of quantum bits, our qubits. So this is

where he's establishing, you know, I've got a bit. The computer is made out of a bunch of quantum bits. I act on these bits with unitary matrices, unitary transformations, and I can start computing things. Is this the first building the bridge from the theory and the software of the algorithm to now how that interacts with the substrate of a hardware? Yeah, in some sense, it's more like it's taking the building blocks that people had made earlier with the gates and things like that and Feynman saying that, you know, you've got these two state systems. He's like, I can now build a touring machine that'll do stuff for me. The framework of how you would be able to make this actually productive.

Yes, these concepts of productive. Yeah, yeah, exactly. And side note, Deutsche's academic pursuit is driven by a commitment to the many world's interpretation of quantum mechanics. He is fanatical about this interpretation. He thinks this is the only way to go. And, you know, there's a lot of people that are very smart out there that are saying this is the only way to go.

During his Oxford studies as a graduate student, he met Bryce DeWitt, who's a very famous theoretical physicist who was a collaborator of John Wheeler at Princeton. I think DeWitt was actually at the Institute for Advanced Studies, so he was not at Princeton at the time. But he and Wheeler used to talk a lot. And Wheeler was the PhD advisor of Hugh Everett, who's the guy behind the Everett hypothesis of many worlds, right? Everett went on to do Rand and like, you know, National Security apparatus type stuff because he got basically shot down by Nealzboer when he went and visited Copenhagen. But Wheeler kept the idea alive of Everettian mechanics.

Bryce DeWitt did a few things with Wheeler about that many world's interpretation. And they met at a pizza parlor in London, Deutsch and DeWitt. And that's when Deutsch got into this like many worlds interpretation. And he got really into it. And in Deutsche's view, when a quantum computer processes like these computations, states simultaneously. What it's actually doing, this is Deutsche's interpretation,

is that the calculations are executed across all of the different branches of your many worlds wave function in this like multiverse, and then they recombine with quantum interference when we like make an observation. It's a form of interdimensional travel. Yeah, yeah.

Effectively. Effectively in some sense. And using those cinematic parlance that people think about. It's, we're going. Yeah, we're like computing

in multiple universes and then we're bringing it all together. Yeah. And we're using the extra compute of these other universes or extra whatever. Whatever. Yeah, yeah, yeah.

That's what he thinks. And then, you know, that's how we can do it where it seems like, ah, it's so funny because this, this is like, um,

obviously, uh, Evredian ideology, as I like to call it. Yeah, yeah, yeah. Is one of the abuses in entertainment. Yeah. That is where quantum and then multi, many worlds, excuse me,

get kind of conflated and then spins out of control. Yeah, yeah, because with many worlds, like, I mean, you could just say anything, right? If you're in Hollywood, you just, yeah, multiverse. And this is, Marvel has got themselves in a problem right now because because of all the stuff that they've done, and they basically say, well, no, Iron Man only died in this universe, but not in the many other universes. Dude, Robert Downey Jr., I think he made enough money, right? Anyways, the reason why I bring this up is because Hartmannevin, who is at Google Quantum AI, I think he's one of the heads there, he wrote a blog post about Google's Willow Chip. Google's Willow Chip is this latest of Google's quantum computing platforms.

where the performance there on this benchmark was astonishing, right? And so what Hartman Nevin wrote is that it performed a computation in under five minutes that would take today's supercomputers 10 septillion years. Okay, if you want to write it out, that's 10 with, I don't know, I'm not going to count however many zeros there are, right? But crucially, he said, this mind-boggling number exceeds known time skills in physics and vastly exceeds the age of the universe. It lends credence to the notion that quantum computation occurs in many parallel universes

in line with the idea that we live in a multiverse, a prediction first made by David Deutsch. And if you go back to that overlay, the media took over, right? And they're like, Google says it appears to have accessed parallel universes. I remember when this came out. And people were texting me because I'm like, you know, they're the only physicist that they know. You're the quantum guy. Yeah, yeah, yeah. And they're like, dude, we live in a multiverse?

I'm like, no, no, we don't. Okay, I mean, maybe, shit, I don't know. But, like, I don't think this proves that we live in a multiverse. It's just funny that, like, one of the heads of Google Quantum AI is also on this hype train, right? So he said that this is proof of that. I don't think so. There's a lot of people out there that don't think so. The Copenhagen interpretation could be just as valid.

I mean, it's all just like philosophy at this point, right, about which one is, I don't know if there's a way to tell if we're in a multiverse or if we're just, Copenhagen is just the way it is and like the universe just is weird. Unless the aliens come from the other universe and they figure out a way. Yeah, yeah. And then they come and tell us. And they like, if an alien came and told us that I'm from the other. I'm, okay. I'm from timeline too.

Yeah. It's like, okay. Yeah. Like I'm from Earth, but like we look different. It's like, okay. Cool. I'm just saying. You know, like so, all right.

So David Deutsch, he wants to prove that a quantum computer. could perform tasks faster than any classical machine, right? Because so far, Feynman has said this, right, in his talk. He said, I mean, clearly, we can't store this many states. But Deutsch wants to design a quantum algorithm that really shows this, okay? And he designs the first quantum algorithm in 1985, and it's expanded alongside with Richard Josah in 1992. This is the paper that comes out.

again, proceedings of royal society. It's a simple enough problem that I think I could describe it in enough detail on this podcast and not lose some of the essence of what's going on in the quantum solution. And I'm going to go ahead and give you the punchline. It's a toy problem, but it's one where a classical computer would take exponentially an amount of time to get to an answer with respect to the size of the input. But a quantum computer can one shot it. Okay, so we're going from exponential to one shot.

One shot. Okay, using quantum algorithm. Here's the problem, okay? So you're given a black box function. And this black box function is going to take inputs of n-digit binary numbers and give back a single digit, either a zero or a one. So if n is like two, it can give, it takes in as input, you know, either 0-0-1, 1-1, and it spits out either a zero or a one.

Now, in essence, this could be any N-digit binary number. N could be very large. So N could be like that giant matrix of zeros and ones. That goes into this black box function. I don't know how this black box function works. Okay? It's a black box. I stick an input and I get an output of either zero or one.

This is similar to the N-gate we talked about at the beginning. In terms of you have two. Then you only have one input on this. So it's not reversible. Yes. Yeah, this is not reversible. Yes, very good. And the and gate would be like 0-0-0-0-0-0-0 goes to 0-0-0. But this is even worse because it only goes to one answer.

Yeah, it only goes to one answer. And no matter how big the thing is. And I don't know if it's an and gate. Right. It's a black box. I don't know what it's doing in there. That's the point. Right. The black box replaces this concept of an and gain in terms of being able to be well defined. Yeah. And gate, I know exactly what the truth table is. Here, I don't know what the truth table is. Right. So I want to make it simple. So let's just consider n equals two. Okay. As I was saying, right? Yep. So in n equals two, we'll go to the next overlay. So at n equals two, there's four different numbers that I can feed in. I can either feed in 0, 0, 0, 1, 1. Those are going to go in one at a time into this black box. And that black box is going to make an output. And it's going to tell me, hey, if you give me this input, the output is either 0 or 1, depending on whatever I gave as input. I'm given another promise. I'm given a promise that this function is either constant or it's balanced. What do I mean by that?

So it's either a constant function in the sense that no matter what the input is, my output is always going to be zero or it's always going to be one. There's only two such functions, right? It's either all ones. So no matter what my input is, it's going to give out a one. No matter what my input is, it's going to get out of zero. right, it's one of these two. Or it is balanced.

A balanced function means that exactly half of the inputs map to zero and exactly half of the inputs map to one. There's several, not several, there's only six examples for a two-bit, for a two-bit input, because, you know, it's four choose two is going to give you six. Two of these I've described over here. The first one I think is like first bit only.

basically whatever the first bit is is that's what it's going to output so for 0 0-0 the first bit is 0 this black box is going to output 0 for 0 1 1 0 1 the first bit is now 1 so it's going to output 1 for 1 1 1 1 1 it's going to output 1 notice there's 2 0 0000 that come out and there's 2 1s that come out because the first input is is whatever the thing is and the function doesn't even look at what the second input is it's just like oh the first one is zero I'm just going to spit that out so that's one version of a balanced function. Another version of a balanced function is an XOR, exclusive or, meaning the bits are different. So if the bits are different, I'm going to output a 1. If the bits are the same, I'm going to output a 0. Notice, if it's 0,0, I output a 0 because

they're the same. If it's 1-1, I output a 0 because they're the same. If it's 01 or 1-0, I output a 1. Okay? So again, this is balanced because there's 2 zeros and 2 1s. There's 6 such functions. I've only shown you 2. Got it. Okay? So these are two examples. These are two examples. And here there's like a systematic rule, but imagine for like n digits, you don't need a systematic rule. There could just be whoever designed the black box chose half of the inputs at random and be like these guys mapped to zero and half of the inputs, these guys map to one. Okay. And has its own basically mapping key that is whatever.

Yes. There's a map, exactly. There's a mapping key that we don't know. Okay, that's the point. Your job is to figure out who am I? Am I balanced or am I constant? I gave you two choices, right? I'm either balanced or I'm constant.

And I give you this black box to play with where all you can do is put in stuff and you get out an answer. The question is, how many queries, how many times do I need to press play on the black box with whatever input I give it to determine if it's balanced or constant? That's the idea.

That's the problem. So how would I do it classically? Yep. but if I want to do it classically it's actually I mean there's only one choice that I have right it's like I feed in a number I get an output I use my logical brain to figure out what it is classically

what I do first is I just test zero zero and suppose I get a zero and I test zero one and suppose I get a zero I cannot claim that it's balanced or constant because it could be both right it could be that the first two go to zero and the next two go to one and I've only checked the first two or it could be that all of them go to zero. So I need to check that third bit string. At this point after two, there are arguments that it could be constant or could be balanced because you've not

yet had enough data to rule out one or the other. Exactly. So I need to do that third query to check. I need to check one zero. And if one zero comes out as zero, then I know that it's constant, right? Because I only have those two choices, and I've already queried three, and they're all the same, so it has to be constant.

On the other hand, if the third one comes out to be one, then I know that it's balanced, because I know that the other guy is also going to be one. I don't need to check the other guy, right? Now, you could say, well, what if, you know, in the case that it's balanced and the first and the third inputs go to go to zero and the second and the fourth go to one, right?

Worst case scenario, what if I chose, like, what if I randomly picked, like, the other stuff and I could choose, right? Well, in the worst case scenario, the guy who's designing the black box knows exactly how you're going to check the first few inputs, right? Right?

And so, and so if you're trying to just get, like the best case scenario is I just picked two, and I get lucky. One of them is zero and one of them is one. And then I'm like, oh, it has to be balanced because it's definitely not constant. Right. And so I'm done. But the guy who's building the black box could know exactly your schema of which bits you're, which bit string you're going to test to make it maximally difficult for you to find the answer. Yeah. So worst case scenario, you always have to do exactly half plus one. Yeah. Right. Yeah. Okay. I get what you're saying. Okay. So I have to do three in this case.

where there's four bit strings. Okay. How would I do this with quantum mechanics? With quantum mechanics, what Deutsche Jose came up with is they said, actually, we could pass a superposition of all four versions. Remember, in Bell's theorem, right, all four versions are not together, right? Like, or sorry, cannot be separated. So I could create a superposition of all of the four states.

I could create a superposition of zero, zero, zero, zero. one zero and one one one and i pass that entire thing through the black box now i can't separate these out and the black box is going to have to interact with the whole thing right and now this black box function what is it going to do to the superposition it is going to act on it with that black box function there's going to be some quantum version of the black box function that's again this this is a theory gimmick where it's like oh there's like there's a way to just like make it quantum mechanical, right? It's like an oracle, is what they call it. So when we do that, what I'm going to do is implement this black box function in such a way that whenever the input goes to zero, I'm going to

leave it alone. But if the input goes to one, I am going to introduce a negative sign in front of that cubit. Like I'm going to attach a negative one as the, as the amplitude in front of that qubit. So what happens here? If it is balanced, all of them are going to have the same sign. Right? And maybe we go to the next, because that'll show it. Yes. So if it's constant, everything is going to be the same, right? Because it's going to be plus, plus, plus, plus, and minus, minus, minus, depending on whether it's a zero or one that gets mapped to. If it's balanced, then two are going to be plus and two are going to be minus, plus, and two are going to be minus. And they're going to interfere with each other. And this is where the interference comes in.

Right? So if it's constant, I'm going to get constructive interference. And if it is balanced, I'm going to get destructive interference. Because they cancel out. Yeah. Because they're different. And this is the key to almost every single, actually every single quantum algorithm. Every single quantum algorithm uses this idea of constructive and destructive interference to do the computation. So now you've one shot at it. This is basically your zero or one now. Yeah.

And if you get constructive interference, I know that it's balanced. And if I get destructive interference, no, if I get constructive interference, I know that it's constant. And if I get destructive interference, I know that it's balanced because everything interfered. And so is the idea that, you know, because effectively what we're saying is the black box is a quantum system. because we can't really know. Yeah, the black box is us implementing the function as a quantum algorithm. Right. Okay.

And we ultimately want to make the black box, which we may not really know what's happening inside it, but we still need to have some level of deterministic output from it to make it functional as a computing system. Yeah. And the point here is because we know this constraint of it's either balanced or constant. We can now implement this black box and say that it's only going to flip the phase. This is called phase flipping of those places where the output is one. And that's why we're going to get that constructive and destructive interference. Now, I want to connect this to a physical reality.

Okay. Okay. Because it's a bit weird, right? So let's just talk about, to really understand why the quantum mechanics lets us do this, let's consider just a quantum interference experiment. Okay. And I want to take the double slit experiment, which we've discussed a lot in this podcast. And I want to try to create a version of the double slit experiment that computes my Deutschejosa problem. Okay. Now, to introduce the double slit experiment, you've got a laser with coherent light.

That light falls on two slits. Two slits, meaning there's like a wall with two holes in it. The light goes through, it interferes with the wall so the wall doesn't let it through except for those two holes. And those two holes then let the light through. The light from one hole is going to interfere with the light in the other hole. And if I were to cover up just one of the holes, then I would get a lump of P1 or P2. That's the first sort of two goshenes that I see. But if I don't cover either one and I let the light go through both, then I get this interference pattern.

right where in the middle you're going to get a really bright spot because the light from one hole and the light from the other hole are sort of constructively interfering and right around there I'm going to get destructive interference because the light from one hole is coinciding with the trough of the wave of another hole and I'm going to get destructive interference which is at the boundary of the dark pink and the light pink yeah in this in this visual here yeah yeah yeah okay so so this is how the double slit experiment works for like light waves and things like that. Now, crucially, it's been shown that single particles also do this, right? I can make the light dim down to the point when only a single photon is going through, and the single photon,

the wave function goes through both, and it interferes with itself to create single photon like interference on my detector, right? So, Feynman took a look at this, and he had a different way of explaining it. Feynman had this idea of the path formulation, sum over all paths of quantum mechanics. And he explained all of quantum mechanics using the sum over pads. He didn't like the wave function analogy. He came up with his own. And it turns out that it's really good because it has applications to quantum field theory. And if you know about Feynman diagrams, that's all the sum over paths stuff. Okay. So here's how he explained it. This is directly from one of his

Feynman lectures of physics. I've added the red lines and things like that. So on the left, I've got an electron gun. Again, I've got those two holes and I've got a detector on that side. Here's what he says. He says, if I've got an electron gun,

right, that's spitting out electrons, even if it's a single electron at a time, the electron is going to go, and suppose I put my detector at that bottom spot over there, okay? What I want, the only thing I can do is calculate the probability that the detector is going to register an electron there.

Okay, and what I want to do is calculate what is that probability? What's the probability that I'm going to see an electron here or here or here or anywhere else? Okay? He said, the electron is going to go through all of the paths, and the way we're going to keep track of what the electron is doing is I'm going to assign an arrow to that electron. Okay? The electron is going to start out from the gun with the arrow pointing to the right. And as it moves along in the universe, the arrow is going to spin around like a clock.

And the frequency of that spinning has to do with the frequency of the electrons wave function. For example, if this was a particle of light, the frequency would literally be the frequency of the light. Okay? But now imagine, I've got this electron that starts out with an arrow pointed to the right, and it's spinning and it's spinning. It goes to the first slit at the top, slit number one, and it goes down to where the detector is at the bottom. Okay. As it's spinning, it's going to end up at the detector and the clock is going to be at a certain location on the, you know, zero to 12. It's going to be pointing in a certain direction. And it's spin. Yeah, and it spin because it traveled for some amount of time. And during that time, it made some amount of rotations based on its frequency.

Okay. Now what about the second path? The electron is going to go through every single path. So if we look at it. at what's going to happen at the second path, there's another path that the electron can take, let's say the blue path, and the electron is going to spin again. It's going to start out at the same part. It's going to spin, and it's going to get to that same point, but it's going to be pointing in a different direction because the path length is different, which means the time is going to be different, which means the amount of time that it's been spinning is different, so it's going to end up, you know, pointing in a different direction. So he said, if we were to now calculate what is the probability of finding an electron there.

All I have to do is add up the two arrows. So I add up the blue arrow and the red arrow, these two vectors. I get a resultant arrow, which is the black thing. And then I take the area of the circle that that black arrow creates. This is his version of Bourne's rule, which is the square of the amplitude of the wave function

tells you the probability. He's saying, oh, just take an area of a circle. He was a wizard would like, like creating mental models. Yeah. And this was his way of doing it. So the area of that circle tells you the probability. Right.

Okay. Yes. And that's the probability for that spot down there. Okay? It's because, and you could do this same thing for every spot along the detector. Very good. So now let's talk about what is the probability in the very middle? We're in the very middle, the two pads are exactly equal.

And so the arrows for the two pads are going to point in the same direction, which is why the area of the circle is going to be way bigger. And so now if you go to the next slide, you'll actually see that this corresponds to that interference pattern that we saw. Right. Right. Where in the middle you have constructive interference because the two arrows are pointing in the same direction.

Having a larger area of probability. Yeah. But where the troughs are, where there's zero probability, that's because the timing there is just right where the arrows are opposite. Mm-hmm. Right? The angles, the angles of their rotation at that particular spot happened to be effectively in opposite direction, which creates that thin line of demarcation where it's destructive. Exactly. And normally with undergrad physics, we think about like it's half a wavelength away.

But half a wavelength means that the clock has turned exactly 180 degrees and not 360. And so this is his way of saying half a wavelength is really my arrow is pointing in the opposite direction. That's interesting. Okay. It's a different, it's a different, yeah, it's the same math.

It's the same math. Yeah. But it's the same math, right? And crucially here, what I want to point out is it doesn't matter which way the arrows point at the end. Okay.

How do you mean? What I mean is, even if the top arrow, both of the arrows pointed in the opposite direction, the area of the circle would be the same. The probability would still be the same. You're saying,

so currently we're looking at both of the arrows pointing slightly, let's say, like, northwest. Sorry, excuse me, northeast. If they were exact, just if we flipped both of them 180 degrees, it doesn't impact the probability. Yes, exactly. It's the exact same. What only matters is the relative between the angle between the two arrows, right? As long as the two add up, the circle remains the same.

Okay? That's a little bit of a key here. The probability space is the same independent of the direction of spin in this construction. Yeah. And independent of the direction of like which way the phase ends up. Right, right, right, right. Which way the phase ends up. The spin is a loaded word.

It's a loaded word. Okay, no, that's fair. I want to be which way the phase ends up. Yeah. Understood. Yeah. Okay. So, yeah, that's the crucial thing to realize is the direction of the arrows don't matter.

It's only the relative directions relative to one another. And I just, and so part of this is we started this conversation, you know, here because we were talking about this algorithm where we were putting in the 0-0-0-0-1-1. Right? And this, we talked about this idea that it's a superposition state. And so we have to put it when we're talking about it as a quantum Turing machine, a quantum algorithm. We can't factor it like we would in a classical system. And so we are able to basically have it either be balanced or kind of.

constant, which gives us effectively this ability to have a zero or one in a quantum system. That's what we talked about previously. Just from a basic, from a math perspective. The reason we brought up the double slit and this Feynman diagram concept is it's representing the same concept. It is. Go ahead. In the sense that those arrows, those arrows represent the complex.

number that is in front of those states. Right. You know when I said like the zero zero, zero one, and like I put a minus one, that's what it represents. So let's, let's actually make a, oh, sorry, go ahead. Actually, yeah, no. So I'm actually going to make a direct comparison between our Deutsche Jose algorithm and that quantum experiment.

And I think you'll see the reason why I sort of did that. So actually, let's go. So yeah, this is, yeah, so if we want to review, this is the Deutsche Jose algorithm, right? You've got the 0-0-1-1-0-1. Right? It starts out with just a 1 in front of everything. So it starts out with the arrows pointing to the right. Okay?

And now it's going to go through the quantum apparatus, and the amplitudes are going to start rotating. And what we want to do is have them interfere at the end. So now, let's consider, instead of two slits, four slits. You see where this is going? Yeah? Our slits are the function in some sense, right? And we've created a superposition.

Each of the super positions is represented by the four holes. And I've got an electron gun. This is, I think, how Feynman might have, like, if he was around to do science communication now, maybe this is how he would have done it, right? So I've got my four holes, and those four holes represent the four binary digits that can go through. Okay? Now, let's see what happens.

The function itself is going to be implemented by some kind of crystal that I'm going to put in those holes, okay? And depending on where the crystals are, that's going to tell me which output goes to one and which output goes to zero. Is the idea that the crystal refracts the light? Yeah, yeah. No, what it's going to do is flip.

Flip, got it. Okay? Whatever direction the arrow came in into that hole. it's just going to add a pie pulse. It's going to add 180 degrees. So in this case, this particular function, this iteration of the function, maps the first and the last 0-0-1-1 into 0,

and 0-1-10 into 1. So this is the X-R function that I'm looking at right now. The X-Or function would have the two crystals that are doing the, I don't know, whatever type of crystal it is, but the two crystals are going to be in the second and the third slits, because those are the ones that are getting mapped to one.

Okay? In this case, this is a balanced function, right? And so that's where I would, but the point is, somebody put the slits there with the holes and put, we don't know where the holes are. In this case, we do, right? But now, now let's go to the next one. Now, suppose that it is a constant,

meaning either there's no crystals in either of the holes, or there's crystals in all four of them. Right. Okay? In that case, what would happen? If there's nothing, then they would all take the red line, and all four of the arrows would point in the same direction, right? Because they're all constructively interfering. This would be four pluses.

Yeah, this would be four pluses, and the resulting arrow would be really long. On the other hand, if there's four crystals, then I'm going to add a 180. And so no matter where I ended up before, I have the 180 added by the crystal. and so they're all going to be pointing in the opposite direction. The phase is going to be pointing in the opposite direction, but the circle that I make is going to be the same. The area of probability is the same. Right?

So I will still detect a particle. This is fascinating. Again, in this constant function, whether either no crystals or all four crystals, our arrow length is the same but in opposite direction. Yes. But it doesn't matter in the context. of the probabilities.

Yes. Because in the Feynman construction, the area of the circle will be identical. The phase direction is irrelevant in that context. Yes, because the detector only cares about what is the area of the circle. Yeah, right?

And so the detector is still going to register a bunch of electrons coming through. Okay, or a bunch of photons or whatever the thing. And the idea is that because when it's constructive, which is that center point, which is a higher probability. constructive interference

that's why the area is so large and then when you get further to the past the other side of there's like the line of deconstructive interference yeah and then well I mean if I were to move the detector somewhere or the other then one of the path lengths will be different from the others right and so some of the arrows will be pointing this way

but the other one that came here and traveled farther is going to like travel more and start like pointing in the other direction Here in this case, it's like those two traveled at exactly the right amount to be pointed in the same direction, right? So this is for a constant function. Now let's look at what a balanced function would do. Like the XOR. In the XOR, the top two are going to have arrows pointing in one direction, but because the middle two have the crystals, they're going to add a phase factor,

and so they're going to have arrows pointing in the opposite direction. And so I'm going to get destructive interference in the middle, where I once had constructive, if there was all crystals or no crystal. Yes. Right? So if I put a detector in the middle there, right?

And all I do is have a one shot. I do a one shot. And I see, do I see a particle or not, right? That'll tell me exactly what the crystal can, like what type of filter the person has put. Is it a balanced filter with only two? or is it a or is it a constant?

Crucially, it doesn't matter where I put these crystals. As long as there's two. Right? As long as there's two, two of the green arrows are going to, two of the arrows are going to be pointing in the opposite direction because I've made that sign flip. Because the phase, again, doesn't matter. Yeah.

Like if I were to put the crystal on the top one, then one of the bottom arrows of the bottom red arrows would flip. Yeah. And one of the top green arrows would flip. But at the end of the day, the sum of the two would still be zero. Yeah. Yeah. This is so good.

And this is so good because it goes back to what it makes me think of again. And correct me if I'm thinking about it. This gives this idea of that reversible function concept we talked about at the beginning. Right. Like we're able to take the result, the arrows on the right, and then look back to construct what the crystal construction was, in the middle because we are able to look at the air. Or am I mixing metaphors there?

I think you're mixing metaphors there. I'm mixing metaphors there. Yeah, yeah, yeah. Yeah, the reversible part of stuff is happening like when we implement the function itself. Like the reversible part is happening. And that's when we have to get into the weeds about like how we actually implement this like function in a quantum computer. We can plus.

Yeah, we need like a, we need like ancillary bit. It's the thing. It's called ancillabit. that like keeps track of all of the information. That stuff, here it's still, it's still, you're still losing information though here, right? Because there's four inputs coming in and only one like thing that I'm thinking, like, you know?

Yes, no, no, that makes sense. I got you. Yeah. And like, remember, quantum mechanics, the observation is not reversible. Right? It destroys whatever thing is happening in the magic box. Yes.

Right. And here we're doing an observation. Yeah. And so that is definitely. Definitely not reversible. No, that's right. That's right. That's right.

Yeah. Whatever is, is the reversible part's happening before we make the observation. Yeah, yeah. The reversible part is how we implement whatever the Oracle and like how we create superpositions because like we're going to start with zero, zero, zero, zero, zero, zero. And then what you do is apply like a Hadamard gate that will make, okay, now I put in a superposition of zero and one, zero and one, and one. And then I entangle them. So now I get all of the different products.

So you can imagine for like n different binary. digits, right? This is going to scale like crazy for a classical computer, but for a quantum computer, all I have to do is one shot. It's what happens inside the brackets of the equation that we were looking at earlier. Yeah, it happens inside of the, you start the cubits, then you do all the nonsense. All of the nonsense has to be reversible. Right, right. Before we make the observation at the very end. No, that makes sense. And that's a good distinction because there's just so many levels to this. So thank you for that correction. Yeah. And so I'm just trying to make sure our, I'm tracking, connecting the ideas we built at the beginning and bringing them down now into.

But I think the way you explain this is between looking at the math structure of balanced versus constant and then correlating it to the experimental architecture of the double slit experiment as a way to visualize the idea of what we're trying to say is happening in the magic box. Yeah, yeah. The double-slit experiment is kind of showing you this interference stuff, right? I mean, in practice, of course, it's a lot more complicated, right? But the main point that I want to say is the reason why the Dozo algorithm works is because it uses interference. Okay?

It's like the problem itself is this kind of useless problem of like, oh, there's a function that's like either balanced or constant. find out what it is. And because it's contrived that way, right, we can use quantum mechanics to like figure it out. And part of the reason why this was the first algorithm is because it's designed to use quantum interference, right? Deutsche was literally thinking about how do I prove to these people that there is a problem that exists, right?

A computational problem that I could solve with a quantum computer in a one shot that would require a classical computer an exponential amount of time. This is a, like, this is a perfectly valid problem, right? Why you would want to solve it? Who knows? Other than it's a very good mental exercise. And it shows you some of the, and it actually proved to the world that, okay, there is a

computational problem out there that definitely a classical computer cannot solve. Okay? Which then created sort of this theoretical motivation or justification to say, okay, well, this is a problem that requires quantum computing to actually be able to efficiently solve. And it's concrete. It's concrete. It's right. It's concrete. It's right there. It's right there. It's right there. I can describe it really well. Yeah. Right. Still, I mean, obviously, people are going to look at this and be like, well, that's a useless problem. Yeah. Okay. Now we're going to get into some useful problems.

This is, well, just to connect it back to the idea of funding and basic research. Sometimes you've got to do stuff that looks useless. Yes. in order to enable and create the foundation for things that are useful. And it's so, it can be counterintuitive, but I always want to hammer this point because we need to just explore sometimes. Yes, I agree.

And just fool around and argue. 100%. 100%. So, Deutsch-Josa, they proposed this thing. 1993, computer scientist Daniel Simon, he formulates a quantum algorithm that demonstrates exponential speed up over a classical randomized algorithms

where he's trying to consider a function that's guaranteed to have a hidden period under Bitwise XOR addition. I don't really want to get into it. Effectively, like, there's a function that has some kind of period. In this case, this is a function that maps three-digit binary numbers

to other three-digit binary numbers, except there's two inputs, always mapped to one input. Okay. So there's eight different binary numbers, but there's only four different outputs. And like, the two green inputs map to the same one, 101, 101, and the two red outputs map to the same zero zero zero, right? And it turns out the bitwise X or of the inputs is the same. It's 110.110 for both, if you were to take the bitwise X or of both of the inputs, okay? The idea is, given I have a function like this with this constraint, can you figure out what is, what is that invariant bitwise X-Hore for the two matched. This is another contrived problem.

It's very similar. It has a similar construction, but it creates a bit more complicated. It creates a different mapping that ultimately is trying to accomplish the same concept. Yeah. It's like we're now trying to think of problems that a quantum computer could do very, very fast that a classical computer can't do very, very fast. It's okay if you didn't understand that. The idea is there's some type of period in my function and this thing is trying to to figure out what that period is. Okay. Simon submits his findings to the 1993 I-Triplea Symposium on theory of computing, okay?

And the program committee rejects the paper. Because it dismisses it as just another artificial black box puzzle. It's like, oh, we got another Deutsch-Jozza here, right? It's like, who cares? Okay, when would I encounter such a periodic bitwise XOR edition function? Right? mathematician Peter Shore is on the committee for the STOC. This is Peter Shore when he was a young man.

And Shore advocates to accept that manuscript because he recognizes that this formulation represents a period finding over an algebraic group. Okay. Why is this important? He realizes that if period finding can be mapped to something that a quantum computer can do, period finding can also be mapped to cyclic groups over integers, meaning like there's some weird algebraic math over integers, and that can be applied to computational problems in cryptography.

The idea is the construction of this has a functional application to cryptography because of some of the mathematical underpinnings. Yes. that define the problem. Exactly. And, you know, Peter Short, he looked at it and was able to see those mathematical underpinnings in the construction.

Yeah. Of the problem. Of the Simon problem. He looked at this and he's like, this looks useless, but there's a way that this can be used to solve something that I think a lot of people are going to care about.

Okay? So he sets out to extend Simon's technique to something called the discrete logarithm problem. April 1994, he succeeded. he figures out how to effectively, how to effectively do like a discrete Fourier transform. You know, in Fourier transforms, we've discussed this a lot. Fourier transforms are when you go from the time domain of a signal to the frequency domain where you're extracting the frequencies

that are relevant in whatever thing, right? In this case, this is like a frequency of numbers type thing, right? And he shares this logarithm result at Bell Labs. He was at Bell Labs. Every Tuesday, they used to have this weekly seminar. He presents it at the seminar. It's known for rigorous and direct questioning. The presentation is very well received. And over the following days, everyone kind of realizes what Shore is going for. Okay? Shore's technique to the discrete logarithm problem gets out and he starts getting phone calls from the academic community because now it's spreading. Okay, Bell Labs had this seminar, the people who attended the seminar, the people who attended the seminar, are talking to their friends. They're talking to their friends. Through the Great Vine, Umesh Vazirani, he's another computer scientist who currently is at the University of California,

Berkeley. He phones Peter Shore on the weekend. So Tuesday is when he gave the seminar on the weekend. Vasirani phones Peter Shore. Yeah, he got that phone call. And Vazirani understands exactly where this is going. And on the phone call, he says, I hear that you can factor efficiently with a quantum computer. Right? And Peter Shore immediately is like this guy. He immediately saw the through line.

Right. Right. In those four days though, Peter Shore spent all of, because I'm sure he got those comments in the seminar, like A. Because basically he sort of had an incomplete map. Yeah. And he had an inkling that this could probably work.

And now he got feedback that it could probably work. More importantly, he got feedback. He got feedback from people who could definitely make it work. And he's like, I need to lock in. Yeah. Like, this is my thing. Right? I mean, Peter Short gave a presentation at UCLA like two or three years ago, like a

symposium. And he was literally talking about this. And he said, you know, when Vasirani telephoned him, and it's like, I hear you can factor efficiently with a quantum computer, he was like, I had been working for four days. And fortunately, I had figured out how to do that. If I hadn't, and like I got that phone call, I would have panicked because I'm like, okay, so now literally everybody is going after the factoring algorithm, right, that he is now known for. Peter Shore spends these days creating that. He establishes a way to find prime factors of large products of primes.

Why is that important? because almost all of cryptography is dependent on large products of primes not being able to get factored efficiently, even by a supercomputer. Okay? If you take a giant prime number and you take a giant prime number, you get an even bigger number, and if you give that to somebody, they could not tell you what two prime numbers make up that product, okay?

Unless you give them one of them. If you give them one of them, then you can just divide and I can get the other one, right? This is how public key and private key encryption works. Public key is the giant big number. Private key is your own special prime number that you can figure out what the other one is based on just dividing. And then you can, you know, this is how passwords work. Email passwords, your Instagram password. This is why, like, hackers need to, like, fool you by telling you that, like, you know, your grandma's in the hospital or something.

And they actually literally need you to type in your past. They can't just like do it. Right? This becomes a huge, huge deal. Okay? In parallel, I just want to also mention in 1996, Love Grover, who's actually, he's an Indian. He develops Grover algorithm also at Bell Labs.

And this is another foundational quantum algorithm. It's the second big foundational quantum algorithm that people are excited about. It's optimal searching of an unstructured database. So if you want to find like where something is, you can do it in square of n time instead of like n. N would be, you know, you got to check every single one to figure out where it is. Squared of n is what he showed. So this is also, this can be like, you know, applied to various other things.

These are the two big algorithms that are the reason why I think quantum computing has found all of this funding. Specifically, I think, Shores, to be perfectly honest. They sort of have two fundamental entry points of what they're actually either doing or solving for. One is this sort of factoring large primes. And the other is like some unbounded database search or bounded database search. Yeah. And because of the structure of the problem, they fundamentally approach it in different ways. Exactly.

And so there's implications and derivative effects. Yeah, you can map certain problems to database search. Right. And then be like, oh, just apply Grover's algorithm. Right. Right. I don't know if there's a lot that you can map to Shores algorithm, but you don't need mapping to understand why Shores is good.

Right. Sure is just like, look, literally anyone in cryptography, CIA, NSA, FBI, China, France, any intelligence community is going to want to have their access to something that can do Shores. World Wars have been lost over not being able to encrypt your communications. 100%. And so from the... Good point.

You know, like that is the... Yeah, exactly. And like prior to Shores' 1994 factoring paper, quantum computing research was like confined to like academic communities. IBM, Yorktown Heights, Oxford, Los Alamos, Bell Labs, physics departments, computer science departments. Shores algorithm altered that dynamic, right? Because now it introduced national security cryptography.

If you have an operational quantum processor that could scale to several thousand logical qubits, now any encrypted communication that relies on RSA, the elliptic curve cryptography that is the bedrock of Bitcoin's blockchain, you can now decrypt it. I can steal all your Bitcoin. There's like, dude, it's, it's kind of scary because, like, I've been reading, there's, there's, I don't know what you want to call them cyber, cyberpunk, cyber gangs, cyber terrorists even, that are just like downloading data.

So that one day when there's a, you know, they're just waiting for one day there's going to be a fault-tolerant quantum computer and then I can just decrypt it. It's that HGTV show or whatever Lifetime TV show hoarders. right like way yeah yeah where they just take what I'm hoarding right yeah and this is

this is such I just briefly want to note that this is kind of like the the scare tactic that in the media context is thrown around a lot it's like oh well like everything that you think is secure now like don't put anything on the internet because as soon as you have

something that breaks this encryption then all of your stuff is accessible and it again like most things somewhere in the middle. It's somewhere in the middle because, like, yes, if you rely on the old algorithms for too long and then a fault-tolerant quantum computer comes in, it's going to be an issue. On the other hand, there's concerns about, like, there's people that calculate how long is it going to take. Even, okay, it's fine. It's not going to take the age of the universe, but for certain hardware

implementations, it might take days or weeks or months, right? I mean, okay, that's better than the age of the universe. But maybe, given. how expensive quantum computers are going to be. Maybe they're not going to like want to get to your Instagram, right? Maybe your Instagram is not worth that. On the other hand, there are also ways to go post-quantum cryptography. There are protocols that are in place. And I think the US government and DARPA specifically have like, and I think NIST, the National Institute for Standards and Technology, they've created like sort of mission statements on how do we go into a post-quantum cryptography world where like things are, things can't be hacked by a quantum computer. So there are efforts to do

this. It's still kind of a hundred percent issue, right? Because if adversarial nation states, like China, I think we have a, we have a headline from Bloomberg that says that China is closing the gap in quantum technology, this is a concern for our own state department and the state departments of the West, right? Because clearly, I mean, you know, for whatever reason geopolitical, China is, is an adversarial nation. And so if they get to this before we do, that's going to be an issue.

Critical infrastructure is definitely going to be the frontier of this battle. Yeah. And because people are going to want to use it for both defensive but 100% offensive purposes. Because in any

proxy war or other kind of geopolitical conflict between the superpowers. This is a thumb on the scale that can be pressed immediately. That arguably because of how connected we are digitally across the world now and even a lot of systems, you can air gap stuff and et cetera, but even we've seen an example of like Stuxnet with the Iranian nuclear missile program and how we can find ways into these

systems that ostensibly are not connected to the quote unquote internet. and still have a lot of damage. And so this is, I know the focus of thousands, tens of thousands of people every single day in the variety of ways that the, because the implications are you would not want encrypted systems related to missiles, silos. Yeah, that would be really bad. And other kind of things, you would not want that to be easily accessible. Yes, exactly. As an example. Yeah.

And to show you just how much Shores algorithm really changed the landscape, like, Shores Algorithm came out in the 1990s and the DARPA QIST program established in 2001, this is the Quantum Information Science and Technology Initiative, this is the thing that funded University and Industrial Laboratories to pursue scalable cubit hardware, right? This created the funding that enabled now technologies like companies like Google and IBM and places to now piggyback. off that research and try to create an actual quantum computer.

The ARDA roadmap, the ARDA, that's the advanced research and development activity, in 2002 and 2004, they convened like a quantum information science and technology experts panel to draft formal roadmaps to establish benchmarks on things like how good a quantum computer can keep its quantum superpositions, things like gate fidelity, cubit scalability and quantum error correction. Those are more hardware questions, which we are going to get into in the next episode when we talk about the hardware.

But I hope that this episode kind of showed you, you know, kind of the theory behind it and why we're building this thing in the first place. Okay? And I really personally, I think it's, personally, I think it's because of Shores and Grovers. Feynman's dream of material science, I think in the age of AI, it's less so much a priority, right?

Because just look at Google DeepMinds Alpha Fold. It won the Nobel Prize because it's really that good at predicting protein structure. Maybe we don't need a quantum computer to predict protein structure. I will make a small note. Yes, it's not 100% efficient. Yes, we've gotten a lot of comments about, yes, alpha fold is interesting. but when brought into later stages. Yeah.

So I'm just qualifying it. Yes, you're aware. It's not perfect. We're not saying that it's perfect. Yeah. But from where we were before to it existing and being able to then iterate and build on top of that. Yeah. It's going to get good. And there's no reason to believe that it's not going to get good for like material science itself.

100%. And like, you know, physics in general. The other thing why the other reason is like, I think the best algorithm with that's out there to, the one that's like most frequently used to figure out things like ground states of a material is something called the variational quantum eigensolver. This is, you know, just like how Shores algorithm is built for this purpose of factoring. This VQE algorithm is built for the purpose of understanding materials. But that algorithm requires you to guess and onsats in, in how Hans Beta had this idea of guessing an answer

and then optimizing around what that answer is. Well, this variational quantum eigensolver requires guessing at what you think the ground state wave function looks like and then optimizing around that wave function. Well, if your guess is completely out of left field, you're not actually going to get anywhere. Right.

Right. So it's not like one of these, it's not the dream of findment of like, oh, just like simulate it, right? You still need a quantum algorithm to do the computation. And it's not as simple as like, oh, we just take density functional theory and create a quantum version of density functional theory, right? Where like, oh, I know exactly what the electron clouds look.

The whole point is that thing is going to tell me what the electron clouds look like, right? So I have to guess first description. And then it only really varies the parameters around my guess. If my guess is wrong, I could be in trouble. And as I get to larger and larger systems, the probability of my guess becoming wrong gets higher and higher. So there's still not a good enough, I think, quantum algorithm to get me the material science promise that Feynman was dreaming of. Maybe one person who will help push the envelope there is someone we just covered in our last episode, Omar Yagi, who's just moved out to Beijing. former Nobel Prize winner, 2025, and is the pioneer of reticular chemistry, and is pushing this

idea of what's being dubbed amometry, which is AI, material science, and chemistry, and trying to basically blend these disciplines. And potentially, I know that the quantum piece and quantum algorithms are not necessarily the basis of the concept. But seeing where this implement, of AI in speeding up next-gen material science discovery. And then if you add a fundamental quantum algorithm discovery in that context, I think the acceleration becomes very interesting. Yeah, yeah. I mean, it could be like, we could live in a future where like, um, AI systems are making the guess. Right. Right. And then they get an answer from the quantum machine. Right. And then they, they iterate on the guess. I mean, who knows, right? Maybe in the future,

only AI uses quantum machines because they're the ones creating such, like amazing algorithms. Who knows? It's a ripe field, but that's how we got here. Yeah. And I think that this is a great foundation. Again, the whole point of this show is we have an expert and a layman, myself being the layman, a resident PhD, Krishna Chowdhury being the expert, trying to navigate these complex topics. at both levels. At an expert level.

So for those who are super technical, shout out members of the HRL team that made it through two hours of this podcast. Literally no one. If you did, drop it in the group chat. I want to hear you guys. And then the regular everyday people like me that do have an interest and curiosity

about some of these things, but may not have the foundational tools to be able to dive in and get it. And I think that blend is why so many people love the pod because we're able to communicate to two different audiences. And so for those who keep asking in the comments, why does Lester just sit there staring the whole time? Yeah, first of all, actually, no, this is a family-friendly show.

So I'm not going to say what I think I want to say. I just, the structure of this show is very much present in other forms of media. You have subject matter expert, you have an everyday person, and you're trying to communicate for two different audiences listening. And so my job is to smile, listen, and look pretty, and sound occasionally kind of smart. Occasionally be like, oh, that's good. That's what I fight for on this show.

Krishina being surprised that I made that, oh, made that connection. That's pretty good. So again, part two, we're going to actually dive into and hopefully have a physical copy of that we can hang on the wall and start our gallery wall in the back of this cover story, quantum silicon processor.

Yeah. Is that, that is correct? Yeah, you're goddamn right. It's going to be so exciting because we will now have this foundation of understanding the history of why this research discipline even began. And in modern times, what was arguably the enabling layer to having the likes of IBM, Google, Microsoft, HRL, a variety of other players. I wouldn't put Microsoft in there, but...

We'll talk about that in part two. We'll talk about that in part two. But this is now going to get into the fun stuff. We again appreciate you all greatly. If you've made it to the end of the pod, and you have not yet given us a five-star on Apple Podcasts or Spotify, now is a great time to do so.

You're on a jog, you're at the gym, you're sitting in the car in traffic on the way to work or from work, it really helps us reach more people. We are trying to build the best science show on the planet. Share in the group chat, DMs, all the other things. Let's have a, because I always like seeing those who reach the end, if you have a comment to leave, you just gave one for, you gave an action for HRL, but that's in the group chat.

Yeah. But for the public, if there's one comment to leave, because they've made it this far into the pod so that we know who the real fans are. What do you think? It's tough. I don't know. What would you want?

What would you want? If you had a personal quantum computer, what would you want to do with it? That's a good one. That's a very good one. I have thoughts, but we will save it for the comments. My name is Lester Nare,

joined as always by my co-host, our resident PhD, Nature cover story co-author. Krishna Chowdhury, we are so grateful for you all listening to us rant every day. We also have seen your feedback, and so we know some of the things you all would like us to do differently as we move forward. As we have the opportunity to do so, we will do so. We will see you all next week for Part 2 on Quantum Computing.