How Quantum Computing Actually Works (Part 1)

Opening

0:00There'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, uh, maybe not. What ends up happening is there's only very specific types of questions where you can exploit

Quantum Computing, Part I

0:31the properties of quantum mechanics. >> Okay. Hello internet. This is your captain speaking Lester Narre 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 8125 released on July 30th 2026 featuring our resident physicist Krishna as a co-author on the cover paper of

1:11nature. We are very excited uh about this. This is going to be right in the wheelhouse of the show and there were 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.

Krishna’s Nature cover paper

1:45Those of you who keep up with us on Instagram and watch our stories there will know that I am 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? Um, 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. Um, I wouldn't have guessed that it would have been a quantum computing story though and I think if if you ask uh PhD Krishna

2:27about it, he'd be like, wait, what happened to the original plot of the movie? You know, 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 that's me highlighted. It's in alphabetical order. Um, so you know, Chowdery CH comes up

3:09maybe 20% down. If if they actually did it in order of importance, I think I'd be somewhere in the bottom uh bottom line there. >> Nobody has to know, >> you know. Yeah. Hey, it still counts. It still counts. And um 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 um the Brook Havens star collaboration when they were doing like um some weird quirk

3:49physics 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 Blandon at Carnegie. He had mentioned this transition from individual name papers to sort of this idea of big science. Exactly. And he kind of lived through that transition. >> Yes. Exactly. And and you know 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

Why quantum computing needs a two-part series

4:31that 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 because um 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 broad broader, you know, 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 mostly a hardware paper. M >> but in order to really understand why

5:13it'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's trapped ions there's neutral atoms there's superconducting cubits there's spins that's the one that um we're going to talk about there's um myano modes there from Microsoft. I don't know why that's on there to be honest, but um 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

5:55should care. >> I hear about quantum, you know, there's Marvel movies that use the word quantum. Yeah. >> Uh it was one of the worst Marvel movies. I think the Ant-Man one. Quantum something. Literally one of the worst. Um it's used as this rhetorical device for a lot of different ideas that are totally unrelated >> Yeah. >> to the actual Yeah. >> uh scientific study. And so I I think this was going to be really interesting. You know, 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 is going to be interesting in helping to really distill

6:36down 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 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, 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 cubit?

7:17What 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. >> Um, >> against the humble beginnings of this field, it's like countercultural beginnings in the 1960s, '7s, and ' 80s. We're going to focus a lot on some of the human stories behind it. Um, 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

7:58beginnings to where we are now, it's a it's a it's an incredible story. I want to give our audience a sense of why everyone is so obsessed with building one. And um I want to dismantle the hype is another big thing that I want to do here because we we hear a lot of hype about quantum as you mentioned. It's in every Marvel movie whenever they need some gimmick. uh to like time travel or like teleport, >> multiverse, what? Like everything has a quantum nexus. >> Yeah. Like erase memories that the the new Spider-Man movie, I haven't watched it yet. I I want to, but there's probably some quantum quantum nonsense in there. Um so if you're not careful, you can get it wrong, right? The hype is

8:40definitely real and it's definitely there. There's a common phrase that's

The biggest misconception about quantum computers

8:43used um that you know quantum 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 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. Um this is a big

9:24argument 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 and can be done in >> Yeah. >> seconds. and encryption is maybe the only thing >> where it's true >> where it's actually true. Everything else though uh maybe not right so that's that's kind of what I'm trying to get into it. What ends up happening is there's only very specific types of questions where you can exploit the the properties of quantum mechanics. Okay. And um in this episode we're going to explore one of the famous algorithms called the Deutsch Joa algorithm. It's probably the simplest algorithm to understand. I don't think it's very useful

10:05except 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 um why what's actually happening and we will talk about Shor's algorithm. Don't worry about it. But um we're not going to like go into detail because that's going to require another full deep dive. I just have to say Deutsch Deutsch Joseph sounds like a starter for Liverpool. >> It totally does. Yeah. Um so 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.

Bell’s theorem and local realism

10:46Um 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 for. A lot of people think that John Bell was mostly at CERN, but actually he took a one-year sbatical and he came to the United States in 1964. He visited Stanford University and the University of Wisconsin. And during that sbatical 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

11:28we 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 Fineman got into it. A lot of people just start with Fineman. >> Mhm. >> There's a lot of stuff that happened before Fineman. Okay. And I don't want to be a podcast that is the cult of Fineman. There's plenty out there. Um Fineman is a great man as we will see. um 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/amea250. It's an interactive timeline that covers

12:08some of the stuff you just mentioned. That's prefineman as well as many of the other great discoveries in our history. Um and it's I think a really humbling experience to go through it in that format. >> Yeah. Um and Fineman is mentioned a lot on that timeline because he did a lot of really cool things. So let's start with um our entanglement experiment that everyone gets to know. Alice and Bob. Okay. They always use Alice and Bob. I don't know why. I think it's because A and B. Um maybe if somebody has an idea of of historically why we always use Alice and Bob in these entanglement thought experiments, please let us know.

12:48So here's the idea. Suppose I create two particles with spin and they're entangled. So I don't know um 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 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. Um, but according to quantum mechanics,

13:28there'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 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 observed? >> Exactly. Which is that's Neil's bore >> which is a complex what is >> yeah what does that even mean? Right. So Neil's bore is like no that second thing. No that's it. Right. Uh there's no well- definfined spin and then only when you observe it the wave function

14:09collapses and then you get uh one direction or the other. Right? And Einstein's like this 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 the speed of light which makes sense. Um 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 the speed of light. There's no communication. Okay. So, effectively, if you've seen the the Denzel Washington movie, Deja Vu, >> he's he's effectively Denzel Washington.

14:49>> 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 uh the and one of the scientists 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 and then he takes a a chair and destroys a monitor and he's like this monitor is now dead. It is not in a superp position of different entropy in such >> and that's Einstein. >> That's a 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 in some ways great and in some ways not so great but it it it

15:32gives a real lived human experience to these theoretical questions in a way that you could try to kind of visualize. >> Yeah. And and honestly I was Denzel Washington before I just sort of you know succumbed to my fate and was like okay just shut up and calculate you know but when you're first learning it everyone is Denzel Washington. What are you talking about? Right. Um 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 Pedolski Rosen paper that Einstein published in 1935 and he showed that you know if you have some kind of

16:14local hidden variable then you can perhaps account for 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. There's like 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 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. Um there's no

16:55way to prove it one way or the other. Who cares? >> Um 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 Fidilski Rosen paradox. Um and crucially the affiliation there is University of Wisconsin Madison. So this is the paper for Bell's inequality and it's in America. Um and that's why it's on our uh America 250. You know it's like it hey that one year that one year was everything. Um, so he realizes that we can actually expand the Alice and Bob experiment to give Alice and Bob a choice.

17:36Instead of them only observing a single um a single direction, right, we can maybe have a filter where they they can observe the spin in the in the Z direction up and down or in the X direction sideways. Okay. So, like when the when 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

18:17options based 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 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 and Bob

18:59and 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. M >> 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 Clauser very famously did this at Berkeley another one in our America 250 timeline. Um and he showed that in fact there's a

Experimental tests of Bell’s inequality

19:36violation right >> there's a violation of Bell's inequality and you cannot factor this probability distribution. Okay, there's no separate components. You have to consider the entire thing in this giant no matter how far apart Alice and Bob are. Okay, John Clauser did this in the he won the 2022 Nobel Prize in physics along with Aline aspect and Anton Zylinger. >> Um these guys were instrumental at taking Bell's inequality to the absolute limit. John Clauser was the first guy to do it and these other two started considering very very like you know whenever whenever um whenever John Clauser did that there's there's people

