 This question also raises important issues about how to measure the complexity of a given quantum algorithm. The answer differs, of course, according to the particular model at hand. In the adiabatic model, for example, one needs only to estimate the energy gap behaviour and its relation to the input size (encoded in the number of degrees of freedom of the Hamiltonian of the system). In the measurement-based model, one counts the number of measurements needed to reveal the solution that is hidden in the input cluster state (since the preparation of the cluster state is a polynomial process, it does not add to the complexity of the computation). But in the circuit model things are not as straightforward. After all, the whole of the quantum-circuit-based computation can be be simply represented as a single unitary transformation from the input state to the output state.