The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment with a smaller computer than Summit/OLCF-$4$ in a reasonable time and if not why not?

  • $\begingroup$ IBM is aware of the spatial locality. Why do you think they didn't take the spatial locality into account in designing their simulation? $\endgroup$ Nov 6, 2019 at 13:21
  • $\begingroup$ Aaronson writes $9$ quadrillion possibilities in NYTimes and not sure why that number should be valid with locality. $\endgroup$
    – VS.
    Nov 6, 2019 at 13:29
  • $\begingroup$ Aaronson may not have read IBM's paper carefully before he calculated that number. $\endgroup$ Nov 6, 2019 at 13:35
  • $\begingroup$ Aaronson refers explicitly $9$ quadrillion states stored in Summit and by way of his writing seems to imply to the reader this is the bottleneck and tests the limit of the system. $\endgroup$
    – VS.
    Nov 6, 2019 at 13:37
  • $\begingroup$ First, 9 quadrillion is not the number of states, it's the size of one quantum state of the entire quantum machine. I don't see how locality is going to reduce this number. $\endgroup$ Nov 6, 2019 at 13:58

1 Answer 1


Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state of the quantum machine in your computer, you will have to keep recomputing pieces of the state, which is going to take much more time.

You have to trust both IBM and Google to have thought about the best way to do the simulation, and give accurate answers for how long a simulation would take. The researchers working at both these places are not stupid, and although it's quite possible that people will come up with better simulation methods eventually, they have indeed taken spatial locality into account.

Consider the paragraphs below taken from their paper, where it's clear that IBM uses spatial locality to make their simulation as fast as it is. Their simulation method is based on reference [14], which is turn is an extension of a simulation method discussed in [9]:

The simulation method in [9] can be seen as a tensor slicing approach. Qubits (and the corresponding tensor indices) are divided into “global” qubits, which are sliced and used to address across processing nodes, and “local” qubits, corresponding to tensor indices used to address tensor slices stored on each processing node. In [9], circuits are partitioned so that all gates within a subcircuit can be applied to the local slice of the quantum state, without communicating quantum state information among processing nodes. Such zero-communication updates of a local quantum state are possible when all non-diagonal gates in a subcircuit are applied to local qubits only. ...

The in-memory method that we presented in [14] considers circuit partitionings in which the resulting tensors either fit in available aggregate primary memory in their entirety, or their slices can be computed using available primary memory (using other tensors already computed and stored in primary memory). With this approach, the resulting tensors and/or their slices will generally be larger than the primary memories of individual processing nodes; this represents a difference between [14] and [9].

As discussed in [14], we combine the zero-communication strategies of [9] with our own tensor partitioning strategy to leverage secondary storage when quantum states are too large to fit in aggregate primary memory.

[9] T. Haner and D. S. Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In ¨ Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’17, pages 33:1–33:10, New York, NY, USA, 2017. ACM.

[14] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint arXiv:1710.05867, 2017.

Of course, it's quite possible that you could design a better simulation by using more information about Google's Sycamore architecture. But you may need to use more sophisticated information about it than just locality.

  • $\begingroup$ Is it possible for the Sycamore processor to beat existing quantum factoring record of 21=7x3 and does Spatial locality limit implementation of Shor's algorithm in some way? $\endgroup$
    – VS.
    Nov 7, 2019 at 6:56
  • 1
    $\begingroup$ @VS. I believe that Google's paper mentions that their processor cannot reliably run Shor's algorithm and not because of the spatial locality of qubit connectivity but because the qubits cannot maintain coherence long-enough to enable fault-tolerance. The depth requirements for larger implementations of Shor's algorithms really means you need fault-tolerance. $\endgroup$ Nov 7, 2019 at 19:36

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.