20:17that'll come up and be like well maybe the hidden variable is like in the lab right in in the giant room that John Clauser is in because because he's making these 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 that are local to him, right? He's like choosing when to 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 is when does it not become >> Yeah. Yeah. So then Alan Aspect Alan Aspect I think one of his one of his amazing experiments he did actually I believe it was at Tenneref in the

20:58observatories there. Tenneref has these amazing observatories um optical telescopes that are across the mountain right so now what you can do the main the main problem with the with um John Clauser'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. Um Alan aspect said okay I'm going to point telescopes in opposite directions of the universe. Okay, one is going to point at a quazar that's like billions of light years this way and one is going to point at a quazar a billion lightyears that way and depending on the light from the quazars the quaazars are

21:40going 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 >> the >> at that point it's like what did the hell are you what is local right and and so just to say this back to you the The idea is like who decides the position of the filter initially was not considered sufficient to say that the hidden variable is 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 >> Yeah. as the variable that decides what

22:22direction the filter is in in this matrix of options. >> The now our experimental design is billions of light years across >> versus just whatever a couple tens of yards or whatever. And so you're and then the argument that this hidden variable can exist in this billion light years across experimental apparatus no long can no longer be considered reasonable. >> Yeah. >> Um and and now we we are able to we still violate Bell >> theorem. And so we we the realists Sorry. >> Yeah. Sorry. I mean, unless you're really like doubling down and you're saying there's just a universewide local variable or something. Uh, you know, it it's getting it's getting tenuous now,

23:02right? >> Because now we're arguing over the definition of local. >> Yeah. Yeah. Yeah. Exactly. Right. Um, so the key thing here that I want you to take away, >> okay, >> 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 Fineman 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 is a there's a rule set above when

23:46either of them observed or act in a system that is not independent of each other? Like I'm just trying. >> Yeah. So there's um there's like in order to really try and understand what is happening in this experiment, we have to 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. They are connected by a single wave function is is is one way of putting it. Right? Like the mathematics is inherently tied. It is one block. >> Yes. >> Right. >> It's a it is a singular Lego block. You can't break it down into subsequent smaller Lego blocks. No. The whole

24:26system that you're observing at whatever scale. >> Yeah. >> Has to be considered a singular Lego block in this analogy. >> Yeah. Yeah. In order to really capture all of the quantum mechanics that is happening. Okay. there's no way to be like there's Aiden variable and so you know this guy has this thing saved that guy has that thing saved and and so >> okay >> you know what I mean okay so that's the key insight that Fman is going to use later in 1981 now this is in the 1960s and we've got a long way to go before 1981 okay cuz 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 like

25:06mathematical ical 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 it's still this mathematical abstraction. Okay. Ralph Landau, he's actually at IBM research, which um we might hear a lot more about in this episode and in the next episode. More on that later. But Ralph Landau in 1961 he establishes that information is actually inherently physical. Okay? And he demonstrates this by saying that any logically irreversible operation meaning

25:47something that destroys information is going to cost you heat. Okay, here's what I mean by that. like um there

Landauer: information is physical

25:58there's a fundamental minimum amount of thermal energy that needs to be dissipated into an environment um 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 to let go of that heat is the the temperature multiplied by Boltzman constant multiplied by log of two the KBT is like the amount of jiggle that you have for every thing that can jiggle every degree degree of freedom and the log two is like it reminds you of like uh entropy is the log of the number of microates. In this case the number of microates 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

26:39normal 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 ANDgate for example let me show you how this thing erases information. Okay, an ANDgate takes your inputs. There's two inputs that are either 0 or one. And if they're 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 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 1 one gets mapped to a one. Now this is irreversible

27:22because 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 if I gave you the output is one then of course you could tell me it's 1 one >> but if the output is zero then you couldn't tell me which of the three it came from >> so that's an eraser 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 ANDgate land's principle comes comes in and you're going to have to release some amount of heat. >> Okay. >> And like the the ability to go back is what's being released in the heat. The degradation of like understanding what your previous state was. >> Exactly. Exactly. It's kind of like an

28:02arrow of time argument that you're making >> TVA from Loki season 1. >> Yeah. And this is totally okay for classical computing. Okay. We use so many gates and not gate and or gates in our exor in our classical laptops. Right. fine in quantum mechanics this is not okay. Okay, there's two reasons. The first one is kind of simple, right? If we want to use quantum mechanics to do computation, um we want to work with the

Why quantum logic must be reversible

28:28quantum 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 um 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 your your quantum system almost has to maintain this single Lego block state. >> Mhm. >> And it can't be messed around with >> because then that fundamentally changes. >> Yeah. >> The quantum magic of the system. >> Exactly. Yeah. It's like um the only

29:09part 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 Schroinger'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 Schroinger's equations. This this means that quantum mechanics has unitary

29:50evolution. 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? Um, no, you can only have reversible logic. Yeah, good, good, good catch. Right. Because the point is a system has to basically continuously maintain >> like like basically until the point of observation, which you want to be able to decide when that happens. >> You want to just be able to have this system >> operate in this state, which means it needs to be able to traverse between >> Yeah. >> all of the quantity >> and I need to be able to save like all

30:30of my progress in some sense, you know? >> Okay. Yeah. Yeah, I I I I get the point that you're saying, which is like the benefit of a quantum system is that um >> you don't mess with it until the end, >> right? Everything is reversible. >> Yeah. You don't Yeah. 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? You have to obey the laws of Schroinger's equations and like unitary dynamics 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

31:12sule or any other kind of cooking analogy. Um 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 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. >> Uh you cannot get out of a classical system no matter how much power compute. Yeah. >> How well you dissipate the heat, none of that matters. >> None of that matters. Okay. In order to work with the quantum magic, you got to you got to work in the constraints of

31:52quantum mechanics and equations >> or Heisenberg if you're in that camp, right? So, um it's unclear whether this is even possible though, right? >> Like can you compute >> with reversible logic, right? because

Bennett, Toffoli and reversible computation

32:08we're used to and gates and or those are those are and and we got algorithms galore for days for that kind of stuff right um 1973 Charles Bennett demonstrates that you can actually use universal reversible computation um and along with him Edward Fredkin and Tomaso Tofouli who's over here Tomaso Tofo invents something called a tofully gate which is a controlled controlled notgate 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 the logic the truth table is is unique because my three inputs give me three

32:49outputs 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 this makes sense It's unlike our previous uh and ANDgate 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 to three so you basically retain all the degrees of information necessary to go backwards um and that's a fundamental building block to now be able to potentially do the type of computation that you would you have uh

33:31the 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 a algorithm. Maybe >> maybe and tofully um for for those that are like well-versed in quantum computing or are like just starting to learn about it, you'll hear a lot about tofully 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 a a gate that can make up universal um logic in some sense. So following this, Paul Beni off at the Argon National Lab, he creates a quantum mechanics version of the state transitions in touring machines. Alan Turing and um Church who we talked about

34:13um again on our America 250. I keep pitching this thing, but um they demonstrated at Princeton that you know um any computable algorithm can be computed on a touring machine using these like straight state transitions and very simple logic. He showed that, you know, there there's a version of that that I can do in quantum mechanics. Okay, side note, um Charles Bennett, who's the guy who um demonstrated that first reversible computation, um he was involved in the early days of quantum cryptography. So his undergrad friend Stephven Wizzner at um at Colombia, they had an idea to use

Quantum money and the birth of quantum information

