“一把茶壶揭真相 量子优势成笑料”的文章发表后，受到了我的一些专家朋友们的关注，在讨论过程中有2封电邮对 Teapot Test 问题的分析有独特的见解，值得公布分享。希望由此引起更深入的讨论，进一步认清 Quantum Supremacy “量子优势”的真相。
I would like to tell you how Borchards’ Teapot Test, also its ridicule expression ‘Teapot Supremacy’, is actually good as intended with a simple extension. I’ll go into the conceptual fine points as simply as I can. I read Aaronson’s response (easily found in the web) which makes the point, like many others did, that the ‘teapot’ is not programmable. He cites a rejoinder similar to my point yesterday, on which his reply fails on two different levels. I spend my precious time on this because the issue involved is important and somewhat subtle. The core of my account is contained in points (1)-(4), with (5)-(7) filling out a complete account. You can use my following freely without attribution in your future Chinese or English articles.
1) It is clear from his 12 minute video that Borcherds has little background in concrete physics or computer science. It is a basic first lesson in computer algorithms that a whole class of inputs is involved for an algorithm, it can’t be a single instance. (Say whether Fermat’s Last Theorem is true doesn’t qualify, only whether the equation has a solution for given n is meaningful.) A given teapot is a single instance. That is what the ‘programmable’ rejoinder really amounts to. Generally programmable computers are not being discussed.
2) One can describe a ‘blueprint’ that produces readily (with whatever implementable machine) a huge number of possible teapots with different, say, compositions. The teapot is then dropped from different angles, orientations, etc. as you brought up, which are part of the initial condition in a given environment with known temperature, pressure, humidity, floor hardness, etc. A classical computer with the same input data is to determine the number and shapes of the pieces the teapot breaks into when dropped. It is to be compared with the actual teapot dropping experimental outcome. The produced teapot is the readin of this “analog” computer, the dropping the processing, examining the broken pieces the readout.
3) Aaronson claims the ‘Extended Church-Turing Thesis’ (ECT), adding ‘if one believes it’, would say the classical computer can do as well as the experiment. ECT is the Church-Turing thesis extended to all physical processes, not just Turing machines, and also extended in the complexity sense. The complexity ECT on machines equivalent to Turing machines is what theoretical computer scientists like to believe, which I am skeptical about but let us ignore it here. The physical ECT is just wishful thinking with no real justification. In fact, the Teapot Test may be considered as evidence it is not true. In any event, ‘if one believes’ Aaronson qualifies shows his defense is circular.
4) Equally significantly, the experiment and the computer have exactly the same input information. Even if ECT is true, the computer does not know what a good algorithm would be other than from simple mechanics with the limited initial data. This is exactly similar to ‘quantum supremacy’ in which they just compare the quantum algorithm to whatever classical algorithm is known for the given problem. Thus Teapot Supremacy is indeed obtained from the experiment.
5) I assume the teapot ‘composition’ is complicated enough that the experimental outcome cannot be efficiently predicted from the initial data. How do we know then the experimental outcome is uniquely determined by the initial data? I claim there is no need for that, contrary to what I thought yesterday. The solution to be sought can be just one of the possible outcomes. Surely the computer can be asked the same question, to produce just one of the possible outcomes.
6) How do we know if the computer gives a different but wrong answer? If there are not too many possible answers we can perform the experiment on many identical input specification teapots. Also whatever classical algorithm used should show why it is a meaningful heuristic algorithm. Yet the Teapot Test is not quite watertight, but the relevant points are brought into sharp focus. I wouldn’t want to spend time trying to work out a watertight example.
7) On the other hand, it is significant that the Teapot Test can go ahead with whatever initial specification and produce a valid result. A computer operating on the initial data simply can’t, especially because any further theoretical help can be prohibited as part of the problem formulation. In that case it shows the limits of computation without the knowledge or competence that are readily available to humans, as in AI.
Please ask if you want clarification on whatever point. With the above elaboration, Teapot Supremacy appears to be a valid ridicule that Borcherds produced about Quantum Supremacy for the reasons he discussed.
I want to talk a bit about the ECT. The original Church-Turing thesis says Turing machines can compute a function if any digital computing machine (or algorithm) can. There are two extensions covered by the term ECT. The first says the above is true if computation is limited to polynomial time in both cases. So far there is no counterexample of that and there is general proof under some formulations and assumptions. In my view, one can’t prove the formulation is general enough similar to the original thesis, or else it is a theorem and no longer just a thesis. But many say the evidence is good that it is true, which is an important but usually unstated assumption in complexity theory.
The original thesis is also extended to cover computation by any physical process, with or without the complexity addition. I have not seen any convincing argument why that thesis is true. In fact, the QC people always hope that is not true in quantum computing. Thus, if one can prove integer factoring is superpolynomial for Turing machines, the Shor algorithm would show ECT is not true. Aaronson would say the ECT would still hold for classical physical systems. As I said, it begs the question in his use of it to refute Teapot Supremacy.
…. Yet it is possible the Teapot Test is still provably superpolynomial, which would show ECT is false in classical physics. (Borchserds’ quantum description of the teapot is not appropriate and impossible to formulate mathematically.) This is not an issue I would look into any time soon, ….