<p>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.</p>

<p>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.</p>

<p>Consider the paragraphs below taken from their <a href="https://arxiv.org/abs/1910.09534" rel="noreferrer">paper</a>, 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]:</p>

<blockquote>
  <p>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. ...</p>
  
  <p>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].</p>
  
  <p>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. </p>
  
  <p>[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.</p>
  
  <p>[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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 4.0
2019-11-07T06:56:36.820Z
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?
VS.
CC BY-SA 4.0
2019-11-07T19:36:52.193Z
@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.
Logan Mayfield
CC BY-SA 4.0
2019-11-06T13:32:07.413Z
2019-11-06T13:50:29.443Z
2019-11-06T13:50:29.443Z
Peter Shor 
<p>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 <a href="https://en.wikipedia.org/wiki/Summit_(supercomputer)" rel="noreferrer">Summit/OLCF-<span class="math-container">$4$</span></a> in a reasonable time and if not why not?</p>

CC BY-SA 4.0
2019-11-06T13:21:42.360Z
IBM is aware of the spatial locality. Why do you think they didn't take the spatial locality into account in designing their simulation?
Peter Shor 
CC BY-SA 4.0
2019-11-06T13:29:17.823Z
Aaronson writes $9$ quadrillion possibilities in NYTimes and not sure why that number should be valid with locality.
VS.
CC BY-SA 4.0
2019-11-06T13:35:47.997Z
Aaronson may not have read IBM's paper carefully before he calculated that number.
Peter Shor 
CC BY-SA 4.0
2019-11-06T13:37:34.580Z
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.
VS.
CC BY-SA 4.0
2019-11-06T13:58:40.857Z
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.
Peter Shor 
<cc.complexity-theory><quantum-computing><big-picture><dc.parallel-comp><sample-complexity>
Qubit gates in google supremacy
VS.
# Qubit gates in google supremacy

(Asked by: username_0 on 2019-11-06)

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$](https://en.wikipedia.org/wiki/Summit_(supercomputer)) in a reasonable time and if not why not?

**Tags:** cc.complexity-theory, quantum-computing, big-picture, dc.parallel-comp, sample-complexity
> **Comments:**
> **username_1**: IBM is aware of the spatial locality. Why do you think they didn't take the spatial locality into account in designing their simulation?  
> **username_0**: Aaronson writes $9$ quadrillion possibilities in NYTimes and not sure why that number should be valid with locality.  
> **username_1**: Aaronson may not have read IBM's paper carefully before he calculated that number.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2019-11-06. Score: 8 | Accepted answer

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](https://arxiv.org/abs/1910.09534), 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.

> **Comments:**
> **username_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?  
> **username_2**: @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.  

---

