Quantum Computing since Democritus

by Scott Aaronson

to be easier than NP-complete, but that are still too hard to efficiently solve with a quantum computer. Two examples are Graph Isomorphism and approximate shortest vector.