Quantum Advantage with Shallow Circuits Under Arbitrary Corruption

While initially realizing a physical quantum computer was thought to be extremely challenging, nowadays various types of high-fidelity processors capable of quantum algorithms have been developed [10, 24, 36, 38, 45]. These devices with noie and relatively small scale are called NISQ (Noisy Intermediate-Scale Quantum) devices [41]. For such devices, “quantum supremacy” [40] has been recently reported [6, 46].

While Shor’s algorithm and such quantum supremacy results strongly suggest that quantum computation is more powerful than classical computation, they are not mathematical proofs. While the superiority of quantum computation has been formally shown in constrained models such as query complexity [4] and communication complexity [22, 34] and considering complexity classes relative to an oracle [12, 42], almost no definite answer is known in standard computational models such as Turing machines or general circuits. Since the complexity class BQP (the class of the problems that can be solved efficiently by a quantum computer) satisfies the inclusions P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE, an unconditional separation between BPP and BQP would imply a separation between P and PSPACE, which would be a significant breakthrough. Therefore, unconditional separations between the computational powers of quantum computers and classical computers in a general setting are expected to be very hard to obtain.

However, with several assumptions from computational complexity such as non-collapse of the polynomial hierarchy or some conjectures on the hardness of the permanent, the superiority of quantum computation has been shown in the circuit model: even approximate or noisy probabilistic distributions of small depth quantum circuits are hard to simulate for classical computers [1, 2, 3, 13, 16, 17, 18, 44]. A recent breakthrough by Bravyi, Gosset and König [14] showed an unconditional separation between the computational powers of small-depth quantum and classical circuits: they constructed a computational problem that can be solved by quantum circuits of constant depth composed of one- and two-qubit gates acting locally on a grid and showed that any probabilistic classical circuit with bounded fan-in gates solving this problem on all inputs must have depth $\Omega(\log n)$, where $n$ denotes the input size. The computational problem they use is a relation problem (i.e., for any input there are several possible outputs). Besides its theoretical importance, this separation is also important since shallow quantum circuits are likely to be easy to implement on physical devices experimentally due to their robustness to noise and decoherence.

There are several results related to this separation. Coudron, Stark and Vidick [21] and Le Gall [26] showed a similar separation in the average case setting, instead of the worst case setting considered in the original version of [14]: there exists a relation problem such that constant-depth quantum circuits can solve the relation on all inputs, but any $O(\log n)$ depth randomized bounded fan-in classical circuits cannot solve it on most inputs with high probability. Bene Watts et al. [9] showed that a similar separation holds against classical circuits using unbounded fan-in gates and, considering interactive tasks, Grier and Schaeffer [28] showed even stronger classical lower bounds.

Bravyi et al. [15] additionally proved, using quantum error-correction, that a similar separation holds even if quantum circuits are corrupted by local stochastic noise (see Definition 1.1 below). The computational problem used in [15] is a generalized version, defined on a 3D grid, of the magic square game [35, 39], which is a nonlocal game with two cooperating players Alice and Bob who cannot communicate. The noise model is as follows.

In this model, an error is given as applying a gate which is $X,Y$ or $Z$. This definition assumes that when picking an arbitrary subset of qubits, the probability of all qubits are corrupted is an exponentially small function of the size of the subset. This property, which implies that a subset of size $\Omega(\log n)$ contains with probability $1-1/\textrm{poly}(n)$ at least one qubit that is not corrupted, is crucial in [15] to use quantum error correction. Note that, considering interactive tasks, Grier, Ju and Schaeffer [27] showed even stronger classical lower bounds in the same noise setting.

We actually describe a slightly more general computational problem that we name the “Graph State Sampling problem” and denote $\rho(G)$. Here $G=(V,E)$ is a graph specifying the problem. For any graph $G$, the problem $\rho(G)$ is a relation $\rho(G)\subseteq\{0,1\}^{|V|+|E|}\times\{0,1\}^{|V|}$. Given an input $x\in\{0,1\}^{|V|+|E|}$ for this relation problem, which we interpret as a pair $x=(y,H)$ with $y\in\{0,1\}^{|V|}$ and $H$ being a subgraph of $G$, we ask to output any bit string $z\in\{0,1\}^{|V|}$ that may appear with nonzero probability when measuring the graph state corresponding to the subgraph $H$ in a basis determined by the bit string $y$. We refer to Section 5.1 for details of the definition of the problem.

