“IAD [the

Information Assurance Directorate] recognizes that there will be a move, in the not distant future, to a quantum resistant algorithm suite.”

*Shtetl Optimized* readers will appreciate that this IAD recommendation faithfully and even artfully reflects Mephistophelian quantum duality (of #133).

For if the optimistic quantum light teaches that quantum computers can break the Suite B cryptographic algorithms, and the skeptical quantum dark teaches that quantum computers are innately lossy — hence noisy, hence simulable in PTIME — then it follows that only quantum-resistant algorithms can resist PTIME classical attacks.

As for the move to a quantum resistant algorithm suite occurring “in the not distant future” … well, who *knows* what secrets remain to be mined from the Snowden disclosures?

**Opinion** The implications of Mephistophelian quantum duality for the engineering and medical arts so greatly surpass in long-term strategic, economic, and humanitarian significance the implications (if any) for the cryptographic arts, that a reasoned appreciation of this enduring asymmetric significance is the only *durable* “secret” that can rationally be associated to quantum information theory.

**Conclusion** Not the least of the virtues of BosonSampling research, for young researchers especially, is that it is unencumbered by secrecy and cryptolects.

“Based on the foundations of computer science, boson sampling is a mathematical proof (using plausible conjectures) that a many-photon state, when acted on by a large LO [linear optics] circuit set to implement a Haar-random unitary, will give rise to a probability distribution that cannot be efficiently sampled by a classical algorithm.”

Our intuitions upon contemplating this passage call to mind the 19th century couplet:

Two hearts do beat

within our breasts:

One heart is dark,

the other bless’d.

Our “blessed hearts” of quantum optimism hope that large LO circuits *will* prove to be a scalable path leading experimental refutation of the extended Church-Turing Thesis (ECT).

Conversely, our “dark hearts” of quantum skepticism wonder whether, in universes governed by QED at least, “large LO circuit” inescapably means “large *lossy* LO circuit”.

And it is natural to wonder too, whether the implications of a “mathematical proof (using plausible conjectures)” are strictly stronger than the implications of an unadorned “plausible conjecture”.

With these conflicting visions in mind, a third synthetic path is suggested by (mathematician) Michael Harris’ *Mathematics Without Apologies* (2015), specifically by a quotation from Goethe’s character Mephistopheles (on page 82):

Mephistopheles“I am a party to that power that always wills the Evil, and always creates the Good.”

(here Harris’ translation closely approximates the *Faust* translation of **physicist Tom Mellett**)

**Mephistopheles’ quantum prediction** Fuller appreciation of the “evil” effects of noise in large-scale quantum simulation, and of “sinful” loopholes in the no-go postulates of complexity theory, will inescapably create the “good” of performative engineering methods for simulating practical quantum technologies, in a QED universe that strictly upholds the ECT … accompanied (we can hope) by a “heavenly” mathematical and scientific appreciation as to *why* the Creation is so helpful (helpful to Faustian engineers at least).

Here the word “performative” has the sense that Harris specifies (on page 85), namely, that performative theories “do not simply describe a pre-existing world, but help to create a world of which the theory is a truer reflection.”

**Conclusion** An appreciation that Kalai-style quantum skepticism, and Harrow-style quantum optimism, alike are *performative* frames-of-mind — and even are *compatibly* performative — helps to deepen our appreciation of the *tremendous* fundamental worth of BosonSampling research.

And for this new research discipline, which so delights *all* of our scientific instincts, Scott Aaronson and Alex Arkhipov deserve immense credit.

Scott #126: yeah, but this didn’t seem to be a white paper, it sounds like they actually want to deploy QC resistant crypto, which surprised me some.

Meanwhile, here’s an Alabama license plate, though the person later came around to the other side: http://s3.neyer.me/pnp.jpg

]]>Very interesting indeed this update about Boson Sampling!

]]>————

**The Story of Sinful Alice**

**Alice** *(claims sinfully)* “With PTIME(n) resources, I can sample n-bit integers weighted by their Kolmogorov complexity.”

**Bob** *(responds doubtfully)* “With an NP oracle, I could falsify your sampling claim”

**Alice** *(replies triumphantly)* “But you haven’t *got* an NP oracle, have you?”

————

The point is that Alice’s state-of-sin — she is using a random-number generator — has extraordinary practical utility. So much so, that vast industries (like public key cryptography) are predicated upon the proposition that sinful claims like Alice’s cannot feasibly be disproven.

In other words, for all practical purposes Alice’s algorithm *does* have the “impossible” (yet extraordinarily useful) algorithmic property that she sinfully claims.

**The Sinful Postulate** Sinful algorithms are presently known for a vast class of problems, that practically are feasible to solve, even though formally they belong to hard complexity classes; it is therefore reasonable to postulate (or at least hope) that a great many quantum simulation problems — including perhaps even BosonSampling — are susceptible to sinful algorithms.

Regarding how we know there’s not a classical “trick”: that’s like, the entire point of our main theorem! Recall, we prove that any polytime classical algorithm to sample the same distribution as the optical experiment would imply a collapse of the polynomial hierarchy (and even an approximate sampler would let you approximate Gaussian permanents in BPP^{NP}.