Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

The PFR theorem (and the closely-related quasi-polynomial Bogolyubov-Ruzsa theorem) also provide powerful tools that found diverse applications to theoretical computer science, including linearity testing of maps $f:{𝔽}_2^n\to {𝔽}_2^m$ [26], constructions of two-source extractors from affine extractors [28], communication complexity lower bounds [9], super-polynomial lower bounds on locally decodable codes [11], constructions of non-malleable codes [1], higher-order Goldreich-Levin theorems [27, 21, 12], sparsification algorithms for 1-in-3-SAT [8], quantum proofs for classical theorems [14], quantum and classical worst-case to average-case reductions [5, 6], tolerant quantum testing of stabilizer states [4], quantum learning of structured stabilizer decompositions [3], and beyond.

However, when considering applications of the PFR theorem and similar tools to theoretical computer science as above, it is often necessary or desirable to have an efficient algorithmic statement, where an explicit description of the subspace can be learned efficiently, as opposed to an existential combinatorial statement. Indeed, the naive algorithm that extracts the subspace runs in time $O(2^n)$. Fortunately, for the quasi-polynomial Bogolyubov-Ruzsa theorem, Ben-Sasson, Ron-Zewi, Tulsiani, and Wolf [10] showed an algorithmic version, which extracts a subspace in time $O(n^3\log n)$.

The above motivates a natural question that arose after the resolution of the PFR conjecture [17]. Namely, now that we know that a subset $A$ of constant doubling can be covered by at most a polynomial number of translates of a subspace $H\subset {𝔽}_2^n$ of size $|H|\le |A|$, can we learn the subspace $H$ efficiently?. We refer to this as the “algorithmic PFR question.” Our main contribution answers this question by proving an algorithmic version of the polynomial Freiman-Ruzsa theorem, where the covering subspace can be learned explicitly in $\mathrm{𝗉𝗈𝗅𝗒}(n)$-time. In the following, a query to a set $A\subseteq {𝔽}_2^n$ is an evaluation of the characteristic function ${\mathrm{𝟏}}_A(x)$ for a chosen $x\in {𝔽}_2^n$, and a random sample from $A$ is a uniformly chosen element $a\in A$.

We remark that the probability of success $2/3$ is arbitrarily chosen and can be amplified via standard error-reduction techniques. The algorithm returns the subspace $V$ specified by an explicit basis. As typically viewed in additive combinatorics, the doubling constant $K$ is a constant independent of $n$ (as constant doubling implies structure), and in turn our asymptotic notation suppresses factors of $K$.

A key reason for the power and centrality of the PFR theorem is its applications to deriving strong structural theorems regarding homomorphism testing and structure-vs-randomness decomposition. However, while the PFR theorem is known to be equivalent to the aforementioned structural theorems [18, 19], the equivalences are not trivially algorithmic. Nonetheless, we provide versions of these theorems that admit efficient algorithms.

The first theorem is concerned with local-to-global phenomena. Namely, it shows that if a map $f:{𝔽}_2^m\to {𝔽}_2^n$ satisfies a local affine-linear constraint with a significant probability, then it must be globally close, in fractional distance, to an affine-linear map, which can be efficiently learned. This statement is useful because it connects the PFR theorem to property testing and coding theory.

The second theorem also exhibits local-to-global structure, this time by showing that maps that are locally an approximate homomorphisms admit a structured decomposition, which can be efficiently learned.

We refer the reader to [2] for the proofs of these results, below, we give an overview of the technical details.

In a recent breakthrough, Chen, Gong, Ye, and Zhang provided an efficient quantum procedure to learn the closest stabilizer state to a given quantum state [13]. The connection between this task and additive combinatorics was first noted by Arunachalam and Dutt [4], who used the following definition of the Gowers $U^3$-norm of an arbitrary $n$-qubit quantum state $|\psi ⟩={\sum }_{x\in {𝔽}_2^n}f(x)|x⟩$ (where ${(f(x))}_x$ is an ${\mathrm{\ell }}_2$-unit vector)

where $C^{|\omega |}f=\overline{f}$ if $\omega :={\sum }_{j\in [3]}{\omega }_j$ is odd and $f$ otherwise. This is proportional to the Gowers $U^3$- norm of the function $f$ encoded in the amplitudes of the state $|\psi ⟩$, but normalized so that ${\Vert |\psi ⟩\Vert }_{U^3}\le {\Vert f\Vert }_{{\mathrm{\ell }}_2}=1$.

Arunachalam and Dutt showed that stabilizer states are the extremizers of the Gowers $U^3$-norm over quantum states²²2Although an explicit description of these extremizers appeared in the literature on higher-order Fourier analysis in 2012 [15], the link to quantum theory appears to have only been made only recently. and that a quantum state has non-negligible $U^3$-norm if it correlates with a stabilizer state. Moreover, using the PFR theorem (Theorem 1), they showed the converse was true as well and obtained a polynomial Gowers inverse theorem for quantum states: the $U^3$-norm of a quantum state and its maximal correlation with a stabilizer state are polynomially related (see also [7, 24]). As such, our high-level strategy is to use the stabilizer learning protocol in [13] to obtain a quantum algorithmic version of the polynomial Gowers inverse theorem, which is known to also be equivalent to the PFR theorem due to work of Green and Tao [20] and of Lovett [22]. We then arrive at an algorithmic result, albeit quantum, of a statement that is combinatorially equivalent to PFR.

