# Learning low-degree quantum objects

Srinivasan
Arunachalam IBM Quantum<EMAIL_ADDRESS>Arkopal
Dutt IBM Quantum<EMAIL_ADDRESS>Francisco
Escudero Gutiérrez Qusoft and CWI<EMAIL_ADDRESS>Carlos
Palazuelos UCM and ICMAT<EMAIL_ADDRESS>
###### Abstract

We consider the problem of learning low-degree quantum objects up to
$\varepsilon$-error in $\ell_{2}$-distance. We show the following results:
$(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and
unitaries can be learned using $O(1/\varepsilon^{d})$ queries (independent of
$n$), $(ii)$ polynomials $p:\\{-1,1\\}^{n}\rightarrow[-1,1]$ arising from
$d$-query quantum algorithms can be classically learned from
$O((1/\varepsilon)^{d}\cdot\log n)$ many random examples $(x,p(x))$ (which
implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$
polynomials $p:\\{-1,1\\}^{n}\to[-1,1]$ can be learned through
$O(1/\varepsilon^{d})$ queries to a quantum unitary $U_{p}$ that block-encodes
$p$. Our main technical contributions are new Bohnenblust-Hille inequalities
for quantum channels and completely bounded polynomials.

##  1 Introduction

Computational learning theory refers to the mathematical framework for
understanding machine learning models and quantifying their complexity. The
seminal result of Leslie Valiant [Val84] (who introduced the Probably
Approximately Correct (PAC) model) gives a complexity-theoretic definition of
what it means for a class of functions $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
to be learnable information-theoretically and computationally.

One of the foundational results in computational learning theory is the one of
Linial, Mansour and Nisan [LMN93] who showed that $\textsf{AC}_{0}$, or
constant-depth $n$-bit classical circuits consisting of AND, OR and NOT gates,
can be learned in quasi-polynomial time. A crucial aspect of their proof is
the following structural theorem: if a Boolean function $f$ is computable by
$\textsf{AC}_{0}$, then $f$ can be approximated by a _low-degree polynomial_.
Using this structural property, the learning algorithm approximates the
coefficients of all the low-degree monomials of $f$ in the PAC model and hence
approximately learns the unknown $\textsf{AC}_{0}$ function. Since their work,
the notion of Boolean functions being low-degree themselves or being
approximated by low-degree polynomials has been a central technique [BT21] to
obtain new learning algorithms. Furthermore, low-degree approximations have
played a significant role in theoretical computer science topics such as
quantum computing, circuit complexity, learning theory and cryptography.

In the last few years, there have been several works in quantum learning
theory where the goal has been to learn an unknown object on a quantum
computer given various access models to the unknown object. There have been
works that considered learning unknown states, channels, unitaries,
Hamiltonians either with our without structure present in them. Motivated by
classical learning theory, in this work our primary focus will be on learning
objects that have the additional structure of being _low-degree_. Since we
consider different objects, when presenting our results we will make clear,
the definition of being low-degree, but the main motivation of this work can
be summarized by the following question:

> _Can we learn low-degree $n$-qubit quantum objects information-theoretically
> with complexity that scales only polynomial (or better polylogarithmic) in
> $n$?_

We give a positive answer to this question for channels, unitaries, quantum
query algorithms, polynomials accessed through a block-encoding unitary and
states. Below we describe our main technical contribution and results.

###  1.1 Technical contribution: New Bohnenblust-Hille inequalities

In 1931, Bohnenblust and Hille [BH31] (generalizing the classic theorem of
Littlewood [Lit30]) gave a solution to the famous _Bohr strip problem_ of
Dirichlet series [Boh13]. To do that, they showed the following: let
$T:([-1,1]^{n})^{d}\rightarrow[-1,1]$ be a $d$-tensor specifed by the
coefficients $T=(\widehat{T}_{i_{1},\ldots,i_{d}})_{i_{1},\ldots,i_{d}\in[n]}$
(meaning that
$T(x_{1},\dots,x_{d})=\sum_{i_{1},\dots,i_{d}\in[n]}\widehat{T}_{i_{1},\ldots,i_{d}}x_{1}(i_{1})\dots
x_{d}(i_{d})$), then

$\Big{(}\sum_{i_{1},\ldots,i_{d}=1}^{n}|\widehat{T}_{i_{1},\ldots,i_{d}}|^{2d/(d+1)}\Big{)}^{(d+1)/2d}\leq
C(d),$ (1)

where $C(d)$ is a universal constant independent of $n$.111We remark that the
inequality above is a simplified version of the original Bohnenblust-Hille
inequality and we discuss this in more detail in the preliminaries. Their work
marked the birth of the Bohnenblust-Hille (BH) inequality, which became a
fundamental tool in functional analysis. Despite being studied for over a
century, the best known upper bound on $C(d)$ scales polynomially with $d$
[BPSS14], while the best lower bound is a constant [DMFPSS14]. Closing this
gap has been an active area of research in mathematics. It was not until 2011
that Defant et al. [DFOC+11] refined the BH inequality and found a striking
application of the BH inequality: they determined the precise asymptotic
behavior of the $n$-dimensional Bohr radius using the BH inequality. Since
then, there has been renewed interest in the BH inequality and has found
several applications in theoretical computer science such as Fourier-Entropy
influence conjecture [ACK+21], classical learning theory [EI22], non-local
games [Mon12], and quantum computing [HCP23, VZ23].

Of particular interest to our work, the BH inequality recently got the
attention of the computer science community when Eskenazis and Ivanisvili
[EI22] used a version of it to prove a major improvement on the problem of
classical learning bounded low-degree multilinear polynomials (which we
discuss in detail below). The key insight of Eskenazis and Ivanisvili was the
following: BH inequalities imply that given a bounded low-degree polynomial,
most of its coefficients are quite small, so one does not have to learn them.
Since then, multiple extensions of the BH have been proved and applied to
learning quantum objects [HCP23, SVZ23a, SVZ23b, VZ23, KSVZ24]. In this work
we extend the BH inequality in two ways:

  1. 1.

We consider a variant of the BH inequality, that can be regarded as a hybrid
between the BH inequality and the celebrated Grothendieck inequality [Gro53].
We show that degree-$d$ completely bounded tensors $\widehat{T}$ (which are
known to be the output of $d$-query quantum algorithms [ABP19]) satisfy

$\Big{(}\sum_{i_{1},\ldots,i_{d}=1}^{n}|\widehat{T}_{i_{1},\ldots,i_{d}}|^{2d/d+1}\Big{)}^{(d+1)/2d}\leq
1.$

In other words, we improve the BH constant for completely bounded tensors from
$\mbox{\rm poly}(d)$ to $1$. See Theorem 19 for a precise statement.

  2. 2.

More recently, the works of [HCP23, VZ23] have considered non-commutative
variants of the BH inequality. They showed that the Pauli coefficients of
$n$-qubit degree-$d$ (i.e., $d$-local) operators that are bounded in operator
norm can be bounded similar to Eq. (1), but with $\exp(d)$ instead of
$\mbox{\rm poly}(d)$.222We remark that Volberg, Zhang [VZ23] obtained a
constant of $\exp(d)$, while Huang et al. [HCP23] obtained $d^{O(d)}$. Here,
we prove another non-commutative version of the BH inequality for quantum
channels (we in fact prove a stronger BH inequality for superoperators that
are bounded in $S_{1}\to S_{\infty}$ norm, and refer the reader to Theorem 12
for more details). In particular, if $\Phi$ is a quantum channel defined as
$\Phi(\rho):=\sum_{x,y}\widehat{\Phi}(x,y)\sigma_{x}\rho\sigma_{y}$ (where
$\sigma_{x}$ is a Pauli operator and $\widehat{\Phi}(x,y)=0$ if $|x|+|y|>d$),
then the Pauli coefficients $\widehat{\Phi}(x,y)$ satisfy

$\Big{(}\sum_{x,y}|\widehat{\Phi}(x,y)|^{2d/(d+1)}\Big{)}^{(d+1)/2d}\leq\exp(d).$
(2)

Here $\exp(d)$ might seem too big compared to the $\mbox{\rm poly}(d)$ of Eq.
1, but Eq. 1 and Eq. 2 are incomparable: Eq. 1 corresponds to tensors, which
are a very structured class of polynomials, while Eq. 2 is a non-commutative
analogue of the BH inequality for general polynomials, for which the best
upper bounds [DMP19] are superpolynomial in $d$.

Our BH inequality for channels is a generalization from operators to
superoperators of the mentioned non-commutative BH inequalities [HCP23, VZ23],
as explained in Remark 13.

These BH inequalities might be of independent interest both for mathematicians
and quantum computing; in this work we crucially use them to analyze our
quantum learning algorithms.

###  1.2 Result 1: Learning channels

Learning a quantum process is a fundamental task in quantum computing and this
can be modelled as learning an unknown _quantum channel_ , also referred to as
_quantum process tomography_. On an experimental level, the dynamics of closed
quantum systems can be modeled as a unitary transformation from the initial
state to the final state. However, in practice, quantum systems interact with
the environment and are generally treated as an open quantum system. To learn
the behavior of these open quantum systems, it is convenient to model this map
as a quantum channel [NC10]. Learning an $n$-qubit quantum channel is however
challenging and is known to require $\Theta(4^{n})$ queries to the channel
[GJ14]. This exponential sample complexity can be drastically improved when
prior information on the structure of the channel is available. For example, a
recent work of Bao and Yao [BY23] considered $k$-junta quantum channels, i.e.,
$n$-qubit channels that act non-trivially only on at most $k$ of the $n$
(unknown) qubits leaving the rest of the qubits unchanged. These channels were
shown to be learnable using $\widetilde{\Theta}(4^{k})$ queries to the channel
[BY23]. In [CL18], it was shown that quantum channels that can be efficiently
generated, can be learned efficiently, albeit in the weaker PAC learning
model. In this work, we consider learning $n$-qubit quantum channels which
have a Pauli decomposition only involving low-degree Pauli operators.

#### Low-degree quantum channels.

To describe our result, we first describe the Pauli analysis for quantum
channels. An $n$-to-$n$ qubit quantum channel $\Phi$ can be expressed as

$\Phi(\rho)=\sum_{x,y\in\\{0,1,2,3\\}^{n}}\widehat{\Phi}(x,y)\cdot\sigma_{x}\rho\sigma_{y},$
(3)

where $\sigma_{x}=\mathop{\otimes}_{i\in[n]}\sigma_{x_{i}}$ and $\sigma_{i}$
for $i\in\\{0,1,2,3\\}$ are the Pauli matrices

$\sigma_{0}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\
\sigma_{1}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\
\sigma_{2}=\begin{pmatrix}0&-i\\\ i&0\end{pmatrix},\
\sigma_{3}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix};$

and $\widehat{\Phi}(x,y)$ are the Pauli coefficients of the channel. Given
$x\in\\{0,1,2,3\\}^{n}$, $|x|$ is the number of non-zero entries of $x$. The
degree of a channel $\Phi$ is the minimum integer $d$ such that
$\widehat{\Phi}(x,y)=0$ if $|x|+|y|>d$. Our first result is an efficient
learning algorithm for low-degree channels. The learning model we consider is
the same as the recent work of Bao and Yao [BY23]. Given a channel $\Phi$, a
learning algorithm is allowed to make _queries to $\Phi$_ as follows: it can
choose a state $\rho$, feed $\rho$ to the channel to obtain $\Phi(\rho)$ and
measure $\Phi(\rho)$ in any basis. From the measurement outcomes, the learner
should output a classical description of a superoperator $\widetilde{\Phi}$
that is close to $\Phi$ in the $\ell_{2}$-distance defined by the usual inner
product for superoperators, i.e.,
$\langle\Phi,\widetilde{\Phi}\rangle=\operatorname{Tr}[J(\Phi)J(\widetilde{\Phi})]/4^{n}$,
where $J(\Phi)$ is the Choi-Jamiolkowski (CJ) representation of $\Phi$.333
Throughout this paper we say an algorithm $(\varepsilon,\delta)$-learns a
quantum object if it succeeds with probability $\geq 1-\delta$ and outputs an
$\varepsilon$-approximation to the unknown quantum object in a metric that
will be clear when used.

######  Theorem 1.

Let $\Phi$ be a $n$-qubit degree-$d$ quantum channel. There is an algorithm
that $(\varepsilon,\delta)$-learns $\Phi$ (in $\ell_{2}$-distance) using
$\exp\big{(}\widetilde{O}(d^{2}+d\log(1/\varepsilon))\big{)}\cdot\log(1/\delta)$
queries to $\Phi$.

We remark that the sample complexity of learning general quantum channels
requires $\Omega(4^{n})$ queries, but if we are promised the channel is _low-
degree_ , then our algorithm is much faster than the general algorithm.
Additionally observe that the sample complexity of our learning algorithm is
independent of $n$, in contrast to the results [HCP23, VZ23, SVZ23a, SVZ23b,
KSVZ24] on quantum learning of low-degree observables, which also are based on
the BH inequality and have a logarithmic dependence on $n$.

To sketch the proof the theorem, we first note the well-known fact that the
matrix $\widehat{\Phi}$ (whose entries are given by
$\widehat{\Phi}_{x,y}=\widehat{\Phi}(x,y)$) is a density matrix of a state
that is unitarily equivalent to the CJ state of the channel $\Phi$ [BY23,
Lemma 8]. Hence, $\widehat{\Phi}$ can be prepared by querying $\Phi$ just
once, and $\\{\widehat{\Phi}(x,x)\\}_{x}$ is a probability distribution. The
high-level idea behind the learning algorithm is the following.

  1. 1.

Prepare $T$ copies of $\widehat{\Phi}$ and measure them in the computational
basis, allowing the learner to sample from the distribution
$\\{\widehat{\Phi}(x,x)\\}_{x}$.

  2. 2.

Using a well-known result in distribution learning theory, we observe that
$O(1/\alpha^{2})$ many samples from $\\{\widehat{\Phi}(x,x)\\}_{x}$ suffices
to obtain the $x$’s such that $\Phi(x,x)$ is $\alpha$-large.

  3. 3.

Approximate all the “large” Pauli coefficients in the step above using a SWAP
test for mixed states that allows to estimate the Pauli coefficients
$\widehat{\Phi}(x,y)$.

  4. 4.

Output a $\widetilde{\Phi}$ with coefficients that were estimated above and
the remaining coefficients set to $0$.

At this point, we use the BH inequality for quantum channels and show that, as
long as $T\sim\exp(d^{2}/\varepsilon^{d})$, then the output $\widetilde{\Phi}$
is $\varepsilon$-close to the target $\Phi$ in $\ell_{2}$-distance.

#### Remark on learning Pauli channels.

One can also consider a special case of quantum channels called _Pauli
channels_ $\Phi$, motivated by the fact that Pauli channels are often the
dominant noise on quantum devices and a practical noise model for analyzing
fault-tolerance [Ter15]. For these channels, the only non-zero terms in the
Fourier expansion of Eq. (3) are $\widehat{\Phi}(x,x)$ (i.e.,
$\widehat{\Phi}(x,y)=0$ when $x\neq y$) and these coefficients are often
called _error rates_. Since learning Pauli channels is an important task on
near-term quantum devices for error mitigation [VDBMKT23] and analyzing error
correction, it is desirable to avoid using entangled copies of a state and
access to ancillary qubits as part of the learning algorithm. With this
requirement, it was shown that, in order to $\varepsilon$-learn (in diamond
norm) an unknown $n$-qubit Pauli channels using unentangled measurements, one
needs to use the channel $\Omega(4^{n}/\varepsilon^{2})$ many times [FOF23].
In this work, we show that the subclass of low-degree Pauli channels are
efficiently learnable. The degree of a Pauli channel $\Phi$ is the minimum
integer $d$ such that the error rates $\widehat{\Phi}(x,x)=0$ if $|x|>d$.

Noise on current large-scale quantum devices is modeled as Pauli channels
containing a sparse set of local Paulis [VDBMKT23], which is a subclass of
low-degree Pauli channels. Such models are available from device physics and
experiments used to characterize noise on quantum hardware. When non-local
interactions but only over few qubits are included in the Pauli channel
[TST23], the corresponding Paulis are still low-degree which fits into the
class of Pauli channels considered. Our learning result is as follows.

######  Proposition 2.

Let $\Phi$ be an $n$-qubit degree-$d$ Pauli channel. There is an algorithm
that $(\varepsilon,\delta)$-learns $\Phi$ (under the diamond norm) using
$O\left(n^{2d}/{\varepsilon^{2}}\cdot\log(n/{\delta})\right)$ queries to
$\Phi$. Moreover, the learning algorithm only requires preparation of product
states and measurements in the Pauli basis.

We remark that the dependence on $n$ in our sample complexity matches the
algorithm in [FO21] for learning low-degree Pauli channels under the diamond
norm but our analysis differs from theirs; our result is obtained using a
Fourier-analytic approach in contrast to the the result of [FO21] which uses
ideas from population recovery.

###  1.3 Result 2: Learning unitaries

Apart from learning channels, in this paper we also consider the task of
learning unknown $n$-qubit unitaries. Similar to the case for channels, it is
well-known that learning an unstructured $n$-qubit unitary requires
$\widetilde{\Theta}(4^{n})$ applications of $U$ [GJ14]. This complexity can be
significantly improved if structural information is available. For example, it
has been shown that efficient learning is possible if the unitary corresponds
to Clifford circuits [Low09], corresponds to Clifford circuits with few non-
Clifford gates [LC22], or are the diagonal unitaries of the Clifford hierarchy
[ABDY23].

In a recent work, Chen et al. [CNY23] considered the task of learning
unitaries $U$ that are $k$-juntas and showed that this class can be learned by
querying the unitary $\widetilde{\Theta}(4^{k})$ many times. In this work, we
consider the scenario where the unitary is degree-$d$ and show such an
exponential saving (in comparison to naive tomography) is possible. This
structured class of low-degree unitaries occur in many instances. For example,
in nature, the dynamics of many physical systems are governed by local
Hamiltonians, whose unitary time evolution operators for short time evolution
are close to being low-degree unitaries. Moreover, through the application of
Lieb-Robinson bounds to structured many-body Hamiltonians, the corresponding
unitary evolution operator can be seen to only have support only on low-degree
Paulis [CLY23]. The learning algorithm that we will present is thus applicable
for learning and verifying such unitaries.

Consider the Pauli decomposition of an $n$-qubit unitary as follows:

$U=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{U}(x)\sigma_{x},$

where $\widehat{U}(x)$ are its Pauli coefficients. The degree of $U$ is the
minimum integer $d$ such that $|x|>d$ implies $\widehat{U}(x)=0$. Our learning
model is similar to the one by Chen et al. [CNY23]. Given an unitary $U$, a
learning algorithm is allowed to make _queries to $U$_ (and to control-$U$) as
follows: it can choose a state $\rho$, apply $U$ to the state to obtain $U\rho
U^{*}$, and measure $U\rho U^{*}$ in a chosen basis. From the measurement
outcomes, the learner should output a classical description of an operator
$\widetilde{U}$ that is close to $U$ in the $\ell_{2}$-distance determined by
the usual inner product for operators defined as $\langle
U,V\rangle=\operatorname{Tr}[U^{*}V]/2^{n}$.

######  Theorem 3.

Let $U$ be an $n$-qubit degree-$d$ unitary. There is an algorithm that
$(\varepsilon,\delta)$-learns $U$ (in $\ell_{2}$-distance) using the unitary
$U$
$\exp\big{(}\widetilde{O}(d^{2}+d\log(1/\varepsilon))\big{)}\cdot\log(1/\delta)$
many times.

The proof of Theorem 3 follows the same structure as the one of Theorem 1, but
now we learn the Pauli coefficients via the algorithm of Montanaro and Osborne
[MO08], and the correctness of the algorithm relies on the non-commutative BH
inequality of Volberg and Zhang [VZ23].

The BH inequality of Volberg and Zhang [VZ23] works for matrices with bounded
operator norm, of which unitaries are a very special case. As argued by
Montanaro and Osborne [MO08], matrices bounded on the operator norm are the
quantum analogue of bounded functions $f:\\{-1,1\\}^{n}\to[-1,1]$, while
unitaries are the analogue of Boolean functions444To be precise, they argue
that unitary hermitian matrices are the analogue of Boolean functions.
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$. These two families of classical functions
differ a lot with respect to the BH inequalities: the best upper bound [DMP19]
for the BH constant for bounded functions is $\exp({d^{1/2}})$, while for
Boolean functions of degree $d$ one can even prove that the _usually much
bigger_ quantity $\sum_{s}|\widehat{f}(s)|$ is at most $2^{d-1}$ [O’D14,
Exercise 1.11]. An open question is if this claim can be generalized to the
quantum setting.

######  Question 4.

Is there a constant $C(d)$ such that
$\sum_{x\in\\{0,1,2,3\\}^{n}}|\widehat{U}(x)|\leq C(d)$ for every $n$-qubit
degree-$d$ unitary $U$?

If 4 was answered positively, then one could improve the $\varepsilon$
dependence of Theorem 3 to $(1/\varepsilon)^{2}$. Some evidence in favor of an
affirmative answer to 4 is that if Montanaro and Osborne’s Conjecture was true
[MO08, Conjecture 4], then every degree-$d$ unitary would be a $2^{d}$-junta,
which would imply an affirmative answer with $C(d)=2^{2^{d}}$.

#### Remark on learning low-degree quantum states.

Learning quantum states has been an active line of research given its
fundamental importance and applications to quantum system characterization,
assessing quality of quantum gates, verification of quantum circuits and
validating performance of quantum algorithms. Breakthrough results of Haah et
al. [HHJ+17] and O’Donnell and Wright [OW16] showed that the sample complexity
of learning an unknown $n$-qubit state, up to trace distance $\varepsilon$ is
$\Theta(4^{n}/\varepsilon^{2})$. A natural consideration is the task of
learning _low-degree_ quantum states. In order to describe this, we first
write down the Pauli expansion of an $n$-qubit state $\rho$ as

$\rho=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{\rho}(x)\sigma_{x}.$ (4)

Then, we say that $\rho$ has degree at most $d$ if $\widehat{\rho}(x)=0$ for
all $|x|>d$. It is not too hard to see that one can use the formalism of
classical shadows [HKP20] to obtain a learning algorithm (in trace norm) that
has a sample complexity of
$\widetilde{O}(n^{d}/\varepsilon^{2}\cdot\log(n/\delta))$. A similar result
(with a different norm and with a bit more structure than just being low-
degree) was noted in a recent work of Nadimpalli et al. [NPVY23], where they
used it to give efficient algorithms to learn QAC0 circuits.

###  1.4 Result 3: Learning quantum query algorithms

Eskenazis and Ivanisvili [EI22] established a surprising connection between
the BH inequality and learning theory. They considered the following question:
suppose $f:\\{-1,1\\}^{n}\rightarrow[-1,1]$ is a bounded degree-$d$ function,
and a learner is given uniformly random $x$ and $f(x)$, then how many
$(x,f(x))$ suffices to learn $f$ up to error $\varepsilon$ in $\ell_{2}^{2}$
error? The seminal low-degree algorithm by Linial, Mansour and Nisan uses
$O_{d,\varepsilon}(n^{d})$ samples [LMN93].555Here and below, we use
$O_{d,\varepsilon}$ to hide factors that depend on $d,1/\varepsilon$ and
independent of $n$. This was not improved until recently, when Iyer et al.
[IRR+21] reduced this complexity to $O_{d,\varepsilon}(n^{d-1})$. In a
surprising work, [EI22] showed that one can learn $f$ in sample complexity
$O_{d,\varepsilon}(\log n)$. For the particular case of bounded $d$-linear
tensors $T:(\\{-1,1\\}^{n})^{d}\to[-1,1]$ they showed that it suffices to use

$(1/\varepsilon)^{d}\cdot\Big{(}\sum_{i_{1},\ldots,i_{d}=1}^{n}|\widehat{T}_{i_{1},\ldots,i_{d}}|^{2d/d+1}\Big{)}^{(d+1)/2d}\cdot\log
n$ (5)

samples $(x,T(x))$, where $x$ is uniform from $(\\{-1,1\\}^{n})^{d}$ and
$\widehat{T}$ is the tensor of coefficients of $T$, i.e.,
$T(x)=\sum_{i_{1},\dots,i_{d}}\widehat{T}_{i_{1},\dots,i_{d}}x_{1}(i_{1})\dots
x_{d}(i_{d})$. Combining that with the upper bound of the BH constant for
multilinear tensors [BPSS14], it yields

$(d/\varepsilon)^{O(d)}\cdot O(\log n)$ (6)

uniformly random samples are enough to learn $T$. Although this result is
surprising since the complexity only scales polylogarithmic with $n$, observe
that if $d=\omega(\log n)$, then the sample complexity is superpolynomial in
$n$. This motivates the following question: are there classes of polynomials
that can be learned using $\mbox{\rm poly}(n)$ samples for any $d=\omega(\log
n)$? Below we answer this question positively for the class of polynomials
that arise from quantum query algorithms.

#### Quantum polynomials.

The result of Eq. 6 can be applied to learn the amplitudes of quantum
algorithms that query different blocks of variables every time (see Fig. 1),
as they are multilinear tensors bounded on the supremum norm [BBC+01]. To be
precise, we consider quantum query algorithms such that they prepare a state

$\ket{\psi_{x}}=U_{d}(O_{x_{d}}\otimes\mathop{\rm
Id}\nolimits_{m})U_{d-1}\dots U_{1}(O_{x_{1}}\otimes\mathbb{\mathop{\rm
Id}\nolimits}_{m})U_{0}\ket u,$

where $m$ is an integer, $x$ stands for $(x_{1},\dots,x_{d})$, $O_{y}$ is the
$n$-dimensional unitary that maps $\ket i$ to $y_{i}\ket i$,
$U_{0},\dots,U_{d}$ are $(n+m)$-dimensional unitaries and $\ket u$ is a
$n+m$-dimensional unit vector. The algorithm succeeds according to a
projective measurement that measures the projection of the final state onto
some fixed $n+m$ dimensional unit vector $\ket v$. Hence, the amplitude of
$\ket v$ is $T(x)=\langle v|\Psi_{x}\rangle$, so $|T(x)|^{2}$ is the
acceptance probability of the algorithm.

@C=1em @R=.7em & 1U_0 O_x_1 1U_1 O_x_d 1U_d
U_0 U_1 … U_d

Figure 1: Quantum query algorithms considered in Theorem 5.

These quantum algorithms have been considered in the quantum computing
literature. For example, $k$-forrelation, that witnesses the biggest possible
quantum-classical separation, has this structure [AA15, BS21]. Also, for these
algorithms the Aaronson and Ambainis conjecture is known to be true, so they
can be classically and efficiently simulated almost everywhere [BSdW22,
Esc23].

In addition, it was shown [ABP19] that those amplitudes are not only bounded,
but also completely bounded. Our main contribution regarding these algorithms
is showing that for $d$-linear tensors $T$ that are _completely bounded_ , we
can improve the BH inequality to

$\Big{(}\sum_{i_{1},\ldots,i_{d}=1}^{n}|\widehat{T}_{i_{1},\ldots,i_{d}}|^{2d/d+1}\Big{)}^{(d+1)/2d}\leq
1.$

Using this upper bound, we show the following.

######  Theorem 5.

For a quantum algorithm that makes $d$-queries as in Fig. 1, there is a
classical algorithm that $(\varepsilon,\delta)$-learns its amplitudes (in
$\ell_{2}^{2}$-distance) using $O\left((1/\varepsilon)^{d}\cdot\log n\right)$
uniform samples.

This exponentially improves the complexity of [EI22], as stated in Eq. (6) for
the natural class of polynomials arising from quantum query algorithms. In
particular, for $d=\omega(\log n)$ and constant $\varepsilon$, one can learn
this class of polynomials with sample complexity that is polynomial in $n$.

###  1.5 Result 4: Quantum learning of classical polynomials

#### Boolean functions.

Quantum learning not only concerns quantum objects, but also classical ones.
For instance, Boolean functions $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ can be
accessed using a _quantum uniform example_ , given by

$\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{-1,1\\}^{n}}\ket{x,f(x)}.$ (7)

