would this help improve Boson Sampling?

]]>**Serge** presupposes “counter-natural efforts that have systematically been trying to keep logic, computability and complexity away from physics.”

Serge, it is entirely feasible to put a name to these efforts: **ABET Accreditation Commissions**

[ABET-certified Computer Science (CS)] students must have one year of science and mathematics:

1.

Mathematics:At least one half year that must include discrete mathematics. The additional mathematics might consist of courses in areas such as calculus, linear algebra, numerical methods, probability, statistics, number theory, geometry, or symbolic logic. [CS]2.

Science:A science component that develops an understanding of the scientific method and provides students with an opportunity to experience this mode of inquiry in courses for science or engineering majors that provide some exposure to laboratory work. [CS]

One year of math, for *any* STEM degree, isn’t very much. And yet it is fundamentally *infeasible* to strengthen undergraduate mathematics curriculums, and still graduate students within four years.

As Scott’s senior MIT colleagues Gerald Sussman, Jack Wisdom, and Meinhard Mayer say in the introduction to their (excellent but immensely long) textbook *Structure and Interpretation of Classical Mechanics*

Classical mechanics is deceptively simple. It is surprisingly easy to get the right answer with fallacious reasoning or without real understanding.

If the Sussman/Wisdom/Mayer lament is true for classical mechanics, how much *more* true is it for quantum mechanics, as learnt by students pushed to study subjects too soon and too fast, by reason of a relentlessly fast-paced four-year curriculum?

**Conclusion** At the undergraduate level, the leisurely maturing of undergraduate mathematical capabilities, to foster a more universal, natural, and performative appreciation of STEM enterprises, is infeasible not by reason of obtuseness or conspiracy, but simply by reason of time.

This passage presupposes, implicitly at least, a converse community of researchers that embraces the implications of partial differential equations, differential geometry, and Lie groups, and is suspicious of (or at least struggles to grasp) the implications of set theory, logic, and computability. That converse community includes me, needless to say!

As far as I’m concerned, I’m not suspicious of any parts of mathematics. I’m just convinced that the counter-natural efforts that have systematically been trying to keep logic, computability and complexity away from physics are now reaching a dead-end. I foresee that a deep connection between relativity, quantum mechanics and complexity theory is about to get uncovered as an unwanted side-effect of the quantum computing adventure.

]]>Perhaps the nearest remark that we have to the last word is this passage from your own *Quantum Computing Since Democritus*:

Something inside me [and, I suspect, inside many other computer scientists!] is suspicious of those

partsof mathematics that bear the obvious imprint of physics, such as partial differential equations, differential geometry, Lie groups, or anything else that’s ‘too continuous.’So instead, I start with some of the most ‘physics-free’ parts of math yet discovered: set theory, logic, and computability.

This passage presupposes, implicitly at least, a converse community of researchers that *embraces* the implications of partial differential equations, differential geometry, and Lie groups, and is *suspicious* of (or at least struggles to grasp) the implications of set theory, logic, and computability. That converse community includes me, needless to say!

This division is at least as old as the atomic (hence discrete) worldview of Democritus, versus the geometric (hence continuous) worldview of Pythagoras. Bridging this division isn’t easy, even with modern mathematical tools that marvelously unite the discrete with the continuous. As Joseph Landsberg remarks in the introduction to his *Tensors: Geometry and Applications* (2012):

In the course of preparing this book I have been fortunate to have had many discussions with computer scientists, applied mathematicians, engineers, physicists, and chemists. Often the beginnings of these conversations were very stressful to all involved. […]

This difference of cultures is particularly pronounced when discussing tensors: for some practitioners these are just multi-way arrays that one is allowed to perform certain manipulations on [while] for geometers these are spaces equipped with certain group actions.

In view of these divisions, the single most enjoyable passage in *Quantum Computing Since Democritus* (for me) was its *zeroth* passage, namely its cover image, Rembrandt’s portrait *Democritus the Laughing Philosopher*.

In this wonderful painting, Rembrandt portrays laughter in its most inspirational and philosophically sophisticated form, which is (as it seems to me) **Spinoza’s hilaritas**. And in turn, the philosophical notion of

**Conclusion** The challenges of 21st century quantum research require all the hilarity that we can summon.

The motivation (possibly mistaken?) for this proviso is the proof in Aaronson/Arkhipov “The Computational Complexity of Linear Optics” (2011) of Theorem 4.3: Hardness of Approximating \(\mathsf{\text{Per}}\,(X)^2\).

The proof stipulates “an input [permanental] matrix, which we assume for simplicity consists only of 0s and 1s.” These (crucially?) restricted 0-or-1 elements, even allowing finite imprecision, are of course only a tiny subset of iid gaussian matrix elements, and moreover the “scattershot” proviso mixes these elements so thoroughly that (seemingly?) oracular assistance is required to sample a set of explicitly reducible 0-1 matrices.

The ensuing web of oracle-dependent complexity-theory implications is plenty tricky, for me at least, and plausibly tricky for the great majority of *Shtetl Optimized* readers too … there is no shortage here of inferences in which loopholes can reasonably be sought.

**Closing confections** Here are four quotes reflecting the time-honored interest in these difficult matters:

“A work should have either intelligibility or correctness; to combine the two is impossible, but to lack both is to be unworthy.”

— Bertrand Russel (1901)“The virtue of a logical proof is not that it compels belief but that it suggests doubts.”

— Henry George Forder (1927)“Beware of bugs in the above code; I have only proved it correct, not tried it.”

— Donald Ervin Knuth (1977)“A proof tells us where to concentrate our doubts.”

— Morris Kline (1988)

**Conclusion** A loophole-closing *Shtetl Optimized* column that clarified the question “What would it take to *really* collapse the polynomial hierarchy?” would be gratefully and enthusiastically read by many (most definitely including me).

Best of all, and most importantly, there’s *zero* margin for doubt that *Shtetl Optimized* is an elite web-forum for ideas and information relating to quantum information and complexity theory.