The Learning Stabilizers with Noise Problem

Let $n,k\in \mathbb{N}$ be integers with $n=\mathrm{𝗉𝗈𝗅𝗒}(k)$, and let $p\in (0,1/2)$ be a parameter. Recall that an instance of the $\mathrm{𝖫𝖯𝖭}$ problem consists of a generator matrix for a random linear code, together with a noisy codeword for a random string; specifically, we consider samples of the form

where $𝐀\in {\mathbb{Z}}_2^{n\times k}$ is a random generator matrix, where $𝐀\cdot 𝐱+𝐞(\mathrm{mod}2)$ is a noisy codeword which encodes uniformly random string $𝐱\sim {\mathbb{Z}}_2^k$, and where $𝐞\sim {\mathrm{𝖡𝖾𝗋}}_p^{\otimes n}$ is a random Bernoulli error. Without loss of generality²²2This happens with overwhelming probability for $𝐀\sim {\mathbb{Z}}_2^{n\times k}$ provided that $n\gg k$., we assume that the matrix $𝐀$ has full column-rank, i.e., the columns of $𝐀$ generate all of ${\mathbb{Z}}_2^k$. We now make a simple observation; namely, we can interpret the $\mathrm{𝖫𝖯𝖭}$ instance $𝐀\cdot 𝐱+𝐞(\mathrm{mod}2)$ as a particular noisy quantum codeword on $n$ qubits³³3Strictly speaking, we should think of $|𝐀\cdot 𝐱+𝐞(\mathrm{mod}2)⟩$ as encoding the row vector ${𝐱}^{⊺}𝐀+{𝐞}^{⊺}(\mathrm{mod}2)$., since

where $X^{𝐞}=X^{e_1}\otimes \mathrm{\cdots }\otimes X^{e_n}$ is a product of low-weight Pauli-X operators and where the unitary operator $U_{𝐀}$ is defined to be the matrix multiplication operation

Because $𝐀$ has full column-rank, $U_{𝐀}$ corresponds to a linear reversible circuit which can be described solely in terms of $\mathrm{CNOT}$ gates [45]. Therefore, $U_{𝐀}$ is a Clifford operator and thus maps Pauli operators to Pauli operators via conjugation.

We may also observe that $U_{𝐀}$ is the encoding circuit for a stabilizer code. The stabilizer group associated with this code is precisely the group of $k$ commuting Pauli operators under which $U_{𝐀}(|0^{n-k}⟩\otimes |𝐱⟩)$ remains invariant. These are easily seen to be the Pauli operators

where $Z_i$ denotes a Pauli operator which acts as a Pauli-$Z$ operator on the $i$-th qubit, and is equal to the identity everywhere else. In other words, the Clifford encoding unitary $U_{𝐀}$ (derived from an instance of an $\mathrm{𝖫𝖯𝖭}$ problem) gives rise to the quantum stabilizer code given by $S_{𝐀}=⟨U_{𝐀}{Z}_1{U}_{𝐀}^{†},\mathrm{\dots },U_{𝐀}{Z}_{n-k}{U}_{𝐀}^{†}⟩$. This shows that every instance of $\mathrm{𝖫𝖯𝖭}$ can be mapped to an instance of decoding stabilizer codes.

We now generalize this idea significantly, ultimately leading us to define the Learning Stabilizers with Noise (LSN) problem – the natural quantum analog of the $\mathrm{𝖫𝖯𝖭}$ problem:

• $\mathrm{■}$

  (Random stabilizer code:) Note that the encoding Clifford unitary in Equation 2 generates a specific stabilizer code of the form $S_{𝐀}=⟨U_{𝐀}{Z}_1{U}_{𝐀}^{†},\mathrm{\dots },U_{𝐀}{Z}_{n-k}{U}_{𝐀}^{†}⟩$. We consider stabilizer subgroups of the Pauli group which are chosen uniformly at random from the set of all stabilizer subgroups with $n-k$ generators, denoted by $\mathrm{𝖲𝗍𝖺𝖻}(n,k)$. In fact, as we show in this work, this is equivalent to choosing random stabilizer codes which are described by the set of generators $⟨C{Z}_1{C}^{†},\mathrm{\dots },C{Z}_{n-k}{C}^{†}⟩$, where $C\sim {\mathrm{𝖢𝗅𝗂𝖿𝖿}}_n$ is a random $n$-qubit Clifford operator.⁴⁴4While this is considered folklore, we are not aware of a proof which has previously appeared in the literature. Therefore, we decided to rigorously prove this statement.

