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.


  • 1
    $\begingroup$ 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. $\endgroup$ – LastIronStar Nov 20 '17 at 5:15
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 26 '17 at 18:43
  • $\begingroup$ Can you credit the source for the architecture image? $\endgroup$ – D.W. Nov 26 '17 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").

  • $\begingroup$ 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? $\endgroup$ – Jake Nov 29 '17 at 6:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Craig Gidney Nov 29 '17 at 8:55
  • $\begingroup$ 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) $\endgroup$ – Jake Nov 29 '17 at 21:25
  • 1
    $\begingroup$ @Jake Bitonic sort assumes you can do interactions between things that aren't adjacent. That's not the case here. $\endgroup$ – Craig Gidney Nov 30 '17 at 1:44
  • $\begingroup$ derp you're right. $\endgroup$ – Jake Nov 30 '17 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.