Can all of the qubits be fully mutually entangled? It is my understanding that the exponential speedup with more qubits requires them all to be entangled.
If you can entangle qubits 1 and 2, and qubits 2 and 3, then you can entangle the whole set of them together with a few more operations (definitely polynomial in scaling compared to whole computer operations, maybe linear?). You just need a connected graph between the qubits where you can run pairwise operations on any qubits that share an edge.