• $\mathrm{■}$

  (Local depolarizing noise:) Recall that the noisy codeword $X^{𝐞}{U}_{𝐀}(|0^{n-k}⟩\otimes |𝐱⟩)$ in Equation 1 is only affected by low-weight bit-flip errors $X^{𝐞}$, where $𝐞\sim {\mathrm{𝖡𝖾𝗋}}_p^{\otimes n}$ comes from a Bernoulli distribution. In quantum systems, however, noise may also come in the form of phase errors. This leads us to consider a quantum noise model in the form of local depolarizing noise ${𝒟}_p^{\otimes n}$. Similar to the Bernoulli distribution, local depolarizing noise also produces low-weight errors with high probability, which therefore naturally generalizes the classical noise model.

In other words, we consider the task of decoding a random quantum stabilizer code in the presence of local depolarizing noise. Because the codeword is a stabilizer state, we call this the Learning Stabilizers with Noise (LSN) problem – in analogy to the classical $\mathrm{𝖫𝖯𝖭}$ problem. We now give a formal definition of the problem.

The Learning Stabilizers with Noise ($\mathrm{𝖫𝖲𝖭}$) problem is to find $x\in {\{0,1\}}^k$ given as input

where $S\sim \mathrm{𝖲𝗍𝖺𝖻}(n,k)$ is a uniformly random stabilizer subgroup, where $E\sim {𝒟}_p^{\otimes n}$ is a Pauli error from a local depolarizing channel, where $x\sim {\{0,1\}}^k$ is a random string, and where $U_{\mathrm{Enc}}^S$ is some canonical encoding circuit for the stabilizer code associated with $S$. As mentioned before, the encoding circuit is typically given in the form of a random $n$-qubit Clifford operator.

At first sight, it may not be clear why the LSN problem is even well-defined, since a unique solution to the quantum learning problem may not exist in certain parameter regimes. The intuition behind our argument for the existence of a unique solution is as follows. Suppose that $p\in (0,1/2)$ is a sufficiently small constant. Then, the quantum Gilbert-Varshamov bound implies that a random stabilizer code is non-degenerate and has distance at least $d=3np+1$ with overwhelming probability, in which case for any pair of codewords with $x,y\in {\{0,1\}}^k$, we have

by the Knill-Laflamme conditions – provided that $E_a,E_b$ have weight at most $|E_a|,|E_b|\le \frac{3}{2}np$. Fortunately, a simple Chernoff bound analysis reveals that this is the case with overwhelming probability for the local depolarizing channel ${𝒟}_p^{\otimes n}$. Therefore, Pauli errors which originate from a local depolarizing noise channel take orthogonal codewords to orthogonal codewords, and hence there must exist a measurement that perfectly distinguishes between them. This observation is also at the core of our algorithms for the LSN problem, which we describe next.

Previously, we discussed why random stabilizer codes give rise to a single-shot decoding problem which exhibits unique solutions with high probability. This suggests that LSN can be solved information-theoretically. Can we also find efficient algorithms for solving the LSN problem? Not surprisingly, the answer depends on the specific noise regime of the error distribution (see Figure 1). We give both polynomial-time and exponential-time quantum algorithms for solving the LSN problem in various noise-regimes:

• $\mathrm{■}$

  Extremely low-noise regime with parameter $p\approx \frac{1}{n}$. In this parameter regime, we show that a simple projection onto the stabilizer codespace (see Algorithm 1) suffices to solve the LSN problem in time $O(n^3)$ with constant success probability.

• $\mathrm{■}$

  Low constant-noise regime for a small constant $p\in (0,1/2)$. In this regime, we show that the Pretty Good Measurement (PGM) [8, 44] (with only a single sample) succeeds with high probability. Concretely, we view the $\mathrm{𝖫𝖲𝖭}$ problem as a state discrimination task where the goal is to identify $1$-out-of-$2^k$ (almost) orthogonal states. The success of the PGM is inextricably linked to the structure of our problem: although the distance between two arbitrary orthogonal states contracts tremendously – in fact, exponentially in system size (see, e.g. Proposition IV.7 in [34]) – under a layer of local depolarizing noise, a random stabilizer code encodes orthogonal states into orthogonal subspaces that are “protected” from such destructive contraction even under noise. This means that the information of the LSN secret is preserved under noise, and this is the intuition behind our approach in Algorithm 2.

