The complexity is 2^n/2, but we don't know (afaik) if the quantum computer is also way faster for a single computation than standard computers. In that case, the more the better