This data access model has been vastly studied in the literature, where
several notable quantum speedups have been proven [BJ95, AS07, ACL+21]. Many
of these speedups are analyzed trough the Fourier transform, that allows to
identify every function $f:\\{-1,1\\}^{n}\to\mathbb{R}$ with a multilinear
polynomial $f=\sum_{s\in\\{0,1\\}^{n}}\widehat{f}(s)\chi_{s}$, where
$\widehat{f}(s)\in\mathbb{R}$ are the Fourier coefficients and $\chi_{s}$ are
the character functions $\chi_{s}(x)=\prod_{i\in[n]}x_{i}^{s_{i}}$. The degree
for these functions is the minimum integer $d$ such that if $|s|>d$ then
$\widehat{f}(s)=0$. It is a well-known fact that Boolean functions
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ of degree $d$ are $2^{1-d}$-granular, meaning
that their Fourier coefficients lie in $2^{1-d}\mathbb{Z}$. This has immediate
consequences for both learning theory and BH inequalities.

######  Fact 6.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be a degree-$d$ function. There is a
quantum algorithm that learns $f$ exactly with probability 1$-\delta$ using
$O\left(4^{d}d\log\left(1/\delta\right)\right)$ quantum uniform examples. In
contrast, any classical algorithm requires $\Omega(2^{d}+\log n)$ uniform
examples and there is a classical algorithm that only uses
$O\left(4^{d}d\log\left(n/\delta\right)\right)$ uniform examples.

Despite the simplicity of the proof of 6, we state it for completeness and
because it seems not to be well-known (see for instance [NPVY23, Corollary
34], which proposes a quantum algorithm for the same problem that requires
$O(n^{d})$ samples, or [EIS22, Corollary 4] that proposes a classical algorthm
that requires $O(2^{d^{2}}\log n)$ samples). We also remark that the classical
lower bound was recently improved from $\Omega(2^{d}+\log n)$ (which is
folklore, and it is a lower bound for learning Boolean $d$-juntas) to
$\Omega(2^{d}\log n)$ [EIS22]. Here, we observe a BH-type inequality for
Boolean functions.

######  Fact 7.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ of degree at most $d$. Then,

$\Big{(}\sum_{s\in\\{0,1\\}^{n}}|\widehat{f}(s)|^{\frac{2d}{d+1}}\Big{)}^{\frac{d+1}{2d}}\leq
2^{\frac{d-1}{d}}.$

The equality is witnessed by the address function.

7 might be of interest in functional analysis for two reasons: $(i)$ it is
conjectured that the value of the BH constant for $d$-linear tensors is
$2^{\frac{d-1}{d}}$ [PT18] (tensors correspond to multilinear forms in the
functional analysis language), so this fact proves the conjecture for
particular case of $d$-linear Boolean tensors, $(ii)$ the address function666
For $d\in\mathbb{N}$, the address function
$f:(\\{-1,1\\}^{2})^{d-1}\times\\{-1,1\\}^{2^{d-1}}\to\\{-1,1\\}$ is defined
as $f(x,y)=\sum_{a\in\\{-1,1\\}^{d-1}}g_{a}(x)y(a),$ where we identify
$\\{-1,1\\}^{d-1}$ with $[2^{d-1}]$ and $g_{a}(x)$ is $0$ unless
$x_{i}(1)=-a_{i}x_{i}(2)$ for every $i\in[n]$, in which case it takes the
value $\prod_{i\in[n]}x_{i}(1)$ ., that saturates the inequality, is a
$d$-linear form that gives a lower bound for the BH constant for multilinear
tensors of $2^{\frac{d}{d-1}},$ which matches the best lower bound known so
far [DMFPSS14].

#### Boolean polynomials.

For bounded functions $f:\\{-1,1\\}^{n}\to[-1,1]$ the definition of quantum
uniform examples defined as in Eq. 7 is unclear. Given that bounded
polynomials have received attention in a few works [LMN93, IRR+21, EI22], we
propose a way learning them quantumly by accessing these polynomials through a
block encoding [CGJ19], i.e., a learning algorithm has access to a block
encoding of the $2^{n}$-dimensional diagonal matrix whose diagonal entries all
equal $f$. To this end, we prove the following theorem.

######  Proposition 8.

Let $f:\\{-1,1\\}^{n}\to[-1,1]$ be a degree-$d$ polynomial. There is an
algorithm that $(\varepsilon,\delta)$-learns $f$ (in $\ell_{2}$-distance)
using $\exp(\widetilde{O}(\sqrt{d^{3}}+d\log(1/\varepsilon))\log(1/\delta))$
copies of a block-encoding of $f$.

The proof of Proposition 8 is a combination of the ideas in [EI22] with the
Fourier sampling and block-encoding quantum primitives. We remind the reader
that the merit of Eskenazis and Ivanisvili was to bring down the classical
complexity of the problem from $O_{d,\varepsilon}(n^{d})$ to
$O_{d,\varepsilon}(\log n)$. Proposition 8 shows that the quantum complexity
could be even reduced to $O_{d,\varepsilon}(1)$. Proposition 8 also implies a
quantum speedup (with respect to $n$), as the lower bound of
$\Omega(2^{d}+\log n)$ also holds for membership queries777Making a membership
query to $f$ consists on accessing one pair $(x,f(x))$ where $x$ is chosen by
the learner, not necessarily uniformly at random. If $f$ is a Boolean function
and $U_{f}$ is the unitary defined by $U_{f}\ket{x}=f(x)\ket{x}$, then a
membership query $(x,f(x))$ can be simulated by applying $(H\otimes\mathop{\rm
Id}\nolimits_{n})CU_{f}(H\otimes\mathop{\rm Id}\nolimits_{n})$ to
$\ket{0}\ket{x}$ and measuring the first qubit in the computational basis.
Note that $U_{f}$ can be regarded as a block-encoding of $f$., which are the
classical analogue of accessing a unitary block-encoding of $f$. Additionally,
we highlight that although our results are about sample complexity, the time
complexity of our quantum algorithm of Proposition 8 scales as $\mbox{\rm
poly}(n,\exp(d^{1.5}))$, while the current state-of-the-art classical
algorithm [EI22] approximates the ${n\choose d}$ Fourier coefficients, so it
requires $\mbox{\rm poly}(n^{d})$ time. In particular, for $d=(\log n)^{2/3}$,
constant $\varepsilon,\delta$, our quantum algorithm has a time complexity of
$\mbox{\rm poly}(n)$ time, while the state-of-the-art classical algorithm runs
in time $n^{\mathrm{polylog}n}$.