• $\mathrm{■}$

  Higher constant-noise regime. In this regime, decoding is still possible at the cost of more samples. We derive the scaling of the sample complexity with noise, up to a certain noise threshold.

Recall that an instance of the LSN problem by definition features quantum inputs, which naturally led us to consider quantum algorithms as a means of solving the problem. However, despite the fact that LSN is a quantum problem, it reduces to a natural classical problem – stabilizer syndrome decoding. One way of solving the problem is to just measure the stabilizer syndromes of the noisy quantum codeword and to tackle the classical decoding problem instead. However, there are good reasons to believe that the classical (average-case) syndrome decoding problem is actually harder: while LSN trivially reduces to stabilizer syndrome decoding, the reverse direction is highly unclear; in particular, it is not at all obvious why an algorithm for the LSN problem would also imply an algorithm for the classical stabilizer syndrome decoding problem.

Recall that the LSN problem is stated as an average-case problem, where the success probability of an algorithm is measured on average over the random choice of stabilizer $S\in \mathrm{𝖲𝗍𝖺𝖻}(n,k)$, secret $x\in {\mathbb{Z}}_2^k$ and error $E\sim {𝒟}_p^{\otimes n}$. While the quantum Gilbert-Varshamov bound does in fact guarantee that an average-case instance of LSN can be solved information-theoretically, our results indicate that the problem becomes computationally intractable for large $k$ – even in constant-noise regimes. This raises the question of whether we can find concrete evidence for the average-case hardness of the LSN problem, beyond the fact that it subsumes the classical $\mathrm{𝖫𝖯𝖭}$ problem.

Recently, a number of works showed that there is in fact evidence of worst-case hardness for $\mathrm{𝖫𝖯𝖭}$; specifically, by studying a related worst-case problem – the nearest codeword problem (NCP) [14, 55]. Using the sample amplification technique [41], Brakerski, Lyubashevsky, Vaikuntanathan and Wichs [14] gave a worst-case to average-case reduction from NCP to $\mathrm{𝖫𝖯𝖭}$. Here, an instance to the former problem consists of $(𝐂\in {\mathbb{Z}}_2^{m\times k},𝐭=𝐂\cdot 𝐬+𝐰(\mathrm{mod}2))$ for some $𝐬\in {\mathbb{Z}}_2^k$, with the promise that the generator matrix $𝐂$ is balanced⁵⁵5Roughly speaking, this means that the minimum and maximum distance of the linear code generated by $𝐂\in {\mathbb{Z}}_2^{n\times m}$ is neither too small nor too large. and that the Hamming weight of the error $𝐰\in {\mathbb{Z}}_2^m$ is known. On a high level, the reduction in [14] proceeds in two steps:

• $\mathrm{■}$

  (Re-randomization of the secret) A random string $𝐮\sim {\mathbb{Z}}_2^k$ is chosen, and the worst-case instance $(𝐂,𝐭)$ gets mapped via an additive shift to

  $$(𝐂,𝐭+𝐂\cdot 𝐮(\mathrm{mod}2))=(𝐂,𝐂\cdot (𝐬+𝐮)+𝐰(\mathrm{mod}2)).$$

  Note that, whereas the initial secret $𝐬\in {\mathbb{Z}}_2^k$ was fixed, the new secret $𝐬+𝐮$ is now distributed according to the uniform distribution over ${\mathbb{Z}}_2^k$.

• $\mathrm{■}$

  (Re-randomization of the code and error) A random $𝐑\in {\mathbb{Z}}_2^{n\times m}$ is sampled from a smoothing distribution ${ℛ}_w^{n\times m}$, and the previous sample gets mapped to

  $$(𝐑\cdot 𝐂,𝐑\cdot (𝐂\cdot (𝐬+𝐮)+𝐰(\mathrm{mod}2)))=(𝐑\cdot 𝐂,𝐑\cdot 𝐂\cdot (𝐬+𝐮)+\overrightarrow{R}\cdot 𝐰(\mathrm{mod}2)))$$

[14] show that the resulting sample is statistically close to an (average-case) $\mathrm{𝖫𝖯𝖭}$ sample – provided that the smoothing distribution ${ℛ}_w^{n\times m}$ is chosen appropriately.

