I agree with you that this is the most exciting time to be alive for someone who is interested in science, since the question of whether quantum supremacy is possible is the one of the most important scientific questions of all time. You may be a quantum supremacist and I may be a member of Antiqua, but I think we can agree on that.

]]>A skeptic like myself would not be convinced by 2 and 3. I don’t know anything about 4. But if they are successful with 50 to 60 qubits, that is much farther than I expected them to get. We shall see.

]]>Any event depends on previous events, if it doesn’t, it’s what QM refers to as pure randomness.

On the other hand, it’s possible for a given system to be both deterministic, and random, at different levels (when a radionuclide decays is apparently random, yet the time for half of 1 x 10 ^50 atoms to decay is consistent between any two samples to a very high precision). So I reject the notion that determinism (or indeed the presence of random events) necessarily prohibits free will.

]]>(1) Most obviously, if the QC is large enough to run Shor’s algorithm, then you just ask it to factor a huge random number and check the result! Unfortunately, that probably won’t be practical until we get full scalability and fault-tolerance.

(2) If the QC can simulate interesting quantum-mechanical systems, then you can test it by comparing the output of the simulation directly against experimental data.

(3) In the very near term—if you have (say) 100 or 200 qubits, but not 1000 qubits, and you want to continue to do the sampling-based quantum supremacy experiments you were doing with 50 qubits—you can vary your quantum circuit, calibrating its error rate on circuits that are easier to simulate classically, and then extrapolating to the ones that you can’t directly simulate. Here you’re making an assumption of “no conspiracy theories” (i.e., that the error rate won’t magically depend on whether this is one of the quantum circuits that happened to have an efficient classical simulation).

(4) Today, there are sophisticated protocols known for forcing a quantum computer to **prove** its answer to a classical skeptic, as long as the skeptic can submit challenges to the QC interactively. Some of these protocols—those of Aharonov-BenOr-Eban and Broadbent-Fitzsimons-Kashefi—require exchanging single, unentangled qubits with the QC, for instance using a fiber-optic cable. Another—that of Reichardt-Unger-Vazirani—requires two QCs that are entangled but unable to communicate. Finally, there’s the breakthrough protocol of Urmila Mahadev from a year and a half ago, which overcomes both of those issues, but requires a QC that’s powerful enough to implement lattice-based encryption (and depends on cryptographic assumptions).

I’m not entirely clear what you are trying to say about Kolmogorov Complexity. However, I am glad you brought it up because for me it is my favorite example of uncomputable behavior. For whatever reason, this is the one that really sparks my *aha* moment of *grokking* what it means to be uncomputable. I think it is really interesting that different people understand these concepts best through different means. Scott will forever have turing machines and the halting problem as his favorite avenue of thinking about computability and uncomputability. My favorites are the lambda calculus and kolmogorov complexity. I don’t know why, but they spark my imagination better than turing and the halting problem. And yet I know they are completely equivalent. Like Scott I’m also struck by this fact of their equivalency and think it very profound and meaningful.

]]>If I were a betting man I would place a bet that CT is actually false. That we are going to discover at some point an empirical refutation of CT by encountering a physical system that can only be explained by adhering to laws of physics that incorporate uncomputable behavior in some fashion. I don’t think I’ve ever asked you this explicitly, but what would your bet be and how sure of it are you? I’m guessing you would place large wager on CT being correct and that it won’t be found to be violated in your lifetime or ever 🙂

Another thing I would note that while the “box on the beach” could very well disprove CT it might be very very difficult for humans to *realize* that uncomputable behavior lies in physical systems we encounter all the time. Why? Because as you stated in your slide all these things we already know are uncomputable – the halting problem, kolmogorov complexity, diophantine equations – are in a sense equivalent, they don’t always appear so or appear *obviously* equivalent. Much in the same way I would add that the lambda calculus does not at first blush appear equivalent to Turing’s formulation. Or the SKI calculus for that matter.

Finally, to lend support for your statement early on in the talk about response to category theorists and type theorists complaining that Turing didn’t anticipate higher order functions… actual transcompilers for all of these things *already* exist and have been written. And interpreters for lambda calculus exist and can be run on your computer right now. The engineering for these compilers is done and it is entirely possible to right now take most any language which employs higher order functions or incredibly complex type systems and transcompile that to lambda calculus and run on a regular old desktop computer thus *demonstrating* the equivalence. You probably already know this, but just wanted to echo it.

]]>I enjoyed listening to Lecture 3 last night. You are the “great communicator” of the quantum computing community.

Question: You talked about the way companies like IBM and Google are trying to prove quantum supremacy by showing that a quantum computer can perform a task in microseconds that the best classical supercomputers take weeks to perform and that doing this requires a quantum computer on the borderline of classical and quantum with around 50 to 60 qubits.

This is great, but what if one wants to test whether a quantum computer with 70 to 150 qubits works? Are there ways that one can test these computers? If not, then how will quantum computing progress?

]]>