Nielsen and Chuang's Quantum Computing and Quantum Information, page 144, ex. 3.29, poses the following problem: "determine whether there is a path between two specified vertices in a graph. Show that can be solved using O(n) operations if the graph has n vertices."
They represent a graph as a set of vertices and a set of edges (vertex pairs). I don't see how you can do this in linear time. It seems like you have to search the vertex list multiple times, potentially once for each vertex, giving $O(n^2)$