COMP 598: Quantum computation |
|||

Some tips: Possible topics 2) Aaronson: The learnability of quantum states 4) Aaronson and Ambainis: Quantum search of spatial regions 5) Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function 6) Bennett, Bernstein, Brassard and Vazirani: Strengths and weaknesses of quantum computing 7) Bacon, Childs and van Dam: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups 8) Barnum, Saks and Szegedy: Quantum query complexity and semidefinite programming 9) Childs, Cleve, Deotto, Farhi, Gutmann and Spielman: Exponential algorithmic speedup by quantum walk 10) [Claimed by Artem Kaznatcheev] Childs, Reichardt, Spalek, Zhang: Every NAND formula can be evaluated in time N^{1/2+o(1)} on a quantum computer 14) Durr, Heiligman, Hoyer and Mhalla: Quantum query complexity of some graph problems 15) [Claimed by Jeffrey Payette] Farhi, Goldstone, Gutmann and Sipser: Invariant quantum algorithms for insertion into an ordered list 16) Farhi and Gutmann: An analog analogue of digital quantum computation 17) Gottesman: An introduction to quantum error correction and fault-tolerant quantum computation 18) Ivanyos, Sanselme, Santha: An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups 19) Jain, Ji, Upadhyay and Watrous: QIP = PSPACE 20) [Claimed by Jonathan Cottrell] Kemme, Osborne, Vollbrecht, Poulin and Verstraete: Quantum Metropolis sampling 21) Kempe, Kitaev and Regev: The complexity of the local Hamiltonian problem 22) [Claimed by Julia Evans] Kuperberg: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem (see also these notes) 24) Watrous: Zero-knowledge against quantum attacks Presentation possibilities (more options): 25) Buhrman, Cleve, Wigderson: Quantum vs. classical communication and computation 26) [Claimed by Anqi Xu] Gottesman: The Heisenberg representation of quantum computers 27) Hallgren's quantum algorithm for solving Pell's equation 28) [Claimed by Alex Frechette] Harrow, Hassidim, Lloyd: Quantum algorithm for solving linear systems of equations 29) Kitaev's method for implementing the Fourier transform mod 30) [Claimed by Andie Sigler] Markov, Shi: Simulating quantum computation by contracting tensor networks 31) [Claimed by Ali Assaf] Mitchison, Jozsa: Counterfactual computation 32) [Claimed by Hao Peng] Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computation 33) [Claimed by Neil Edelman]: Laflamme et al.: Introduction to NMR Quantum Information Processing 34) [Claimed by Jan Florjanczyk] Cubitt: Deciding whether a quantum channel is Markovian is NP-hard 35) Magniez, Nayak, Roland, Santha: Search via Quantum Walk 36) [Claimed by Dave Touchette] Arshed, Toor and Lidar: Channel Capacities of an Exactly Solvable Spin-Star System 37) [Claimed by Mahdi Milani Fard] Somma, Boixo and Barnum: Quantum Simulated Annealing 38) [Tomas Jochym-O'Connor] Mochon: Quantum Weak Coin-Flipping with Bias 0.192 |
Home |
||