Okay, you say, but, uh, I also keep hearing about these quantum computers. So what's up with that? Like, did Turing already have in mind quantum computers? Well, I, I don't know. I don't know the answer to that question literally.
Uh, but I can tell you that any computation performed by a quantum computer can in fact be simulated by a Turing machine. So any computation on a, on a quantum computer that can be carried out in a finite number of steps can equally way-- can equally well be carried out on a standard Turing machine in a possibly much larger but finite number of steps. So again, we said why-- like how do you amass evidence for the Church-Turing thesis? You show that any other way of expressing computations you can think about, you can simulate those computations on a Turing machine. And exactly that type of simulation can be done with quantum computers.
And so for that reason, once again, quantum computers are just in the very, very long list of ways of expressing computation, which can be mapped onto Turing machine computations. So Church-Turing thesis, alive and well, you know, as sort of, you know, prominent as ever as it was ninety years ago. What's going to be more interesting to discuss is the extended version of the Church-Turing thesis, which, to be clear, was stated by neither Church nor Turing. And so this is something that was added on by later researchers who were focusing on efficient computation. So the extended Church-Turing thesis says that, uh, you know, not only do Turing machines capture computations in any other reasonable model, but that polynomial time Turing machines, meaning Turing machines that complete their task in a number of steps polynomial in the input size, polynomial time Turing machines capture any other reasonable notion of efficient computation.
So Turing machines being the right model, not just for arbitrary computation, but also for efficient computation. That's the extended Church-Turing thesis. And there is, in fact, a really major challenge to the extended Church-Turing thesis to the point that, you know, most people kind of believe that in its original form, that thesis is false. And indeed, that challenge to the extended Church-Turing thesis is quantum computers. So briefly, quantum computers differ from the classical computers that you and I are familiar with by taking advantage of some of the peculiarities of quantum mechanics in a way that classical computers cannot.
So for example, uh, using superpositions over states, using entanglements, using interference. Now, one open question is whether quantum computers are kind of only possible in principle. So it's kind of an open question whether we can actually build in the physical world really large sc-- large-scale quantum computers. Now, over the past five or ten years, I, I have to say there's been pretty impressive progress, okay, of making qu- quantum computers larger and more robust and more reliable. So for this episode, I'm gonna take the optimistic approach, and I'm going to assume that we do actually get large scale, um, reliable quantum computers in the next, I don't know, decade or two, something like that.
Let's go ahead and assume that that's the case and then explore the ramifications for the extended Church-Turing thesis. So for example, all right, so why do quantum computers challenge the extended Church-Turing thesis? Well, a lot of the story here again concerns the problem of factoring. So again, taking a, taking a number and decomposing it into the product of its prime factors, like a hundred being equal to two times two times five times five, okay? So it turns out, and this was a big, big deal when this was first proved by Peter Shor in nineteen ninety-four, it turns out that if you can build large-scale quantum computers, you can use them to efficiently factor large numbers.
So there exists an efficient quantum algorithm for factoring large numbers, and that is something we do not know how to do on a classical computer. We do not know how to do that, uh, without using the extra power given to us by quantum mechanics. In fact, you'll recall for decades we've actually been rather relying on the fact that classical computers cannot solve the factoring problem efficiently 'cause again, common methods of encryption like RSA encryption actually are only secure under the assumption that factoring is a hard problem for classical computers. And so at this point, uh, like you, you should be like putting two and two together at the moment. You're kind of like, "Wait a minute.
So, uh, when I send my credit card information over the web, I'm using probably something like RSA encryption, and RSA encryption is broken if there's fast algorithms for factoring, and quantum computers give you a fast algorithm for factoring." Yep. So if we can build large-scale quantum computers, cryptography as it's practiced mostly today, uh, will be broken, okay? And in particular, we will not be able to continue to send, uh, our credit card information encrypted in the same way that we do right now. Quantum computers-- This is one of the reasons quantum computing has been such a big deal is 'cause building them really does break the most common ways of doing cryptography. Now, the good news is that quantum computers, you know, while they would break the current approaches we take to cryptographic primitives like encryption, they're not an existential threat to cryptography, or at least we don't believe so.
Remember earlier I said, you know, if P and NP collapse, if we live in world number two, then kind of every approach we can think of to implement cryptography fails. You really need a separation between P and other problems in NP for all of the approaches we have in mind for how to do cryptography. So with quantum computers, the good news is they do not put us in world number two, or at least we don't think that quantum computers can solve NP-complete problems. Remember, remember factoring Factoring, not in the NP-complete region, okay? So the fact that a quantum computer can solve factoring doesn't put us in world number two because it's not NP-complete, right?
It's NP-intermediate, okay? So it's totally consistent that P and NP are different, that quantum computers can't solve NP-complete problems, and that quantum computers can solve factoring, okay? There's no contradiction there. And so the good news is, is that while quantum computers would break any approach to cryptography predicated on the computational difficulty of factoring, they do not automatically break all other known approaches to having secure cryptographic systems. And so, for example, it's all the rage in cryptography land these days to be talking about post-quantum cryptography, which means cryptographic systems which remain secure even when we have available to us large-scale quantum computers.
And a lot of super smart cryptographers have come up with a lot of really nice constructions for post-quantum cryptographic systems, including encryption. So what this means is we're still gonna have cryptography even after we have quantum computers. It's just that a lot of people are gonna have to do an upgrade from the old ways they were doing, for example, encryption, uh, using RSA encryption to some of these newer methods, newer post-quantum methods, uh, for doing encryption. And you will notice in the next decade or two, you will start noticing, uh, lots of different sites and products rolling out these upgrades to post-quantum cryptographic systems. But even if quantum computers are not an existential threat to cryptography, uh, they are in fact an existential threat to the extended Church-Turing thesis, at least in its original form.
Remember, the original form of the extended Church-Turing thesis says that any efficient computation on some reasonable, like physically realizable computing device, any efficient computation on any realizable device should be equally well expressed as an efficient computation on a classical Turing machine. And, um, but look, let's review kind of what we now know to be true and/or believe, right? So if factoring can be solved efficiently on a quantum computer, and again, we know that's actually true, right? That's what Shor proved, uh, with his algorithm back in nineteen ninety-four. So first of all, factoring is efficiently solvable on a quantum computer.
Secondly, if factoring cannot be solved efficiently, meaning in polynomial time on a classical computer, and we certainly believe that because we've bet all of e-commerce on that fact for the last multiple decades, and if large-scale quantum computers can actually be physically realized, as increasingly seems likely to be the case, those three facts together literally imply that the extended Church-Turing thesis is false, is wrong. It is not the case that any efficient computation on some realizable device can be expressed as an efficient computation on a classical Turing machine. In particular, a factoring algorithm, an efficient factoring algorithm on a quantum computer cannot be equally well expressed as an efficient factoring algorithm on a classical computer because we believe that such an algorithm does not exist. So you can imagine what happened next, which was that, um, researchers interested in computation just sort of, you know, updated the extended Church-Turing, uh, thesis to take into account this kind of new technology that's out there. So there's now a quantum version of the extended Church-Turing thesis, and you can guess what it says.
It says any efficient computation, uh, that can be carried out on some realizable device, realizable computing device, can be equally well expressed as an efficient computation on a quantum analog of a Turing machine. So a Turing machine augmented with extra capabilities to take advantage of superpositions of states, of entanglements, and of interference. So that was now what people think of as the revised version, the post-quantum, if you like, version of the, uh, extended Church-Turing, uh, hypothesis. Any efficient computation that you're ever gonna see in the real world can equally well be expressed as an efficient computation, uh, on a quantum computer. And actually to this day, so in twenty twenty-six, I don't really know of any challenges, any serious challenges to this revised, this quantum-based version, uh, of the extended Church-Turing hypothesis.
Now, we already had to revise it once, right? Once people realized that quantum computers really were likely to be built at large scale. Maybe we have to revise it again at some point in the future, like when there's some new technology. I'm not so sure that's gonna be true, but, you know, we can be ready to revise it as needed if more technology comes online. So that has been the change with the new computing paradigms as far as our understanding of expressing computation.
Original Church-Turing thesis, totally unchanged, totally unchallenged. The extended Church-Turing thesis concerning efficient computations, the one change that ha- has had to be made has been to accommodate the advent of quantum computers.