Computational advantage of quantum random sampling

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently the first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. Here the theoretical underpinning of quantum random sampling is comprehensively reviewed in terms of computational complexity and verifiability, as are the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. Open questions in the field are discussed, and perspectives for the road ahead, including potential applications of quantum random sampling, are provided.

Figure 1

Circuit diagrams for (a) random universal circuits as performed in the experiment by [29] with random single-qubit gates from the gate set comprising $\sqrt{X},\sqrt{Y},\sqrt{W}$ and fixed two-qubit entangling gates $i$swap^* at fixed positions in the circuit, and (b) boson sampling, where passive linear optics comprising beam splitters and phase shifters are applied to a Fock input state $|1^n⟩$ and then measured in the Fock basis with outcomes $S_i$.

Figure 2

The polynomial hierarchy is a hierarchy of complexity classes defined by adding consecutive $\mathsf{NP}$ oracles, where any layer is presumed to strictly contain all lower-lying layers. Toda’s theorem (Theorem 12) states that the polynomial hierarchy is contained in ${\mathsf{P}}^{\mathsf{\#}\mathsf{P}}$.

Figure 3

(a) The output probabilities of Fock boson sampling [Eq. (45)] can be expressed as the modulus squared of the permanent of a submatrix $U_{S,1_n}$ of the Haar-random unitary $U$ constructed by discarding rows and columns according to the outcome and input registers $|S⟩$ and $|1{⟩}_k$. (b) Analogously, the output probabilities of Gaussian boson sampling [Eq. (54)] with squeezed state inputs on $k$ modes are proportional to the modulus squared of the Hafnian of $U_{S,1_k}{U}_{S,1_k}^T$.

Figure 4

In the proof of Theorem 15, the idea is to relate the hardness of approximating the probabilities in a distribution to the hardness of exactly sampling from that distribution.

Figure 5

Outline of the proof strategy for additive-error sampling hardness. A derandomizable sampling algorithm $\mathcal{A}$, given $C$ as an input, samples from a distribution $p$ that is $\epsilon$ close in total-variation distance (TVD) to the target distribution $p(C)$. Using Markov’s inequality and the hiding property, this implies that the output probability $p_0$ of $p$ is within additive error $2\epsilon /2^n\delta$ of the ideal output probability $p_0(C)$, with a probability of at least $1-\delta$. Given $\mathcal{A}$ as an input, Stockmeyer’s algorithm can infer a [$1/\mathsf{poly}(n)$]-multiplicative approximation $q_0$ of the approximate output probability $p_0$ in the third level of the polynomial hierarchy.

Figure 6

While in the proof of exact sampling hardness it was sufficient to build on the hardness of approximating the output probabilities of quantum circuits, in order to prove hardness of approximate sampling further properties of the circuit family $\mathcal{C}$ are required: approximate average-case hardness of computing the output probabilities and the hiding property.

Figure 7

(a) From at least $r+1$ interpolation points $\mathbf{(}{t}_i,q(t_i)\mathbf{)}$ one can efficiently interpolate a polynomial $q(t)$ of degree $r$. (b) Using the Berlekamp-Welch decoding algorithm ([433]) for the Solomon-Reed code, one can reconstruct a degree-$r$ polynomial from $k$ points $(t_i,y_i)$ if at least $(k+r)/2$ of those points are correct. (c) When drawing instances from a distribution on the infinite field $\mathbb{C}$ as opposed to the uniform measure over a finite field, the interpolation points are chosen from the interval $[0,\epsilon ]$ for $\epsilon =1/\mathsf{poly}(n)$ so that the distribution of $G(t)$ in Eq. (108) does not deviate too far from the original distribution. (d) Using the result of Theorem 23 by [352], one can bound the interpolation error of a degree-$r$ polynomial in the interval $(-\epsilon ,\epsilon )$ when given evaluation points that are correct up to an error $\mathrm{\Delta }$ (with inverse polynomial failure probability). Using the Lemma 22 of [334], one can then bound the extrapolation error when extrapolating to the hard problem instance at $t=1$.

Figure 8

In the task heavy-outcome generation (HOG) one is asked to output a list of strings $\{x_1,\dots ,x_k\}$ for which $P_C(x_i)\ge \mathrm{med}(P_C)$.

Figure 9

The fine-grained generalization of heavy-outcome generation is to bin the samples $x_1,\dots ,x_k$ from the noisy distribution $Q$ according to the probabilities $P_C(x_i)$. This constitutes a coarse-grained estimator of the total-variation distance between $Q$ and $P_C$. Since $P_C$ is nearly exponentially distributed for random circuits, a suitable choice of $m$ bins $[p_i,p_{i+1})$ is such that they are equifilled with a $1/m$ fraction of the ideal samples. This is shown for a noisy exponential distribution on an ($n=3$)-qubit sample space, with $m=12$ bins and $k=100$ samples.

Figure 10

Given a target state $\rho =|\psi ⟩⟨\psi |$, a fidelity witness $W$ for $\rho$ provides a lower bound on the fidelity $F(\rho ,\sigma )\ge \mathrm{Tr}[W\sigma ]$ so that, in particular, all states $\sigma$ such that $F(\rho ,\sigma )\le F_T$, it also holds that $\mathrm{Tr}[W\sigma ]\le F_T$. Conversely, all states $\sigma$ satisfying $\mathrm{Tr}[W\sigma ]\ge F_T$ will also satisfy $F(\rho ,\sigma )\ge F_T$. There is a gap $\delta \ge 1-F_T$ such that all states $\sigma$ with fidelity $F(\rho ,\sigma )\ge F_T+\delta$ lie on the left side of the witness.

Figure 11

(a) To build trust in the proxy methods (elided and patch circuits) for full circuit simulation used to estimate the XEB fidelity, sampling on the quantum processor is performed using circuits with the same gate count as the “supremacy circuits,” but in a simplifiable pattern and with a depth of 14. Each data point is an average of the XEB fidelity of ten circuit instances with $(0.5–2.5)\times {10}^6$ many samples per instance. The solid line represents the predicted value of the XEB fidelity given the error model. (b) In the “supremacy regime” of 53 qubits and a depth of up to 20, the elided and patch methods are used to estimate the XEB fidelity and the classical simulation time for verification and sampling is extrapolated. From [29].

Figure 12

In a tensor network every edge corresponds to a rule to sum over the corresponding index of the neighboring tensors. In a quantum circuit two-qubit gates are represented as four-index tensors (boxes) and single-qubit computational-basis states (vertices) are single index tensors or vectors. Contracting an edge with a neighboring computational-basis state (indices $i$ and $j$) corresponds to selecting a slice of the neighboring tensor. Contracting an edge between two arbitrary tensors (index $l$) corresponds to summing over the entries of the neighboring tensors over that index, resulting in a new, larger tensor.

Figure 13

In frugal rejection sampling, we sample a point $(x,u)$ uniformly at random over the area $\{0,1{\}}^n\times [0,c/2^n]$. A sample is accepted if $u\le p(x)$ (green area) and rejected otherwise. For Porter-Thomas exponentially distributed outcome probabilities (solid green line), this will result in a TVD error $\epsilon =2\exp [-c/(1-e^{-c})]$ of the actually sampled distribution (dashed pink line) compared to the target distribution.