# If you had a 1000 qubit NISQ machine with arbitrary connectivity, what would you do?

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?

• 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. Commented Aug 27, 2022 at 21:23
• Maybe variational algorithms like VQE or QAOA would run successfully. Commented Aug 28, 2022 at 6:05
• @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? Commented Aug 28, 2022 at 10:45
• 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. Commented Aug 28, 2022 at 12:13
• @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:) Commented Aug 28, 2022 at 12:42