34:48Heisenberg's uncertainty principle to create unforgeable money. So this is before um 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, right? Um there's a funny story where Bennett attended the ITLE e conference on foundations of computer science in Puerto Rico and on one of these afternoons um this cryptographer Jillis 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 and the quote we have from Brassard

35:30is like, "I was trapped, so I listened politely because they're in the middle of the ocean." He's just Brassard is just trying to have a good time before his talk about like cryptography. >> Puerto Rico. He's not trying to have a good time. >> Yeah. Yeah. He's trying to have a good time and and Bennett just swims up to him. He's 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 um 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. Um and the two of them form a collaboration that starts a whole new field of quantum information science. They win the touring prize together. Um

36:11and 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 touring prize together. Um, but all from a serendipitous meeting in Puerto Rico in the ocean, right, where Bennett just like accosted this guy. This the only context I have recently of this idea of quantum teleportation was a news story maybe from a year or two ago where the 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

36:52heard that and cuz 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, >> right? So, it starts here on a beach in Puerto Rico. >> Yeah. And now it's in orbit. Um, but that's we're 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 there all these stories and headlines and tech blogs and whatever. Oh quantum teleportation everything is going to be whatever. >> Yeah. But it it starts with these small meetings between human beings right at conferences crucially. Yes. So when

37:32people say that they don't want to fund conferences, conferences is where ideas come together. Osmosis >> you know like it's it's very important to bring human beings together. Um so this is the status in the early 1980s. Okay, we've got some indication that quantum computing could work, right? Like Landar's principle is not a no-go that we thought. There's ways to get around um 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. Fineman is comes in over here. Okay, so this is where Fineman enters the fray. Um, he visits his old

Feynman enters quantum computing

38:16alma mater, MIT. >> We make fun of MIT a lot on this podcast. In this one, I I'll have to give him credit. Okay. 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 um 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 um that's similar >> out in um Lake Arrowhead actually. Um and I had a I had the pleasure of

38:57attending like a neuroscience workshop there. It'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 taken by Charles Bennett, the the guy who went into the ocean and tried to pitch this quantum money thing. So, Charles Bennett was there. >> Okay. >> Um along with you've got Freeman Dyson on the left. Um Paul Beni off. Paul Benoff's the turning machine guy. Um, you've got Ralph Landau. That's the Land Hour limit thing. John Wheeler. Wheeler is just there in allwhere. He's everywhere.

39:37>> He's like a Nick Fury in Marvel. >> Yeah, dude. Oh my god, that's such a good analogy. >> Yeah. Wheeler is the Nick Fury of 20th century physics. Yeah. And then, um, of course, Richard Fineman and, um, Tom Tafoy. So, all all of the guys that we just talked about, they're at this conference, right? Fineman 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. Um 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,

Why simulate physics with a quantum computer?

40:20everyone 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 you're 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 t tunneling, the thermal fluctuations. It limits how small you can make your transistors, things like that. Fineman 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

41:01quantum 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 um 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 Fineman 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? >> Mhm. >> This is where Bell's theorem came in. >> Okay. >> Mhm. >> Remember I was harping on earlier this

41:42idea that the physics of two particles cannot be factored into two independent mathematical probabilities. >> We have to look at it as one Lego block, not 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 there's no way to combine them later on, right? Um if you could then simulating an n particle quantum system with a classical computer would be pretty straightforward. You just create some kind of software program that assigns like n independent data tables or sub routines for all of the n independent particles. You look them up. Each is tracking some kind of isolated

42:22local state. And then your memory and processing time scales linearly like the order of n like however many particles you have that's about you know how it's going to scale. >> The point being it's just becomes a compute and power. >> Yeah. Yeah. And you make a bigger computer right you could infinite you could scale up to some upper bound that then covers all the types of >> Yeah. >> simulations you're trying to >> and you just have like one subruine for each particle and you're fine and you're fine. Right. But quantum probability distributions do not factor. >> That's what Belle showed. Right. Right. If you want to talk about reality, the experiments show this, right? This is no longer in our head.

43:04>> 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 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 um that can be like, you know, spin up or spin down. Um, a classical computer would be forced to store and update a joint probability

Why classical simulation explodes

43:41like vector tensor or like set of numbers across all 2 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 up. And those are different >> across both the Z and the X. >> Well, here I'm just I'm just saying like >> even if you keep it even if you 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 you know because like they're all like like Yeah. Whatever. In any case, like let's let's just say two two particle states, right?

44:22Two state systems, right? Those two states can actually go in Z and X is is is the point that I was trying to make. But but um >> what you need to do is for Alice and Bob, you need to keep track of four possibilities. The up, the down, the down up, and the and the and the up down. Really, you got to take take um 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 the electron one is up and electron 2 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 combining like linear combinations of them. But in any case it's always 2 to the n >> is the idea. Now this becomes

45:03insurmountable very very quickly. very very quickly. Okay, if you want 50 entangled two-state particles, that's 2 to the 50 complex numbers that you have to take care of, right? 2 to the 50 um hack for students that are listening. Um 2 10 is like 10 3 because 2 to the 10 is 10 24 which is 10 3. So if you ever want to go into base 10, 2 is like 10 3 to the 5 which is 10 15. So you got to take care of 10 15 complex numbers. If you're trying to sim 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, um that's going to

45:43be 2 300, which is uh 2 10 to the 30, which is 10 3, which is 10 90 numbers. That exceeds the number of elementary particles in our observable universe. There's estimates out there that there are only 10 the 80 atoms, right? So just to simulate 300 two-state particles, I need 10^ the 90 numbers. And it's kind of crazy. The 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. Yeah.

46:23>> That only had two states, which is not real. Like it's not practical in real life. >> Yeah. No, I'm saying a protein would be would be crazy. I mean, maybe you could simulate if you had all the time in the universe like a water molecule with 10 with with 10 electrons, right? there there's no amount brute force um 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 uh because you can't factor >> factor it means that the amount of uh variables and interactions you're

47:03tracking continuously is just is just insane. Yeah. And 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 80 particles, right? Even if all of those particles are two-state systems, there's two there's 2 to the 10 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. Yeah. >> But I'm just saying like it's kind of crazy that the universe is keeping track of all of those complex amplitudes to

47:44give 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 it's it's cuz it's hard to even >> and like where anyway. Yeah, but that's that's an aside about like just like the nature of reality and like totally totally totally >> why quantum mechanics is weird. But in any case, right, this is what Fineman is talking about and he says instead of classical bits where we'd have to we'd have to create 10 the 90 bits to keep track of 300 thingies. Um instead, what if we use a quantum version of a bit, right? What if we create a computer

The idea of a quantum bit

48:24where 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 the quantum mechanics inside the computer is going to take care of all of the superposition entanglement and all of the blow up of complex numbers, right? Because 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. 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 um rings across a lot of quantum computing

49:05literature 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, um, we're still trying to make one. >> This is I 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 at a theoretical level. Mhm. How that informed the early

49:46countercultural 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 found violations of Bell's theorem that mean that the hidden variable thing and the realists sorry >> and if we really want to create simulations that are true to our lived fourdimensional time space. >> Yeah. Whatever. Yeah. >> Right. This magical thingy.

50:27>> Um we're going to need the compute layer to reflect the same quantum mechanical attributes that our theoretical frameworks currently suggest. Yeah. >> Exist. >> Yes. Is that a fair? >> That's exactly right. And and that talk happened in 1981. And he he mentions all of the priors that I've been talking about. He mentions Bell's theorem. He mentions Tifo and Beni off and all these people who said, "Hey, quantum 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

