Mistake of the Week: The Unknown Unknown
And how is not this the most reprehensible ignorance, to think that one knows what one does not know? But I, O Athenians! in this, perhaps, differ from most men; and if I should say that I am in any thing wiser than another, it would be in this, that not having a competent knowledge of the things in Hades, I also think that I have not such knowledge.
Shtetl-Optimized’s Mistake of the Week series finally resumes today, with what’s arguably the #1 mistake of all time. This one’s been noted by everyone from Defense Secretary Donald Rumsfeld, to some toga-wearing ancient dude, to the authors of the paper Unskilled and Unaware of It: How Difficulties In Recognizing One’s Own Incompetence Lead to Inflated Self-Assessments.
Rather than give examples of this mistake — where would I start? where would I stop? how often have I made it myself? — I figured it’d be easier to give an example where someone didn’t make it. Today I received an email from a graduate student who had proved a quantum oracle separation, and wanted to know whether or not his result was too trivial to publish. I get fan mail, I get hate mail, I get crank mail, I get referee requests, but this is something I almost never see. After telling the student why his result was, indeed, too trivial to publish, I wrote:
There’s no shame in proving things that are already known, or that follow easily from what is. Everyone does it, the more so when they’re just starting out … The very fact that you cared enough to ask me if your result is trivial bodes well for your proving something nontrivial.
Follow
Comment #1 June 22nd, 2006 at 12:34 pm
Was the result considered too trivial because it followed already from known results, or were the results new but the techniques too “easy?” In the latter case, the student might want to try having it published or presented at a workshop or lower-tier conference just as a way to meet people, get people to meet him, and gain some experience.
Comment #2 June 22nd, 2006 at 1:14 pm
From my own personal experience and looking at those around me, telling when something is too trivial to publish (or not) is one of the last things a researcher learns.
Grad students and young faculty tend to be all over the map, sometimes thinking trivial things are publishable, sometimes not publishing results that are certainly publishable (**see below). On the other hand, truly senior people tend to think that everything is trivial, given their much broader knowledge.
No offense Scott, but the student should ask someone with slightly more experience for a ruling. Can the paper be submitted as a one page note to IPL or Arxiv? Should it be presented in a grad workshop?
** I sat on a paper for a long time, trying to “refine the model so that it became publishable” only to see the same result appear in STOC. What a mistake!
Comment #3 June 22nd, 2006 at 1:15 pm
Oh, all right: it was an oracle where BQP is not in P/poly. The proof is almost the same as an oracle separating BPP from BQP — you just need many instances of Simon’s problem for each input length, to kill off all possible circuits.
I’ve seen plenty of things at poster sessions at the same difficulty level. Here in Canada (eh?), there’s a quantum computing students’ conference that might be suitable.
(Such a conference reminds me of the Simpsons episode where Lisa is reading the “The New Republic for Kids”…)
Comment #4 June 22nd, 2006 at 10:09 pm
For any American Idol fans out there, I think this Kruger and Dunning paper sheds some light on why, during the initial auditions, some of the absolutely worst singers are convinced that they sound at least as good as the original recording artists. Furthermore, they are exactly the people who become very angry after being told by the judges that they suck, and then claim that the judges don’t know what they’re talking about.
Comment #5 June 23rd, 2006 at 1:57 am
To be fair, it’s pretty hard to know what your own singing voice is like. Especially if you mostly sing in the shower.
(also, how can you tell if your significant other actually likes it when you croon at them, or if they’re just humoring you?)
Comment #6 June 23rd, 2006 at 3:30 am
To be fair, it’s pretty hard to know what your own singing voice is like.
Yeah, but I’m talking about the people who walk in and say, “I sound like a cross between Aretha Franklin and Alicia Keys.” They also talk a lot of smack before they audition. Then, they start singing a really difficult song, like one by Whitney Houston or Christina Aguilera. It is then immediately apparent that they are completely tone deaf. They are then absolutely stunned when told how bad they are; they often don’t believe it.
So, the question is, why do these people do this?
A likely answer is that they just can’t hear the difference betweeen good and bad singing, so to their ears, they really do sound like the professional artists they hear on the radio. Bad notes sound just like good ones – if they could hear the difference, they would learn to sing better, and at least be better at assessing whether they had a snowflake’s chance in Hell toward becoming the next American Idol…
Comment #7 June 23rd, 2006 at 7:08 am
Ahh, what a fine topic just when I’ve run across a truly wonderful example, which is unfortunately too long to fit in the margin of this page…. (Apologies for the little Fermat joke – wonderful example follows.)
Dave Scott, who is apparently considered something of a science expert over at “Uncommon Descent,” Bill Dembski’s weblog on Intelligent Design, stated in a comment mocking a pro-evolutionist that “gravity is the strongest force in nature.” He was immediately challenged on this, whereupon he replied with the following slight qualification:
“In high mass regimes gravity is the strongest of all the forces.”
Yah, and of course we have the corollary that light is the strongest in high brightness regimes.
Comment #8 June 23rd, 2006 at 10:44 am
At the risk of political incorrectness, I will remark that this failing is apparently far more prevalent in males than females.
A Harvard business school demonstration (I believe this is well known, standard, I did not see this demonstration first hand but only heard a first hand report) asks the students to control a system, and then report on the results. They control it for a while, and various things happen. At then end, the ladies report things like: nothing I seemed to do helped. The guys report results about how great they were and how they made such important inputs. It turns out the system is random and they are totally decoupled from it.
Comment #9 June 23rd, 2006 at 11:52 am
Inflated self-estimation could bring serious problems some times. But why do people do this? It is most probably mostly because of the conditioning created by modern society.
So changes that are more fundamental than just penalizing or rewarding (coz these are the reasons people tend to do such things) are needed.
I am currently certainly not qualified to suggest such changes but since this a very popular blog some one can point out to any such efforts already being made or suggest some ideas.
Comment #10 June 23rd, 2006 at 1:22 pm
Scott: It was an oracle where BQP is not in P/poly.
Even if it is too elementary to publish, it is a valuable remark for the Complexity Zoo. The Zoo is a great illustration how every non-trivial work is ultimately composed of trivial pieces.
Comment #11 June 23rd, 2006 at 1:52 pm
Speaking of elementary remarks that pertain to the Zoo, is it clear that BPP//log is contained in P/poly?
Comment #12 June 23rd, 2006 at 2:29 pm
By the way, do I count as crank mail, fan mail, or something else?
Comment #13 June 23rd, 2006 at 4:05 pm
Michael, you’re a separate category (“unsolicited transhumanist life coaching”).
Comment #14 June 23rd, 2006 at 4:12 pm
is it clear that BPP//log is contained in P/poly?
Sure. First amplify, then hardwire a random string that works for all inputs of size n (as in the proof that BPP is in P/poly), then hardwire the // advice corresponding to that string.
Comment #15 June 23rd, 2006 at 9:33 pm
Even if it is too elementary to publish, it is a valuable remark for the Complexity Zoo. The Zoo is a great illustration how every non-trivial work is ultimately composed of trivial pieces.
Yes, indeed. If it had been mentioned in the zoo, I wouldn’t have even bothered asking the silly question!
Thanks for adding it. In fact, it can be added to the EQP section as well (the stronger result: there exists an oracle relative to which EQP is not in P/poly – this is the result that I had asked about). Also, there exists an oracle relative to which EQP is not contained in P^NP – that can be added as well. That result is due to Pruim and Green (appeared in IPL).
Comment #16 June 23rd, 2006 at 10:38 pm
Can someone provide a completely rigorous definition of EQP for me? I have put some work into the Zoo, but EQP has always confused me.
Yes, I know the statement that the probabilities in EQP should be exactly zero or one. My question is, what is the gate set of an EQP circuit, and how would a generating Turing machine describe the circuits?
Comment #17 June 23rd, 2006 at 11:37 pm
Yeah, EQP is kind of the toothless, one-legged tiger of the Zoo, kept alive only as a sympathy case.
Mike Mosca and Christof Zalka showed in quant-ph/0301093 that factoring is in EQP, for some definition of EQP.
I hereby license you to make up any definition of EQP you want that leaves their result valid.
Comment #18 June 24th, 2006 at 2:46 am
Actually, Mosca and Zalka specifically say that they don’t show that factoring is in EQP. They refer to a paper in progress by Mosca that does that, using a “slightly generalized model of exact quantum computation”. But I can’t find this paper by Mosca anywhere.
What Mosca and Zalka actually claim is an EQP algorithm for QFT and discrete logarithm with a known modulus. I think that they do not and cannot use Bernstein and Vazirani’s definition. As best I can tell, if the modulus p is part of the input, then they have a classical computer that (a) delivers a polynomial-time algorithm to generate the angles of some unitary gates, and (b) builds a quantum circuit.
Bernstein and Vazirani define EQP using a quantum Turing machine instead. It means, in effect, that an algorithm can only have one fixed gate set. There is no simple way to reconcile that with what Mosca and Zalka do. QFT_p cannot be in EQP in the Bernstein-Vazirani definition, because the field of definition of the unitary matrix entries grows with p.
Then, too, there probabily is no exact quantum universal TM in the Bernstein-Vazirani definition — they argue universality in the context of BQTIME rather than EQTIME. If you allow a classical computer to describe any quantum circuit, then of course that can be universal, but only for a cheap reason.
Another question is why the gate matrix entries have to be computable in P, rather than EQP (whatever that is in the end).
Another remark is that the distinction between BQP and EQP is not tenable in the context of fault tolerant quantum computation.
In my view, EQP is a tiger with goat’s feet and a serpent tail, and some suspicious sutures. The Zoo should warn visitors away from it. This story has been a big distraction for a lot of people.
Comment #19 June 24th, 2006 at 1:46 pm
Maybe I like Scott’s metaphor for EQP better than mine. As the Zoo veterinarian, I added a pessimistic medical diagnosis for EQP, and I added the healthier classes RQP and ZQP.
I am also added my own medical concerns for PhP, and if I may, rephrasing the ones that Scott had. The “holographic principle” should be downplayed because it is not established physics, even though it is very reasonable conjectured physics.
Comment #20 June 24th, 2006 at 8:14 pm
Maybe I like Scott’s metaphor for EQP better than mine. As the Zoo veterinarian, I added a pessimistic medical diagnosis for EQP, and I added the healthier classes RQP and ZQP.
Does this mean that EQP is not worth studying? From what I can gather from Greg’s comments, it seems that it’s not well-defined. Is this correct?
Comment #21 June 24th, 2006 at 8:58 pm
I shoudln’t say that EQP isn’t worth studying at all. However, the first question is whether the distinction between BPQ and any particular flavor of EQP is really worthwhile.
As I explained it in the Zoo page, there are at least two rigorous but inequivalent definitions of EQP. Some papers may implicitly use other definitions as well. Again, clarifying these definitions, and determining if they serve a good purpose, is more important than finding algorithms and oracle separations.
You certainly shouldn’t study EQP before you study some other objects in quantum complexity theory.
Comment #22 June 25th, 2006 at 6:26 pm
bikini calculus
I’m waiting for Scott’s “speedo quantum mechanics.”