By taking a similar approach, we develop a worst-case to average-case reduction for the LSN problem. Here, the starting point is a worst-case stabilizer decoding instance $(S,E{|{\overline{\psi }}_x⟩}^S)$ for some stabilizer $S\in \text{Stab}(n,k)$, Pauli error $E$ of bounded weight (at most ${\log }^c(n)$ for any $c>0$), and secret $x\in {\{0,1\}}^k$. First, we observe that, in order to re-randomize the secret $x$, we need to act on the encoded data ${|{\overline{\psi }}_x⟩}^S$ itself. Hence, it suffices to choose a random string $u\sim {\{0,1\}}^k$ and to apply the logical Pauli operator ${\overline{X}}^u$ associated with $S$ to the noisy codeword itself, resulting in the desired transformation $E{|{\overline{\psi }}_{x\oplus u}⟩}^S$.

To re-randomize the code and the error, we first observe that the shifted codeword ${|{\overline{\psi }}_{x\oplus u}⟩}^S$ can be written as

for some (not necessarily random) encoding Clifford $U_{\mathrm{Enc}}^S\in {\mathrm{𝖢𝗅𝗂𝖿𝖿}}_n$. Because ${\mathrm{𝖢𝗅𝗂𝖿𝖿}}_n$ forms a finite group, this suggests that one could simply sample a uniformly random $C\sim {\mathrm{𝖢𝗅𝗂𝖿𝖿}}_n$ and consider the state $CE{|{\overline{\psi }}_{x\oplus u}⟩}^S=(CE{C}^{†})C{|{\overline{\psi }}_{x\oplus u}⟩}^S$, where $C{|{\overline{\psi }}_{x\oplus u}⟩}^S$ now comes from a random stabilizer code for a uniformly random encoding Clifford $C\cdot U_{\mathrm{Enc}}^S$. While this does seem to result in a re-randomized stabilizer code, the aforementioned transformation could potentially blow up the weight of the Pauli error $E$. In fact, it is well-known that random Cliffords are Pauli-mixing [19, 1]: they take any non-identity Pauli operator and map it to a uniformly random non-identity Pauli operator via conjugation. This seems to suggest that any naive worst-case to average-case reduction for LSN is doomed to fail: the weight of the re-randomized Pauli error now appears to follow a Binomial distribution with parameter $3/4$, thereby inducing a high-noise distribution which is statistically far from any reasonable noise channel (e.g., such as a local depolarizing channel).

In an attempt to overcome this barrier, we develop a re-randomization strategy which is much more gentle on the error (i.e., it does not cause it to blow up), and yet still ensures that the code gets somewhat re-randomized; however, this occurs at an expense: our random self-reduction only applies to a very restrictive case of the $\mathrm{𝖫𝖲𝖭}$ problem. Our strategy is to follow the random Pauli operator with a twirl – another random unitary consisting of a random permutation operator, followed by a layer of random single-qubit Cliffords. Similar ensembles of unitaries been used in the randomized compiling and benchmarking literature in order to tailor noise with arbitrary coherence and spatial correlations into a symmetric Pauli channel [51, 23].⁶⁶6To our knowledge, however, our work is the first to identify the twirl as a useful tool in the context of a worst-case to average-case reduction. Under this twirl, a worst-case error of weight $w$ is transformed into a uniformly random error of weight $w$; in particular, the weight of the error remains invariant. However, that the distributions of the error and the code are now correlated, which requires a much more refined analysis.

What is the computational complexity of solving the LSN problem? Notice that the description of the learning task features quantum inputs, which means that its complexity cannot be characterized by traditional complexity classes such as $\mathrm{𝖡𝖰𝖯}$ or $\mathrm{𝖰𝖬𝖠}$ which deal with classical-input decision problems. Instead, we show that (a variant of) the $\mathrm{𝖫𝖲𝖭}$ problem lies in the complexity class called ${\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖡𝖰𝖯}}^{\mathrm{𝖭𝖯}}$, a (distributional and oracle) unitary synthesis class which was recently formalized by Bostanci et al. [13]. At a high level, this follows from the quantum Gilbert-Varshamov bound which ensures that a random $\mathrm{𝖫𝖲𝖭}$ instance carries a unique stabilizer syndrome with overwhelming probability. Once the syndrome is computed, it can then be decoded with the help of an $\mathrm{𝖭𝖯}$ oracle. In other words, any polynomial-time quantum machine which access to the oracle can synthesize the appropriate Pauli correction for the noisy quantum codeword.

