Theoretical Computer Science

Qubit gates in google supremacy

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?


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:133: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.

Comments (2)

  • +0 – 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? — Nov 07, 2019 at 06:56  
  • +1 – @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. — Nov 07, 2019 at 19:36  

External Links

External links referenced by this document: