Many current devices are constrained to nearest neighbor connectivity or small system sizes, but suppose that a NISQ machine with 99-99.5% level two-qubit gate fidelities and arbitrary connectivity were available, with 1000 qubits. Are there really interesting algorithms that could be run that are not otherwise accessible on a similar-sized nearest-neighbor connected machine?

As an example, are there explicit quantum chemistry problems where this all-to-all connectivity would be a huge advantage?

  • 3
    $\begingroup$ With 99% fidelity on your favorite representative gate (say, the square-root-of-SWAP), you'd be hard-pressed to get a depth of more than 1000 gates - which is what you might need, to take advantage of the all-to-all connectivity of the 1000 qubits that you have. $0.99^{1000}=0.000043$, pretty small. $\endgroup$ Aug 27, 2022 at 21:23
  • $\begingroup$ Maybe variational algorithms like VQE or QAOA would run successfully. $\endgroup$ Aug 28, 2022 at 6:05
  • $\begingroup$ @MarkS nice argument! But why $n$ gates for $n$ qubits on full connectivity rather than, say, $n^2$? Also, is $0.5\times 10^{-4}$ really too small for, say, QPE? $\endgroup$ Aug 28, 2022 at 10:45
  • $\begingroup$ Well, I think you need $n^2$ gates to have all qubits have an opportunity to talk with each other in a nearest-neighbor topology, by doing a bunch do SWAPS… Also, the overall fidelity may not be too small, you’re probably right about that. $\endgroup$ Aug 28, 2022 at 12:13
  • 1
    $\begingroup$ @MarkS well, $n$ gates on a linear topology is enough to produce a GHZ state, say. On the other hand, you need at least $n(n-1)/2$ gates to use all the potential that comes with the full connectivity. So my estimations are opposite to yours, yet they probably both make sense:) $\endgroup$ Aug 28, 2022 at 12:42

1 Answer 1


The first thing I would do is ask the question: how good are they?

The comments to your question have already hinted at the answer. Not so good.

All-to-all connectivity is a dream for some platforms (e.g. superconducting) and very hard to realise on others (e.g. trapped ions). In fact, I would be happy to have an all-to-one to start with, given that it is a good CNOT connection. Note that the error rates of CNOT gates are much higher than Rz rotations.

With a thousand qubits and say a constant depth of five, I would try a very simple problem of finding the ground state energy of a mean-field model. The answer would be known and it would serve as a benchmark (i.e. can your QC find it?). Such a simple problem is not meant to show any 'advantage' which remains arguable for the 2019 supremacy paper too. Just don't ask what 'advantage' means.

I would return your 1000 qubits and tell you that I would be happier if you gave me 100 qubits with 1000 low-error-depth. On such a device I would run VQE with a highly customised (variational Hamiltonian) ansatz to find the ground state energy of the Hubbard model at any filling.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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