1. Hamiltonian Complexity.
This is a new area of quantum computing that ties in with questions of interest to condensed matter physics - such as ground states and ground energies of local hamiltonians.
[Complexity of local hamiltonians on a line]
[consistency of density matrices is QMA complete]
[Quantum detectability lemma and quantum gap amplification]

2. Efficient algorithm for 2QSAT; stoquastic hamiltonians and the sign problem
[Efficient Algorithm for 2QNP]
[Complexity of stoquastic hamiltonians ]

3. Classical simulations.
[Matrix product states]
[Multi-scale entanglement renormalization]

4. Quantum resistant cryptography
[Lattice based cryptography]
[Quantum resistant one-way function]

5. Quantum algorithm for solving linear systems of equations.
This is a very recent paper.
[paper]

6. Verifying quantum computers
The issue here is how you would verify a claim that a particular device is a quantum computer.
[Interactive proofs for quantum computation]
[Universal blind quantum computation]

7. Measurement based quantum computation
This is a novel model of computation in which a multiparticle entangled state is the initial resource for a quantum computation. The actual computation is carried out using adaptive single qubit measurements. This plays a role in the universal blind quantum computation from item 6 above.
[survey]

8. Interactive games + semidefinite programming + matrix mult updates
[Parallel approximation of non-interactive zero sum quantum games]
[Unique games conjecture with entangled provers is false.]

9. Quantum extractors.
This paper uses quantum random access codes.
[Short seed extractors against quantum strorage]
[slides from QIP talk]

10. Quantum expanders. [Quantum expanders from any Cayley graph]