Quantum Complexity Theory Student Project Showcase 3

Merry Christmas (belatedly)!  This year Quanta Claus has brought us eight fascinating final project reports from students in my 6.845 Quantum Complexity Theory class, covering everything from interactive proofs to query and communication complexity to quantum algorithms to quantum gates (and one project even includes a web-based demo you can try!).  Continuing in the tradition of the two previous showcases, I’m sharing the reports here; some of these works might also be posted to the arXiv and/or submitted to journals.  Thanks so much to the students who volunteered to participate in the showcase, and to all the students for making this such a great class.

19 Responses to “Quantum Complexity Theory Student Project Showcase 3”

  1. Craig Gidney Says:

    Always enjoy seeing these posted.

    (I also like that my hobby stuff would be good enough to count as a project, although it looks a bit more cartooney: http://jsfiddle.net/1hxemh1e/1/embedded/result/ )

  2. aviti Says:

    now that’s surely a quantamplex mass…congrats to your students.

  3. Fred Says:

    Hi Scott, are any of your classes available in video form on iTunesU or other online service?

  4. Scott Says:

    Fred #3: Sorry, no (though I do have lots of talks and a mini-course up on YouTube). Maybe I’ll do a MOOC in the future; for now, though, I think I prefer interacting with the wider world through the medium of text.

  5. rrtucci Says:

    “Maybe I’ll do a MOOC”

    just checked:
    Coursera- 890 courses
    EdX- 393 courses (MiTx-44 courses)

    I’m not trying to put any pressure on you 🙂

  6. rrtucci Says:

    Can an MIT professor produce a MOOC for Coursera, or is that forbidden?

  7. Michele Says:

    These works look great!
    I will tell my students to play with Chelsea’s web tools and to read the reports.

    Thank you, Quanta Claus! 😀

  8. Jr Says:

    A merry Christmas, happy Chanukah, kwazy Kwanza, a tip-top Tet, and a solemn, dignified Ramadan, yourself Scott.

  9. Scott Says:

    rrtucci #6: It’s allowed.

  10. Joshua Zelinsky Says:

    I’m reading Ross Rheingans-Yoo’s now, and I’m confused by a detail. On page 2 right after claim IV.1 how does the example of g(n):=n^2 get an example that must be tame? I see why the inequalities in (8) are close enough for that, but this doesn’t show it for other more complicated interactions. In particular, I don’t see how this rules out some more complicated product and sum involving elements from the A set constructed having unexpected cancellations which lead to non-tame number. I’m pretty sure that that doesn’t occur, but it doesn’t seem obvious to me. Is there some easy argument I’m missing?

  11. Joshua Zelinsky Says:

    One other comment on Rheingans-Yoo. On page 3 on the expoisition of Rosen’s proof he looks at at the field of fractions of Z[\alpha_i] with the alpha_i assumed to be yth roots of various integers. Not all algebraic numbers arise this way, so how can one justify restricting to this? I don’t think it actually is necessary for the proof at all so I don’t think it impacts things but I don’t think this step is justified.

  12. Ross Rheingans-Yoo Says:

    JZ #10: You’re correct. I conjecture that numbers of this form are tame, but I don’t have a proof.

    JZ #11: I’ve accidentally used the index ‘i’ twice — the intended meaning was the field of fractions of Z[\alpha_1,\alpha_2,…,\alpha_s], where any individual a_i might draw on more than one \alpha_j, not just a single \alpha_i.

    I’ve posted an updated print at http://blog.rossry.net/static/qc_tameness.pdf and emailed it to Scott, so that he can update his link.

  13. Scott Says:

    OK, my version is now updated as well. Thanks Ross and Joshua!

  14. Joshua Zelinsky Says:

    Ross Rheingans-Yoo #12,

    I don’t think that completely solves the problem. Not all algebraic numbers arise from root extensions. The classic example is a root of x^5 + x+1=0. The Galois group is of the polynomial is S_5 and one cannot represent any of the roots by any amount of simple root extractions.

  15. Greg Kuperberg Says:

    Ross – I’ve accidentally used the index ‘i’ twice

    Hey, besides, it’s also a square root of -1.

  16. Ross Rheingans-Yoo Says:

    Ah, you’re right. (That’s what I get for dashing off a quick response over break.)

    To be fair, the errors here are all mine; on MO, Rosen simply asserts
    min\{\prod_{v\in P}|x|_v^{-1}:x\in S_A(n)\}=2^{O(n)},
    which is true, if unexplained, and I’m simply trying (apparently unsuccessfully) to provide a slightly more rigorous explanation of why it’s true. I’ll take some time and try to get it sorted properly.

  17. Ross Rheingans-Yoo Says:

    Joshua, is this as simple as allowing the \alpha_j to be any algebraic roots? (Presumably, we want them to form an independent set, to make fractions sensible.)

  18. Joshua Zelinsky Says:

    Ross, I think that works fine.

  19. Ben Standeven Says:

    @Ross Rheingans-Yoo:
    In Theorem VI.2, why did you restrict the degree of the polynomials? I am fairly certain that the same result will hold without the bound.