Quantum Computing Since Democritus Lecture 7: Randomness
Yes, less than a week after the course itself finished, a new set of lecture notes is finally here! The topic: randomness.
I’m writing this post from über-commenter Greg Kuperberg’s office at UC Davis, where I’m visiting for a few days to give a math colloquium. Greg has been trying to fill my thick skull with something called “t-cubature formulas,” and writing this post provides me with a much-needed break!
After Davis, I’ll be going to Berkeley for a couple weeks (not that I ever really left it), then my parents’ place in Pennsylvania for the holidays, then Caltech, then New Zealand (why the hell not?), then Australia for QIP, then back to Waterloo in February. Much more relaxing than last year’s trip — note that I won’t return from this one with an (additional) 2πi phase.
Follow
Comment #1 December 5th, 2006 at 12:29 am
But assuming you picked up a 2πi phase last year, then you would still have a 2πi phase now.
Comment #2 December 5th, 2006 at 12:37 am
Yeah, yeah, I thought of that as I was writing it … alright, alright, fixed.
Comment #3 December 5th, 2006 at 2:19 am
Oh, come on! I spent like four days writing these notes for you. Can’t I get some feedback? 🙂
Comment #4 December 5th, 2006 at 3:40 am
I would this the 1st puzzle (how to simulate a perfect coin with a crooked coin) has a fairly simple solution.
Let’s say h, t stands for head, tail of the crooked coin and
H, T stands for Head and Tail of the simulated perfect one.
The we define h followed by t as H whereas t followed by h is T (and we ignore h followed by h and t followed by t and throw again).
I am too lazy right now to think about the 2nd puzzle 😎
Comment #5 December 5th, 2006 at 3:41 am
typo alert: I meant to write “I would think the 1st puzzle …”
and “Then we define h …”
Comment #6 December 5th, 2006 at 3:58 am
Yep — that was von Neumann’s answer no less!
Comment #7 December 5th, 2006 at 4:53 am
The second problem in your lecture is ill-defined…
Comment #8 December 5th, 2006 at 5:02 am
How so?
Comment #9 December 5th, 2006 at 7:00 am
For the record, here is the result that I was explaining to Scott. I doubt that his skull is as thick as he claims, although it is true that we all get tired in the afternoon.
Theorem: Consider a randomly chosen state in a p-state qudit of th eform e2*pi*a(x)/p|x>>, where a(x) is a polynomial function from Z/p to Z/p of degree at most t-1. Then the expected value of
tensor t A |psi>tensor t
exactly equals the value that it would take if all of the phases of |psi> were uniformly random on the circle. In other words, this set of states is a t-design, or a t-cubature formula, for the torus of unbiased states. This construction is asymptotically optimal for any fixed t, certainly if you want exact equality, and possibly even if you want approximate equality.
Comment #10 December 5th, 2006 at 7:01 am
Blech, WordPress destroyed the math formula in the previous posting. I won’t try again, because (as I just found out) WordPress as configured here has no preview page.
Comment #11 December 5th, 2006 at 10:21 am
About question 2, they all vote at the same time? That is, a person can condition his vote only on what hats he sees the other people wearing and not on what on anyone has voted?
I am to lazy to think about the problem before I am certain I have understood the question.
Comment #12 December 5th, 2006 at 2:49 pm
Johan: They all vote at the same time. I revised the notes to clarify this. Thanks!
Comment #13 December 6th, 2006 at 2:31 am
Good notes, Scott.
One thing I might’ve added (though I realize you are cramming material in as is) is more on the distinction between the various strengths of derandomization we might hope for, i.e. if P = BPP, it’s still unclear whether derandomization is achievable by pseudorandom inputs to BPP algorithms, and if so, whether one pseudorandom generator can work for all BPP algs simultaneously.
We should be sure to emphasize not just that Impagliazzo-Wigderson suggests P = BPP, but that it suggests pretty much the strongest kind of derandomization is possible, covering Monte Carlo estimation, etc. Seems like the latter is what most people care about, not e.g. polynomial identity testing.
I also think it’s interesting that we can’t find significantly weaker complexity hypotheses (than the I-W one) that would show P = BPP but not strong derandomization.
Comment #14 December 6th, 2006 at 5:19 am
Sigh, there is no comment preview and the math formula support probably sucks, but I will try one more time.
Theorem from my paper: If p is prime, then there exists an ensemble of p^t unbiased states on a p-state qubit with the following property: If you have t copies of a state |psi> drawn from the ensemble, the result is measurement-indistinguishable from t copies of a uniformly random state in the torus of all unbiased states. In other words, there is a t-design on this torus with p^t points.
Scott had found a very similar t-design for n qubits with 4^{tn} points. It seems that if you use a prime p instead of the prime power 2^n, and if you tweak the construction a tiny bit, then you can square-root the number of points needed in the design.
Comment #15 December 6th, 2006 at 6:36 am
Andy D: Thanks for the comments! All things I would’ve put in if I’d thought of them, and if my students weren’t already griping at me for journeying too deep into complexityland.
Comment #16 December 6th, 2006 at 1:44 pm
Hi scott !
Is there a mistake in the following ?
assumption: BBP \in NP
suppose P=NP => P=BPP
suppose contrary P!=NP => (Impagliazzo-Wigderson) P=BPP
hence: BBP \in NP => P=BPP
Comment #17 December 6th, 2006 at 3:16 pm
Hi Volker,
I admittedly couldn’t understand your claimed argument. But let me make two remarks:
* Impagliazzo-Wigderson did not prove that P!=NP implies P=BPP. They proved that if E requires exponential-size circuits then P=BPP. Their assumption is both weaker and stronger than P!=NP: weaker because you only need a lower bound for E, but stronger because the lower bound you need is nonuniform and exponential (as opposed to uniform and superpolynomial).
* If we could prove that P!=NP implies P=BPP, then we could conclude P=BPP unconditionally! For there are only two cases: P!=NP or P=NP. And if P=NP, then we know the polynomial hierarchy collapses down to P, and hence P=BPP by Sipser-Gacs-Lautemann.