However, as discussed in the previous section, it is non-trivial to make such combinatorial equivalences algorithmic. In this paper, we algorithmize a proof of equivalence between these two results (inspired by the proofs of Green-Tao and Lovett), thus allowing us to employ the stabilizer learning algorithm [13] to obtain efficient quantum algorithms for the PFR theorem and the structural theorems stated in Section 1.2.

With the strategy above in mind, we proceed to give a high-level outline of the proofs of Theorems 2 and 3, which build on the combinatorial arguments of Green and Tao [20] and Lovett [22]. Our other algorithmic results follow via similar methods from these two theorems and the combinatorial arguments of Green and Ruzsa [19].

Suppose we have sample and query access to a set $A\subseteq {𝔽}_2^n$ such that $|A+A|\le K|A|$ for a doubling constant $K\ge 1$. We shall first need to localize $A$ inside the space ${𝔽}_2^n$, which in applications can be much larger than $A$ itself (indeed, this is the reason why sample access to $A$ is necessary). We do this by first sampling $O(\log |A|)$ uniformly random elements from $A$ and taking their linear span, which we denote by $U\le {𝔽}_2^n$. While $U$ might not contain all of the original set, using the fact that $A$ has bounded doubling we can show that their intersection $A^{\prime }:=A\cap U$ will likely comprise at least half of the points in $A$ (for a careful choice of parameters). This allows us to shift attention from $A$, which can be arbitrarily sparse inside ${𝔽}_2^n$, to the localization $A^{\prime }$, which occupies a positive fraction (at least a $2^{-2K}$-fraction) of the vector space $U$, by the Freiman-Ruzsa theorem. Note that $A^{\prime }$ will also have small doubling constant:

We next wish to obtain a “dense model” of the localized set $A^{\prime }$; that is, a set $S\subseteq {𝔽}_2^m$ that is “additively equivalent” to $A^{\prime }$, as captured by the notion of Freiman isomorphisms, but which has density at least $1/K^C$ (for a universal constant $C>1$) inside its ambient space ${𝔽}_2^m$. In particular, we show that with high probability a uniformly random linear map $\pi :U\to {𝔽}_2^m$, for $m=\log |4A^{\prime }|+10$, will be a Freiman isomorphism (i.e., isomorphism of additive quadruples) from $A^{\prime }$ to $S:=\pi (A^{\prime })$. Informally, this means they have the same additive structure, and hence such a dense model can be efficiently obtained by sampling.

Equipped with the localized dense model, we proceed to learn the covering subspace. Denote by $f:S\to A^{\prime }$ the inverse of $\pi$ when restricted to $S$. By the definition of Freiman isomorphisms, we have that

From this approximate linearity condition of $f$ on $S$, we can show that the function

is approximately quadratic.

In particular, following the approach of Green [19] and Green-Tao [20], we show a slight strengthening of the homomorphism testing formulation of the PFR theorem, which we then proceed to algorithmize, relying on tools such as the quadratic Goldreich-Levin theorem. In more detail, we first prove that there exists a quadratic function $q:{𝔽}_2^{m+n}\to {𝔽}_2$ such that

for some polynomial $P:{ℝ}_{+}\to {ℝ}_{+}$.

Crucially, we can efficiently learn such a high-correlation quadratic function $q$. This is done relying on the stabilizer learning algorithm of Chen et al [13] in the quantum setting, or its dequantization by Briët and Castro-Silva [12] in the classical setting. In order to use those theorems, however, we need to be able to efficiently query the function $g(x,y)$. This requires making queries to the set $S=\pi (A^{\prime })$, and inverting the linear map $\pi$ restricted to $A^{\prime }$. We show how this can be done using a $O(n^3)$ time pre-processing step, and an extra cost of $O(n^2)$ time for each query to $g$. The total time and query complexities of our algorithms follow from this step.

From Eq. (2) and algebraic manipulations, we conclude that the homogeneous bilinear form

correlates well with $g(x,y)$. Since we obtained an explicit description of $q$, we can compute a matrix $M\in {𝔽}_2^{n\times m}$ such that $B(x,y)=y^{T}Mx$. By a simple Fourier analytic argument, we can then conclude there is some $v\in {𝔽}_2^n$ such that

where $P^{\prime }:{ℝ}_{+}\to {ℝ}_{+}$ is another polynomial we obtain in our proof. This implies that the subspace

satisfies

By an application of Ruzsa’s covering lemma, we conclude that $P^{\prime }(K)$ translates of $V$ can cover $A$. By our choice of $m$ and the fact that $A^{\prime }$ has bounded doubling, we deduce that $V$ is covered by $2^m/|A|\le 2^{12}{K}^4$ translates of any of its subspaces having size $|A|$, which concludes the high-level overview of the proof.