51:07there's this rich underlying layer that we can actually exploit if we want to, right? um Fineman's argument about

Why quantum computing became worth billions

51:15fundamental science and like you know this this becomes something that um is a polinomial 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 the reason it is a trillion dollar computing industry is because of the stuff that we are getting into after our break, namely Shor's algorithm and um Bitcoin going to zero.

FFP break + science headlines

51:54And so with that, let's 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 overlays 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. For

52:38those who catch our clips on Tik Tok and Instagram on a regular basis, put them in those group DMs. Share the best science show on the planet with your friends, co-workers, bring it to Journal Club. If you are watching this full episode from the f 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 uh announcements or uh 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 oneyear anniversary.

53:18You may have noticed behind us there are gold balloons representing 250. And while we talked a lot about America 250, the gold balloons Yeah. are not necessarily here to celebrate our America 250 episode, but they are here thanks to the loving wives Anna and Joanie 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. Uh, we love you both so much. And I'm just going to

54:00hit one last note before we get into some quick headlines as a pallet cleanser before we dive back into our quantum episodes. If you would like to support the show, fivestar reviews, like, comment, share, subscribe. If you would like to donate to the show, you can head to ffpod.com/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

54:41out there in the world of science. Our first story came out breaking today. It's been all over the news related to pharmaceutical giants Maderna and Merc saying uh 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. uh this was a combination of madna bringing their mRNA vaccine structure and merc bringing their kruda and the idea is they you know we've talked about the immune system in the past on the pod and part

55:21of 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 uh what was previously not visible to them. However, uh they've not published their results, >> okay, >> 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 um some real there's there does seem to be a there there. >> Okay. Um and so according to their news release, the mRNA based vaccine was

56:02tested in a latestage trial involving people who had had uh 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 it there's potential that it generalizes. >> Interesting. >> So that 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. But that's an interesting first story from us that's uh that's out today. Our second story in the news headlines that was interesting. This is from UC Berkeley. Uh this idea of a new uh technique called trace that pinpoints

56:43human DNA inherited from ghost ancestors. Uh there have been a lot of uh 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 before previously as well Neanderthalss and Dennisovven's uh interbred with modern human ancestors leaving behind a telltale DNA in our genomes. And so if you do 23 andme or ancestry.com you can kind of know and see where those ancestry is from. Um but now the researchers at UC Berkeley have found out that we may actually have evidence for uh modern human interbreeding with

57:24two much older unknown ancestors that have not yet been recorded in any of the genomic records specifically. Wow. >> And the time period in which the interbreeding started was prior to the 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 >> Yes. >> then it's much more widespread, 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 uh

58:05traces of these two uh ancestral lines across every uh the Eurasian the the like Denisova and Neander it's it's present across everybody. >> Oh okay. >> And so now there's obviously going to be followup around this but is it it is an interesting and the thing is it started uh there was this breakoff. It started prior and then there was apparently a reconnection right before uh the rise of homo sapiion and so there there seems to be some interesting >> there's some interesting genetic history uh 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 uh story

58:46reference point here uh we are always going to talk about funding. Yesterday the NSF announced $1.5 billion of the foundational research. This is the idea that uh every year a couple of different times they will have their new notices for funding opportunities which define what their funding under what dynamics and the requirements to submit your proposals. Um there's a lot of kurfuffle right now around funding uh because there's uh significant cuts that the current Trump administration is trying to make around funding generally as well as changes to how grants are actually um uh how grants are awarded themselves

59:26which 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 um yeah, the the peer review panel of um experts and scientists no longer have final say. It's just an opinion >> which um again we can talk about iterating on the process. Um, but I think this is a a hammer approach to something that requires a scalpel. Um, the $ 1.5 billion uh uh new uh proposals that were announced cross all of the fundamental hard sciences. Okay.

1:00:07>> Uh so this is not the social sciences per se. We're talking about things like uh biological science, expeditions and computing, electrical communications, bioengineering, uh manufacturing. One new area that I think was allocated about $30 million was emerging frontiers in wavebased computing. Um, which has maybe some kind of tangential relation to what we're talking about. And so the thing is 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 uh you know bolstering from a

1:00:48geopolitical perspective. Obviously, we want to be able to do fundamental research as we've talked about a lot that does not necessarily have a direct throughine to a practical commercial application because some of the biggest things we have discovered in the US 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 US, we have an incredible interactive explorer for funding over the last 60 years in the United States. you can understand how research and development funding uh has

1:01:29been allocated across agencies even including last year's FY2026 and this year's still ongoing FY2027 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 AAS 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 can't remember the Marvel movie quantum uh quantum mania? There it

Correction: the Riemann Hypothesis

1:02:08is. And that's the one and it was apparently terrible. So, we don't care about that. But we have one one correction from our previous episode which was on the Remon hypothesis. >> Yes. So, um the the previous episode, um a lot of you saw it and um most of it I'm very proud of. Um there's one segment where I think I could have done better. Um and it was when we were discussing some of Claude's results and um specifically this particular graphic came up. Um as background um Claude made some progress in a related problem to the Remon hypothesis where the remon hypothesis is where are the zeros of the

1:02:49remon zeta function um are they all on the critical line where the real part of the zeros is is 1/2. 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, right? And and I mistakenly said that if we get to 100% that's going to be the remon hypothesis. And it's because that graphic um showed 100% line over there and it said remon hypothesis and I just wasn't really thinking it's it's a lot richer than

1:03:30that because this is a statistical argument, right? Um, and you actually brought it up earlier when you said that, you know, um, with infinities, it's hard to talk about percentages. Like when we say that we when we say that 67% or let's say 2/3, let's say 2/3 of all zeros are on the critical line. Um, GH 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 2/3? Well, what that means is two out of three in that infinite set are on the line. That's what that's what Claude is saying, right? There's an infinite set and just like how one out

1:04:10of 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? Um and then and then I mistakenly said that if we get to 100 that'll mean the remon hypothesis is true. That's not it'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 remon hypothesis

1:04:51would still be false because not every zero is on the critical line. Statistically, we can reach a hundred and you still haven't proven the remon hypothesis. That's the point. >> And so, AI, you're still 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 know what I'm talking about. It's 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 rent might actually go down.

1:05:33>> I don't care if I lose my hearing with like like I don't care if my wife like you know and it's like obviously satire satire around it but um 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

1:06:15were 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

David Deutsch and universal quantum computing

1:06:26Fineman's keynote address at that conference. Um and as I said, you know, Fineman'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. Um, if you notice it is communicated by Roger Penrose, fellow of the Royal Society to

1:07:06the proceedings of the Royal Society. So, Roger Penrose is also in this story. um 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 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 when we look at like quantum algorithms and you have like these blocks. We're going to see some of these later on. Um the logic operations are now represented by unitary matrices the the kinds of tofully gates and things like that that we were talking about earlier. Um these

1:07:47are reversible logic gates and they can act on a register of quantum bits or cubits. 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 this theory and the software of the algorithm to now how that interacts with the 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 Fineman saying that you know you've got these two-state

1:08:28systems. He's 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 um side note, Deutsche's academic pursuit is driven by a commitment to the many worlds 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. um during his Oxford studies as a graduate student um he met Bryce Dwit who's a very famous theoretical physicist who was a collaborator of John Wheeler at

1:09:09Princeton. I think Dwit 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 adviser of Hugh Everett who's the guy behind the Everett hypothesis of many worlds. Right? Everett went on to do um Rand and like you know national security apparatus type stuff because he got he got basically shot down by Neils Boore when he went and visited um Copenhagen. But >> Wheeler kept the idea alive of Everettian mechanics. Um Bryce Dit did a few >> things with Wheeler about that many

