*Hi Scott, can you comment on John Baez’s recent career change?*

He’s an inspiration to me in his new career, just as he was in his previous one.

*Does he inspire you to devote at least part of your time and mental energies to tackling ‘practical’ problems whose solution might ‘change the world’?*

I’ve *always* wanted to “tackle practical problems and change the world.” But outside of teaching, popularizing CS theory to high-school students and others, and raging against doofosity on this blog, I don’t think I’ve found the right area yet—a place where the (bizarre and unusual) skills that I happen to have would make a significant difference.

When nerdy academics *try* to influence politics, the results have often been counterproductive and borderline-horrifying, as in the case of Chomsky. Granted, I’m not a sophistic, genocide-minimizing loon like Chomsky is—just another left-moderate academic who thinks President Obama’s agenda sounds pretty good, and hopes it won’t be completely thwarted by the obstructionists in Congress or his own administration’s blunders. But that brings up a different problem: namely, how much do I have to say about climate change, renewable energy, nuclear proliferation, etc. etc. that’s at all original?

For years, I’ve daydreamed about helping start a school for gifted kids in math and science (though the term “gifted” is one I’ve never liked—I prefer to call them just nerds). Later in my career, I hope to try it if the opportunity arises. If someone could solve the problem of the repression and social ostracism of nerdy kids, that’s certainly one advance that would change the world.

]]>It was a tough decision to post on *MathOverflow* rather than *CS Theory*. The most fun answer (it seems to me) would be a concrete example … the kind of concrete example that characteristically is given on *MathOverflow*. But if the answer turns out to be that (provably) no such hard-to-bound algorithms exist in *P*, then *CS Theory* should have been the host.

Oh well … as Dick Lipton would say … in either event, answers are *greatly* welcomed from CS *cognoscenti* of every persuasion.

Recent advances in automated proof-checking show us that the peer-review proof-checking system used by mathematicians works amazingly well … rigorously correct proofs have been found for every major theorem that has ever been seriously checked (dozens of them, according to Freek Wiedijk’s list). So it is highly unlikely that we will ever discover that quantum factoring is not in BQP, or more generally, that BQP^P is not the same complexity class as BQP.

None-the-less, it is worthwhile to work through the details, for a reason that has been mentioned in several *Gödel’s Lost Letter and P=NP* posts. Dick Lipton and Ken Regan have called it the “Flaming Arrow Reason.” A “flaming arrow” is a piece of proof machinery that causes the reader to exclaim “Are they allowed to do that?”

The machinery of complexity theory—especially quantum complexity theory—contains many flaming-arrow methods; this is why its conclusions often are received with skepticism. In particular, when we work through the (many!) steps in the reduction of *BQP^P* to *BQP*, we find that some steps in the reduction require EXP resources to carry through, or are infeasibly prolifigate in the number of logic gates, or (most unrealistically of all, in engineering eyes) blithely assume that no independent verification or validation of the reduction is needed.

By the rules of complexity theory, these “flaming arrows” are permitted, and once we accept that these arrows are admissible elements of the game, then we are reasonably assured—as assured as we ever can be, of any branch of mathematics—that the main results of both classical and quantum complexity theory are not only valid, but very beautiful.

From a practical point of view, though, some of the “flaming arrows” of complexity theory—particularly quantum complexity theory—have proved to be extraordinarily difficult to realize in working devices. This is a big part of the reason why the *Quantum Information Science and Technology (QIST) Roadmaps* of 2002 and 2004 have proved to be far too optimistic in the projected rates of progress: so much so, that serious doubts as to whether practical quantum computers can *ever* be built, have not (as yet) been laid to rest.

In summary, the Great Truths of quantum complexity theory seemingly stand in opposition to the Great Truths of quantum systems engineering. Quantum complexity theory teaches us that robust quantum computation is feasible (in theory) while *P*-bounded quantum simulation is infeasible … whereas quantum systems engineering teaches us the exact opposite Great Truth, namely, that robust quantum computation are infeasible (in practice) while *P*-bounded quantum simulation is eminently feasible.

It is greatly to our overall benefit, that once we appreciate that each of these disciplines embraces its own unique set of “flaming arrows,” and we learn how to condition our conclusions upon these “arrows,” then the apparent contradictions disappear. Only then we are ready to greatly accelerate the pace of understanding how quantum dynamical systems work, and applying this understanding in addressing the urgent challenges of the 21st century. Good!

For engineers, this tension among Great Truths is why complexity theory in general, and quantum complexity theory in particular, is such a wonderful field of study, and why we engineers are so grateful for weblogs like *Shtetl Optimized* and *Gödel’s Lost Letter and P=NP*. Long may these weblogs prosper, and innoculate our minds with Great Truths! 🙂

Scott has offered to Dick and Ken’s readers the excellent advice (IMHO):

The gaps are small enough that any expert (or enterprising student), working in good faith, can fill them without difficulty … the proof assumes a bit of background knowledge that needs to be filled in if you don’t have it … [which is what] sites like MathOverflow and CS Theory StackExchange are perfectly designed for.

Taking Scott’s advice to heart, I have posed the question on MathOverflow (in a slightly generalized form) as *Does BQP^P = BQP ? … and what proof machinery is available?*.

It seems to me, that Dick and Ken are absolutely right that everyone benefits when questions like this are answered fully, and that Scott too is right, in reminding us that sites like MathOverFlow are a good place for such discussion … and so I would like to especially invite you, who are Scott’s students, to contribute to answering these questions.

Regarding the mathematical value of these questions, I have no special qualifications to judge .. but regarding their value in engineering and medicine, please let me assure you that good answers to these questions have very great significance.

So thank you Scott, both for teaching & encouraging these fine CS/CT/QIT students, and for your thoughtful suggestions regarding how best to pose these questions! 🙂

]]>