The 2D Hidden Linear Function problem considered in [14] is essentially the problem $\rho(G)$ where $G$ is the family of 2D grid graphs. Since the graph states of subgraphs of a 2D grid can be constructed by constant-depth quantum circuits whose gates act locally on the grid graphs, the problem $\rho(G)$ can be solved by a constant-depth quantum circuit. At the same time, Bravyi et al. [14] prove that no small-depth classical circuits can solve this problem using an argument based on the existence of quantum nonlocality in a triangle (first shown by Barrett et al. [7]). The main result in [14] can essentially be restated as follows.¹¹1In this paper, for any graph $G$ we use the notation $|G|$ to denote the size of the vertex set of $G$.

Item (ii) of Theorem 1.3, which is proved by considering the Graph State Sampling problem over expander graphs, gives a significantly stronger hardness guarantee than in Theorem 1.2 and thus provides us further compelling evidence of the computational power of quantum shallow circuits.

We stress that Theorem 1.3 does not claim a quantum advantage for noisy shallow quantum circuits: Theorem 1.3 simply shows that there exists a problem that can be computed by shallow quantum circuit but such that a shallow classical circuit cannot solve any (large) subproblem of it. We can nevertheless interpret Item (ii) as follows. A quantum circuit $\mathcal{C}$ solving the relation $\rho(G_{i})$ has $|G_{i}|$ output qubits, which are measured at the end of the computation to give the output string $z\in\{0,1\}^{|G_{i}|}$ that is a solution for the relation. Assume that an adversary chooses up to $\epsilon|G_{i}|$ qubits among these $|G_{i}|$ qubits and corrupts them in an arbitrary way (or, essentially equivalently, corrupts the bits of the measurement outcomes corresponding to these positions). Let $S_{i}$ denote the set of qubits that are not corrupted by the adversary. Since $\rho(S_{i})$ corresponds to a subproblem²²2This property can immediately be derived from the formal definition of the computational problem given in Section 5.1 of $\rho(G_{i})$, and since $\mathcal{C}$ before the corruption solved the problem $\rho(G_{i})$ on all inputs, even after the corruption the part of the output of $\mathcal{C}$ corresponding to the qubits in $S_{i}$ gives a correct solution to the problem $\rho(S_{i})$. On the other hand, Item (ii) of Theorem 1.3 shows that no small-depth classical circuit can solve $\rho(S_{i})$. (Note that in Item (ii) we even allow the classical circuit to depend on $S_{i}$.)

Let us compare this model of corruption of qubits with the model of noise considered in [15]. As already mentioned, in the error model of [15] (Definition 1 above), the probability that all qubits in a given set of size $\Theta(\log n)$, where $n$ denotes the total number of qubits, are corrupted by the noise is polynomially small and thus can be neglected. In comparison, Theorem 1.3 deals with the case where any subset of qubits of size as large as $\Theta(n)$ can be corrupted, and shows that the quantum advantage is still preserved in this case. In this sense, our result gives a further compelling evidence of the computational power of quantum shallow circuits.

After giving preliminaries in Section 2, in Section 3 we present graph-theoretical results about expander graphs. In particular, we prove Lemma 3.3 about the existence of large grid minors in corrupted expander graphs. In Section 4, we review the result about the nonlocality of a triangle quantum graph state used in prior works. In Section 5, we define our computational problem and prove Theorem 1.3.

Let us describe the definition of graph minors. Graph $\Gamma$ is a graph minor of graph $G$ if it is isomorphic to a graph obtained from $G$ by deleting edges and vertices and by contracting edges. Note that if a graph $\Gamma$ is a minor of a subgraph $S$ of a graph $G$, $\Gamma$ is also a minor of $G$. The definition is equivalent to the following definition, that if graph $\Gamma$ is a minor of graph $G$, we can decompose $G$ to connected subgraphs which connect to each other like $\Gamma$. We will use this definition later for explicit explanations.

Next, we will define the product of graphs $G\times H$ of graphs $G=(V_{G},E_{G})$ and $H=(V_{H},E_{H})$. The vertex set of $G\times H$ is the Cartesian product $V_{G}\times V_{H}$ and an edge is spanned between $(u_{G},u_{H})$ and $(v_{G},v_{H})$ if and only if $u_{G}=v_{G}$ and $\{u_{H},v_{H}\}\in E_{H}$, or $u_{H}=v_{H}$ and $\{u_{G},v_{G}\}\in E_{G}$. There are several ways to define graph products but we will use the definition above. In this paper, we particularly use $G\times K_{2}$, which $K_{2}$ is the complete graph of two vertices. Given a graph $G=(V,E)$, the graph product $G\times K_{2}$ is with $2|V|$ vertices and $2|E|+|V|$ edges.