#### Future directions.

In this work we have considered the normalized $\ell_{2}$-norm as a measure of
accuracy of the learning algorithms. This norm is standard in learning theory
if $f$ and $g$ are Boolean functions, since $\mathrm{P}_{x}[g(x)\neq
h(x)]\leq\left\|{f-g}\right\|_{2}^{2},$ so learning under the
$\ell_{2}$-distance implies PAC learning under the uniform distribution. In
the quantum case, the normalized $\ell_{2}$-norm can be interpreted as
average-case distances and the $\ell_{1}$-norm represent worst-case distances
and usually has a better operational interpretation. Thus, in the quantum
realm it would desirable to obtain $n$-independent learning results with
respect to $\ell_{1}$-distances. Our work leaves this as an open question.

#### Acknowledgements.

We thank the referees of ICALP’24 and TQC’24 for useful comments. We thank Jop
Briët and Antonio Pérez Hernández for useful discussions. We thank Alexandros
Eskenazis, Paata Ivanisvili, Alexander Volberg and Haonan Zhang for useful
comments. A.D. and S.A. thank the Institute for Pure and Applied Mathematics
(IPAM) for its hospitality throughout the long program “Mathematical and
Computational Challenges in Quantum Computing” in Fall 2023 during which part
of this work was initiated. This research was supported by the European
Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreement no. 945045, and by the NWO Gravitation
project NETWORKS under grant no. 024.002.003. C.P. is partially supported by
the MICINN project PID2020-113523GB-I00, by QUITEMAD+-CM, P2018/TCS4342,
funded by Comunidad de Madrid and by Grant CEX2019-000904-S funded by
MCINN/AEI/ 10.13039/501100011033.

##  2 Preliminaries

Throughout this work we will consider different constants, all of which will
be denoted by $C$ and their value will be clear from context. We will use
$C(d)$ to refer to quantities that only depend $d$ and are constant with
respect to other parameters. Given a natural number $m$, $[m]$ represents the
set $\\{1,2,\dots,m\\}$ and $[m]_{0}$ represents $\\{0\\}\cup[m].$

We will work with $n$-qubit systems throughout this work and denote the
dimension of the underlying Hilbert space as $N=2^{n}$. We denote the
$n$-qubit Pauli group as $\mathcal{P}_{n}$ which is the set of $n$-fold tensor
product of single qubit Pauli operators $\\{\pm 1,\pm
i\\}\times\\{I,X,Y,Z\\}^{\mathop{\otimes}n}$. We will denote Pauli operators
(up to a phase) by $\sigma_{x}=\otimes_{i\in[n]}\sigma_{x_{i}}$, where
$x\in\\{0,1,2,3\\}^{n}$ and the single qubit Pauli operators are defined by
$\sigma_{0}=I$, $\sigma_{1}=X$, $\sigma_{2}=Y$, and $\sigma_{3}=Z$. For
example, the $4$-qubit Pauli operator $XYZI$ is equivalently denoted by
$\sigma_{s}$ with $s=(1,2,3,0)$. This convention to parameterize the Pauli
operators in $\mathcal{P}_{n}$ (up to a phase) by strings in
$\\{0,1,2,3\\}^{n}$ will be useful in defining the Pauli expansion of quantum
states and unitaries later. For any $n$-qubit Pauli operator $\sigma_{x}$, we
call the size of the support of the Pauli over non-identity single qubit
Paulis as its degree, denoted by $|x|$. A particular set of states that we
will use throughout this work are the eigenstates of the Pauli operators. We
denote the $\pm 1$ eigenstates of the single-qubit Pauli operators
$\sigma_{b}$ as $\ket{\chi_{\pm 1}^{b}}$, where $b\in\\{1,2,3\\}$. Product
states over eigenstates can then be denoted by
$\rho_{s,a}=\mathop{\otimes}_{j=1}^{n}\ket{\chi_{a_{j}}^{s_{j}}}\bra{\chi_{a_{j}}^{s_{j}}}$
with $s\in\\{1,2,3\\}^{n}$ and $a\in\\{+1,-1\\}^{n}$ i.e., they correspond to
strings $s$ and $a$.

We will write $\mathcal{M}_{N}$ to denote the set of linear operators from
$\mathbb{C}^{N}$ to $\mathbb{C}^{N}$. The set of $n$-qubit quantum unitary
operators can then be defined as

$\mathcal{U}_{N}:=\\{U\in\mathcal{M}_{N}:UU^{*}=U^{*}U=I\\}.$ (8)

We define $n$-qubit to $n$-qubit quantum channels $\Phi$ to be completely
positive and trace-preserving maps from $\mathcal{M}_{N}$ to
$\mathcal{M}_{N}$.

#### Choi-Jamiolkowski isomorphism.

We will often use the Choi-Jamiolkowski isomorphism to encode a quantum
unitary or quantum channel as a quantum state. We call the resulting state as
the Choi-Jamiolkowski state (or CJ state for short). In the case of unitaries
$U$, the CJ state will be denoted by $\ket{v(U)}$, which is

$\ket{v(U)}:=(U\mathop{\otimes}I)\left(\frac{1}{\sqrt{N}}\sum_{i\in[N]}\ket{i}\ket{i}\right)=\frac{1}{\sqrt{N}}\sum_{i,j\in[N]}U[i,j]\ket{i}\ket{j}.$
(9)

The CJ state $\ket{v(U)}$ can be prepared by first preparing $n$ EPR pairs
(over $2n$ qubits) and the applying the unitary $U$ to the $n$ qubits coming
from the first half of each of the $n$ EPR pairs. Noting the Fourier
decomposition of the unitary
$U=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{U}(x)\sigma_{x}$ (which will be
presented shortly), we can also equivalently express the CJ state of $U$ in
terms of the CJ states corresponding to the different Pauli operators
$\ket{v(\sigma_{x})}$ as follows:

$\ket{v(U)}=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{U}(x)\ket{v(\sigma_{x})}.$
(10)

In case of quantum channels $\Phi$, the CJ representation is given by

$J(\Phi)=\sum_{i,j\in[N]}\Phi\left(\ket{i}\bra{j}\right)\mathop{\otimes}\ket{i}\bra{j}=(\Phi\mathop{\otimes}I)\left(\sum_{i,j\in[N]}\ket{i}\bra{j}\mathop{\otimes}\ket{i}\bra{j}\right),$
(11)

with the CJ state $v(\Phi)$ then defined to be

$v(\Phi)=\frac{J(\Phi)}{\operatorname{Tr}[J(\Phi)]}=\frac{J(\Phi)}{N}.$ (12)

###  2.1 Fourier and Pauli analysis

In this section, we describe Fourier expansion of Boolean functions and of
different quantum objects (states, unitaries, channels) that we consider
throughout this work. Note that the terms _Pauli expansion_ and _Fourier
expansion_ will often be used interchangeably in the context of quantum
objects .

#### Fourier expansion.

In this section we will talk about the space of functions defined on the
Boolean hypercube $f:\\{-1,1\\}^{n}\to\mathbb{R}$ endowed with the inner
product $\langle f,g\rangle=\mathbb{E}_{x}[f(x)g(x)]$, where the expectation
is taken with respect to the uniform measure of probability. For
$S\subseteq[n]$, the Fourier characters, defined by $\chi_{S}(x)=\prod_{i\in
S}x_{i}$, constitute an orthonormal basis of this space. Hence, every $f$ can
be identified with a multilinear polynomial via the Fourier expansion

$f=\sum_{s\in\\{0,1\\}^{n}}\widehat{f}(s)\chi_{s},$ (13)

where $\widehat{f}(s)$ are the Fourier coefficients given by

$\widehat{f}(s)=\langle\chi_{s},f\rangle=\mathbb{E}_{x}[f(x)\chi_{s}(x)].$
(14)

The degree of $f$ is the minimum $d$ such that $\widehat{f}(s)=0$ if $|s|>d$.
We will often use Parseval’s identity:

$\left\|{f}\right\|_{2}^{2}:=\langle
f,f\rangle=\sum_{s\in[n]}\widehat{f}(s)^{2}.$ (15)

We will also consider the $p$-norms of the Fourier spectrum, which are defined
as

$\left\|{\widehat{f}}\right\|_{p}=\left(\sum_{s\in\\{0,1\\}^{n}}|\widehat{f}(s)|^{p}\right)^{1/p}.$

#### Pauli expansion of operators.

In this section we consider $\mathcal{M}_{N}$ endowed with the usual inner
product $\langle A,B\rangle=\frac{1}{N}\operatorname{Tr}[A^{*}B]$, where here
and in the following $A^{*}$ denotes the adjoint matrix of $A$. The Pauli
operators $\sigma_{x}$ form an orthonormal basis for this space. The Pauli
expansion of a matrix $M$ of $\mathcal{M}_{N}$ is given by

$M=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{M}(x)\sigma_{x},$ (16)

where $\widehat{M}(x)=\langle\sigma_{x},M\rangle$. are Pauli coefficients of
$M$. We will refer to the collection of non-zero Pauli coefficients
$\\{\widehat{M}(x)\\}_{x}$ as the Pauli spectrum of $M$ with the set of
corresponding strings denoted by $\mathrm{spec}(M)$. As $\\{\sigma_{x}\\}_{x}$
is an orthonormal basis, we have a version of Parseval’s identity for
operators.

$\left\|{M}\right\|_{2}^{2}:=\langle
M,M\rangle=\sum_{x\in\\{0,1,2,3\\}^{n}}|\widehat{M}(x)|^{2}.$ (17)

In particular, for $U\in\mathcal{U}_{N},$ this implies that
$(|\widehat{U}(x)|^{2})_{x}$ is a probability distribution. We will also
consider the $p$-norms of the Pauli spectrum, which are defined as

$\left\|{\widehat{M}}\right\|_{p}=\left(\sum_{x\in\\{0,1,2,3\\}^{n}}|\widehat{M}(x)|^{p}\right)^{1/p}.$

We now define a notion of degree for states and unitaries that generalizes the
classical notion of Fourier degree (see [MO08, Section 5]).

######  Definition 1 (Degree of a matrix).

Given $M\in\mathcal{M}_{N}$ its degree is the minimum $d$ such that
$\widehat{M}(x)=0$ for any $x\in\\{0,1,2,3\\}^{n}$ with $|x|>d$.

We recall that this analogy between between Fourier analysis and Pauli
analysis for operators was first explored by Montanaro and Osborne [MO08].

#### Pauli expansion of superoperators.

We consider the space of superoprators (linear maps from $\mathcal{M}_{N}$ to
$\mathcal{M}_{N}$) endowed with the inner product
$\langle\Phi,\Psi\rangle=\langle J(\Phi),J(\Psi)\rangle/N^{2}$. An orthonormal
basis for superoperators is defined using characters

$\Phi_{x,y}(\rho)=\sigma_{x}\rho\sigma_{y},$ (18)

for any $x,y\in\\{0,1,2,3\\}^{n}$. The Pauli expansion of superoperators and
hence quantum channels is then defined as

$\Phi=\sum\limits_{x,y\in\\{0,1,2,3\\}^{n}}\widehat{\Phi}(x,y)\Phi_{x,y},$
(19)

where $\widehat{\Phi}(x,y)=\langle\Phi_{x,y},\Phi\rangle$ are the Pauli
coefficients of the superoperator. As $\\{\Phi_{x,y}\\}_{x}$ is an orthonormal
basis, we have a version of Parseval’s identity for superoperators

$\left\|{\Phi}\right\|_{2}^{2}:=\langle\Phi,\Phi\rangle=\sum_{x,y\in\\{0,1,2,3\\}^{n}}|\widehat{\Phi}(x,y)|^{2}.$

We will also consider the $p$-norms of the Pauli spectrum of superopertors,
which are defined as

$\left\|{\widehat{M}}\right\|_{p}=\left(\sum_{x,y\in\\{0,1,2,3\\}^{n}}|\widehat{\Phi}(x,y)|^{p}\right)^{1/p}.$

If $\Phi$ is a channel, then $\widehat{\Phi}=(\widehat{\Phi}(x,y))_{x,y}$ has
a couple of important properties [BY23, Lemma 8].

######  Fact 9.

If $\Phi$ is a channel, then $\widehat{\Phi}$ is a state unitarily equivalent
to $v(\Phi)$. In particular, $(\widehat{\Phi}(x,x))_{x}$ is a probability
distribution.

The degree of a superoprator is defined in the analogue way to operators.

######  Definition 2 (Degree of a superoperator).

Given a superoperator $\Phi$ its degree is the minimum $d$ such that
$\widehat{\Phi}(x,y)=0$ for any $x,y\in\\{0,1,2,3\\}^{n}$ with $|x|+|y|>d$.

We recall that this analogy between Fourier analysis and Pauli analysis for
superoperators was first explored by Bao and Yao [BY23].

###  2.2 Bohnenblust-Hille inequalities

#### Littlewood and Bohnenblust-Hille inequalities.

In 1930 Littlewood [Lit30] showed that for every bilinear form
$B:\mathbb{C}^{n}\times\mathbb{C}^{n}\to\mathbb{C}$ it holds that

$\left\|{\widehat{B}}\right\|_{4/3}\leq\sqrt{2}\left\|{B}\right\|_{\infty},$
(20)

where $\widehat{B}\in\mathbb{C}^{n\times n}$ are the coefficients of $B$,
i.e., $B(x,y)=\sum_{i,j\in[n]}\widehat{B}_{i,j}x_{i}y_{j}$, and

$\|\widehat{B}\|_{4/3}=\left(\sum_{i,j\in[n]}|\widehat{B}_{i,j}|^{4/3}\right)^{3/4}\quad\mathrm{and}\quad\left\|{B}\right\|_{\infty}=\sup_{|x_{i}|,|y_{j}|\leq
1}\left|\sum_{i,j\in[n]}\widehat{B}_{i,j}x_{i}y_{j}\right|.$

A year later, Bohnenblust and Hille [BH31] generalized the result for
$d$-linear tensors $T:(\mathbb{C}^{n})^{d}\to\mathbb{C}$ by showing that there
exists a constant $C(d)$, depending only on $d$ (and not $n$), such that

$\left\|{\widehat{T}}\right\|_{\frac{2d}{d+1}}\leq
C(d)\left\|{T}\right\|_{\infty},$ (21)

where $\widehat{T}$ are the coefficients of $T$ and
$\|\widehat{T}\|_{2d/(d+1)}$ and $\left\|{T}\right\|_{\infty}$ are defined in
analogue way to the bilinear case. These inequalities also hold (possibly with
different constants) if the tensors are defined over $\mathbb{R}$ instead of
$\mathbb{C}$. Determining the optimal constants has received a lot of
attention in mathematics [PSS12, MFPCSS12, NAPSSSR13, PT18, VCJ18, CPT20]. In
terms of upper bounds, it is known that $C(d)\leq\mbox{\rm poly}(d)$ [BPSS14],
but the best known lower bound is no bigger than a constant: $1$ for the
complex case and $2^{1-\frac{1}{d}}$ for the real case [DMFPSS14]. It is also
known that $p(d)=2d/(d+1)$ is the smallest number such that the inequality
$\|\widehat{T}\|_{p(d)}\leq C(d)\left\|{T}\right\|_{\infty}$ holds for some
constant $C(d)$ independent of $n$.

#### Grothendieck inequality.

In 1953, Grothendieck introduced his famous inequality for bilinear maps
[Gro53]. It establishes888We note that the original formulation of the
inequality was not the one presented here. In particular, Grothendieck did not
mention the cb-norm used in this work. that there is a constant $K$ such that
for every bilinear map $B:\mathbb{K}^{n}\times\mathbb{K}^{n}\to\mathbb{K}$,
with $\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$, it holds that

$\left\|{B}\right\|_{{\mathrm{cb}}}\leq K\left\|{B}\right\|_{\infty}.$ (22)

Here $\left\|{B}\right\|_{\mathrm{cb}}$ stands for the completely bounded norm
and is given by

$\left\|{B}\right\|_{{\mathrm{cb}}}=\sup\left\|{\sum_{i,j\in[n]}\widehat{B}_{i,j}X(i)Y(j)}\right\|_{\operatorname{op}},$

