Architectures for Quantum Simulation Showing a Quantum Speedup

One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as “quantum computational supremacy,” referring to the experimental realization of a quantum device that computationally outperforms classical computers. In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation. In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis. The correctness of the final-state preparation in each scheme is fully efficiently certifiable. We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments. This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing. Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.

Popular Summary

Quantum computing, which relies on the often bizarre and nonintuitive behavior of subatomic particles, offers the potential to solve problems that cannot be handled by even the most powerful traditional supercomputers. As a step toward creating a universal, fault-tolerant quantum computer, researchers are focused on creating simple devices that show a marked speedup compared to their classical cousins. However, it is currently impossible to experimentally demonstrate if such a speedup exists. One route towards achieving these benchmarks is to rigorously prove a speedup for experimentally available, quantum many-body systems and then invoke further advances in computer theory, physics, and numerical studies. Crucially, one must be able to certify that the output of a quantum device is correct, which is a highly nontrivial task. Here, we demonstrate that a certifiable and rigorous quantum speedup is possible for architectures achievable with present technology, even in the presence of reasonable noise levels.

Our scheme requires little local control and is inspired by dynamical quantum simulation experiments in setups that use cold atoms. In these systems, a product state is prepared, evolved under a local translation-invariant Hamiltonian, and measured in a single shot. We devise a scheme on a two-dimensional square lattice that complies with these experimental requirements while at the same time allowing for a rigorous certificate via a simple product measurement on the final state. We prove that sampling from the distribution of measurement outcomes is intractable on a classical computer even up to an experimentally plausible error.

Our work makes it possible, in the near future, to devise a means for demonstrating and certifying a quantum speedup in a realistic experimental architecture.

Figure 1

Architectures I–III. Colors illustrate the rotation angle of the initial state (1): ${\beta }_i=0$ (blue), ${\beta }_i=\pi /4$ (yellow), and ${\beta }_i=\pi /8$ (crimson). Solid lines between qubits represent Ising-type interactions (2) with coupling constants $J_{i,j}=\pi /4$ (gray) and $J_{i,j}=\pi /8$ (black). $X$ and $Z$ label the basis in which the respective qubits are to be measured.

Figure 2

Certification protocol. We illustrate how our scheme works for architecture I. Qubits with thick (thin) borders denote odd (even) sites in $V_{\mathrm{odd}}$ ($V_{\mathrm{even}}$). The figure illustrates a pattern of on-site measurements for one execution of the certification protocol that measures the energy of $H_{\mathrm{odd}}=\sum _{i\in V_{\mathrm{odd}}}{h}_i$ for the configuration of initial states in Fig. 1. On-site measurements are of type $Z$, $X$, and $X_{\pi /4}$. Three Hamiltonian terms whose joint measurement can be simulated from these single-qubit measurements are singled out by the depicted dashed diamonds.

Figure 3

Mapping the TI quantum computation scheme of Ref. [39] to a cluster-state MBQC.

Figure 4

(i) Measurement of $X_{{\theta }_i}$, $X_{{\theta }_j}$ on an edge of a 1D cluster state: The outcomes $s_i$, $s_j\in \{0,1\}$ are uniformly random. (ii) The associated logical circuit: The by-product operator $X^{s_i}$ can be propagated forward in the circuit by substituting ${\theta }_j$ with $(-1{)}^{s_1}{\theta }_j$. The argument extends to the full cluster by induction, choosing the first qubit to be measured in the $X$ basis (this fixes the input of the logical circuit and does not change its universality properties). The 2D cluster-state case is analogous [29, 38].

Figure 5

Linear-depth implementation of dense IQP circuits (10). We illustrate our algorithm for four qubits. Yellow (resp. blue) blocks implement the two- (resp. one-) qubit gates in Eq. (10). The circuit consists of four single-qubit gates (resp. six two-qubit ones), which coincides with the number of vertices (resp. edges) of the complete graph $K_4$.

Figure 6

We show the logical circuit corresponding to architectures I and III (left) and II (right) for 5-row, 2-column lattices prepared with uniformly random ${\beta }_i\in \{0,\pi /4\}$ (blue, yellow) (I and III) and column-random ${\beta }_i\in \{0,\pi /8\}$ (blue, magenta) (II). At those qubits that have been prepared with ${\beta }_i=0$, an identity gate is applied; on those with ${\beta }_i=\pi /4$, a $T$ gate; and on those with ${\beta }_i=\pi /8$, a $\sqrt{T}$ gate.

Figure 7

Fraction of output probabilities larger than $1/2^n$ of random circuits drawn from the families ${\mathcal{F}}_{\mathrm{DO}}$ (l.h.s.) and ${\mathcal{F}}_{\mathrm{col}}$ (r.h.s.) for both linear (top) and quadratic (bottom) circuit depth in the number of qubits the circuit acts upon $n$, i.e., lattices of size $n\times n$ (top) and $n\times n^2$ (bottom). For each $n$, we draw 100 i.i.d. realizations $(\beta ,y)$, thus of the circuit ${\mathcal{C}}_{\beta ,y}$, and plot the resulting distribution in the form of a box plot. The red dashed line shows the value of $1/e$, which is precisely the value to be expected if the output probabilities are Porter-Thomas distributed.

Figure 8

Total variation distance to the Porter-Thomas distribution of the empirical distribution of output probabilities of random circuits from the families ${\mathcal{F}}_{\mathrm{DO}}$ (l.h.s.) and ${\mathcal{F}}_{\mathrm{col}}$ (r.h.s.) for both linear (top) and quadratic (bottom) circuit depths in the number of qubits the circuit acts on $n$, i.e., lattices of size $n\times n$ (top) and $n\times n^2$ (bottom). For each $n$, we draw 100 i.i.d. realizations $(\beta ,y)$, thus of the circuit ${\mathcal{C}}_{\beta ,y}$, and plot the resulting distribution in the form of a box plot.

Figure 9

Modified architectures I and II, named “MI” and “MII” in the figure. Changes are introduced on the even rows with respect to Fig. 1. On even rows, we pick ${\beta }_i\in \{0,\pi /2\}$ (black stands for 0, white stands for $\pi /2$) and perform a local Hadamard rotation. In architecture MI, ${\beta }_i$ is uniformly random. In architecture MII, ${\beta }_i$ is translation invariant on columns with a period less than or equal to 4 (i.e., ${\mathrm{TI}}_{(4,\infty )}$ in the notation of the main text).