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) 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) 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) Kemme, Osborne, Vollbrecht, Poulin and Verstraete: Quantum Metropolis sampling 21) Kempe, Kitaev and Regev: The complexity of the local Hamiltonian problem 22) 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) Gottesman: The Heisenberg representation of quantum computers 27) Hallgren's quantum algorithm for solving Pell's equation 28) Harrow, Hassidim, Lloyd: Quantum algorithm for solving linear systems of equations 29) Kitaev's method for implementing the Fourier transform mod 30) Markov, Shi: Simulating quantum computation by contracting tensor networks 31) Mitchison, Jozsa: Counterfactual computation 32) Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computation 33) Laflamme et al.: Introduction to NMR Quantum Information Processing 34) Cubitt: Deciding whether a quantum channel is Markovian is NP-hard 35) Magniez, Nayak, Roland, Santha: Search via Quantum Walk 36) Aaronson: A linear-optical proof that the permanent is #P-hard 37) Somma, Boixo and Barnum: Quantum Simulated Annealing 38) Mochon: Quantum Weak Coin-Flipping with Bias 0.192 |
Home |
||