where $\left\|{\cdot}\right\|_{\operatorname{op}}$ stands for the operator
norm of matrices (largest singular value), the supremum runs over all integers
$m\in\mathbb{N}$ and all matrices $X(i),\
Y(j)\in\mathcal{B}(\ell_{2}^{m}(\mathbb{K}),\ell_{2}^{m}(\mathbb{K}))$ whose
operator norm is at most $1$. We denote the smallest constants that can appear
in (22) by $\operatorname{G_{\mathbb{K}}}$. Determining the exact value of
these constants has also been a separate line of research (see [Pis12, Section
4] and the references therein). The current state of the art are the bounds
$1.676<\operatorname{G_{\mathbb{R}}}<1.782$ [Dav84, Ree91, BMMN13] and
$1.338<\operatorname{G_{\mathbb{C}}}<1.4049$ [Haa87, Dav06]. Grothendieck
inequality has found a lot of applications in computer science and quantum
information, for instance in non-local games [Tsi80], quantum-query complexity
[AAI+16] and matrix approximation theory [AN04].

For $d$-linear tensors the completely bounded norm is defined in analogue way:

$\left\|{T}\right\|_{{\mathrm{cb}}}=\sup\left\|{\sum_{\mathbf{i}\in[n]^{d}}\widehat{T}_{\mathbf{i}}X_{1}(i_{1})\dots
X_{t}(i_{t})}\right\|_{\operatorname{op}},$ (23)

where again $X_{s}(i_{s})$ are bounded on operator norm. This norm has been
vastly studied in the complex case, where it corresponds with the Haagerup
tensor norm of $\ell_{1}^{n}(\mathbb{C})$ (see for instance [Pau03, Chapter
17]). In contrast to the Littlewood inequality (20), which generalizes to the
BH inequality, one can show that Grothendieck inequality fails for $d$-linear
tensors (this follows, for instance, from the stronger results proved in
[PGWP+08]). More precisely, there is no constant $K^{\prime}$ independent of
$n$ such that for every trilinear form $T$ it holds

$\left\|{T}\right\|_{{\mathrm{cb}}}\leq
K^{\prime}\left\|{T}\right\|_{\infty}.$

#### The completely bounded BH inequality.

From the BH inequality and the fact that
$\left\|{T}\right\|_{\infty}\leq\left\|{T}\right\|_{{\mathrm{cb}}}$ it follows
that there is a constant $C(d)$ such that

$\left\|{\widehat{T}}\right\|_{\frac{2d}{d+1}}\leq
C(d)\left\|{T}\right\|_{{\mathrm{cb}}}.$ (24)

We call this inequality the _completely bounded BH inequality_.

#### Non-commutative BH inequalities.

Since the breakthrough of Eskenazis and Ivanisvili, the BH inequality got the
attention of the quantum learning theory community. That lead to the non-
commutative versions of the BH inequality [HCP23, VZ23, SVZ23a, SVZ23b,
KSVZ24]. Volberg and Zhang [VZ23] proved that for a matrix
$M\in\mathcal{M}_{N}$ there exists a constant $C$ such that

$\left\|{\widehat{M}}\right\|_{\frac{2d}{d+1}}\leq
C^{d}\left\|{M}\right\|_{\operatorname{op}}.$ (25)

##  3 Learning low-degree quantum channels

In this section we give our learning algorithms for quantum channels, i.e., we
prove Theorems 1 and 2. Before that, we need to prove a new BH inequality for
quantum channels.

###  3.1 Bohnenblust-Hille inequality for quantum channels

In this section we prove a Bohnenblust-Hille inequality for quantum channels.
In fact, it is a result for superoperators that are bounded in the $S_{1}$ to
$S_{\infty}$ norm (defined below), of which quantum channels are an example.
Hence, in this section $\Phi$ will be treated a linear map from
$\mathcal{M}_{N}$ to $\mathcal{M}_{N}$. The $S_{1}$ to $S_{\infty}$ norm of
superoperator is defined by

$\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}=\sup_{M\neq
0}\frac{\left\|{\Phi(M)}\right\|_{S_{\infty}}}{\left\|{M}\right\|_{S_{1}}},$

where $\left\|{M}\right\|_{S_{1}}$ is the Schatten $1$-norm of $M$, i.e., the
sum of the singular values of $M$, and $\left\|{\Phi(M)}\right\|_{\infty}$ is
the Schatten $\infty$-norm, which coincides with the usual operator norm given
by the largest singular value.

In order to prove our theorem will reduce to the classical case of functions
$f:\\{-1,1\\}^{n}\to\mathbb{R}$.

######  Theorem 10 ([DMP19]).

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most $d$. Then,

$\left\|{\widehat{p}}\right\|_{\frac{2d}{d+1}}\leq C^{\sqrt{d\log
d}}\left\|{p}\right\|_{\infty},$

where $C>0$ is a constant.

We follow a similar argument to the one used in [VZ23]. However, we need to
modify their argument in order to considered maps from $S_{1}$ to $S_{\infty}$
and not just matrices in $M_{N}$. Here, for every superoperator
$\Phi:\mathcal{M}_{M}\to\mathcal{M}_{N}$, we will assign it a function
$f_{\Phi}:\\{-1,1\\}^{3n}\times\\{-1,1\\}^{3n}\to\mathbb{C}$ defined as
follows. For $a=(a^{1},a^{2},a^{3}),\
b=(b^{1},b^{2},b^{3})\in\\{-1,1\\}^{n}\times\\{-1,1\\}^{n}\times\\{-1,1\\}^{n}$
and $s,t\in\\{1,2,3\\}^{n}$, define the following matrices (which are not
necessarily states)

$\ket{a^{s}}\langle
b^{t}|=\mathop{\otimes}_{i\in[n]}\ket{\chi^{s(i)}_{a^{s(i)}_{i}}}\bra{\chi^{t(i)}_{b^{{t}(i)}_{i}}},$

The function $f_{\Phi}:\\{-1,1\\}^{3n}\times\\{-1,1\\}^{3n}\to\mathbb{C}$ is
then given by

$f_{\Phi}(a,b)=\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}\operatorname{Tr}[\Phi\left(\ket{a^{s}}\langle
b^{t}|\right)|b^{t}\rangle\langle a^{s}|],$

where $f_{\Phi}$ has the following properties, which allow for a reduction to
the classical BH inequality.

######  Lemma 11.

Let $\Phi$ be a degree-$d$ superoperator. Then,
$|f_{\Phi}(a,b)|\leq\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}$ for all $a,b$
and $\left\|{\widehat{\Phi}}\right\|_{p}\leq
3^{d}\left\|{\widehat{f}_{\Phi}}\right\|_{p}$. The degree of $f_{\Phi}$ as a
multilinear polynomial is $d$.

  * Proof:

We first show the bound on $|f_{\Phi}|$. Given that $\ket{a^{s}}\langle
b^{t}|$ is a rank one operator such that
$\|\ket{a^{s}}\|_{2}=\|\ket{b^{t}}\|_{2}=1$, we conclude that

$\left\|{\ket{a^{s}}\langle b^{t}|}\right\|_{S_{1}}=1.$ (26)

Thus, we have that $f_{\Phi}$ is bounded:

$\displaystyle|f_{\Phi}(a,b)|$
$\displaystyle\leq\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}|\operatorname{Tr}[\Phi\left(\ket{a^{s}}\langle
b^{t}|\right)|b^{t}\rangle\bra{a^{s}}]|$
$\displaystyle\leq\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}\left\|{\Phi\left(\ket{a^{s}}\langle
b^{t}|\right)}\right\|_{S_{\infty}}\left\|{|b^{t}\rangle\bra{a^{s}}}\right\|_{S_{1}}$
$\displaystyle\leq\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}\left\|{\Phi}\right\|_{S_{1}\to
S_{\infty}}\left\|{\ket{a^{s}}\langle
b^{t}|}\right\|_{S_{1}}\left\|{|b^{t}\rangle\bra{a^{s}}}\right\|_{S_{1}}$
$\displaystyle\leq\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}\left\|{\Phi}\right\|_{S_{1}\to
S_{\infty}}=\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}},$

where in the first inequality we have used the triangle inequality, in the
second inequality the duality between $S_{1}$ and $S_{\infty}$, in the third
the definition of $S_{1}\to S_{\infty}$ norm and in the fourth Eq. 26. We now
prove that $\left\|{\widehat{\Phi}}\right\|_{p}\leq
3^{-d}\left\|{\widehat{f}_{\Phi}}\right\|_{p}$ and that the degree of
$f_{\Phi}$ is $d$. For that it suffices to show that

$f_{\Phi}(a,b)=\sum_{x,y\in\\{0,1,2,3\\}^{n}}\frac{\widehat{\Phi}(x,y)}{3^{|x|+|y|}}\prod_{i\in\mathrm{supp}(x)}\prod_{j\in\mathrm{supp}(y)}a^{x(i)}_{i}b^{y(j)}_{j},$
(27)

where $\mathrm{supp}(x)=\\{i\in[n]:\,x_{i}\neq 0\\}$ and $|x|$ is the size of
supp$(x)$. Indeed, this follows from the fact that for every
$x,y\in\\{0,1,2,3\\}^{n}$, the product
$\prod_{i\in\mathrm{supp}(x)}\prod_{j\in\mathrm{supp}(y)}a^{x(i)}_{i}b^{y(j)}_{j}$
can be read as $\chi_{S_{x,y}}(a,b)$ for a certain $S_{x,y}\in\\{-1,1\\}^{6n}$
satisfying that $S_{x,y}\neq S_{x^{\prime},y^{\prime}}$ whenever
$(x,y)\neq(x^{\prime},y^{\prime})$.

To prove Eq. 27 the key is observing that for every $s,t\in\\{1,2,3\\}$,
$x,y\in\\{0,1,2,3\\}$ and $a,b\in\\{-1,1\\}$ we have that

$\operatorname{Tr}[\sigma_{x}\ket{\chi^{s}_{a}}\langle\chi^{t}_{b}|\sigma_{y}|\chi^{t}_{b}\rangle\langle\chi^{s}_{a}|]=\left\\{\begin{array}[]{ll}0&\mathrm{if}\
(s\neq x\ \mathrm{and}\ x\neq 0)\ \mathrm{or}\ (t\neq y\ \mathrm{and}\ y\neq
0),\\\ 1&\mathrm{if}\ x=0\ \mathrm{and}\ y=0,\\\ a&\mathrm{if}\ s=x\ \
\mathrm{and}\ y=0,\\\ b&\mathrm{if}\ x=0\ \ \mathrm{and}\ t=y,\\\
ab&\mathrm{if}\ s=x\ \ \mathrm{and}\ y=t.\\\ \end{array}\right.$

Hence taking tensor products we that for every $s,t\in\\{1,2,3\\}^{n}$,
$x,y\in\\{0,1,2,3\\}^{n}$ and $a=(a^{1},a^{2},a^{3}),\
b=(b^{1},b^{2},b^{3})\in\\{-1,1\\}^{n}\times\\{-1,1\\}^{n}\times\\{-1,1\\}^{n}$
it holds that

$\operatorname{Tr}[\sigma_{x}\ket{a^{s}}\langle
b^{t}|\sigma_{y}|b^{t}\rangle\langle
a^{s}|]=\langle\chi^{s}_{a}|\sigma_{x}\ket{\chi^{s}_{a}}\langle\chi^{t}_{b}|\sigma_{y}|\chi^{t}_{b}\rangle=\prod_{i\in\operatorname{supp}x}\prod_{j\in\operatorname{supp}y}a_{i}^{x(i)}b_{j}^{y(j)}\delta_{x(i),s(i)}\delta_{y(j),t(j)}.$

In particular, from this follows that

$\displaystyle f_{\Phi_{x,y}}(a,b)$
$\displaystyle=\frac{1}{9^{n}}\sum_{s,t\in\\{1,2,3\\}^{n}}\operatorname{Tr}[\sigma_{x}\ket{a^{s}}\langle
b^{t}|\sigma_{y}|b^{t}\rangle\langle a^{s}|]$
$\displaystyle=\frac{1}{9^{n}}\prod_{i\in\operatorname{supp}x}\prod_{j\in\operatorname{supp}y}a_{i}^{x(i)}b_{j}^{y(j)}\sum_{s\in\mathcal{X},t\in\mathcal{Y}}1,$

where $\mathcal{X}=\\{s\in\\{1,2,3\\}^{n}:s(i)=x(i)\ \forall\
i\in\operatorname{supp}(x)\\}.$ Hence, as $|\mathcal{X}|=3^{n-|x|}$, Eq. 27
follows for the case of $\Phi_{x,y}$. By linearity, Eq. 27 follows for every
superoperator. $\Box$

######  Theorem 12 (Bohnenblust-Hille inequality for $S_{1}\to S_{\infty}$
maps).

Let $\Phi$ be a superoperator of degree at most $d$. Then,

$\left\|{\widehat{\Phi}}\right\|_{\frac{2d}{d+1}}\leq
C^{d}\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}.$

In particular, if $\Phi$ is a quantum channel, then there exists a constant
$C$ such that

$\left\|{\widehat{\Phi}}\right\|_{\frac{2d}{d+1}}\leq C^{d}.$

  * Proof:

Let $\mbox{\rm Re}f_{\Phi}:\\{-1,1\\}^{6n}\to\mathbb{R}$ be defined as
$(\mbox{\rm Re}f_{\phi})(x)=\mbox{\rm Re}(f_{\Phi}(x))$ and $\mbox{\rm
Im}f_{\Phi}:\\{-1,1\\}^{6n}\to\mathbb{R}$ as $(\mbox{\rm
Im}f_{\phi})(x)=\mbox{\rm Im}(f_{\Phi}(x))$. Note that we have that
$\widehat{f}_{\phi}=\widehat{\mbox{\rm Re}f}_{\Phi}+i\widehat{\mbox{\rm
Im}f}_{\Phi}$. By Lemma 11, $|(\mbox{\rm Re}f_{\phi})(a,b)|,|(\mbox{\rm
Im}f_{\phi})(a,b)|\leq|f_{\Phi}(x)|\leq\left\|{\Phi}\right\|_{S_{1}\to
S_{\infty}}$ and that the degree of both the real and imaginary part is at
most $d$. Hence, by the triangle inequality and Theorem 10 we have

$\left\|{\widehat{f}_{\Phi}}\right\|_{\frac{2d}{d+1}}\leq\left\|{\widehat{\mbox{\rm
Re}f}_{\Phi}}\right\|_{\frac{2d}{d+1}}+\left\|{\widehat{\mbox{\rm
Im}f}_{\Phi}}\right\|_{\frac{2d}{d+1}}\leq C^{\sqrt{d\log
d}}\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}.$

Thus, using that $\left\|{\widehat{\Phi}}\right\|_{2d/(d+1)}\leq
3^{d}\left\|{\widehat{f}_{\Phi}}\right\|_{2d/(d+1)}$ it follows that
$\left\|{\widehat{\Phi}}\right\|_{2d/(d+1)}\leq
C^{d}\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}$. This proves the first part
of the statement.

For the second we just have to show that if $\Phi$ is a quantum channel, then
$\left\|{\Phi}\right\|_{S_{1}\to S_{\infty}}\leq 1$. This is true since
$\left\|{\Phi}\right\|_{S_{1}\to
S_{\infty}}\leq\left\|{\Phi}\right\|_{S_{1}\to S_{1}}$ and $\Phi^{\dagger}$ is
a completely positive and unital map between C∗-algebras, so we have
$\left\|{\Phi}\right\|_{S_{1}\to
S_{1}}=\left\|{\Phi^{\dagger}}\right\|_{S_{\infty}\to S_{\infty}}=1$ [Pau03,
Proposition 3.2]. $\Box$

######  Remark 13.

Theorem 12 generalizes the non-commutative BH inequality by Volberg and Zhang
[VZ23], displayed in Eq. 25. Indeed, given $M\in\mathcal{M}_{N}$, one can
consider the superoperator $\Phi_{M}(\cdot)=\mathop{\rm Id}\nolimits\cdot M$,
which satisfies $\widehat{\Phi}_{M}(x,y)=\delta_{x,0^{n}}\widehat{M}(y)$ and
$\left\|{\Phi_{M}}\right\|_{S_{1}\to
S_{\infty}}=\left\|{M}\right\|_{\operatorname{op}}.$

###  3.2 Learning low-degree quantum channels

Before we prove the main theorem of the section, we show that for a given
$x,y\in\\{0,1,2,3\\}^{n}$, the corresponding Fourier coefficient
$\widehat{\Phi}(x,y)$ can be efficiently learned. To do that, we just have to
combine a few SWAP tests.

######  Fact 14 (SWAP test for mixed states [KMY03]).

Let $\rho,\rho^{\prime}$ be two states. Then, one can estimate
$\operatorname{Tr}[\rho\rho^{\prime}]$ up to error $\varepsilon$ with
probability $1-\delta$ using $O((1/\varepsilon)^{2}\log(1/\delta))$ copies of
$\rho$ and $\rho^{\prime}$.

######  Lemma 15 (Pauli coefficient estimation for channels).

