I’m an old-fashioned physicist. I know very little about complexity theory. Maybe some day I’ll learn more about it. Nevertheless, I recognize that complexity theory is quite important to this quantum computing joint quest of ours. (although not as important as physics and engineering ) But note, dear physicist reader, that complexity theorists and other mathematicians “are different from you and me”.
Understanding without proving (what physicists do)
Proving Without Explaining (what mathematicians do)
Explaining Without Understanding (what I do)
Complexity Theorist Scott Aaronson recently gave a talk at UPenn Law School. I had a lot of fun reading the Powerpoint slides of the talk. Check them out. They are not very technical, as one would expect, considering that they are intended for a general audience.
In the comments section of Scott’s blog, I posed the following question:
Can one define quantum proofs very generally so that probabilistic, interactive and zero knowledge proofs are special cases of quantum proofs? Classical probability is a limit of quantum mechanics, interactive depends on what observables one is allowed to measure, zero knowledge sounds like the least number of observables are allowed to be measured.
My question turned out to be a dumb one, but Scott nevertheless patiently answered it. Thanks Scott. You can read Scott’s answer here.
I still think it would be cool if you could build a machine called a Quantum Prover, such that all other provers were special cases of it. The Quantum Prover would be the baddest, fastest gun in the West. It could simulate all other provers and either match or outperform them in speed and efficiency. Plus it could do extra stuff that the other provers couldn’t do.
Today, bayesian networks are an important tool in Google’s tool chest. If quantum provers ever come to pass, no doubt Google will have to upgrade its tools from classical bayesian networks to quantum bayesian networks…
The Quantum Fog 9000