1:09:50worlds interpretation and they met at a pizza parlor in London.

Many-worlds and quantum computation

1:09:54Deutsch and Dwit and that's when Deutsch got into this like many worlds interpretation and he got really into it and in Deutsch's view when a quantum computer processes like these computational state states simultaneously what it's actually doing this is 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 it's a form of interdimensional travel. Yeah. Effectively >> effectively in some for and using those cinematic parlance to think about it's

1:10:37we're we're going >> Yeah. We're we're like computing in multiple universes and then we're bringing it all together 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 it's so funny because this this is like um obviously uh aian ideology as I like to call it. >> Yeah. >> Um is one of the abuses in uh entertainment. >> Yeah. That is where quantum and then multi many worlds, excuse me, >> get kind of conflated and then spins out

1:11:19of control. >> Yeah. Yeah. Because with many worlds like I mean you could just say anything, right? If you're if you're in Hollywood, you just Yeah. Uh multiverse, right? And this Marvel has got themselves in a problem right now because because of all the stuff that they've done and they've basically saying, "Well, no, Iron Man only died in this universe, but not in the many other universe." >> Dude, Robert Downey Jr., I think you made enough money, right? Anyways, the reason why I bring this up is because um Hartmund Nevin, who is at Google Quantum AI, I think he's one of the heads there. um he wrote a blog post about Google's willow chip. Google's willow chip is this like latest of Google's quantum

1:12:02computing platforms um where the performance there on this benchmark was astonishing right and so what um Hartman Nevin wrote is that it performed a computation in under 5 minutes that would take today's supercomputers

Google Willow and the multiverse claim

1:12:17um 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 how however many zeros there are, right? Um, this mind but crucially, he said, this mind-boggling number exceeds known time scales 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 um 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. >> I remember when this came out and and people were texting me because I'm like,

1:12:58you know, they're the only physicist that they know. Yeah. Yeah. Yeah. And they're like they're like, "Dude, we live in a multiverse." I'm like, "No, >> no, we don't." Okay. I mean, maybe. I don't know. But like I don't think this proves >> that we live in a multiverse. I'm It's just funny that like one of the heads of uh Google Quantum AI is also on this hype train, right? So he said that this is proof of that. I don't think so. I 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.

1:13:39>> Unless the aliens come from the other universe and they figure out a way. >> Yeah. Yeah. And then they come and tell us if if an alien came and told us that I I'm from the other what 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 uh Fineman has has said this right in his talk he said that I mean clearly we can't store this many states um but Deutsch wants to design a quantum

Deutsch–Jozsa: the first quantum algorithm

1:14:21algorithm that really shows this okay and he designs the first quantum algorithm in 1985 and it's expanded alongside with um Richard Jose in 1992 this is the paper that comes out again proceedings of Royal Society um 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. Okay? And I'm going to go ahead and give you the punch line. >> 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 oneshot it.

1:15:03>> Okay. So, we're going from exponential to one shot. >> One shot. >> Okay. using a quantum algorithm. Here's the problem. Okay, so you're given a blackbox function and this blackbox function is going to take inputs of ndigit binary numbers and give back a single digit either a zero or a one. So if n is like two, it can give it it takes in as input you know either 0 0 1 1 0 1 1 and it spits out either a zero or a one. Now, in in essence, this could be any nd-digit binary number. N could be very large. So, N could be like that giant matrix of zeros and ones that goes into this blackbox function. I don't know how this

1:15:44black box function works. Okay, it's it's a black box. >> I stick an input and I get an output of either zero or one. >> This is similar to the and gate we talked about at the beginning in terms of you have two then you only have one input on the other. It's so it's not reversible. >> Yes. Yeah. This is not reversible. Yes. Very good. And an ANDgate would be like um 0 0 goes to zero. 01 goes to zero. This even worse because it only goes to one answer. >> Yeah. It only goes to one answer and no matter how big the the thing is and I don't know if it's an andgate, >> right? We Yeah. Right. Right. >> It's a black box. I don't know what it's doing in there. >> That's the point. The black box replaces this concept of an ANDgate in terms of

1:16:24being able to be well defined. >> Yeah. Andgate. I know exactly what the truth table is here. I don't know what the truth table is, right? So I want I want to make it simple. So let's just consider n equals 2. >> Okay. >> As I was saying, right? Yep. So in n equals 2, we'll go to the next overlay. So at n equals 2, there's four different numbers that I can feed in. I can either feed in 0 0 1 1 0 or 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 zero or one, depending on whatever I gave as input. I'm given another promise. Okay, I'm given a promise that this function is

1:17:05either 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 it's going to give out a one. No matter what my input is, it's going to give out a 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 there's not several there's only six examples for a two cubit for a two um

1:17:45bit input like cuz you know it's it's four choose two is going to give you six. Um two of these I've described over here. There's 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, the first bit is 0. This black box is going to output zero. For 0 1, it's going to output zero. For 1 0, the first bit is now one. So it's going to output one. For 1 one, it's going to output one. Notice there's two zeros that come out and there's two ones that come out of the four. >> Because the first input is is >> whatever the thing is. And the 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

1:18:27a balanced function is an exor, exclusive or, meaning the bits are different. >> So if the bits are different, I'm going to output a one. If the bits are the same, I'm going to output a zero. Notice if it's 0 0, I I output a zero because they're the same. If it's 1 one, I output a zero because they're the same. If it's 0 1 or 1 0, I output a one. Okay? So again, this is balanced because there's two zeros and two ones. There's six such functions. I've only shown you two. >> Got it? Okay. So these are two examples of >> 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 map to zero and half of the inputs these guys map to one okay

1:19:09>> it has it 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 >> if it's balanced or constant. That's the idea. That's that's the problem. Y >> So, how would I do it classically?

1:19:49>> Yep. If I 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. Um,

Classical vs. quantum solution

1:20:04classically na what I what I do first is I just test 0 >> and suppose I get a zero >> and I test 01 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 fir third >> bit string at at this point after two there are arguments that it could be constant or it could be balanced because you've not yet had enough data to deter to uh rule out one or the other. >> Exactly. So I need to do that third

1:20:45query to check I I need to check one zero. And if one zero comes out as zero, >> then I know that it's constant, right? Because because I 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 what if um you know, in the case that it's balanced and and and the first and the third inputs go to go to zero and the second and the fourth go to one, right? Um worst case scenario, what what if I chose like what if I randomly picked like the other stuff and and I

1:21:25could choose, right? Well, in the worst case scenario, the the guy who's designing the black box knows exactly how you're going to check check the first few inputs, right? Right. And so and so if if you're trying to just get like the best case scenario is I just I just pick 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 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, so worst case scenario, you always have to do exactly half >> plus one.

1:22:06>> Yeah. >> Right. >> Yeah. Okay. I get what you're saying. >> Okay. So, I 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 Deutsch Joa came up with is they said actually we could pass a superposition of all four versions.

Superposition enters the computation

1:22:29Remember in Bell's theorem right all four versions are not together right like or sorry are not cannot be separated so I could create a superposition of all of the four states I could create a superposition of 0 0 1 1 0 and 1 1 and I pass that entire thing 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 blackbox function what is it going to do to the superposition. It is going to act on it with that blackbox function. There's going to be some quantum version of the blackbox fun box function. That's again this this is a theory gimmick where it's like oh there's like there's a way to

1:23:11just like make it quantum mechanical, right? We it's like a oracle is what they call it. Um, so when we do that, what I'm going to do is implement this blackbox 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 cubit. So what happens here? If it is balanced, all of them are going to have the same