Let $x,y\in\\{0,1,2,3\\}^{n}$. Then, $\widehat{\Phi}(x,y)$ can be estimated
with error $\varepsilon$ and probability $1-\delta$ using
$O((1/\varepsilon)^{2}\log(1/\delta))$ queries to $\Phi$.

  * Proof:

If $x=y$, we just have to prepare $\widehat{\Phi}$ and apply 14 to
$\widehat{\Phi}$ and the state $\rho=\ket{x}\bra{x}$. If $x\neq y$, one first
learns $\widehat{\Phi}(x,x)$ and $\widehat{\Phi}(y,y)$ with error
$\varepsilon$ as before. One the one hand, one can learn
$\widehat{\Phi}(x,x)+\widehat{\Phi}(x,x)+2\mbox{\rm Re}\widehat{\Phi}(x,y),$
with error $\varepsilon$ by applying 14 to $\widehat{\Phi}$ and
$1/2\sum_{z,t\in\\{x,y\\}}\ket{z}\bra{t}$. Hence, one learns $\mbox{\rm
Re}\widehat{\Phi}(x,y)$ with error $3\varepsilon/2$. On the other hand, one
can learn $\widehat{\Phi}(x,x)+\widehat{\Phi}(y,y)+2\mbox{\rm
Im}\widehat{\Phi}(x,y),$ with error $\varepsilon$ by applying 14 to
$\widehat{\Phi}$ and
$1/2(\ket{x}\bra{x}+i\ket{x}\bra{y}-i\ket{y}\bra{x}+\ket{y}\bra{y}),$ and thus
one can learn $\mbox{\rm Im}\widehat{\Phi}(x,y)$ with error $3\varepsilon/2$.
$\Box$

We will also need the following well-known result about distribution learning
theory. See [Can20, Theorem 9] for a proof.

######  Lemma 16.

Let $p=\\{p(x)\\}_{x}$ be a probability distribution over some set
$\mathcal{X}.$ Let $p^{\prime}=(p^{\prime}(x))_{x}$ be the empirical
probability distribution obtained after sampling $T$ times from $p$. Then, for
$T=O((1/\varepsilon)^{2}\log(1/\delta))$ with probability $\geq 1-\delta$ we
have that $|p(x)-p^{\prime}(x)|\leq\varepsilon$ for every $x\in\mathcal{X}$.

Now, we are ready to prove Theorem 1, which we restate for the convenience of
the reader. See 1

  * Proof:

We first state the algorithm. Let $C$ be the constant in the statement of
Theorem 12.

Algorithm 1 Learning low-degree channels via BH inequality

Input: A quantum channel $\Phi$ of degree at most $d$, and error $\varepsilon$
and a failure probability $\delta$

1:Let $c=\varepsilon^{4d+2}C^{-4d^{2}}$

2:Prepare $T_{1}=O((1/c)^{2}\log(1/\delta))$ copies of $\widehat{\Phi}$ to
sample from $(\widehat{\Phi}(x,x))_{x}$. Let
$(\widehat{\Phi}^{\prime}(x,x))_{x}$ be the associated empirical distribution

3:for $x,y\in\mathcal{X}_{c}=\\{x:|\widehat{\Phi}^{\prime}(x,x)|\geq c\\}$ do

4: Prepare $O((1/c)^{2}(1/\varepsilon)^{2}\log((1/c)^{2}(1/\delta)))$ copies
of $\widehat{\Phi}$ and use them to approximate $\widehat{\Phi}(x,y)$ with
$\widehat{\Phi}^{\prime\prime}(x,y)$ using Lemma 15.

Output:
$\sum_{x,y\in\mathcal{X}_{c}}\widehat{\Phi}^{\prime\prime}(x,y)\Phi_{x,y}$

Let $c>0$ to be determined later. In the first part of the algorithm we
prepare $\widehat{\Phi}$ and measure, i.e., we sample from
$(\widehat{\Phi}(x,x))_{x\in\\{0,1,2,3\\}^{n}}$. Let
$(\widehat{\Phi}^{\prime}(x,x))_{x\in\\{0,1,2,3\\}^{n}}$ be the empirical
distribution one obtains after $T_{1}$ samples. Let us consider the event
$\mathcal{E}=\\{|\widehat{\Phi}(x,x)-\widehat{\Phi}^{\prime}(x,x)|\leq c\
\forall x\in\\{0,1,2,3\\}^{n}\\}$. By Lemma 16, taking $T_{1}$ to be
$O((1/c)^{2}\log(1/\delta))$ ensures that

$\mathrm{Pr}[\mathcal{E}]\geq 1-\delta.$

Let $\mathcal{X}_{c}=\\{x:\ |\widehat{\Phi}^{\prime}(x,x)|\geq c\\}$. Note
that, since $\sum_{x\in\mathcal{X}_{c}}\Phi(x,x)\leq 1,$ we know that

$\displaystyle|\mathcal{X}_{c}|\leq c^{-1}.$ (28)

Hence, assuming the event $\mathcal{E}$ holds, we have that

$\displaystyle
x\notin\mathcal{X}_{c}\implies|\widehat{\Phi}(x,x)|\leq|\widehat{\Phi}^{\prime}(x,x)|+||\widehat{\Phi}(x,x)|-|\widehat{\Phi}^{\prime}(x,x)||\leq
2c.$ (29)

In particular, it follows that

$\displaystyle
x\notin\mathcal{X}_{c}\implies|\widehat{\Phi}(x,y)|\leq\sqrt{|\widehat{\Phi}(x,x)||\widehat{\Phi}(y,y)|}\leq\sqrt{2c}\quad\forall\,y\in\\{0,1,2,3\\}^{n},$
(30)

where in the first inequality we have used that $\widehat{\Phi}$ is positive
semidefinite and in the second inequality Eq. 29 and that
$\widehat{\Phi}(y,y)\leq 1.$

Let us assume that the first part of the algorithm succeeds, meaning that
$\mathcal{E}$ happens and we will continue the algorithm conditioned to this
fact. In the second part of the algorithm we invoke Lemma 15 to state that, by
querying $\Phi$ just

$T_{2}=O((1/c)^{4}(1/\varepsilon)^{2}\log((1/c)^{2}(1/\delta)))$

times, we can find approximations $\widehat{\Phi}^{\prime\prime}(x,y)$ of
$\Phi(x,y)$ for every $x,y\in\mathcal{X}_{c}$, such that

$\sup_{(x,y)\in\mathcal{X}_{c}\times\mathcal{X}_{c}}|\widehat{\Phi}(x,y)-\widehat{\Phi}^{\prime\prime}(x,y)|\leq
c\varepsilon$

happens with probability $\geq 1-\delta$.

Note that $T_{2}>T_{1}$, so this complexity dominates the one of the first
part of the algorithm. Let $\widehat{\Phi}^{\prime\prime}(x,y)$ be these
approximations and let
$\Phi^{\prime\prime}=\sum_{x,y\in\mathcal{X}_{c}}\widehat{\Phi}^{\prime\prime}(x,y)\sigma_{x}\cdot\sigma_{y}$.
Now, we have that

$\displaystyle\left\|{\Phi-\Phi^{\prime\prime}}\right\|_{2}^{2}$
$\displaystyle=\sum_{x,y\in\mathcal{X}_{c}}|\widehat{\Phi}(x,y)-\widehat{\Phi}^{\prime\prime}(x,y)|^{2}+\sum_{x\lor
y\notin\mathcal{X}_{c}}|\widehat{\Phi}(x,y)|^{2}$
$\displaystyle\leq\varepsilon^{2}+\sum_{x\lor
y\notin\mathcal{X}_{c}}|\widehat{\Phi}(x,y)|^{\frac{2}{d+1}}|\widehat{\Phi}(x,y)|^{\frac{2d}{d+1}}$
$\displaystyle\leq\varepsilon^{2}+(2c)^{\frac{1}{d+1}}\left\|{\widehat{\Phi}}\right\|_{\frac{2d}{d+1}}^{\frac{2d}{d+1}}$
$\displaystyle\leq\varepsilon^{2}+c^{\frac{1}{d+1}}C^{d},$

where in the equality we have used Parseval’s identity; in the first
inequality we used Eq. 28, the learning guarantees of the second part of the
algorithm and that $2=1/(d+1/2)+2d/(d+1/2)$ ; in the second inequality we have
used Eq. 30; and in the third inequality we used the Bohnenblust-Hille
inequality for channels (Theorem 12). Hence, by choosing

$c=\varepsilon^{2d+2}C^{-d(d+1)}$

we obtain the desired result. $\Box$

##  4 Learning low-degree quantum unitaries

In this section our goal will be to prove the following theorem.

See 3

The proof strategy is identical to the one of Theorem 1, but now we learn the
Pauli coefficients with an extension of the routine of Montanaro and Osborne
(Lemma 17) and use the BH ienquality of Volberg and Zhang to ensure
correctness (Eq. 25).

The routine used in [MO08, Lemma 24] for estimating Fourier coefficients of
quantum Boolean functions can be extended for estimating Fourier coefficients
of any quantum unitary. A Hadamard circuit is used for estimating the real and
complex values of Fourier coefficients separately, which is shown in Figure 2.
The corresponding sample complexity for estimation can then be easily shown.

Figure 2: Quantum circuit for estimating the Fourier coefficient
$\widehat{U}(\alpha)$ for any $\alpha\in\\{0,1,2,3\\}^{n}$. Gate $G$ on the
ancilla qubit is set to $I$ for estimating $\mathrm{Re}(\widehat{U}(\alpha))$
and is set to the $S$ gate for estimating $\mathrm{Im}(\widehat{U}(\alpha))$.
The circuit $U_{\mathrm{EPR}}$ corresponds to the state preparation unitary of
$n$-qubit EPR pairs over $2n$ qubits which contains $n$ sequential CNOT gates
with control on the $j$th qubit in the first $n$-qubit register and target on
the $j$th qubit in the second $n$-qubit register, ordered with increasing
$j\in[n]$.

######  Lemma 17.

Given a unitary $U$ and a string $x\in\\{0,1,2,3\\}^{n}$. There is an
algorithm that $(\varepsilon,\delta)$-estimates the Fourier coefficient
$\widehat{U}(x)$ using $O\left((1/\varepsilon)^{2}\log(1/\delta)\right)$
queries to $U$.

  * Proof of Theorem 3:

Let $c>0$ to be determined later. In the first part of the algorithms we
prepare $T_{1}$ copies of the CJ state $\ket{v(U)}$ and measure them in the
Bell basis, i.e., we sample from $(|\widehat{U}(x)|^{2})_{x}$. Let
$(|\widehat{U}^{\prime}(x)|^{2})_{x}$ be the empirical distribution obtained
after sampling. Let
$\mathcal{E}=\\{||\widehat{U}(x)|^{2}-|\widehat{U}^{\prime}(x)|^{2}|\leq
c^{2}:\,\forall\,x\in\\{0,1,2,3\\}^{n}\\}$. By Lemma 16, taking
$T_{1}=O((1/c)^{4}\log(1/\delta))$ times ensures that

$\mathrm{Pr}[\mathcal{E}]\geq 1-\delta.$

Note that in the event of $\mathcal{E}$

$||\widehat{U}(x)|-|\widehat{U}^{\prime}(x)||\leq c,$

for every $x\in\\{0,1,2,3\\}^{n}$. Let
$\mathcal{X}_{c}=\\{|\widehat{U}^{\prime}(x)|\geq c\\}$. Note that, since
$\sum_{x\in\mathcal{X}_{a}}|\widehat{U}^{\prime}(x)|^{2}\leq 1$, we have that
$|\mathcal{X}_{c}|\leq c^{-2}$ and in the event of $\mathcal{E}$ we have that

$\displaystyle
x\notin\mathcal{X}_{c}\implies|\widehat{U}(x)|\leq|\widehat{U}^{\prime}(x)|+||\widehat{U}(x)|-|\widehat{U}^{\prime}(x)||\leq
2c.$ (31)

In the second part of the algorithm we assume that the first has succeeded,
i.e., that $\mathcal{E}$ occurs, Next, we learn the Pauli coefficients of
$\mathcal{X}_{c}$ with error $c\varepsilon$ and probability $1-\delta$ using

$T_{2}=O((1/c)^{4}(1/\varepsilon)^{2}\log((1/c)^{2}(1/\delta)))$

queries for each of them (which can be done using Lemma 17). As $T_{2}>T_{1},$
the cost of this second part dominates over the first. Let
$\widehat{U}^{\prime\prime}(x)$ be the approximations obtained for
$\widehat{U}(x)$ with $x\in\\{0,1,2,3\\}^{n}$. Let
$U_{c}=\sum_{x\in\mathcal{X}_{c}}\widehat{U}^{\prime\prime}(x)\sigma_{x}$.
Now, we have that

$\displaystyle\left\|{U-U_{c}}\right\|_{2}^{2}$
$\displaystyle=\sum_{x\in\mathcal{X}_{c}}|\widehat{U}(x)-\widehat{U}^{\prime}(x)|^{2}+\sum_{x\notin\mathcal{X}_{c}}|\widehat{U}(x)|^{2}\leq\varepsilon^{2}+(2c)^{\frac{2}{d+1}}\left\|{\widehat{U}}\right\|_{\frac{2d}{d+1}}^{\frac{2d}{d+1}}\leq\varepsilon^{2}+c^{\frac{2}{d+1}}C^{d},$

where in the equality we have used Parseval; in the first inequality we have
used our upper bound on $|\mathcal{X}_{c}|$, Eq. (31) and the learning
guarantees of the second part of the algorithm; and in the second inequality
the Bohnenblust-Hille inequality of Volberg and Zhang Eq. 25. Hence, by
choosing

$c=\varepsilon^{d+1}C^{-d(d+1)72}$

we obtain the desired result. $\Box$

##  5 Learning low-degree functions

###  5.1 Boolean functions.

In this section, we prove Facts 6 and 7, both based on the well-known
granurality of Boolean polynomials (see [O’D14, Exercise 1.11] for a proof).

######  Fact 18 (Granularity of Boolean polynomials).

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be a function of degree $d$. Then,
$\widehat{f}(s)\in 2^{1-d}\mathbb{Z}$ for every $s\in\\{0,1\\}^{n}.$

We restate the facts we are going to prove for the convenience of the reader.

###### Fact 6.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be a degree-$d$ function. There is a
quantum algorithm that learns $f$ exactly with probability 1$-\delta$ using
$O\left(4^{d}d\log\left(1/\delta\right)\right)$ quantum uniform examples. In
contrast, any classical algorithm requires $\Omega(2^{d}+\log n)$ uniform
examples and there is a classical algorithm that only uses
$O\left(4^{d}d\log\left(n/\delta\right)\right)$ uniform examples.

  * Proof:

The classical lower bound follows from the fact that $d$-juntas (functions
depending only on $d$ variables) have degree $d$ and it requires
$\Omega(2^{d}+\log n)$ to learn them (see, for instance, [AS07, Lemma IV.1]).
For the classical upper bound we take $T=O(4^{d}\log(n^{d}/\delta))$ uniform
samples $(x_{i},f(x_{i}))$. Define the empirical Fourier coefficients as

$\widehat{f}^{\prime}(s)=\frac{1}{T}\sum_{i\in[T]}f(x_{i})\chi_{s}(x_{i}).$

Define the event
$\mathcal{E}=\\{|\widehat{f}(s)-\widehat{f}^{\prime}(s)|<2^{-d}\
\forall\,|s|\leq d\\}.$ From Eq. 15, the Hoeffding bound and a union bound
over the $\sum_{i\in[d]_{0}}{n\choose i}\leq n^{d}$ strings $s$ with $|s|\leq
d$ it follows that

$\mathrm{Pr}[\mathcal{E}]\geq 1-\sum_{i\in[d]_{0}}{n\choose
i}e^{-\frac{4^{-d}T}{2}}\geq 1-\delta.$

In the second part of the algorithm, we round every $\widehat{f}^{\prime}(s)$
to the closest number $\widehat{f}^{\prime\prime}(s)\in 2^{d-1}\mathbb{Z}$. If
$\mathcal{E}$ occurs, by granularity we have that
$\widehat{f}^{\prime\prime}(s)=\widehat{f}(s)$ for every $|s|\leq d,$ so we
learn $f$ exactly.

For the quantum upper bound we first use $T_{1}=O(4^{d}d\log^{2}(1/\delta))$
quantum uniform samples to do Fourier sampling (see for instance [ACL+21,
Lemma 4]). This allows us to sample $4^{d}\log(4^{d}/\delta)$ times from
$(\widehat{f}(s)^{2})_{s\in[n]}$. Given $s$ such that $\widehat{f}(s)\neq 0$,
and thus $|\widehat{f}(s)|^{2}\geq 4^{1-d}$ by 18, the probability of not
sampling $s$ is at most

$\left(1-4^{1-d}\right)^{N}\leq{\delta}/{4^{d}}.$

