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.
- On Applications of the Equilibrium Value Method, by Serena Booth. A survey about Xiaodi Wu’s simpler alternative approach to proving QIP=PSPACE, and whether it might also yield a proof of QRG=RG=EXP.
- Improved Quantum Query Complexity Bounds for Some Graph Problems, by Prafulla Dhariwal and Vinay Mayar. Building on Lin and Lin’s striking recent work on “Vaidman-bomb query complexity,” obtains some new results about the quantum query complexity of k-source shortest paths and minimum vertex cover in bipartite graphs.
- On Quantum Sieve Approaches to the Lattice Shortest Vector Problem, by Daniel Epelbaum. Surveys Greg Kuperberg’s subexponential-time quantum algorithm for the dihedral Hidden Subgroup Problem, as well as Oded Regev’s reduction of the approximate shortest vector problem to dihedral HSP. Discusses in detail why these two things, combined, do not yield a quantum algorithm for lattice problems that outperforms the best known classical algorithms.
- Approximate Degree of AND-OR Trees, by Pritish Kamath and Prashant Vasudevan. Discusses the wonderful open problem of proving that every AND-OR tree with N leaves, even a highly-unbalanced one, has approximate degree Ω(√N) as a real polynomial. (We know from Reichardt’s seminal work on quantum query complexity that the degree is O(√N).) Makes some partial progress on this conjecture—e.g., resolves it up to a polylog(N) factor for trees of constant depth.
- Infinite Separation of Quantum Information and Communication, by Dax Koh and Zi-Wen Liu. Wrings a further implication out of the striking recent work of Perry, Jain, and Oppenheim, about a communication task with infinite quantum/classical separation (“infinite” meaning that one of them is O(1)—o(1) actually—and the other is Ω(N)).
- Taming Quantum Amplitudes with Gateset Limitations, by Ross Rheingans-Yoo. Surveys the issue of doubly-exponentially small probabilities for PostBQP circuits, which I covered recently on this blog as well as on MathOverflow. Takes an initial step toward resolving the problem of whether π and e are “tame” numbers, by using the concept of irrationality coefficients to show that a constant number of gates with π- and e-like amplitudes can be tolerated in a PostBQP circuit.
- Tools for Quantum Circuit Synthesis, by Chelsea Voss. Click here to try Chelsea’s software! Discusses the creation of a web-based tool that lets you experiment with synthesizing quantum circuits and observing their behavior, and also gives you quantum-circuit-synthesis puzzles to solve.
- Complexity of the Quantum Separability Problem and Its Variants, by Charles Xu. Surveys the problem of deciding whether a quantum state described in various ways is separable or far from separable (and the use of that problem to characterize quantum interactive proof classes), concentrating on recent work by Gutoski, Hayden, Milner, and Wilde.
Follow
Comment #1 December 26th, 2014 at 2:24 am
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/ )
Comment #2 December 26th, 2014 at 3:46 am
now that’s surely a quantamplex mass…congrats to your students.
Comment #3 December 26th, 2014 at 9:08 am
Hi Scott, are any of your classes available in video form on iTunesU or other online service?
Comment #4 December 26th, 2014 at 10:40 am
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.
Comment #5 December 26th, 2014 at 11:11 am
“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 🙂
Comment #6 December 26th, 2014 at 12:52 pm
Can an MIT professor produce a MOOC for Coursera, or is that forbidden?
Comment #7 December 26th, 2014 at 1:01 pm
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! 😀
Comment #8 December 26th, 2014 at 4:25 pm
A merry Christmas, happy Chanukah, kwazy Kwanza, a tip-top Tet, and a solemn, dignified Ramadan, yourself Scott.
Comment #9 December 26th, 2014 at 6:37 pm
rrtucci #6: It’s allowed.
Comment #10 December 27th, 2014 at 8:07 am
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?
Comment #11 December 27th, 2014 at 8:40 am
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.
Comment #12 December 28th, 2014 at 12:53 am
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.
Comment #13 December 28th, 2014 at 11:16 am
OK, my version is now updated as well. Thanks Ross and Joshua!
Comment #14 December 28th, 2014 at 2:07 pm
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.
Comment #15 December 28th, 2014 at 5:35 pm
Ross – I’ve accidentally used the index ‘i’ twice
Hey, besides, it’s also a square root of -1.
Comment #16 December 28th, 2014 at 5:58 pm
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.
Comment #17 January 7th, 2015 at 5:40 pm
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.)
Comment #18 January 7th, 2015 at 7:29 pm
Ross, I think that works fine.
Comment #19 January 9th, 2015 at 8:29 pm
@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.