1:23:52sign. >> Mhm. >> Right. >> Mhm. >> And maybe maybe we go to the next uh cuz 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 and minus - depending on whether it's a zero or one that it gets mapped to. >> If it's balanced, >> it's going to be >> then two are going to be 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. >> Yeah. >> And if it is balanced, I'm going to get destructive interference. >> They cancel out because they're different. >> And this is the key to almost every single actually every single quantum

1:24:33algorithm. Every single quantum algorithm uses this idea of constructive and destructive interference to do the computation. So now you've one-shotted it. >> Is this B? This is basically your zero or one now. >> Yeah. And what if you get constructive interference, I know that it's balanced. >> Mhm. >> 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 everything um 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

1:25:15the 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 the point here is because we know this constraint of it's either balanced or constant. >> Yes. >> 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

1:25:56this to a physical reality. Okay? Because it's it's a bit weird, right? So let's let's just talk about um to really understand why the quantum mechanics lets us do this. Let's consider just a quantum interference experiment. Okay. And I want to I want to take the double slit experiment which we've discussed a lot in this podcast

The double-slit experiment as a computer

1:26:15and I want to try to create a version of the double slit experiment that computes my Deutsch Joa >> problem. Okay. Now, to introduce the double slit experiment, um you've got a laser with coherent light. That light falls on two slits that 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

1:26:57the the first sort of two gausian that I see. But if I don't cover either one, and I I 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. Yeah. Okay. So, so this is how the double slit experiment works for like light waves and things

1:27:37like that. Now, crucially, it's been shown that single particles also do this, right? I can 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 um single photon >> interference >> like interference on my detector. Right? So Fineman took a look at this and he had a different way of explaining it. Fineman had this idea that of um the path formulation sum over all paths of quantum mechanics and he explained all of quantum mechanics using the sum over paths. He didn't like the wave function

1:28:18analogy. He he came up with his own and it turns out that it's it's really good because it like has applications to quantum field theory and if you know about fineman diagrams that's that's all this sum over path stuff. Okay. So here's how he explained it. This is this is directly from um one of his um Fineman lectures of physics. I've added the red lines and things like things like that. Okay. So um 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

1:28:58there. >> 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 um I'm

Feynman’s path-integral intuition

1:29:25going 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, it's going to 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 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

1:30:05at the detector and the and the clock is going to be at a certain location >> on the uh, you know, 0 to 12. >> It's going to be pointing in a certain direction >> and it spin. >> Yeah. And it spin because it it 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 what this 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

1:30:45>> 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 the the area of the circle that that black arrow creates. This is his version of Bourne's rule, which is that the square of the amplitude of the wave function tells you

1:31:27the probability. He's saying, "Oh, just take an area of a circle." He was he was he was a wizard with like with like creating mental models. 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. >> Mhm. >> Okay. >> It's because and you could do this same thing for every single spot along the detector. >> Very good. So now let's let's talk about what is the what is the probability in the very middle >> where in the very middle the two paths are exactly equal >> and so the arrows for the two paths 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

1:32:07>> you'll actually see that this corresponds to that interference pattern that we saw >> right >> 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 in where the troughs are where there's zero probability. That's because the arrows are co the the the timing there is just right where the arrows are opposite. >> Mhm. >> Right. >> The angles the angles of their rotation at that particular spot happen to be effectively in opposite opposite direction. And which which creates that that thin line of demarcation where it's destructive. >> Exactly. And and normally with with undergrad physics, we we think about

1:32:48like it's half a wavelength away, but half a wavelength means that the clock has turned exactly 180° and not 360. And so this is his way of saying half a wavelength is really my my arrow is pointing in the opposite direction. >> That's interesting. It's it's a different yeah metaphor to explain the same idea. >> But it's the it's the same math, right? And 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

1:33:29me, northeast. If they were exact, just if we flipped both of them 180°, it doesn't impact the probability. >> Yes. Exactly. It's exactly, >> right? What only matters is the relative >> the rel between >> the angle between the two arrows, right? As long as the two add up. >> Yeah. Yeah. >> The circle remains the same. >> Okay. That's that's a little bit of a key here. >> The the the probability space is the same independent of the direction of spin >> in this construction. >> Yeah. >> Um and independent of the direction of like which way the phase ends up. >> Right. Right. Right. Yeah. >> Which way the phase ends up. The spin is a different loaded word. >> It's a loaded word. Okay. No, that's fair. I want I want to be

1:34:10>> which way the phase ends on. Understood. >> Yeah. >> Okay. So, >> the 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 we started this conversation, you know, here because we were talking about um this algorithm where we were putting in the 000 1 0 0 1 1, right? And this we talked about this idea that it's a superp position state and we so we have to put it when we're talking about it as a quantum touring machine, a quantum algorithm. we can't factor it like we would in a classical

1:34:51system. And so we are able to basically have it either be balanced or constant. >> Uh 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 fman diagram concept is it's representing the same concept. It is in the in go ahead. >> In the sense that those arrows >> Yes. >> those arrows represent the complex number that is in front of those states. Right? You know when I said like the 0 0

1:35:32the 01 and like I put a minus one. That's what it represents. So let's let's actually make a >> if we go Oh, sorry. Go ahead. No, go ahead. >> Actually, yeah. No. So I I'm actually going to make a direct comparison between our Deutsch Joa algorithm and that quantum quantum experiment. And I'll I think you'll see the reason why I I sort of did that. So actually, let's go. So yeah, this is Yeah. So if we want to review, this is the Deutsch Joe's algorithm, right? You've got the 0 0 1 1 011, right? Um it starts out with just a one in front of everything. Mhm. >> 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.

1:36:12>> And what we want to do is have them interfere at the end.

How interference performs a computation

1:36:16>> So now let's consider instead of two slits, four slits. You see where this is going? Yeah. Our our slits are the function in some sense, right? And we've we've we've created a superposition. Each of the superp positions is represented by the four holes. Okay. And I've got an electron gun. Okay. This is I think how Fineman might have like if he if if he was around to to do science communication now maybe this is how he would have done it. Right. So I've got I've got my four holes and those four holes represent the four binary digits that can go through. Okay. Now let's see

1:36:57what happens. The function itself is going to be implemented by some kind of crystal >> that I'm going to put in the in the um 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. >> It's the idea that the crystal refracts the light. >> Yeah. Yeah. It's 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 pi pulse. It's going to add 180°. So in this case this particular function this iteration of the function maps the first and the last 0 0 and 1 1 into zero

1:37:38>> and 0 1 and 1 0 into one. So this is the exor function that I'm looking at right now. The exor 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? Yeah. >> And so that's where I would but the point is somebody put the slits there with the holes and put the holes. In this case we do, right? But the 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 >> in any of the four >> fs or there's crystals in all four of

1:38:20them. >> Right? >> Okay. In that case what would happen? If there's nothing, then they would all take the red the red line. Yeah. >> 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 and 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 I 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 >> right so I will still detect a particle

1:39:02>> this this is fascinating again in in this constant function whether either no crystals or all four crystals um our our arrow length is the same but in opposite directions >> but it doesn't matter in the context of the probabilities yes >> because the surf The C the in the Fineman 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. 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 whatever the thing. >> And the idea is that the because it when

1:39:42it's constructive which is that center point which is a higher probability >> uh constructive interference. Yeah. It's like a constructive interference. That's why the area is so large. And then when you get further to the past the other side of the there's like a 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 it's like those two traveled at exactly the right amount to be to be