Then, taking a union bound over the at most $4^{d-1}$ non-zero Fourier
coefficients (due to 18 and $\sum_{s}|\widehat{f}(s)|^{2}=1$), it follows that
with probability $1-\delta$ we will have sampled every non-zero Fourier
coefficient. In the second part of the algorithm we use
$T_{2}=O(4^{d}\log(4^{d}/\delta))$ quantum uniform samples and measure them in
the computational basis, which generates _classical_ uniform samples. From
here, we can argue as in the classical upper bound and learn $f$ exactly. The
quantum advantage comes from Fourier sampling, that allows to detect the
relevant Fourier coefficients, after what one can learn those few coefficients
in a classical way.

Note that the quantum advantage comes from Fourier sampling, that allows to
detect the relevant Fourier coefficients, after what one can learn those few
coefficients in a classical way. $\Box$

###### Fact 7.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ of degree at most $d$. Then,

$\Big{(}\sum_{s\in\\{0,1\\}^{n}}|\widehat{f}(s)|^{\frac{2d}{d+1}}\Big{)}^{\frac{d+1}{2d}}\leq
2^{\frac{d-1}{d}}.$

The equality is witnessed by the address function.

  * Proof:

Granularity (18) and Parseval’s identity Eq. 15,
$\sum_{s}\widehat{f}^{2}(s)=\mathbb{E}_{x}f(x)^{2}=1,$ imply that there $f$
has at most $2^{2(d-1)}$ non-zero Fourier coefficients. Hence, using Hölder’s
inequality it follows that for $p\in[1,2)$

$\displaystyle\sum_{s:\widehat{f}(s)\neq 0}|\widehat{f}|^{p}\cdot
1\leq\left(\sum_{s\in\\{0,1\\}^{n}}\widehat{f}^{2}(s)\right)^{\frac{p}{2}}\left(2^{2(d-1)}\right)^{\frac{2-p}{2}}=2^{(d-1)(2-p)}.$

Taking $p=2d/(d+1)$ the claimed inequality follow.

The equality is witnessed by the _address function_
$f:(\\{-1,1\\})^{n})^{d}\to\\{-1,1\\}$ of degree $d$ and $n=2^{d-1}$, which is
defined as

$f(x)=\sum_{a\in\\{-1,1\\}^{d-1}}\underbrace{\frac{x_{1}(1)-a_{1}x_{1}(2)}{2}\dots\frac{x_{d-1}(1)-a_{d-1}x_{d-1}(2)}{2}}_{g_{a}(x_{1},\dots,x_{d-1})}x_{d}(a),$
(32)

where we identify $\\{-1,1\\}^{d-1}$ with $[2^{d-1}]$ in the canonical way.
The address function is Boolean because for every
$(x_{1},\dots,x_{d-1})\in(\\{-1,1\\}^{n})^{d-1}$ there is only one
$a\in\\{-1,1\\}^{d-1}$ such that $g_{a}(x_{1},\dots,x_{d-1})$ is not $0$, in
which case it takes the value $\pm 1$. Given that it has $2^{2(d-1)}$ Fourier
coefficients and all of them equal $2^{1-d}$, we have that

$\Big{(}\sum_{s\in\\{0,1\\}^{n}}|\widehat{f}(s)|^{\frac{2d}{d+1}}\Big{)}^{\frac{d+1}{2d}}=2^{1-d}2^{2(d-1)\cdot\frac{d+1}{2d}}=2^{\frac{d-1}{d}},$

as promised. $\Box$

###  5.2 Bounded functions.

In this section our goal will be to prove the following proposition.

###### Proposition 8.

Let $p:\\{-1,1\\}^{n}\to[-1,1]$ be a degree $d$ polynomial. There is an
algorithm that $(\varepsilon,\delta)$-learns $p$ (in $\ell_{2}$-accuracy)
using $\exp(\widetilde{O}(\sqrt{d^{3}\log
d}+d\log(1/\varepsilon))\cdot\log(1/\delta))$ copies of a block-encoding of
$p$.

In comparison to the Boolean function scenario, for bounded multilinear
polynomials $p:\\{-1,1\\}^{n}\to[-1,1]$ things get more complicated because 18
no longer holds and uniform random samples do not make sense. However, we can
circumvent both issues. The first, because, as noted by Eskenazis and
Ivanisvili, it is already useful to have an upper bound for
$\left\|{\widehat{p}}\right\|_{q}$ for a $q<2$ [EI22], which is exactly what
the Bohnenblust-Hille inequality of Defant et al. (Theorem 10). The second
issue can be solved by accessing bounded functions $p:\\{-1,1\\}^{n}\to[-1,1]$
through block-encodings in $2^{n+1}$-dimensional unitary $U_{p}$. We consider
the block-encodings defined by

$U_{p}=\begin{pmatrix}\operatorname{Diag}(p)&-\operatorname{Diag}((1-p^{2})i)\\\
\operatorname{Diag}((1-p^{2})i)&-\operatorname{Diag}(p)\end{pmatrix},$ (33)

where for a function $g:\\{-1,1\\}^{n}\to\mathbb{C}$ we define
$\operatorname{Diag}g$ as the $2^{n}\times 2^{n}$ diagonal matrix whose
diagonal is given by the values of $g$. In terms of the Pauli matrices and the
Fourier spectrum of $p$, $U_{p}$ can be written as

$U_{p}=\sigma_{3}\otimes\left[\sum_{s\in\\{0,1\\}}\widehat{p}(S)\otimes_{i\in\operatorname{supp}(s)}(\sigma_{3})_{i}\right]+\sigma_{2}\otimes\left[\sum_{s\in\\{0,1\\}^{n}}\widehat{1-p^{2}}(s)\otimes_{i\in\operatorname{supp}(s)}(\sigma_{3})_{i}\right],$
(34)

where $\otimes_{i\in\operatorname{supp}(s)}(\sigma_{3})_{i}$ stands for the
Pauli string with $\sigma_{3}$ indicated by $s$ and identities on the rest.
Now, we are ready to present our quantum learning algorithm for bounded
functions, which combines Fourier sampling techniques and the learning ideas
of Eskenazis and Ivanisvili [EI22].

  * Proof of Proposition 8:

Let $a,b>0$ to be fixed later. In the first of the algorithm we prepare
$T_{1}=(1/a)^{2}\log(2/\delta a^{2})$ copies of the CJ state of $U_{p}$ and
measure them in the basis $\\{\ket{v(\sigma_{x})}\\}$. By Eq. 10, this is the
same as sampling $T_{1}$ times from
$(|\widehat{U}_{p}(x)|^{2})_{x\in\\{0,1,2,3\\}^{n+1}}$. Now note that

$\widehat{U}_{p}(x)=\widehat{p}(s_{x})$

if $x\in\\{3\\}\times\\{0,3\\}^{n}$, where $s_{x}\in\\{0,1\\}^{n}$ is defined
as $(s_{x})_{i}:=\delta_{x_{i+1},3}$. Let
$\mathcal{S}_{a}=\\{s\in\\{0,1\\}^{n}:|\widehat{p}(s)|\geq a\\}$. The
probability of not measuring an $s\in\mathcal{S}_{a}$ in $T_{1}$ samples is at
most

$(1-a^{2})^{T_{1}}\leq a^{2}\delta.$

Thus, as $|\mathcal{S}_{a}|\leq a^{-2}$ (because
$\sum_{s}|\widehat{p}(s)|^{2}=\left\|{p}\right\|_{2}^{2}\leq 1$), it follows
that after $T_{1}$ samples of $(|\widehat{U}_{p}(x)|^{2})_{x}$ with
probability$\geq 1-\delta$ we will have sampled at least once every element of
$\mathcal{S}_{a}$. In other words, if $\mathcal{T}_{1}$ are the
$s\in\\{0,1\\}^{n}$ such that correspond to an $x\in\\{0,1,2,3\\}^{n+1}$ that
has been sampled at least once, then $\mathcal{S}_{a}\subseteq\mathcal{T}_{1}$
with high probability.

In the second part of the algorithm we use

$T_{2}=O((1/b)^{2}\log(2/(\delta T_{1})))$

uniform random samples to learn with error $b$ and probability $\geq 1-\delta$
the at most $T_{1}$ Fourier coefficients sampled in the first part of the
algorithm. This can be done by estimating the empirical Fourier coefficients,
as in the proof of 6. We denote these estimations by
$\widehat{p}^{\prime}(s).$ Let
$h_{a,b}=\sum_{s\in\mathcal{T}_{1}}\widehat{p}^{\prime}(s)\chi_{s}.$ We claim
that $h_{a,b}$ is a good approximation of $p$. Indeed,

$\displaystyle\left\|{p-h_{a,b}}\right\|_{2}^{2}$
$\displaystyle=\sum_{s\in\mathcal{T}_{1}}|\widehat{p}(s)-\widehat{p}^{\prime}(s)|^{2}+\sum_{s\notin\mathcal{T}_{1}}|\widehat{p}(s)|^{2}$
$\displaystyle\leq
b^{2}T_{1}+\sum_{s\notin\mathcal{T}_{1}}|\widehat{p}(s)|^{\frac{2d}{d+1}}|\widehat{p}(s)|^{\frac{2}{d+1}}$
$\displaystyle\leq b^{2}\frac{1}{a^{2}}\log\left(\frac{2}{\delta
a^{2}}\right)+a^{\frac{2}{d+1}}\left\|{\widehat{p}}\right\|_{\frac{2d}{d+1}}^{\frac{2d}{d+1}}$
$\displaystyle\leq b^{2}\frac{1}{a^{2}}\log\left(\frac{2}{\delta
a^{2}}\right)+a^{\frac{2}{d+1}}C^{\sqrt{d\log d}},$

where in the equality we have used Parseval’s identity; in the first
inequality we have used the learning guarantee of the second part; in the
second inequality that $S_{a}\subseteq\mathcal{T}_{1}$; and in the third
inequality the BH inequality for multilinear polynomials (Theorem 10). Hence,
taking $b^{2}=\varepsilon^{2}a^{2}(\log(2/\delta a^{2}))^{-1}$ and
$a=\varepsilon^{d+1}C^{d^{3/2}(\log(d))^{1/2}}$ it follows that
$\left\|{p-h_{a,b}}\right\|\leq\varepsilon^{2},$ as desired. This way,
$T_{2}>T_{1}$ and the sample complexity is upper bounded by

$T_{2}=\widetilde{O}((1/b^{2})\log(1/\delta))=\widetilde{O}((1/a^{2}\varepsilon^{2})\log(1/\delta))=\widetilde{O}((1/\varepsilon)^{2d+4}C^{d^{3/2}(\log(d))^{1/2}}\log(1/\delta)).$

Regarding the time complexity dependence on $n$, the algorithm runs in
$\mbox{\rm poly}(n)$ up to $d=(\log n)^{\eta}$ with $\eta<2/3$, because
generating a CJ state requires $O(n)$ elementary gates (we generate $T_{1}$ CJ
states); computing a empirical Fourier coefficient requires $\mbox{\rm
poly}(n)$ time (we compute $T_{1}$ empirical Fourier coefficients); and
$T_{1}=\widetilde{O}(\varepsilon^{2d+2}C^{d^{3/2}(\log(d))^{1/2}})$, so
$T_{1}=O(\mbox{\rm poly}(n))$ even for $d=(\log n)^{\eta}.$ $\Box$

##  6 Learning quantum query algorithms

In this section our goal will be to prove the Theorem 5, restated below for
the readers convenience. See 5

  * Proof:

Eskenazis and Ivanishvili showed that a function $f:\\{-1,1\\}^{n}\to[-1,1]$
with degree at most $d$ and $\left\|{\widehat{f}}\right\|_{\frac{2d}{d+1}}\leq
C$, can be learned with success probablity $1-\delta$ and error $\varepsilon$
in $\ell_{2}^{2}$ accuracy using

$O(\varepsilon^{-(d+1)}C^{2d}\log(n/\delta))$ (35)

samples $(x,f(x))$, where $x$ is drawn uniformly at random from
$x\in\\{-1,1\\}^{n}$. The first author, Briët and Palazuelos [ABP19] showed
that the amplitudes of quantum algorithms that $d$ queries as in Fig. 1 are
completely bounded $d$-tensors. Hence, using Theorem 19 (which we prove below)
one can use Eq. 35 with $C=1$, from which the stated result follows. $\Box$

#### The constant of the completely bounded BH inequality is 1.

In this section we determine that the exact value of the constant of the
completely bounded BH inequality is 1.

######  Theorem 19.

Let $\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$. Let
$T:(\mathbb{K}^{n})^{d}\to\mathbb{K}$ be a $d$-linear form. Then,

$\left\|{\widehat{T}}\right\|_{\frac{2d}{d+1}}\leq\left\|{T}\right\|_{{\mathrm{cb}}},$

and the equality can be witnessed.

Theorem 19 establishes that the best constant for the completely bounded BH
inequality is exactly $1$. This sharply contrasts with the current knowledge
about the Grothendieck constants, and specially with the BH constants, where
only poly($d$) upper bounds are known. This way, we _close_ one of the edges
of comparison of the three norms that appear in Grothendieck and Bohnenblust-
Hille inequalities (see Fig. 3).

$\lVert B\rVert_{\infty}$$\lVert B\rVert_{\frac{2d}{d+1}}$$\lVert
B\rVert_{{\mathrm{cb}}}$$\leq\sqrt{2}$$G_{\mathbb{R}}\geq$$\leq 1$

$\lVert T\rVert_{\infty}$$\lVert T\rVert_{\frac{2d}{d+1}}$$\lVert
T\rVert_{{\mathrm{cb}}}$$\leq\mbox{\rm poly}(d)$$C(d)\not\geq$$\leq 1$

Figure 3: Triangles of norm comparisons. In the left triangle we display the
norm comparisons implied by the Littlewood [Lit30] and Grothendieck
inequalities [Gro53] and our Theorem 19 for real bilinear maps. In the right
triangle we depict the best upper bound for the BH constant [BPSS14], the no
extension of the Grothendieck inequality [PGWP+08], and our Theorem 19 for
$d$-linear tensors.

The main ingredient of the proof of Theorem 19 is a general lower bound for
the completely bounded norm, Lemma 21. This technique is inspired on an idea
of Varoupoulos to rule out a generalization of von Neumann’s inequality
[Var74] and was already used by the third author to show a particular case of
the famous Aaronson and Ambainis conjecture of quantum query complexity
[Esc23]. Combining Lemma 21 with Blei’s inequality (Lemma 20), Theorem 19
follows. For a proof of Blei’s inequality see [BPSS14, Theorem 2.1].

######  Lemma 20 (Blei’s inequality).

Let $\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$ and let
$\widehat{T}\in(\mathbb{K})^{n^{d}}$. Then,

$\left(\prod_{s\in[d]}\sum_{i_{s}\in[n]}\sqrt{\sum_{i_{1},\dots,i_{s-1},i_{s+1},\dots,i_{d}\in[n]}|\widehat{T}_{\mathbf{i}}|^{2}}\right)^{\frac{1}{d}}\geq\left\|{\widehat{T}}\right\|_{\frac{2d}{d+1}}.$

######  Lemma 21.

Let $\mathbb{K}\in\\{\mathbb{R},\mathbb{C}\\}$, let
$T:(\mathbb{K}^{n})^{d}\to\mathbb{K}$ be a $d$-linear form, and let $s\in[d]$.
Then,

$\left\|{T}\right\|_{{\mathrm{cb}}}\geq\sum_{i_{s}\in[n]}\sqrt{\sum_{i_{1},\dots,i_{s-1},i_{s+1},\dots,i_{d}\in[n]}|\widehat{T}_{\mathbf{i}}|^{2}}.$

  * Proof:

Let us fix $s\in[d]$. The proof consists on evaluating Eq. 23 on an explicit
set of contractions (matrices with operator norm at most 1). Let
$m=\sum_{r=0}^{d-r}n^{r}+\sum_{r=0}^{s-1}n^{r}$ and let
$\\{e_{\mathbf{i}},f_{\mathbf{j}}:\,\mathbf{i}\in[n]^{r},\,r\in\\{0\\}\cup[d-s],\,\mathbf{j}\in[n]^{t},\,t\in\\{0\\}\cup[s-1]\\}$
be an orthonormal basis of $\ell_{2}^{m}(\mathbb{K}),$ where we identify
$[n]^{0}$ with $\emptyset$. We define matrices $X(i)\in\mathcal{M}_{m}$ for
$i\in[n]$ by

$\displaystyle X(i)e_{\mathbf{j}}$ $\displaystyle=e_{(i,\mathbf{j})},\
\mathrm{if\ }\mathbf{j}\in[n]^{r},\ r\in\\{0\\}\cup[d-s-1],$ $\displaystyle
X(i)e_{\mathbf{j}}$
$\displaystyle=\frac{\sum_{\mathbf{k}\in[n]^{s-1}}\widehat{T}_{\mathbf{k}i\mathbf{j}}^{*}f_{\mathbf{k}}}{\sqrt{\sum_{k_{1},\dots,k_{s-1},k_{s+1},\dots,k_{d}\in[n]}|\widehat{T}|^{2}_{(k_{1},\dots,k_{s-1},i,k_{s+1},\dots,k_{d})}}},\
\mathrm{if\ }\mathbf{j}\in[n]^{d-s},$ $\displaystyle X(i)f_{\mathbf{j}}$
$\displaystyle=\delta_{i,j_{t}}f_{(j_{1},\dots,j_{t-1})},\ \mathrm{if}\
\mathbf{j}\in[n]^{d-t},\ t\in\\{0\\}\cup[d-1].$

