Can differennt computation model lead to different complexity?

There are many examples where someone replaces a CPU with a GPU or an FPGA and get a performance boost of $$\times 100$$ or more, but is it possible for a change in the architecture of computational resource to reduce the least possible complexity of solving a problem, say, from $$\Theta(n^2)$$ to $$\Theta(n)$$?

Basically, I'm looking for an example like Bead sort.

• It depends on how you define complexity. If you use PRAMs instead of a Turing Machine, then you can sort a list of $n$ elements in time $\mathcal{O}(\log n)$, however the total number of operations performed accross all processors is still $\mathcal{O}(n\cdot \log n)$. Then you can also consider quantum circuits: but I'm not sure how to quantify the complexity of quantum gates vs classical gates. – eru-cs Dec 14 '19 at 11:10
• In the quantum setting, Grover's algorithm searches unstructured databases in time $\sqrt{n}$ vs $n$ on a classical Turing Machine. – eru-cs Dec 14 '19 at 11:13