1:40:22pointed at at in the same direction right now. So this is for a constant function. Now let's look at what a balanced function would do like the exor. >> Yep. >> In the exor 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 crystals. >> Yes. >> Right. So, if I put a detector in the middle there, >> right, and all I do is have a one shot. I send uh I I I do a oneshot and I see do I see a particle or not, >> right?

1:41:04>> That'll tell me exactly what the crystal can like what type of filter the the person has put. Is it a balanced filter with only two or is it a or is it a um a constant? Crucially, it doesn't matter where I put these crystals. As long as there's two, >> 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 >> cuz the phase again doesn't matter. >> Yeah. Um, it >> like if I if I were to put the crystal on the top one, then one of the bottom arrows of the one of the bottom red arrows would flip and one of the top green arrows would flip, but at the end

1:41:44of the day, the sum of the two would still be zero. >> Yeah. Yeah. This is this is so good. And this is so good because it 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 uh 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 filter what the crystal construction was in the middle because we are able to look at the or am I mixing >> metaphor I think you're mixing metaphor I'm mixing >> metaphors yeah yeah the the reversible part of stuff is happening like when we implement the function itself like the

1:42:26reversible part is happening and that's when we we we we have to get into the weeds about like how we actually implement ment this like function in a quantum computer like yeah we have we need like a we need like an ancillary bit it's I think it's called an ancilla bit that like keeps track of all of the information that stuff here it's still it's still um you're still losing information though here right because there's four inputs coming in and only one like thing that I'm think like >> I got you yes no no that makes sense I got you >> yeah and like remember quantum mechanics the observation is not reversible. It destroys whatever

1:43:06thing is happening in the magic box. >> Yes. Right. And here we're doing an observation. >> And so that is definitely not reversible. >> No, that that's right. That's right. The 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 superp positions because like we're going to start with 00 0 and then what you do is apply like a hatamard gate that will make okay now I put in a superp position of 0 and 1 0 and 1 0 and 1 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

1:43:47quantum computer, all I have to do is one shot. >> It's time 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 that makes sense. And and that's a good distinction because there there's just so many levels to this. So, thank you for that correction. And so I'm just trying to make sure I'm tracking connecting the ideas we built at the beginning and bringing them down now into but I I think the way you explain this is between looking at the math structure of balanced versus

1:44:27constant >> 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. That's it's 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 um the main point that I want to say is >> the reason why the Doza algorithm works is because it uses interference. >> Mhm. >> Okay. Mhm. >> It's it's like it the the the problem itself is this kind of useless problem

1:45:07of like, oh, there's a function that's like either balanced or constant. Find out what it is. And like because it's contrived that way, right? We can use quantum mechanics to like figure it out. And part of the reason why this this was the first algorithm is because it's designed to use quantum interference, right? Deutsch Deutschin Deutsch 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 um an exponential amount of time this is a like this is a perfectly valid um problem right why you would want to solve it who knows right

1:45:48>> other than it's it's a very good mental exercise and it shows you some of the um and it and it actually proved to the world that okay there is a computational problem out there that definitely a

Why “useless” problems matter

1:45:59classical uh computer cannot solve. >> Mhm. >> Okay. >> Which then created sort of this theoretical motivation or justification to say okay well this is a problem that requires >> quantum computing >> uh to actually be able to efficiently solve and it's no and it's it's it item right it's right there I can describe it really well right still I mean obviously people are going to look at this and be like well that's a useless problem. Okay, now we're going to get into some useful problems. >> This is Well, we just to connect it back to the idea of funding and basic research. Sometimes you got to do stuff that looks useless. >> Yes. >> In order to enable and create the foundation for things that are useful

1:46:40and it's so can be counterintuitive, but I like I always want to hammer this point because we need to just explore sometimes. >> Yes, I agree. >> And just fool around. >> Yeah. >> And argue. >> 100%. 100%. So do Joseph they proposed this thing.

Simon’s algorithm

1:46:58>> Um 1993 computer scientist um Daniel Simon he formulates a quantum algorithm that demonstrates exponential speed up over um a classical randomized algorithms where he's trying to consider a function that's guaranteed to have a hidden period under bitwise exor edition. Um if I don't 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 a function that maps threedigit binary numbers to other three-digit binary numbers except there's um two inputs always map to one input. Okay? So, there's eight different binary numbers, but there's only four

1:47:39different outputs. And like the two green inputs map to the same one 0 1 1 0 1 and the two red outputs map to the same 0 0, right? And it turns out the bitwise exor of the inputs is the same. It's 1 0 1 1 0 for both. If you were to take the bitwise exor 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 that invariant bitwise exor for the two matched? This is another contrived problem. >> It's it's very similar. It has a similar construction but it but it and it creates >> it's a bit more complicated. creates a different mapping that ultimately is trying to accomplish the same concept.

1:48:20>> Yeah, it's like it's like we're 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 figure out what that period is. Okay. Simon submits his findings to the 1993 IE symposium on theory of computing. Okay. And the program committee rejects the paper >> because it dismisses it as just another another artificial blackbox puzzle. It's like, oh, we got another Deutsch Joa here, right? It's like, who cares? >> Okay, when would I encounter such a periodic bitwise exor edition function,

1:49:03>> right? >> Mathematician Peter Shore is on the committee for the STOC. This is Peter Shore when he was a young man. Um, and Shore advocates to accept that manuscript because he recognizes that this formulation represents a period finding over an algebraic group. Okay. >> 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

1:49:43algebraic math over integers and that can be applied to computational problems in cryptography.

Peter Shor changes everything

1:49:51The 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 Simon problem, right? Of Simon's 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,

1:50:32he succeeds. He figures out how to effectively how to effectively do like a discrete 4A transform. You know, in Forier transforms, we we've discussed this a lot. for your transforms are when you go from the time domain of a signal to the frequency domain where you're 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 um and he shares this logarithm result at Bell Labs he was at Bell Labs um every Tuesday they used to have this weekly seminar he presents it at the seminar um it's known for rigorous and direct questioning the presentation is very wellreceived And over the following days, everyone

1:51:14kind 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 f the people who attended the seminar are talking to their friends. They're talking to their friends. um through the grapevine umesh vaz vazirani he's uh another computer scientist who currently is at um the university of California Berkeley he phones Peter Shore on the weekend so Tuesday is when he gave the seminar on the weekend >> uh Vaserani phones yeah he got that

1:51:55phone call and Vaserani understands exactly where this is going and on the phone call he says I hear that you can factor efficiently with a quantum computer Mhm. >> Right. And Peter Shore immediately is like this guy. >> He's like he all he immediately like saw the through line. Right. >> Right. >> In those four days though, Peter Shore spent all of cuz I'm sure he got those comments in the seminar like a >> because basically he sort of had an incomplete map. >> Yeah. And 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 from people who could definitely make it work, right? And he's like, I need to

1:52:36lock in. >> Yeah. Yeah. >> Like, this is my thing, right? That I mean, he Peter Sh gave a gave a presentation at UCLA like 2 or 3 years ago, um, like a symposium, and he was literally talking about this and he said, you know, when Vaserani telephoned him, it's like, I hear you can factor efficiently with a quantum computer. He was like, "I had been working for 4 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 Shaw

Factoring and cryptography

1:53:14spends 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 supercomput. >> Okay? If you take a giant prime number and you take a giant prime number, >> you get a even bigger number. >> And if you give that to somebody, they could not tell you what two prime numbers make up that product. Okay?

1:53:54Unless you give him one of them. You give him 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 your grandma's in the hospital or something. Yeah. And they actually literally need you to type in your pass. They can't just like do it. >> Yeah. >> Right. >> This becomes a huge huge deal. >> Okay. Um in parallel I just want to also