To give some intuition of the behaviour of these matrices, one may interpret
the first $d-s$ applications of the matrices $X(i)$ as _creation_ operators
and the last $s-1$ as _destruction_ operators.

Assume for the moment that $X(i)$ are contractions. Given that

$\displaystyle\langle f_{\emptyset},X(i_{1})\dots
X(i_{d})e_{\emptyset}\rangle=\frac{\widehat{T}_{\mathbf{i}}^{*}}{\sqrt{\sum_{i_{1},\dots,i_{s-1},i_{s+1},\dots,i_{d}\in[n]}|\widehat{T}_{\mathbf{i}}}|^{2}},$

it would then follow that

$\displaystyle\left\|{T}\right\|_{{\mathrm{cb}}}$
$\displaystyle\geq\left\|{\sum_{\mathbf{i}\in[n]^{d}}\widehat{T}_{\mathbf{i}}X(i_{1})\dots
X(i_{d})}\right\|_{\operatorname{op}}$
$\displaystyle\geq\sum_{\mathbf{i}\in[n]^{d}}\widehat{T}_{\mathbf{i}}\langle
f_{\emptyset},X(i_{1})\dots X(i_{d})e_{\emptyset}\rangle$
$\displaystyle\geq\sum_{\mathbf{i}\in[n]^{d}}\widehat{T}_{\mathbf{i}}\frac{\widehat{T}_{\mathbf{i}}^{*}}{\sqrt{\sum_{k_{1},\dots,k_{s-1},k_{s+1},\dots,k_{d}\in[n]}|\widehat{T}|^{2}_{(k_{1},\dots,k_{s-1},i_{s},k_{s+1},\dots,k_{d})}}}$
$\displaystyle=\sum_{i_{s}\in[n]}\sqrt{\sum_{i_{1},\dots,i_{s-1},i_{s+1},\dots,i_{d}\in[n]}|\widehat{T}_{\mathbf{i}}|^{2}},$

as desired. Thus, it just remains to prove that the matrices $X(i)$ are
contractions. Given that $X(i)$ maps
$\\{e_{\mathbf{i}}:\,\mathbf{i}\in[n]^{r},\,r\in\\{0\\}\cup[d-s-1]\\}$,
$\\{e_{\mathbf{i}}:\,\mathbf{i}\in[n]^{d-s}\\}$ and
$\\{f_{\mathbf{i}}:\,\mathbf{i}\in[n]^{t},\,t\in\\{0\\}\cup[s]\\}$ to
orthogonal subspaces, it suffices to show that the $X(i)$ are contractions
when restricted to those subspaces. For the first and third sets that is true
because $X(i)$ maps each basis vector of those sets to a different basis
vector or to $0$. For the second set, is also true because for every
$\lambda\in\mathbb{K}^{n^{d-s}}$

$\displaystyle\left\|{X(i)\sum_{\mathbf{j}\in[n]^{d-s}}\lambda_{\mathbf{j}}e_{\mathbf{j}}}\right\|_{2}^{2}$
$\displaystyle=\left\|{\frac{\sum_{\mathbf{k}\in[n]^{s-1}}(\sum_{\mathbf{j}\in[n]^{d-s}}\lambda_{\mathbf{j}}\widehat{T}_{\mathbf{k}i\mathbf{j}}^{*})f_{\mathbf{k}}}{\sqrt{\sum_{k_{1},\dots,k_{s-1},k_{s+1},\dots,k_{d}\in[n]}|\widehat{T}_{k_{1},\dots,k_{s-1},i,k_{s+1},\dots,k_{d}}|^{2}}}}\right\|_{2}^{2}$
$\displaystyle=\frac{\sum_{\mathbf{k}\in[n]^{s-1}}|\sum_{\mathbf{j}\in[n]^{d-s}}\lambda_{\mathbf{j}}\widehat{T}_{\mathbf{k}i\mathbf{j}}^{*}|^{2}}{\sum_{k_{1},\dots,k_{s-1},k_{s+1},\dots,k_{d}\in[n]}|\widehat{T}_{k_{1},\dots,k_{s-1},i,k_{s+1},\dots,k_{d}}|^{2}}$
$\displaystyle\leq\frac{\Big{(}\sum_{\mathbf{k}\in[n]^{s-1}}\sum_{\mathbf{j}\in[n]^{d-s}}|\widehat{T}_{\mathbf{k}i\mathbf{j}}^{*}|^{2}\Big{)}\Big{(}\sum_{\mathbf{j}\in[n]^{d-s}}|\lambda_{\mathbf{j}}|^{2}\Big{)}}{\sum_{k_{1},\dots,k_{s-1},k_{s+1},\dots,k_{d}\in[n]}|\widehat{T}_{k_{1},\dots,k_{s-1},i,k_{s+1},\dots,k_{d}}|^{2}}$
$\displaystyle=\sum_{\mathbf{j}\in[n]^{d-s}}|\lambda_{\mathbf{j}}|^{2}=\left\|{\lambda}\right\|^{2}_{2},$

where we have used Cauchy-Schwarz for the sum over $\mathbf{j}$. $\Box$

  * Proof of Theorem 19:

The inequality
$\|\widehat{T}\|_{\frac{2d}{d+1}}\leq\left\|{T}\right\|_{{\mathrm{cb}}}$
follows from Lemmas 20 and 21. The inequality is saturated by the form
$T(x_{1},\dots,x_{d})=x_{1}(1).$ $\Box$

