## Quantum Complexity Theory Student Project Showcase 3

December 26th, 2014Merry 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.