1:54:34mention um in 1996 law of Grover who's actually he's an Indian um 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. Um it's optimal

Grover’s algorithm

1:54:51searching of an unstructured database. So if you want to find like where something is, you can do it in square root of n time instead of like n would be you know you got to check every single one to figure out where it is. Square root of n is what he showed. So this is also this can be like you know applied to a various other things. These are the two big algorithms that are the reason why um I think quantum computing has found all of this funding. Specifically, I think shores to be perfectly honest. >> They're they sort of have two fundamental entry points of what they're actually either doing or solving for. One is this sort of large factoring large primes and the other is like uh un

1:55:35like some unbounded database search or bounded database search. >> Yeah. Um and

Quantum computing becomes a national-security problem

1:55:42because of the structure of the problem, they appro they they fundamentally approach it in different ways. Exactly. >> And so there's implications and derivative effects. >> Yeah. You can map like you can map certain problems to database search, right? >> And then be like, oh, just apply Grover's algorithm, right? Uh I don't know if there's a lot that you can map to Shor's algorithm, but you don't need mapping to understand why Shores is good. Right. Right. Sure is just like look literally anyone in cryptography CIA NSA FBI China France >> any intelligence community is going to is going to want to >> have their access to something that can do shores.

1:56:22>> World we world wars have been lost over not being able to encrypt your communications >> 100%. >> And so from the you know like that is the >> Yeah, exactly. And like prior to Shor's 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. Shor's algorithm altered that dynamic, right? Cuz now it introduced national security, cryptography. Um, if you have an operation quantum proc operational quantum processor that could scale to several thousand logical cubits, now any

1:57:03encrypted 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. Um there's like dude it's it's kind of scary because like I've been reading there's there's um I don't know what you want to call them cyber uh cyber punk cyber gangs cyber terrorists even that are just like downloading data. >> Mhm. >> So that one day when there's a you know they're just waiting for one day there's going to be a fall tolerant quantum computer and then I can just decrypt it >> there. It's that HGTV show or whatever Lifetime TV show hoarders.

1:57:45>> Oh >> right. like they just take what right 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 um a fall tolerant quantum computer comes in, >> it's it's going to be an issue. On the

1:58:26other hand, like 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

Post-quantum cryptography

1:58:37implementations, it might take days or weeks or months, right? I mean, okay, that's better than the age of the universe, but maybe Yeah. 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 um the US government and DARPA specifically have like and I think NIST the National Institute for Standards and Technology they've created like um 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

1:59:18computer. So there are efforts to do this. It's still kind of a >> issue, right? Because if adversarial nation states like China, I think we we have a we have a headline from Bloomberg that says that China is closing the gap >> um 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 an adversarial um 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 um because people are going to

2:00:01want to use it for both defensive but 100% offensive purposes because in any uh proxy war or other kind of geopolitical conflict between the superpowers >> um this is a thumb on the scale that can be pressed immediately. >> Yeah. uh 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 etc. But even we've seen the example of like stucks neck stuckset uh with the Iranian nuclear missile program and how we can find ways into these systems that ostensibly are not connected to the

2:00:42quote unquote internet and still have a lot of damage. And so this is I know the focus of

DARPA and the quantum-computing race

2:00:50thousands, tens of thousands of people >> every single day in the variety of ways that the the and 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 um to to show you just how much Shor's algorithm like really changed the landscape like Shor's 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 industrial laboratories to pursue scalable cubit

2:01:31hardware. Right? This this this created the the the funding that enabled now technologies like companies like Google and IBM and places to now piggyback off that research and try and create an actual quantum computer. um the ARDA roadmap the ARDA that's the advanced research and development activity um in 2002 and 2004 they convened like a quantum information science and technology experts panel to draft formal road maps to establish benchmarks on things like how good a quantum computer can keep its quantum superpositions

2:02:11things like gate fidelity cubit scalability and quantum error correction Those are more hardware questions which we are going to get into the next episode when we talk about the hardware. But I hope that this episode kind of showed you um you know kind of the

What quantum computers may actually be good for

2:02:26theory behind it and why we're building this thing in the first place. Okay. And I I really personally I think it's personally I think it's because of Shores and Grovers Fineman's dream of material science. I think um in the age of AI it's less so much a priority right because I like just look at um Google deep mind's alpha fold right 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 there's we've gotten a lot of comments

2:03:07about yes alphafold is interesting but when brought into later stages. So, I'm just qualifying it. Yes, we are aware >> it's not perfect. We're not saying that it's perfect, but from when we where we were before >> to it existing and being able to then iterate and build on top of that, >> 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 and like you know, physics in general. Um the other thing why I the other um reason is like I think the best algorithm 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

2:03:49variational quantum solver. This is you know just like how Shor's algorithm is built for this purpose of factoring. Um this VQE algorithm is built for the purpose of understanding materials. But that algorithm requires you to guess an onsat in L you know how um Hans beta had this idea of guessing uh guessing an answer and then optimizing around what that answer is. Well, this variational quantum solver >> requires guessing at what you think the ground state wave function looks like and then optimizing around that wave function. Well, if your

2:04:29guess is like completely out of left field, you're not actually going to get anywhere, right? So, it's not like one of these. It's not the dream of Fineman of like, oh, just like simulate it, right? You still need a quantum algorithm to do the the computation. And it's not as simple as like, oh, we just like 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. And the whole point is that thing is going to tell me what the electron clouds look like, right? So I have to guess at 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

2:05:09guess 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 Fineman was dreaming of. Maybe one person who will help push the envelope there is someone we just covered uh in our last episode, Omar Yagi. Yes. who's just uh 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 uh aometry which is AI material science and chemistry

2:05:50>> and trying to basically blend these disciplines >> and potentially I know that the quantum piece in quantum algorithms are not necessarily the basis of the concept But seeing where this implementation of AI in speeding up nextg material science discovery and then if you add a fundamental quantum algorithm discovery in that context I think the acceleration becomes very interesting. So >> 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 and then they they iterate on the guess. I mean, who knows,

2:06:30right? Maybe in the future only AI uses quantum machines because they're the ones creating such create like amazing algorithms. Who knows? It's it's it's a ripe field, but um that's how we got here. >> Yeah. And and I think that this this is great foundation. Again, the whole point of this show is we have an expert and a layman. Myself being the layman. our resident PhD Krishna Chowdery 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 uh and

2:07:12literally no one. >> If you did, drop it in the group chat. I want to 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 this is a familyfriendly 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

2:07:54media. 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. question of being surprised that I made the Oh, made that connection. That's pretty good. Um, so again, part two we're going to actually dive into and hopefully have a physical copy of Yes. >> that we can hang on the wall and start our gallery wall in the back of this cover story um quantum silicon

Part II: building the hardware

2:08:34processor. >> Yeah. >> Is that is that that's that is correct? >> Yeah, you're goddamn right. It's 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 uh enabling layer to having the likes of IBM, Google, Microsoft, HRL, a variety of other >> 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. Uh, we again appreciate you all greatly. If

2:09:14you'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 cuz I always like seeing those who reach the end. Uh if you have a comment to leave, you 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

2:09:55comment 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? I I It's tough. It's I I don't >> 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. Uh

Closing

2:10:15I have thoughts, but we will save it for the comments. My name is Lester Nar, joined as always by my co-host, our resident PhD and nature cover story co-author Krishna Chowdery. 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. Um as we have the opportunity to do so we will do so. We will see you all next week for part two on quantum computing.