[graphene]

Isn't it true though that there would be an O(n^2)-type difficulty in adding extra qubits, since they all need to interact?

Or is that an oversimplified view?

[reikonomusha]

They do not all need to interact directly with one another. You can create full entanglement even if they linearly interact. It just means you pay a penalty in the compilation of your program.

Architectures with higher two-qubit connectivity is merely an optimization.