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.

17 Responses to “Quantum Computing Since Democritus Lecture 7: Randomness”

  1. Jon Says:

    But assuming you picked up a 2πi phase last year, then you would still have a 2πi phase now.

  2. Scott Says:

    Yeah, yeah, I thought of that as I was writing it … alright, alright, fixed.

  3. Scott Says:

    Oh, come on! I spent like four days writing these notes for you. Can’t I get some feedback? :)

  4. wolfgang Says:

    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 8-)

  5. wolfgang Says:

    typo alert: I meant to write “I would think the 1st puzzle …”
    and “Then we define h …”

  6. Scott Says:

    Yep — that was von Neumann’s answer no less!

  7. Jonathan Katz Says:

    The second problem in your lecture is ill-defined…

  8. Scott Says:

    How so?

  9. Greg Kuperberg Says:

    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.

  10. Greg Kuperberg Says:

    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.

  11. Johan Richter Says:

    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.

  12. Scott Says:

    Johan: They all vote at the same time. I revised the notes to clarify this. Thanks!

  13. Andy D Says:

    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.

  14. Greg Kuperberg Says:

    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.

  15. Scott Says:

    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.

  16. volker Says:

    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

  17. Scott Says:

    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.