The encoding of graphs and the development of efficient algorithms over graphs in the Quantum framework is still a challenging problem. More in general, the understanding of whether a problem can benefit of the Quantum speed-up or not is far from being complete. In this paper we analyse, compare, and generalize some proposals for the encoding of graphs in Quantum computing. A question peeping out on the horizon of our analysis concern the shift from a procedural way of thinking to a declarative one in the context of Quantum computing.