Lastly, we refer to the Vizing’s theorem, which is about edge coloring. Edge coloring is to assign colors to edges so that the edges of the same color are not incident.

Let us explain about quantum circuits. An $n$-qubit quantum circuit is initialized to $\ket{0^{n}}$ and then arbitrary gates are applied to the state. We can apply gates at one time if each gate is applied to disjoint sets of qubits. The depth of a quantum circuit is $d$ if the whole operation of circuits can be decomposed to $U_{d}...U_{2}U_{1}$ where each $U_{j}$ is a tensor product of one- and two-qubit gates which act on disjoint sets of qubits.

Next, we describe measurements of quantum states. Mathematically, (projective) measurements are projections to some orthogonal bases. In this paper, We will use two kinds of measurements with the $X$ basis and the $Y$ basis. The orthogonal two states of $X$ basis are $\{\ket{+},\ket{-}\}$ and the ones of $Y$ basis are $\{\frac{\ket{0}+i\ket{1}}{\sqrt{2}},\frac{\ket{0}-i\ket{1}}{\sqrt{2}}\}$. Note that the measurements of $X$ and $Y$ basis are equivalent to the measurements of the computational basis if we apply $H$ and $HS$ gates before the measurements respectively.

Expander graphs are highly sparse but well connected graphs. Notable applications of the graphs have been found in mathematics and computer science [8, 19, 29]. Before giving the definition, we define the expansion ratio $h(G)$ of graph $G$. There are several ways to define the expansion ratio, for example edge expansion, vertex expansion and spectral expansion, but these are related to each other. The way we use is called vertex expansion.

The definition of expander graphs we use in this paper is as follows.

$h$ and $d$ specify the family of expander graphs. The existence of expander graphs is by no means obvious, but it can be shown using probabilistic approaches or concrete constructions of such graphs [31]. In this paper, an expander graph denotes a graph with sufficiently large $i$ of an expander family.

We want to prove the robustness of expander graphs to arbitrary vertex removals in terms of the size of grid minor, which is Lemma 3.3. We provide its proof in Appendix A.

In specific circumstances, local classical circuits cannot simulate measurement outcomes of entangled quantum states. This is called $quantum\ nonlocality$. In this section, we explain it occurs in a triangle graph state, as first shown in [7]. We will use this property to show the hardness of classical circuits to solve the relation problem in Section 5.

First, we note about properties of a graph state in a triangle shape. Let $\Gamma$ be a triangle such that the distance between three vertices $u,v,w$ are all even and $\ket{\psi_{\Gamma}}$ be a graph state for $\Gamma$ as in Equation (1). We define $L,R,B$ as the vertices between $u$ and $v$, $v$ and $w$, $u$ and $w$, and $M$ as a total number of vertices in $\Gamma$. Also define $L_{odd},L_{even},R_{odd},R_{even},B_{odd},B_{even}$ as vertices of $L,R,B$ which have odd and even distance from $u,v,w$ respectively. The three bits $x=x_{u}x_{v}x_{w}$ decide the measurement basis of $u,v,w$ (the $X$ basis if $x_{i}$ = 0 and the $Y$ basis if $x_{i}$ = 1) and the other vertices are measured in the $X$ basis. We denote $\tau(x)$ possible measurement outcomes of all qubits of $\ket{\psi_{\Gamma}}$ for input $x$, i.e., $\tau(x)=\left\{z\in\{0,1\}^{M}:\braket{z}{H^{\otimes{M}}{S_{u}}^{x_{u}}{S_{v}}^{x_{v}}{S_{w}}^{x_{w}}}{\psi_{\Gamma}}\neq 0\right\}$. We consider a relationship between input $x$ and output $z\in\tau(x)$. Define the following summations:

The following lemma is about quantum nonlocality in graph states of triangles and similar to Lemma 3 in Section 4.1 of [14]. It shows that when we assume a classical circuit has a kind of locality, the classical circuit cannot satisfy the relation of Claim 1 as inputs and outputs. We will give the proof in Appendix B.

In this section, we define Graph State Sampling problem and prove a separation of depth between quantum circuits and classical circuits. We consider an almost all induced subgraph $S$ of a graph $G\times K_{2}$ such that $G$ is an expander graph. Then, we prove $\rho(G\times K_{2})$ can be solved on all inputs by a constant-depth quantum circuit on $\Theta(|G\times K_{2}|)$ qubits, but $\Omega(\log|S|)$ depth is required for any classical probabilistic circuits to solve $\rho(S)$ on all inputs.