No, Principia Mathematica didn’t have a 1000-page proof of 1+1=2. It had 1000 1-page proofs of the machinery needed to prove 1+1=2 in only 1 page. So you see, I trust, why appending a proof of each trivial fact you use in a paper isn’t a workable plan.

Job @68:

From my understanding of the papers Scott alluded to in his original post, a machine that allows the efficient reproduction of quantum statistics and follows a definite execution path will be strictly more powerful than a quantum computer.

My understanding is that the interference bit wouldn’t be sufficiently useful to solve Simon’s problem efficiently.

In Simon’s algorithm, if the secret value has a single zero bit, then the vast majority of execution paths should interfere destructively. In this case the interference bit would almost always be true and we’d just have that plus a non-orthogonal value of y, which is not much.

I find this interesting because the problem of determining whether an execution path destructively interferes does not seem to be an easy problem either, so this type of not-quite-quantum machine might as well be somewhere between BQP and BPP.

In trying to narrow down the computational advantage of a quantum computer relative to a probabilistic classical machine, i’ve gone through the following stages of decreasing naivety:

1. It’s magical because Quantum Physics is not well understood.

2. It’s because of entanglement. Entaglement is weird and must have weird computational power.

3. It’s because a QC is implicitly keeping track of 2^n possibilities with varying probabilities (riiight).

4. It’s because of the negative amplitudes and the phase kickback trick (nope).

5. It’s because of interference, it’s difficult to determine which results will never be measured (maybe?).

As i understand it, it’s not any of the above. A QC is faster than a classical machine because it can, not just identify, but avoid execution paths that have the property of destructive interference. Can we say that a QC avoids non-symmetrical execution paths?

What if we define a machine that avoids execution paths based on different criteria? For example, let M be a machine that avoids execution paths for which a valid though different yet isomorphic execution path exists. Or maybe M avoids execution paths based on sub-isomorphism?

How many distinct classes of universal machines can we define based on execution-path avoidance? Are any of these more powerful than BQP?

]]>Suppose we have a not-quite-quantum machine which, given a quantum circuit, processes a random execution branch and returns the result along with a boolean indicating whether the execution path destructively interferes.

What’s the computational power of this machine? How much does the interference boolean buy us?

]]>I wouldn’t say it quite like that. I think that the recent victories of formal proof systems is that Principia was just as much an honorable failure, indeed a prescient effort, as the Babbage calculating engine. They just didn’t have computers, that’s all.

What is true is that rigorous coding is not easy; and not the same thing as a human proof even if it is derived from that; and is really someone else’s effort. Even if a computer scientist publishes an algorithm, everyone understands that implementation can fairly be someone else’s business. It’s absurd to impose some absolute standard that every published algorithm should include an implementation, or any other specific element.

Likewise, it’s absurd to demand an absolute standard of completeness for a human proof. No matter what details you put in a proof, there is always someone else to demand more details. Until you reach the limit of formalized proof so that no one would want to read it. Indeed, good writing can make the problem “worse”. When scientists write well and write carefully, as Scott certainly does for the most part, it tends to pull in readers, some of whom who have trouble understanding the material. (Just as many “bad” doctors are very good doctors and many “bad” roads are very good roads, that simply create >1 unit of demand for every unit of achievement.) The only way to play it safe is to write impenetrable papers that no one enjoys reading.

]]>“I think you’re ignoring a massive selection effect: 99% of what gets handwaved as trivial in math/TCS papers, really is as trivial and unproblematic as the authors said it was! But of course, that’s not the 99% that later prompts blog posts like one.”

We will have to disagree here. I think the percentage is well below 99%. This is based on experience, not blog posts.

“Furthermore, trying to justify every trivial claim would make papers unreadably and unwrite-ably long—try earnestly to do so, and what you get is not a research paper but Principia Mathematica (where by volume II, Russell and Whitehead had finally developed enough machinery to prove 1+1=2).”

Again, I can’t agree with this hyperbole. Nobody in TCS is arguing about 1+1=2. They are making statements, calling them trivial, and skipping the proofs. Most of the statements have one-page proofs that would fit fine in an appendix. If it really requires a 1000-page proof, then it probably isn’t trivial and less definitive language should be used: “We suspect that this statement can be verified by a straightforward but lengthy calculation, but have not checked the details.”

“My understanding is that the latter is what happened with the Fortnow-Rompel-Sipser paper. They published a paper with a side-note saying something like, ‘obviously, you can then just do parallel repetition to decrease the error.’ …”

This kind of claim can be truly bad. If the result is true, then they’ve preemptively claimed credit for it, without actually proving the result. In this way, they discourage others from working on it in either direction, because there’s less incentive. If the result is wrong, then they spread errors through the literature. In the worst cases, you end up with subfields where outsiders can’t judge the status or progress, with knowledge tied up in a spaghetti of claims, published and unpublished. Again, this protects the insiders from competition.

]]>“The theoretical justification is that we can only implement gates to finite accuracy.”

Is this accuracy related to de-coherence creeping in, and amplitude superposition is lost?

Or is this something even more fundamental, like an analogy to a classical coin flip that would have a theoretical arbitrary randomness associated with it, e.g. prob(head) = 0.1 * PI, but in practice the accuracy of the realization is always going to be limited?