Entanglement scaling in quantum advantage benchmarks

A contemporary technological milestone is to build a quantum device performing a computational task beyond the capability of any classical computer, an achievement known as quantum adversarial advantage. In what ways can the entanglement realized in such a demonstration be quantified? Inspired by the area law of tensor networks, we derive an upper bound for the minimum random circuit depth needed to generate the maximal bipartite entanglement correlations between all problem variables (qubits). This bound is lattice geometry dependent and makes explicit a nuance implicit in other proposals with physical consequence. The hardware itself should be able to support superlogarithmic ebits of entanglement across some poly($n$) number of qubit bipartitions; otherwise the quantum state itself will not possess volumetric entanglement scaling and full-lattice-range correlations. Hence, as we present a connection between quantum advantage protocols and quantum entanglement, the entanglement implicitly generated by such protocols can be tested separately to further ascertain the validity of any quantum advantage claim.

Figure 1

Example of (a) a quantum processor grid and (b) the induced projected entangled pair state. (a) Grid for a quantum processor of $3\times 3$ qubits. Each node represents a qubit and each edge a tunable coupling between the qubits. (b) PEPS induced by the grid in (a). Each node with an open wire is a tensor. The open wires represent physical degrees of freedom in the tensor network and the internal edges represent internal bonds of some fixed dimension.

Figure 2

Comparison of findings: qubits versus gate depths superimposed on runtimes. In pink is the area below the gate depth required to achieve maximally entangled states for every bipartition containing existing numerical data (depicted as the $n/2$ ebit bound). (Data points are from Google [5, 8], Alibaba [12], Sunway TaihuLight [11], IBM [9], USTC [26], and ETH [27].)

Figure 3

Examples of graph topologies for a quantum processor: (a) Line topology, a line with $n=6$ qubits, (b) Ring topology, a ring with $n=8$ qubits, and (c) Rigetti topology, architecture announced by Rigetti [30]. We consider here a grid composed of octagonal rings connected as shown in the figure.