## References

  * [AA15] Scott Aaronson and Andris Ambainis.  Forrelation: A problem that optimally separates quantum from classical computing.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 307–316, New York, NY, USA, 2015. Association for Computing Machinery.  doi:10.1145/2746539.2746547.
  * [AAI+16] Scott Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, and Juris Smotrovs.  Polynomials, quantum query complexity, and Grothendieck’s inequality.  In 31st Conference on Computational Complexity, CCC 2016, pages 25:1–25:19, 2016.  arXiv:1511.08682.
  * [ABDY23] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder.  Optimal Algorithms for Learning Quantum Phase States.  In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:24, 2023.
  * [ABP19] Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos.  Quantum query algorithms are completely bounded forms.  SIAM J. Comput, 48(3):903–925, 2019.  Preliminary version in ITCS’18.
  * [ACK+21] Srinivasan Arunachalam, Sourav Chakraborty, Michal Kouckỳ, Nitin Saurabh, and Ronald De Wolf.  Improved bounds on Fourier entropy and min-entropy.  ACM Transactions on Computation Theory (TOCT), 13(4):1–40, 2021\.
  * [ACL+21] Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald De Wolf.  Two new results about quantum exact learning.  Quantum, 5:587, 2021.
  * [AN04] Noga Alon and Assaf Naor.  Approximating the cut-norm via Grothendieck’s inequality.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 72–80, New York, NY, USA, 2004. Association for Computing Machinery.  doi:10.1145/1007352.1007371.
  * [AS07] Alp Atıcı and Rocco A Servedio.  Quantum algorithms for learning and testing juntas.  Quantum Information Processing, 6(5):323–348, 2007.
  * [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  J. ACM, 48(4):778–797, 2001.
  * [BH31] Henri Frédéric Bohnenblust and Einar Hille.  On the absolute convergence of Dirichlet series.  Annals of Mathematics, pages 600–622, 1931.
  * [BJ95] Nader H. Bshouty and Jeffrey C. Jackson.  Learning DNF over the uniform distribution using a quantum example oracle.  In Proceedings of the Eighth Annual Conference on Computational Learning Theory, COLT ’95, page 118–127, New York, NY, USA, 1995. Association for Computing Machinery.  doi:10.1145/225298.225312.
  * [BMMN13] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor.  The Grothendieck constant is strictly smaller than Krivine’s bound.  Forum Math. Pi, 1:453–462, 2013.  Preliminary version in FOCS’11. arXiv:1103.6161.
  * [Boh13] Harald Bohr.  Ueber die Bedeutung der Potenzreihen unendlich vieler Variablen in der Theorie der Dirichletschen Reihen.  Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, 1913:441–488, 1913.
  * [BPSS14] Frédéric Bayart, Daniel Pellegrino, and Juan B Seoane-Sepúlveda.  The Bohr radius of the $n$-dimensional polydisk is equivalent to $(\log n)/n$.  Advances in Mathematics, 264:726–746, 2014.
  * [BS21] Nikhil Bansal and Makrand Sinha.  k-forrelation optimally separates quantum and classical query complexity.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1303–1316, New York, NY, USA, 2021. Association for Computing Machinery.  doi:10.1145/3406325.3451040.
  * [BSdW22] Nikhil Bansal, Makrand Sinha, and Ronald de Wolf.  Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms.  In 37th Computational Complexity Conference (CCC 2022), volume 234, pages 28:1–28:21, 2022.  doi:10.4230/LIPIcs.CCC.2022.28.
  * [BT21] Mark Bun and Justin Thaler.  Guest column: Approximate degree in classical and quantum computing.  ACM SIGACT News, 51(4):48–72, 2021.
  * [BY23] Zongbo Bao and Penghui Yao.  On Testing and Learning Quantum Junta Channels.  In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1064–1094. PMLR, 12–15 Jul 2023.  URL: https://proceedings.mlr.press/v195/bao23b.html.
  * [Can20] Clément L Canonne.  A short note on learning discrete distributions.  arXiv preprint arXiv:2002.11457, 2020.
  * [CGJ19] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery.  The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.33, doi:10.4230/LIPIcs.ICALP.2019.33.
  * [CL18] Kai-Min Chung and Han-Hsuan Lin.  Sample efficient algorithms for learning quantum channels in pac model and the approximate state discrimination problem.  arXiv preprint arXiv:1810.10938, 2018.
  * [CLY23] Chi-Fang Chen, Andrew Lucas, and Chao Yin.  Speed limits and locality in many-body quantum dynamics.  Reports on Progress in Physics, 2023.
  * [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen.  Testing and Learning Quantum Juntas Nearly Optimally.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185. SIAM, 2023.
  * [CPT20] WV Cavalcante, DM Pellegrino, and EV Teixeira.  Geometry of multilinear forms.  Communications in Contemporary Mathematics, 22(02):1950011, 2020\.
  * [Dav84] A. Davie.  Lower bound for $K_{G}$.  Unpublished, 1984.
  * [Dav06] AM Davie.  Matrix norms related to Grothendieck’s inequality.  In Banach Spaces: Proceedings of the Missouri Conference held in Columbia, USA, June 24–29, 1984, pages 22–26. Springer, 2006.
  * [DFOC+11] Andreas Defant, Leonhard Frerick, Joaquim Ortega-Cerdà, Myriam Ounaïes, and Kristian Seip.  The Bohnenblust–Hille inequality for homogeneous polynomials is hypercontractive.  Annals of mathematics, pages 485–497, 2011.
  * [DMFPSS14] Diogo Diniz, Gustavo Muñoz-Fernández, Daniel Pellegrino, and J Seoane-Sepúlveda.  Lower bounds for the constants in the Bohnenblust–Hille inequality: The case of real scalars.  Proceedings of the American Mathematical Society, 142(2):575–580, 2014.
  * [DMP19] Andreas Defant, Mieczysław Mastyło, and Antonio Pérez.  On the Fourier spectrum of functions on boolean cubes.  Mathematische Annalen, 374:653–680, 2019.
  * [EI22] Alexandros Eskenazis and Paata Ivanisvili.  Learning low-degree functions from a logarithmic number of random queries.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 203–207, New York, NY, USA, 2022. Association for Computing Machinery.  doi:10.1145/3519935.3519981.
  * [EIS22] Alexandros Eskenazis, Paata Ivanisvili, and Lauritz Streck.  Low-degree learning and the metric entropy of polynomials.  arXiv preprint arXiv:2203.09659, 2022.
  * [Esc23] Francisco Escudero Gutiérrez.  Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms.  arXiv:2304.06713, 2023.
  * [FO21] Steven T Flammia and Ryan O’Donnell.  Pauli error estimation via population recovery.  Quantum, 5:549, 2021.
  * [FOF23] Omar Fawzi, Aadil Oufkir, and Daniel Stilck França.  Lower bounds on learning Pauli channels.  arXiv preprint arXiv:2301.09192, 2023.
  * [FW20] Steven T. Flammia and Joel J. Wallman.  Efficient estimation of Pauli channels.  ACM Transactions on Quantum Computing, 1(1), dec 2020.  doi:10.1145/3408039.
  * [GJ14] Gus Gutoski and Nathaniel Johnston.  Process tomography for unitary quantum channels.  Journal of Mathematical Physics, 55(3), 2014.
  * [Gro53] Alexandre Grothendieck.  Résumé de la théorie métrique des produits tensoriels topologiques.  Soc. de Matemática de São Paulo, 1953.
  * [Haa87] Uffe Haagerup.  A new upper bound for the complex Grothendieck constant.  Israel Journal of Mathematics, 60:199–224, 1987.
  * [HCP23] Hsin-Yuan Huang, Sitan Chen, and John Preskill.  Learning to predict arbitrary quantum processes.  PRX Quantum, 4:040337, Dec 2023.  URL: https://link.aps.org/doi/10.1103/PRXQuantum.4.040337, doi:10.1103/PRXQuantum.4.040337.
  * [HHJ+17] Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.  Sample-optimal tomography of quantum states.  IEEE Transactions on Information Theory, 63(9):5628–5641, 2017\.
  * [HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.
  * [HYF21] Robin Harper, Wenjun Yu, and Steven T. Flammia.  Fast estimation of sparse quantum noise.  PRX Quantum, 2:010322, Feb 2021.
  * [IRR+21] Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, and Amir Yehudayoff.  Tight bounds on the Fourier growth of bounded functions on the hypercube.  arXiv preprint arXiv:2107.06309, 2021.
  * [KMY03] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami.  Quantum merlin-arthur proof systems: Are multiple merlins more helpful to arthur?  In Algorithms and Computation: 14th International Symposium, ISAAC 2003, pages 189–198. Springer, 2003.
  * [KSVZ24] Ohad Klein, Joseph Slote, Alexander Volberg, and Haonan Zhang.  Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality.  In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:22, 2024.
  * [LC22] Ching-Yi Lai and Hao-Chung Cheng.  Learning quantum circuits of T-depth one.  In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2213–2218, 2022.  doi:10.1109/ISIT50566.2022.9834452.
  * [Lit30] John E Littlewood.  On bounded bilinear forms in an infinite number of variables.  The Quarterly Journal of Mathematics, pages 164–174, 1930.
  * [LMN93] Nathan Linial, Yishay Mansour, and Noam Nisan.  Constant depth circuits, Fourier transform, and learnability.  Journal of the ACM (JACM), 40(3):607–620, 1993.
  * [Low09] Richard A. Low.  Learning and testing algorithms for the clifford group.  Phys. Rev. A, 80:052314, Nov 2009.
  * [MFPCSS12] GA Muñoz-Fernández, D Pellegrino, J Ramos Campos, and JB Seoane-Sepúlveda.  A geometric technique to generate lower estimates for the constants in the bohnenblust–hille inequalities.  arXiv preprint arXiv:1203.0793, 2012.
  * [MGE12] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson.  Characterizing quantum gates via randomized benchmarking.  Phys. Rev. A, 85:042311, Apr 2012.  URL: https://link.aps.org/doi/10.1103/PhysRevA.85.042311, doi:10.1103/PhysRevA.85.042311.
  * [MO08] Ashley Montanaro and Tobias J Osborne.  Quantum Boolean functions.  arXiv preprint arXiv:0810.2435, 2008.
  * [Mon12] Ashley Montanaro.  Some applications of hypercontractive inequalities in quantum information theory.  Journal of Mathematical Physics, 53(12), 2012.
  * [NAPSSSR13] D Nuñez-Alarcón, Daniel Pellegrino, Juan B Seoane-Sepúlveda, and DM Serrano-Rodríguez.  There exist multilinear Bohnenblust–Hille constants $c_{n}$ with $\lim(c_{n+1}-c_{n})$= 0.  Journal of Functional Analysis, 264(2):429–463, 2013.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, Cambridge, UK, 2010.  doi:10.1017/CBO9780511976667.
  * [NPVY23] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen.  On the Pauli spectrum of QAC0.  arXiv preprint arXiv:2311.09631, 2023.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [OW16] Ryan O’Donnell and John Wright.  Efficient quantum tomography.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery.  doi:10.1145/2897518.2897544.
  * [Pau03] Vern Paulsen.  Completely Bounded Maps and Operator Algebras.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 02 2003.
  * [PGWP+08] David Pérez-García, Michael M Wolf, Carlos Palazuelos, Ignacio Villanueva, and Marius Junge.  Unbounded violation of tripartite Bell inequalities.  Communications in Mathematical Physics, 279:455–486, 2008.
  * [Pis12] Gilles Pisier.  Grothendieck’s theorem, past and present.  Bulletin of the American Mathematical Society, 49(2):237–323, 2012\.
  * [PSS12] Daniel Pellegrino and Juan B Seoane-Sepúlveda.  New upper bounds for the constants in the Bohnenblust–Hille inequality.  Journal of Mathematical Analysis and Applications, 386(1):300–307, 2012.
  * [PT18] Daniel Pellegrino and Eduardo V Teixeira.  Towards sharp Bohnenblust–Hille constants.  Communications in Contemporary Mathematics, 20(03):1750029, 2018\.
  * [Ree91] J. Reeds.  A new lower bound on the real Grothendieck constant.  Manuscript (http://www.dtc.umn.edu/~reedsj/bound2.dvi), 1991.
  * [SVZ23a] Joseph Slote, Alexander Volberg, and Haonan Zhang.  Bohnenblust–Hille inequality for cyclic groups.  arXiv preprint arXiv:2305.10560, 2023.
  * [SVZ23b] Joseph Slote, Alexander Volberg, and Haonan Zhang.  Noncommutative bohnenblust-hille inequality in the heisenberg-weyl and gell-mann bases with applications to fast learning.  arXiv preprint arXiv:2301.01438, 2023.
  * [Ter15] Barbara M. Terhal.  Quantum error correction for quantum memories.  Rev. Mod. Phys., 87:307–346, Apr 2015.
  * [Tsi80] B. S. Tsirelson.  Quantum generalizations of Bell’s inequality.  Letters in Mathematical Physics, 1980.  doi:10.1007/BF00417500.
  * [TST23] Minh C Tran, Kunal Sharma, and Kristan Temme.  Locality and error mitigation of quantum circuits.  arXiv preprint arXiv:2303.06496, 2023.
  * [Val84] Leslie G. Valiant.  A Theory of the Learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [Var74] N. Th. Varopoulos.  On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory.  J. Functional Analysis, 16:83–100, 1974.  doi:10.1016/0022-1236(74)90071-8.
  * [VCJ18] Fernando Vieira Costa Júnior.  The optimal multilinear Bohnenblust–Hille constants: A computational solution for the real case.  Numerical Functional Analysis and Optimization, 39(15):1656–1668, 2018.
  * [VDBMKT23] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala, and Kristan Temme.  Probabilistic error cancellation with sparse Pauli–Lindblad models on noisy quantum processors.  Nature Physics, pages 1–6, 2023.
  * [VZ23] Alexander Volberg and Haonan Zhang.  Noncommutative Bohnenblust–Hille inequalities.  Mathematische Annalen, pages 1–20, 2023.

##  Appendix A Learning low-degree Pauli channels

In this section, we consider learning low-degree Pauli channels, a special
case of general quantum channels and prove the following theorem. See 2

We define the orthonormal basis for Pauli channels as follows. For any
$x\in\\{0,1,2,3\\}^{n}$, let $\Phi_{x}=\sigma_{x}\rho\sigma_{x}$. For Pauli
channels $\Phi$, the Pauli expansion is then

$\Phi=\sum_{x\in\\{0,1,2,3\\}^{n}}\widehat{\Phi}(x)\Phi_{x},$ (36)

where $\widehat{\Phi}(x)$ are the Fourier coefficients corresponding to the
characters $\Phi_{x}$. It can then be immediately shown that the Fourier
coefficients $\widehat{\Phi}(x)$ are nothing but the error rates $p_{x}$. Our
goal is learning a classical description of the Pauli channel $\Phi$ within
$\varepsilon$-diamond norm. The diamond norm between two Pauli channels is
equivalent to twice the total variation distance between their corresponding
probability distributions (or error rates) [MGE12]. We thus aim to learn the
probability distribution $\widehat{\Phi}=\\{\widehat{\Phi}(x)\\}_{x}$ over the
error rates of a Pauli channel within $\varepsilon/2$ total variation
distance.

The eigenvalues of a Pauli channel are given by
$\lambda_{s}=\frac{1}{2^{n}}\operatorname{Tr}(\sigma_{s}\Phi(\sigma_{s}))$.
They are related to the error rates by a Fourier transform:

$\displaystyle\lambda_{k}=\sum_{j\in\\{0,1,2,3\\}^{n}}(-1)^{[\sigma_{k},\sigma_{j}]}p_{j},\quad
p_{k}=\frac{1}{4^{n}}\sum_{j\in\\{0,1,2,3\\}^{n}}(-1)^{[\sigma_{k},\sigma_{j}]}\lambda_{j}$
(37)

Most approaches for learning Pauli channels [FW20, HYF21] which have prior
information regarding the sparsity in $\widehat{\Phi}$ have attempted to learn
the channel by estimating the channel’s eigenvalues. In contrast, we directly
estimate error rates.

Let us warm-up by giving a learning algorithm for low-degree Pauli channels
when given access to entanglement.

######  Theorem 22.

Let $\Phi$ be an $n$-qubit degree-$d$ channel. There is an algorithm that
$(\varepsilon,\delta)$-learns $\Phi$ (in diamond norm) using
$O\left(n^{d}/{\varepsilon^{2}}+1/\varepsilon^{2}\cdot\log({1}/{\delta})\right)$
queries to $\Phi$.

  * Proof:

Let $J(\Phi)$ be the CJ state of $\Phi$. If we measure $J(\Phi)$ in the Bell
basis, we sample $x\in\\{0,1,2,3\\}^{n}$ with probability $\widehat{\Phi}(x)$
as long as $|x|\leq d$. By [Can20, Theorem 1], measuring $J(\Phi)$,
$O\left(\frac{3^{d}n^{d}}{\varepsilon^{2}}+\frac{1}{\varepsilon^{2}}\log\frac{1}{\delta}\right)$
times we learn the corresponding probability distribution
$\\{\widehat{\Phi}(x)\\}_{x}$ of the Pauli channel in total variation distance
of $\varepsilon$ with probability $1-\delta$. This translates to learning the
corresponding Pauli channel in $\varepsilon$-diamond norm. $\Box$

We now describe our learning algorithm for low-degree Pauli channels that does
not require any access to entanglement and can be implemented on near-term
quantum devices. As part of the learning algorithm, we apply the Pauli channel
$\Phi$ to a product state $\rho$ and then measure $\Phi(\rho)$ in the Pauli
basis. Let us describe what these product states, measurements and the
resulting outcomes are. Let us first recall from Section 2 that we denote the
$\pm 1$ eigenstates of a single-qubit Pauli $\sigma_{j}$ (where
$j\in\\{1,2,3\\}$) by $|\chi_{\pm 1}^{j}\rangle$. The algorithm repeats the
following procedure $T$ times: pick a uniformly random $s\in\\{1,2,3\\}^{n}$,
prepare the product state
$\rho_{s}=\otimes_{j=1}^{s}\ket{\chi_{+1}^{s_{j}}}\bra{\chi_{+1}^{s_{j}}}$,
apply $\Phi$, measure $\Phi(\rho_{s})$ in the Pauli basis $\sigma_{s}$, and
store the outcome $r$. The remaining of the section is devoted to show that
with a few repetitions of this procedure, one can recover $\Phi$ from the
outcomes $r$. The first thing to do is to determine the behaviour of $r$ as
random variable. To express it in a concise way, we introduce the following
‘$\star$’ operation. Given $s,x\in\\{0,1,2,3\\}$, $(s\star x)$ is the element
of $\\{0,1\\}^{n}$ defined by

$(s\star x)_{j}=\left\\{\begin{array}[]{ll}0&\mathrm{if}\
[\sigma_{s_{j}},\sigma_{x_{j}}]=0,\\\
1&\mathrm{otherwise},\end{array}\right.\quad\forall j\in[n].$ (38)

######  Proposition 23.

Let $\Phi_{x}(\rho)=\sigma_{x}\rho\sigma_{x}$ be the superoperator
corresponding to $x\in\\{0,1,2,3\\}^{n}$ and let $s\in\\{1,2,3\\}^{n}.$
Measuring $\Phi_{x}(\rho_{s})$ in the Pauli basis $\sigma_{s}$ produces the
measurement outcome $r=s\star x$.

  * Proof:

Upon measuring the $j$th qubit of the state $\sigma_{x}\rho_{s}\sigma_{x}$ in
basis $\sigma_{s}$, the probability of the measurement outcome
$r_{j}\in\\{0,1\\}$ is given by

$\displaystyle\mbox{\rm Pr}[r_{j}=0]$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left(\sigma_{s_{j}}\sigma_{x_{j}}\ket{\chi_{+1}^{s_{j}}}\bra{\chi_{+1}^{s_{j}}}\sigma_{x_{j}}\right)$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left(\sigma_{x_{j}}\sigma_{s_{j}}\sigma_{x_{j}}\ket{\chi_{+1}^{s_{j}}}\bra{\chi_{+1}^{s_{j}}}\right)$
$\displaystyle=\frac{1}{2}+\frac{1}{2}(-1)^{[\sigma_{s_{j}},\sigma_{x_{j}}]}\operatorname{Tr}\left(\sigma_{s_{j}}\ket{\chi_{+1}^{s_{j}}}\bra{\chi_{+1}^{s_{j}}}\right)$
$\displaystyle=\frac{1+(-1)^{[\sigma_{s_{j}},\sigma_{x_{j}}]}}{2},$

where we used the fact
$\sigma_{a}\sigma_{b}\sigma_{a}=(-1)^{[\sigma_{a},\sigma_{b}]}\sigma_{b}$ for
any $a,b\in\\{0,1,2,3\\}^{n}$ in the third line and $\ket{\chi_{+1}^{s_{j}}}$
is the $+1$ eigenstate of $\sigma_{s_{j}}$. Note from the above probability
expression, we have that $r_{j}$ takes the value of $0$ if $\sigma_{s_{j}}$
and $\sigma_{x_{j}}$ commute and $1$, otherwise. This proves the desired
result. $\Box$

Let $\\{(s^{(t)},r^{(t)})\\}_{t\in[T]}$ be the samples obtained by our
algorithm. We now describe how to learn the Pauli coefficients (or error
rates) $\widehat{\Phi}(x)$ from these $T$ samples, and thereby learn the Pauli
channel. The following empirical estimation gives us an estimate of the Pauli
coefficients, which we denote by $\widetilde{\Phi}(x)$

$\widetilde{\Phi}(x)=\frac{1}{T}\sum_{t=1}^{T}\left[\left(-\frac{1}{2}\right)^{\left(\sum\limits_{j\in\text{supp}(x)}r^{(t)}_{j}\oplus({s^{(t)}_{j}}\star
x_{j})\right)\oplus\left(\sum\limits_{j\notin\text{supp}(x)}r^{(t)}_{j}\right)}\right],$
(39)

where we have used $\oplus$ to denote addition modulo $2$, the operation
‘$\star$’ which was defined in Prop. 23 and $\text{supp}(x)$ denotes the
support of the string $x$ over non-zero values. Note that the internal
summation involving the Fourier character $x$ is now only over its support
which is at most of size $d$. The empirical estimator of Eq. 39 was proposed
in [FO21]. The following statement argues that the empirical estimate of Eq.
39 is indeed consistent (which was previously shown as part of [FO21, Theorem
22] but is described here for completeness).

######  Proposition 24.

For any $x\in\\{0,1,2,3\\}^{n}$, we have
$\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\widetilde{\Phi}(x)\right]=\widehat{\Phi}(x).$

  * Proof:

Considering the expectation over the empirical estimate and substituting Eq.
39, we have

$\displaystyle\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\widetilde{\Phi}(x)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{s\in\\{1,2,3\\}^{n}}\left[\left(-\frac{1}{2}\right)^{\left(\sum\limits_{j\in\text{supp}(x)}r_{j}\oplus({s_{j}}\star
x_{j})\right)\oplus\left(\sum\limits_{j\notin\text{supp}(x)}r_{j}\right)}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\left(-\frac{1}{2}\right)^{\sum\limits_{j\in[n]}r_{j}\oplus({s_{j}}\star
x_{j})}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{z\sim\widehat{\Phi}}\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\left(-\frac{1}{2}\right)^{\sum\limits_{j\in[n]}({s_{j}}\star
z_{j})\oplus({s_{j}}\star x_{j})}\mid z\right]$
$\displaystyle=\mathop{\mathbb{E}}_{z\sim\widehat{\Phi}}\prod_{j\in[n]}\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\left(-\frac{1}{2}\right)^{({s_{j}}\star
z_{j})\oplus({s_{j}}\star x_{j})}\mid z\right],$ (40)

where we simplified the summation in the second line noting that $x_{j}=0$ for
$j\notin\text{supp}(x)$. In the third line, we used the law of total
expectations considering that the action of a Pauli channels involves the
action of the superoperator $\Phi_{z}$ on the input state with probability
$\widehat{\Phi}(z)$ and which allows us to then use Prop. 23 regarding the
measurement outcome $r$. Note that for a given $z$ and $j\in[n]$,

$\mathop{\mathbb{E}}_{s_{j}\sim\\{1,2,3\\}}\left[\left(-\frac{1}{2}\right)^{({s_{j}}\star
z_{j})\oplus(s_{j}\star x_{j})}\mid z\right]=\begin{cases}1&\text{if
}z_{j}=x_{j},\\\ 0&\text{if }z_{j}\neq x_{j},\\\ \end{cases}$ (41)

which can be readily verified. The expression of Eq. 41 can thus be simply
written as $\mathds{1}\\{z_{j}=x_{j}\\}$. Substituting back into Eq. 40 gives
us

$\mathop{\mathbb{E}}_{s\sim\\{1,2,3\\}^{n}}\left[\widetilde{\Phi}(x)\right]=\mathop{\mathbb{E}}_{z\sim\widehat{\Phi}}\prod_{j\in[n]}\mathds{1}\\{z_{j}=x_{j}\\}=\mathop{\mathbb{E}}_{z\sim\widehat{\Phi}}\mathds{1}\\{z=x\\}=\widehat{\Phi}(x),$
(42)

which is the desired result. This completes the proof. $\Box$

The summary of the learning algorithm for low-degree Pauli channel, described
so far, is presented in Algorithm 2. We now derive its sample complexity.

Algorithm 2 Learning low-degree Pauli channels through unentangled
measurements

Input: Budget $T=O(9^{d}n^{2d})$, access to Pauli channel $\Phi$, parameter
$d$

1:Initialize $\widetilde{\Phi}(x)=0$ for each $x\in S$ with
$S=\\{x:x\in\\{0,1,2,3\\}^{n},\,|x|\leq d\\}$

2:for sample $t=1,\ldots,T$ do

3: Randomly sample string $s\sim\\{1,2,3\\}^{n}$

4: Prepare state
$\rho_{s}=\otimes_{j=1}^{s}\ket{\chi_{+1}^{s_{j}}}\bra{\chi_{+1}^{s_{j}}}$

5: Query Pauli channel $\Phi$ with $\rho_{s}$ to obtain $\Phi(\rho_{s})$

6: for qubit $k=1,\ldots,n$ do

7: Measure qubit $k$ of state $\Phi(\rho_{s})$ in Pauli basis $\sigma_{s_{k}}$

8: Save measurement $r^{(t)}_{k}\in\\{0,1\\}$

9:Compute estimates $\widetilde{\Phi}(x)$ using Eq. 39 $\forall x\in S$

Output: $\\{\widetilde{\Phi}(x)\\}_{x\in S}$

  * Proof of Proposition 2:

We learn the channel $\Phi$ by estimating the Fourier coefficients
$\widehat{\Phi}(x)$ for each $x\in S$ with
$S=\\{x:x\in\\{0,1,2,3\\}^{n},\,|x|\leq d\\}$. Suppose that we use $T$
measurement outcomes from the learning algorithm in Algorithm 2, then we can
estimate $\widehat{\Phi}(x)$ using the empirical estimator from Eq. 39.
Combining with Prop. 24, we have by Hoeffding’s inequality that

$\mbox{\rm Pr}[|\widetilde{\Phi}(x)-\widehat{\Phi}(x)|\geq a]\leq
2\exp(-2a^{2}T).$ (43)

To learn the channel $\Phi$ within $\varepsilon$-diamond norm, it is enough to
learn the probability distribution
$\widehat{\Phi}=\\{\widehat{\Phi}(x)\\}_{x}$ in total variation distance of
$\varepsilon/2$. We require

$\frac{1}{2}\|\widetilde{\Phi}-\widehat{\Phi}\|_{1}=\frac{1}{2}\sum_{x\in
S}|\widetilde{\Phi}(x)-\widehat{\Phi}(x)|\leq\frac{a}{2}3^{d}n^{d}\leq\frac{\varepsilon}{2}.$
(44)

To ensure we learn $\Phi$ with probability $1-\delta$, we let
$T=O\left(\frac{9^{d}n^{2d}}{\varepsilon^{2}}\log\frac{n}{\delta}\right)$
after applying the union bound. $\Box$