This note is part of [[quantum/Practical Quantum Information System]]. > [!info] Course code > Use the companion repository for this lecture's runnable lab, helper functions, and regression checks: > - [notebooks/by_concept/extended_church_turing_thesis.ipynb](https://github.com/montekkundan/quantum-code/blob/main/notebooks/by_concept/extended_church_turing_thesis.ipynb) > - [qcourse/analysis.py](https://github.com/montekkundan/quantum-code/blob/main/qcourse/analysis.py) > - [tests/test_analysis.py](https://github.com/montekkundan/quantum-code/blob/main/tests/test_analysis.py) [TODO: add video - Extended Church-Turing Thesis] ## What This Concept Is Imagine trying to simulate a physical system on an ordinary computer. If the system is small, that sounds routine. If the system is a many-particle quantum system, that can become brutally expensive very quickly. The Extended Church-Turing Thesis is the claim that, despite all the complexity of the physical world, efficient classical simulation should still be possible up to polynomial overhead. Quantum computing matters because it puts pressure on that claim. The weaker [[quantum/Glossary#Church-Turing Thesis|Church-Turing Thesis]] is about what can be computed at all. The stronger extended version is about what can be computed efficiently on a classical machine. A quantum computer is interesting not because it computes magic answers, but because it appears to make some physically natural computations easier than classical simulation would suggest. ## Foundation Terms You Need First Keep three claims separate. The [[quantum/Glossary#Church-Turing Thesis|Church-Turing Thesis]] says physically realizable computation can be modeled by Turing-style computation. The [[quantum/Glossary#Extended Church-Turing Thesis|Extended Church-Turing Thesis]] adds the claim that efficient classical simulation should still be possible. A [[quantum/Glossary#Qubit|qubit]] is the basic quantum information unit whose joint state space grows rapidly with system size. That last point matters immediately. An $n$-qubit pure state lives in a space with $2^n$ basis amplitudes. Even before you design an algorithm, the representation size already hints at why exact classical simulation can become hard. ## How The Idea Actually Works The extended thesis became compelling because classical physics, chemistry, and engineering often looked computationally tame enough to model with digital machines. Even when simulation was expensive, the working belief was that the cost would grow in a controlled way. Quantum mechanics complicates that picture. The state of a many-qubit system is not described by one bit string or one classical probability table. It is described by a large complex-valued object whose dimension doubles with every added qubit. That does not automatically prove a classical simulation impossibility, but it does make efficient classical simulation a much stronger claim than it first appears. This is why the first lectures of a quantum information course begin with computational worldview questions rather than immediately jumping to gates. The field is partly about algorithms and hardware, but it is also about asking what the laws of physics allow efficient computation to look like. The practical takeaway is simple: if a physical process naturally evolves in a space whose classical description explodes, then efficient classical simulation is no longer something you get for free. Quantum computing is the study of what you can do when you let the device itself inhabit that quantum state space instead of forcing a classical computer to track every detail explicitly. ## Why It Matters - It gives the big-picture reason quantum computing is not just another hardware platform. - It connects complexity theory to physical law from the first lecture. - It prepares you to ask not only "can this be computed?" but also "who can compute it efficiently?" ## Source Reading Lens Use `qclec.pdf` Lecture 1 for the formal course framing: probability, interference, and which "self-evident" assumptions quantum mechanics preserves or overturns. Use *Quantum Computing since Democritus* as the broader companion. The useful thread is not "quantum computers can do anything." It is the narrower claim that the efficient-computation boundary suggested by classical Turing machines might not match the efficient-computation boundary allowed by physics. > [!question] Why does quantum computing pressure the Extended Church-Turing Thesis without refuting the ordinary Church-Turing Thesis? >> [!answer] The ordinary Church-Turing Thesis is about computability: whether a physical process can be simulated at all by a Turing-style model. Quantum computing does not obviously produce noncomputable functions. The Extended Church-Turing Thesis is about efficient simulation. Quantum algorithms suggest that some physical processes may be efficiently realizable quantumly while lacking efficient classical simulations. > [!question] What is the careful version of the quantum speedup claim? >> [!answer] Quantum computing gives strong evidence for new efficient algorithms in some structured problems and oracle models. It does not automatically imply efficient algorithms for arbitrary hard problems, and it especially does not prove that NP-complete problems become easy. ## Practical Lab Use a small notebook to make the claim concrete rather than leaving it at the slogan level. - Count how many complex amplitudes are needed to describe 1, 2, 3, 10, and 20 qubits in a full statevector simulation. - Compare that growth to the number of entries in an ordinary classical probability table over the same number of binary variables. - Write one short summary of when exact classical simulation still feels routine and when the representation size already starts dominating the problem. ## Homework Keep the homework split between concept and computation. - Explain the difference between the Church-Turing Thesis and the Extended Church-Turing Thesis in your own words. - Give one reason quantum computing challenges the extended version without obviously destroying the ordinary version. - Use your notebook counts to argue why state-space growth matters before you have even chosen a quantum algorithm. ## References - Scott Aaronson, [Introduction to Quantum Information Science](https://www.scottaaronson.com/qclec.pdf), Lecture 1. - Scott Aaronson, *Quantum Computing since Democritus*, Chapters 5, 6, 9, and 15. - IBM Quantum Learning, [learning portal](https://quantum.cloud.ibm.com/learning/en). - Microsoft Learn, [Azure Quantum documentation](https://learn.microsoft.com/en-us/azure/quantum/).