In the full version of the paper, we give a brief review of unitary complexity and also prove our aforementioned complexity upper bound on the hardness of the $\mathrm{𝖫𝖲𝖭}$ problem.

Just as $\mathrm{𝖫𝖯𝖭}$ has been fundamental to lower bounds in classical learning theory, we expect that $\mathrm{𝖫𝖲𝖭}$ will be a useful tool for proving lower bounds in quantum learning theory. In the full version of the paper, we identify one such learning setting: learning from quantum data [16, 18, 24, 17], a generalization of Probably Approximately Correct (PAC) learning to the quantum setting. Here, the goal is to learn a map $\rho :𝒳\to L({\mathscr{H}}_d)$ from classical to quantum data – for example, a Hamiltonian can be construed as a map from temperatures to Gibbs states, or time-evolved states.

In one special case of this task known as learning state preparation processes, the learner is allowed to observe input-output pairs for an unknown map, but the inputs are sampled from a distribution and are not identical. Refs. [18, 24] gave sample-efficient algorithms for learning in this setting, thus showing that it is information theoretically possible. But we show that these algorithms can never be computationally efficient – assuming the hardness of our $\mathrm{𝖫𝖲𝖭}$ assumption. While the lack of computational efficiency was implicit for the fully general learning setting due to a result of [7], that result does not apply when there are physically natural restrictions on the concept class, such as learning processes that involve quantum noise. Our $\mathrm{𝖫𝖲𝖭}$ hardness assumption fills this gap.

In the full version of the paper, we give a cryptographic application of LSN and show how to construct a statistically hiding and computationally binding quantum commitment scheme [53]. This is a fundamental cryptographic primitive that allows two parties (called a sender and receiver) to engage in a two-phase quantum communication protocol: in the first phase (the “commit phase”), the sender sends a commitment (i.e., a quantum register) to a bit $b$ to the receiver; the hiding property of a bit commitment scheme ensures that the receiver cannot decide the value of $b$ from the commitment alone. In the second phase (the “reveal phase”), the sender sends another quantum register to the receiver that allows the receiver to compute the value of $b$; the binding property of commitments ensures that the sender can only reveal the correct value of $b$, i.e. if the sender sent a reveal register that was meant to convince the receiver it had committed to a different value of $b$, the receiver would detect this.

Recall that the input in Definition 2 consists of a sample

where $S\sim \mathrm{𝖲𝗍𝖺𝖻}(n,k)$ is a (classical description of) uniformly random stabilizer, where $E\sim {𝒟}_p^{\otimes n}$ is a Pauli error $E\in {\overline{𝒫}}_n$, where $x\sim {\{0,1\}}^k$ is a random string. Occasionally, we also consider more general variants of the problem, denoted by ${\mathrm{𝖫𝖲𝖭}}_{n,k,𝒩,𝒮,ℐ}$, that feature samples

which are captured by the following set of distributions (which depend on $n$ and $k$):

• $\mathrm{■}$

  $𝒩$ is a general noise distribution with support over $n$-qubit Pauli errors $E\in {\overline{𝒫}}_n$.

• $\mathrm{■}$

  $𝒮$ is a general distribution over Stabilizer codes, either with support over the set of stabilizers $S\in \mathrm{𝖲𝗍𝖺𝖻}(n,k)$, or over Clifford encoding circuits in $C\in {\mathrm{𝖢𝗅𝗂𝖿𝖿}}_n$.

• $\mathrm{■}$

  $ℐ$ is a general distribution over input strings of the form $x\in {\{0,1\}}^k$.

Depending on the choice of distributions $𝒩$, $𝒮$ and $ℐ$, the learning task may either become easier or harder than the canonical learning problem in Definition 2.

We recall the following result by Montanaro:

We’re going to use the following block-encoding based algorithm in [29] for implementing the PGM. Let ${\kappa }_{\rho }$ denote the reciprocal of the smallest eigenvalue of a density matrix $\rho$. We use the following theorem.

In our case, since a purification of ${\rho }_x$ is

we may prepare this purification simply by applying $U_{\text{Enc}}^S$ on a coherent superposition. The number of gates required to implement an $n$-qubit Clifford is $N_{\rho }=O(n^2)$. We show the following theorem.