# Computational power difference between all interconnected qubit vs few interconnected qubit

Recently I came across some news that Google and IBM are planning to unveil a 50 qubit quantum computer. I read that in this design, each qubit is not connected to all other qubits rather only to the two nearby qubits(neighours). In layman terms, what difference will this create in terms of the system's computational power?

I can't find the article but the architecture image is below. Hopes that will help.

• Welcome to CS Stack Exchange! Can you post the link to the article mentioned in your question? It will be helpful with finding the answer. Nov 20, 2017 at 5:15
• It looks like you accidentally created two accounts. I encourage you to merge them (see cs.stackexchange.com/help/merging-accounts for how) so that you retain access to your question and can edit it and post comments under it. If you can't do that, you can at least suggest an edit, which will be reviewed by others. I also encourage you to register your account so you'll retain access to it in the future.
– D.W.
Nov 26, 2017 at 18:43
• Can you credit the source for the architecture image?
– D.W.
Nov 26, 2017 at 18:44

A linear chain of qubits has two big disadvantages over a planar grid of qubits:

1) Resilience. If you arrange your qubits into a line, and any one of them doesn't work well, your quantum computer has been cut in half. In a grid you instead end up with a hole that, while inconvenient, can be routed around.

2) Closeness. In a linear chain, the qubits are on average farther apart. So if you want to interact two states, it may take longer to swap them towards each other so that they can interact. That being said, in highly parallel algorithms where you're already saturating all the connections with operations, you tend to be able to combine the swaps with the interactions you wanted to do anyways for no extra cost (e.g. see the paper "Quantum Simulation of Electronic Structure with Linear Depth and Connectivity").

• I think the question is not ho difficult or slow the operation of the machine would be but instead whether you can actually compute all the same things in the same asymptotic time. I believe your answer implies that either a) there is no asymptotic slowdown or b) the asymptotic slowdown is at most linear due to swapping bits around. Could you confirm?
– Jake
Nov 29, 2017 at 6:12
• @Jake The slowdown could be quadratic, since the max distance is O(n) instead of O(sqrt(n)). In terms of early non-error-corrected machines, going slower does mean you can compute fewer things. You don't have a lot of time before the errors build up and swamp your signal with noise. But if you had perfect qubits there'd be no difference in in terms of computability. Nov 29, 2017 at 8:55
• Thinking about this a bit more can't we get from any permutation of bits to any other in O(lg(N)^2) using bitonic sort? So why would the slowdown be quadratic? Shouldn't O(lg(N)^2) be the answer in the worst case? (btw I'm assuming perfect qubits since this is computer science not engineering/physics)
– Jake
Nov 29, 2017 at 21:25
• @Jake Bitonic sort assumes you can do interactions between things that aren't adjacent. That's not the case here. Nov 30, 2017 at 1:44
• derp you're right.
– Jake
Nov 30, 2017 at 7:48