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]