Estimating operator norms using covering nets

Introduction

In this paper we give new algorithms for several variants of the basic operator norm of interest in quantum information theory, theoretical computer science, and the theory of Banach spaces. Unlike most past work which was based on SDP hierarchies, our algorithms simply enumerate over a carefully chosen net of points. This yields run-times that often match the SDP hierarchies and sometimes improve upon them. Besides improved performance, our algorithms have the advantage of being based on simple geometric properties of spaces we are optimizing over, which may help explain which types of norms are amenable to quasipolynomial optimization. In particular we consider the following four optimization problems in this work:

Optimization over Separable States: An important problem in quantum information theory is to optimize a linear function over the set of separable (i.e. non-entangled) states, defined as bipartite density matrices that can be written as a convex combination of tensor product states. This problem is closely related to the task of determining if a given quantum state is entangled or not (called the quantum separability problem) and to the computation of several other quantities of interest in quantum information, including the optimal acceptance probability of quantum Merlin-Arthur games with unentangled proofs, optimal entanglement witnesses, mean-field ground-state energies, and measures of entanglement; see [HM13] for a review of many of these connections.

The first result on the complexity of computing $h_{\operatorname{Sep}(d_{1},d_{2})}$ was negative: Gurvits showed that the problem is NP-hard for sufficiently small additive error (inverse polynomial in $d_{1}d_{2}$) [Gur03]. Then [HM13] showed there is no $\exp(O(\log^{2-\Omega(1)}(d_{1}d_{2})))$ time algorithm even for a constant error additive approximation of the quantity, assuming the exponential time hypothesis (ETHThe ETH is the conjecture that 3-SAT instances of length $n$ require time $2^{\Omega(n)}$ to solve. This is a plausible conjecture for deterministic, randomized or quantum computation, and each version yields a corresponding lower bound on the complexity of estimating $h_{\operatorname{Sep}}$.). This left open the question whether there are quasipolynomial-time algorithms (i.e. of time $\exp(\operatorname{polylog}(d_{1},d_{2})))$.

In [BCY11] it was shown that this is indeed the case at least for a class of linear functions: namely those corresponding to quantum measurements that can be implemented by local operations and one-directional classical communication (one-way LOCC or 1-LOCC). For this particular class of measurements the problem can be solved with error $\delta$ in time $\exp\left(O\left(\delta^{-2}\log(d_{1})\log(d_{2})\right)\right)$. The proof was based on showing that the hierarchy of semidefinite programs for the problem introduced in 2004 by Doherty, Parrilo and Spedalieri [DPS04] (which is an application of the more general Sum-of-Squares (SoS) hierarchy, also known as the Lasserre hierarchy, to the separability problem) converges quickly. The approach of [BCY11] was to use ideas from quantum information theory (monogamy of entanglement, entanglement measures, hypothesis testing, etc) to find good bounds on the quality of the SoS hierarchy. Since then several follow-up work gave different proofs of the result, but always using quantum information-theoretic ideas [BH13, LW14, BC11, Yan06].

A corollary of [BCY11] and the other results on 1-LOCC $M$ is that $h_{\operatorname{Sep}(d_{1},d_{2})}(M)$ can also be approximated for a different class of operators $M$: those with small Hilbert-Schmidt norm $\|M\|_{\text{HS}}:=\operatorname{tr}(M^{\cal y}M)^{\frac{1}{2}}$. Ref. [BaCY11] showed that also in this case there is a quasipolynomial-time algorithm for estimating Eq. (1). An interesting subsequent development was the work of Shi and Wu [SW12] (see also [BKS13]), who gave a different algorithm for the problem based on enumerating over nets. It was left as an open question whether a similar approach could be given for the case of one-way LOCC measurements (which is more relevant both physically The one-way LOCC norm gives the optimal distinguishably of two multipartite quantum states when only local measurements can be done, and the parties can coordinate by one-directional communication. See [MWW09] for a discussion of its power. and in terms of applications; see again [HM13]).

Estimating the Output Purity of Quantum Channels: Another important optimization problem in quantum information theory consists of determining how much noise a quantum channel introduces. A quantum channel models a general physical evolution and is given mathematically by a completely positive trace preserving map $\Lambda:\mathcal{D}_{d_{1}}\rightarrow\mathcal{D}_{d_{2}}$. One way to measure the level of noise of the channel is to compute the maximum over states of the output Schatten-$\alpha$ norm, for a given $\alpha>1$:

with $\|Z\|_{\alpha}=\operatorname{tr}(|Z|^{\alpha})^{\frac{1}{\alpha}}$. The quantity $\|\Lambda\|_{1\rightarrow\alpha}$ varies from one, for an ideal channel, to $d_{2}^{-1+\alpha^{-1}}$ for the depolarizing channel mapping all states to the maximally mixed state. This optimization problem has been extensively studied, in particular because for $\alpha\approx 1$ it is related to the Holevo capacity of the channel, whose regularization gives the classical capacity of the channel (i.e. how many reliable bits can be transmitted per use of the channel).

It was shown in [HM13] that, assuming ETH, there is no algorithm that runs in time $\exp(O(\log^{2-\Omega(1)}{(d)}))$ and can decide if $\|\Lambda\|_{1\rightarrow\alpha}$ is one or smaller than $\delta$ (for any fixed $\delta>0$ and $\alpha>1$) for a general quantum channel $\Lambda:{\cal D}_{d}\rightarrow{\cal D}_{d}$. On the algorithmic side, nothing better than exhaustive search over the input space (taking time $\exp(\Omega(d_{1}))$) is known.

An interesting subclass of quantum channels, lying somewhere between classical channels and fully quantum channels, are the so-called entanglement-breaking channels, which are the channels that cannot be used to distribute entanglement. Any entanglement-breaking quantum channel $\Lambda$ can be written as [HSR04]:

with $Y_{i}\geq 0$, $\operatorname{tr}(Y_{i})=1$ quantum states and $X_{i}\geq 0$, and $\sum_{i}X_{i}=I$ a quantum measurement. Because of their simpler form, one can expect that there are more efficient algorithms for computing the maximum output norm of entanglement-breaking channels. However until now no algorithm better than exhaustive search was known either (apart from the case $\alpha=\infty$ where the Sum-of-Squares hierarchy can be used and analyzed using [BCY11]).

Computing $p\rightarrow q$ Norms: Given a $d_{1}\times d_{2}$ matrix $A$ we define its $p\rightarrow q$ norm by

On the algorithmic side, besides the $2\rightarrow 2$ and $2\rightarrow\infty$ norms being exactly computable in polynomial time, Ref. [BBH+12] showed that one can use the Sum-of-Squares hierarchy to compute in time $\exp(O(\log^{2}(n)\varepsilon^{-2}))$ a number $X$ s.t.

Whether similar approximations can be obtained for $2\rightarrow q$ norms for other values of $q$ was left as an open problem.

Computing the Operator Norm between Banach Spaces: These problems are all special cases of the following general question. Given a map $T:\mathcal{A}\rightarrow\mathcal{B}$ between Banach spaces $\mathcal{A},\mathcal{B}$, can we approximately compute the following operator norm?

In this paper we give new algorithmic results for the four problems discussed above. They can be summarized as follows.

Separable-state optimization by covering nets: We give a different algorithm for optimizing linear functions over separable states (corresponding to one-way LOCC measurements) based on enumerating over covering nets (see Algorithm 1). The complexity of the algorithm matches the time complexity of [BCY11] (see Theorem 2). The proof does not use information theory in any way, nor the SoS hierarchy. Instead the main technical tool is a matrix version of the Hoeffding bound (see Lemma 3). It gives new geometric insight into the problem and gives arguably the simplest and most self-contained proof of the result to date. It also gives an explicit rounding (as does [BH13] but in contrast to [BCY11, LW14, BC11, Yan06]).

For particular subclasses of one-way LOCC measurements our algorithm improves the run time of [BCY11]. One example is the case where Bob’s measurement outcomes are low rank, in which we find a $\operatorname{poly}(d_{2})d_{1}^{O(\varepsilon^{-2})}$-time algorithm.

Generalization to arbitrary operator norms: Computing $h_{\operatorname{Sep}}$ is mathematically equivalent to computing the $1\rightarrow\infty$ norm of a quantum channel, or more precisely the $S_{1}\rightarrow S_{\infty}$ norm where $S_{\alpha}$ denotes the Schatten-$\alpha$ norm. This perspective will help us generalize the scope of our algorithm, to estimating the $S_{1}\rightarrow\mathcal{B}$ norm for a general Banach space $\mathcal{B}$. The analysis of this algorithm is based on tools from asymptotic geometric analysis, and we will see that its efficiency depends on properties of $\mathcal{B}$ known as the Rademacher type and the modulus of uniform smoothness. Besides generalizing the scope of the algorithm, this also gives more of a geometric explanation of its performance. We focus on two special cases of the problem:

maximum output norm: A particular case of the generalization is the problem of computing the maximum output purity of a quantum entanglement-breaking channel (measured in the Schatten-$\alpha$ norms). We prove that for any $\alpha>1$ one can compute $\|\Lambda\|_{1\rightarrow\alpha}$ in time $\operatorname{poly}(d_{2})d_{1}^{O(\varepsilon^{-2})}$ to within additive error $\varepsilon$. (see Corollary 16). In contrast known hardness results [HM10, HM13] show that no such algorithm exists for general quantum channels (under the exponential time hypothesis). Previously the entanglement-breaking case was not known to be easier.

matrix $2\rightarrow q$ norms: As a second particular case of the general framework we extend the approximation of [BBH+12] to the $2\rightarrow 4$ norm, given in Eq. (6), to the $2\rightarrow q$ norms for all $q\geq 2$ (see Corollary 17).

We remark that this generalization is not completely for free, so we cannot simply derive all our other algorithms from this final one. In the case where $\mathcal{A}=S_{1}^{d}$ (which corresponds to all of our specific applications), we are able to easily sparsify the input; i.e. given $\sum_{i=1}^{n}A_{i}\otimes B_{i}$, we can reduce $n$ to be $\operatorname{poly}(d)$ without loss of generality. For general input spaces $\mathcal{A}$ we do not know if this is possible. Also, the case of $h_{\operatorname{Sep}}$ is much simpler, and so it may be helpful to read it first.

2 Comparison with prior work

As discussed in the introduction, previous algorithms for separable-state optimization (and as a corollary, the $2\rightarrow 4$ norm) have been obtained using SDP hierarchies. Our algorithms generally match or improve upon their parameters, but with the added requirement for the separable-state problem that the input be presented in a more structured form.

Several parallels between LP/SDP hierarchies and net-based algorithms have been developed for other problems. The first example of this was Ref. [DKLP06a] which gave both types of algorithms for the problem of maximizing a polynomial over the simplex, improving on a result implicit in the 1980 proof of the finite de Finetti theorem by Diaconis and Freedman [DF80]. Besides the separable-state approximation problem that we study, hierarchies and nets have been found to have similar performance in finding approximate Nash equilibria [LMM03, Har15] and in estimating the value of free two-prover games [AIM14, BH13]. The state-of-the-art run-time for solving Unique Games and Small Set Expansion have also been achieved using both hierarchies and covering-nets. These parallels are summarized in the table:

While this paper focuses on the particular problems where we can improve upon the state-of-the-art algorithms, we hope to be a step towards more generally understanding the connections between these two methods. In almost every case above, the best covering-net algorithms achieve nearly the same complexity as the best analyses of SDP hierarchies. There are a few exceptions. Ref. [BBH+12] shows $O(1)$ rounds of the SoS hierarchy can certify a small value for the Khot-Vishnoi integrality gap instances of the unique games problem, but we do not know how to achieve something similar using nets. A more general example is in [BKS13], which shows that the SoS hierarchy can approximate $h_{\operatorname{Sep}}(M)$ in quasipolynomial time when $M$ is entrywise nonnegative.

The closest related paper to this work is [SW12] by Shi and Wu (as well as Appendix A of [BKS13]), which also used enumeration over $\varepsilon$-nets to approximate $h_{\operatorname{Sep}}$. Here we explain their results in our language.

Achieving a multiplicative approximation is stronger than what our algorithms achieve, but it is at the cost of a runtime that can be exponential in the input size even for a constant-factor approximation. By contrast, our algorithms yield nontrivial approximations in polynomial or quasipolynomial time.

3 Notation

Define the sets of $d\times d$ real and complex semidefinite matrices by $\mathcal{S}^{d}_{+},\mathcal{H}^{d}_{+}$ respectively. For complex vector spaces $V,W$, define ${\cal L}(V,W)$ to be the set of linear operators from $V$ to $W$, ${\cal L}(V):={\cal L}(V,V)$ and $\mathcal{H}(V),\mathcal{H}_{+}(V)$ to be respectively the Hermitian and positive-semidefinite operators on $V$.

Banach spaces are normed vector spaces with an additional condition (completeness, i.e. convergence of Cauchy sequences) that is relevant only in the infinite dimensional case. In this work we will consider only finite-dimensional Banach spaces.

Warmup: algorithm for bipartite separability

In this section we describe a simple version of our algorithm. It contains all the main ideas which we will later generalize. Let $M=\sum_{i=1}^{n}X_{i}\otimes Y_{i}$, where $X_{i}\in\mathcal{S}^{d_{1}}_{+}$, $Y_{i}\in\mathcal{S}^{d_{2}}_{+}$, $\sum_{i}X_{i}\leq I$, and each $Y_{i}\leq I$. In quantum information language, $M$ is a 1-LOCC measurement, meaning it can be implemented with local operations and one-way classical communication Conventionally these have $\sum_{i}X_{i}=I$, but our formulation is essentially equivalent.. In later sections we will see that $M$ can also be interpreted in a (mathematically) more natural way as a bounded map from $S_{1}$ to $S_{\infty}$. The goal of our algorithm is to approximate $h_{\operatorname{Sep}(d_{1},d_{2})}(M)$, where we define the set of separable states as

There have been several recent proofs [BCY11, BH13, LW14], each based on quantum information theory, that SDP hierarchies can estimate $h_{\operatorname{Sep}(d_{1},d_{2})}(M)$ to error $\varepsilon\|M\|$ in time $\exp(O(\log^{2}(d)/\varepsilon^{2}))$. Similar techniques also appeared in [BKS13, LS14] for different classes of operators $M$. The role of the 1-LOCC conditions in these proofs was typically not completely obvious, and indeed it entered the proofs of [BCY11, BH13, LW14] in three different ways. We now give another interpretation of it that is arguably more geometrically natural.

Algorithm 1 (Basic algorithm for computing $h_{Sep}\left(M\right)$ for one-way LOCC $M=\sum_{i}X_{i}\otimes Y_{i}$). Input: $\{X_{i}\}_{i=1}^{n}\subset\mathcal{H}_{+}^{d_{1}},\{Y_{i}\}_{i=1}^{n}\subset\mathcal{H}_{+}^{d_{2}}$. Output: States $\alpha\in\mathcal{D}_{d_{1}}$ and $\beta\in\mathcal{D}_{d_{2}}$. 1. Enumerate over all $p\in\Delta_{n}(k)$, with $k=9\ln(d_{2})/\delta^{2}$. (a) For each $p$, check (using Lemma 5) whether there exists $q\in S$ with $\|p-q\|_{Y}\leq\delta/2$. (b) If so, compute $\|q\|_{Y}$. 2. Let $q$ be such that the $\|q\|_{Y}$ is the maximum, and let $\alpha\in\mathcal{D}_{d_{1}}$ be the state for which $q_{i}=\operatorname{tr}[X_{i}\alpha]$. Output this $\alpha$ and $\beta$ satisfying $\operatorname{tr}[\beta\sum_{i}q_{i}Y_{i}]=\|\sum_{i}q_{i}Y_{i}\|$.

Let $M=\sum_{i=1}^{n}X_{i}\otimes Y_{i}$ be such that $\sum_{i}X_{i}\leq I$, $X_{i}\geq 0$, $0\leq Y_{i}\leq I$. Algorithm 1 runs in time $\operatorname{poly}(d_{1},d_{2},n)\exp\left(O\left(\delta^{-2}\log(n)\log(d_{2})\right)\right)$ and outputs $\alpha\in{\cal D}_{d_{1}}$ and $\beta\in{\cal D}_{d_{2}}$ such that

For $n=\operatorname{poly}(d_{1},d_{2})$ this is the same running time as found in [BCY11] (while for $n\ll\operatorname{poly}(d_{1},d_{2})$ it is an improvement). Later in this section we will show how we can always modify the measurement to have $n=\operatorname{poly}(d_{1},d_{2})$ only incurring in a small error. But before that, we now show that Theorem 2 follows easily from two simple lemmas.

One of the lemmas is a consequence of the the well-known matrix Hoeffding bound.

This is a special case of Theorem 2.8 from [Tro10]):

Our first lemma shows that one can restrict the optimization to a net of size $n^{O(\log(d_{2})\delta^{-2})}$:

For any $p\in\Delta_{n}$ there exists $q\in\Delta_{n}(k)$ with

with positive probability if $k>8\ln(d)/\delta^{2}$. Setting $\delta=\sqrt{9\ln(d_{2})/k}$ we find that there exists a choice of $q\in\Delta_{n}(k)$ satisfying Eq. (14). ∎

The second lemma shows that one can decide efficiently if an element of the net is a valid solution. A similar result is in [SW12].

Given $p\in\Delta_{n}$ and $\varepsilon>0$, we can decide in time $\operatorname{poly}(d_{1},d_{2},n)$ whether the following set is nonempty

Both are convex sets, defined by semidefinite constraints. So we can test for feasibility with a SDP of size $\operatorname{poly}(d_{1},d_{2},n)$. Indeed this is manifest for $S_{X}$ in Eq. (11), while $\{q:\|p-q\|_{Y}\leq\varepsilon\}$ can be written as

Whatever the output $x$ is, $x\leq h_{\operatorname{Sep}}(M)+\delta/2$. On the other hand, let $q=\arg\max_{q\in S}\|q\|_{Y}$, so that $\|q\|_{Y}=h_{\operatorname{Sep}}(M^{\prime})$. By Lemma 4, there exists $p\in\Delta_{n}(k)$ with $\|p-q\|_{Y}\leq\delta/2$. Thus our algorithm will output a value that is $\geq h_{\operatorname{Sep}}(M)-\delta$. We conclude that the algorithm achieves an additive error of $\delta$ in time $\operatorname{poly}(d_{1},d_{2})n^{O(\log(d_{2})/\delta^{2})}$. ∎

We now consider the case where $n\gg\operatorname{poly}(d_{1},d_{2})$. It turns out that we can modify the algorithm such that its running time is polynomial in $n$ by first sparsifying the number of local terms of the measurement. This results in the following theorem.

Let $M=\sum_{i=1}^{n}X_{i}\otimes Y_{i}$ be such that $\sum_{i}X_{i}\leq I$, $X_{i}\geq 0$, $0\leq Y_{i}\leq I$. Algorithm 8 runs in time $\operatorname{poly}(n)\exp\left(O\left(\delta^{-2}\log d_{1}\log(d_{1}d_{2})\right)\right)$ and outputs $\alpha\in{\cal D}_{d_{1}}$ and $\beta\in{\cal D}_{d_{2}}$ such that

The key element of the theorem is the following Lemma.

Given a 1-LOCC measurement $M=\sum_{i=1}^{n}X_{i}\otimes Y_{i}$ and some $\varepsilon>0$ there exists a 1-LOCC measurement $M^{\prime}=\sum_{j=1}^{n^{\prime}}X^{\prime}_{j}\otimes Y^{\prime}_{j}$ with $\|M-M^{\prime}\|\leq\varepsilon$ and $n^{\prime}\leq\operatorname{poly}(d_{1},d_{2})/\varepsilon^{2}$. If the decomposition of $M$ is explicitly given then $M^{\prime}$ and its decomposition can be found in time $\operatorname{poly}(d_{1},d_{2},n)$ using a randomized algorithm.

Algorithm 8 (Algorithm for computing $h_{Sep}\left(M\right)$ for one-way LOCC $M=\sum_{i}X_{i}\otimes Y_{i}$). Input: $\{X_{i}\}_{i=1}^{n},\{Y_{i}\}_{i=1}^{n}$. Output: States $\alpha\in\mathcal{D}_{d_{1}}$ and $\beta\in\mathcal{D}_{d_{2}}$. 1. Use Lemma 7 to replace $M=\sum_{i=1}^{n}X_{i}\otimes Y_{i}$ with $M^{\prime}=\sum_{i=1}^{n^{\prime}}X_{i}^{\prime}\otimes Y_{i}^{\prime}$ satisfying $\|M-M^{\prime}\|\leq\delta/2$. 2. Run Algorithm 1 on $M^{\prime}$.

The proof of correctness is straightforward.

Whatever the output $x$ is, $x\leq h_{\operatorname{Sep}}(M^{\prime})\leq h_{\operatorname{Sep}}(M)+\delta/2$. On the other hand, let $q=\arg\max_{q\in S}\|q\|_{Y}$, so that $\|q\|_{Y}=h_{\operatorname{Sep}}(M^{\prime})$. By Lemma 4, there exists $p\in\Delta_{n}(k)$ with $\|p-q\|_{Y}\leq\delta/2$. Thus our algorithm will output a value that is $\geq h_{\operatorname{Sep}}(M^{\prime})-\delta/2\geq h_{\operatorname{Sep}}(M)-\delta$. We conclude that the algorithm achieves an additive error of $\delta$ in time $\operatorname{poly}(n)(d_{1}d_{2})^{O(\log(d_{2})/\delta^{2})}$. ∎

It remains only to prove Lemma 7. This requires a careful use of the matrix Hoeffding bound (Lemma LABEL:lem:Heoff). The details are in Appendix A.

2 Multipartite

Ref. [LS14] recently strengthened the result of [BH13] (from parallel one-way LOCC to fully one-way LOCC measurement) and proved that the SoS hierarchy approximates

to within additive error $\delta$ in time $\exp(O(\log^{2}(d)l^{3}/\delta^{2}))$, with $d:=\max_{i\in[l]}d_{i}$. Here we show that our previous algorithm for the bipartite case can be extended to the multipartite setting to give the same run time.

Algorithm 10 above runs in time $\exp(O(l^{3}\ln^{2}(d)/\delta^{2})$ and outputs states $\alpha_{i}$, $i\in[l]$, satisfying

3 The need for an explicit decomposition

The input to our algorithm is not only a 1-LOCC measurement $M$ but an explicit decomposition of the form $M=\sum_{i}X_{i}\otimes Y_{i}$ with each $X_{i}\geq 0$. Previous algorithms for $h_{\operatorname{Sep}}$ were mostly based on the SoS hierarchy (or its restriction to the separability problem also known as $k$-extendible hierarchy) [DPS04]. Running these requires only knowledge of $M$ and not its decomposition. The decomposition appears in the analysis of [BCY11, LW14, BC11, BH13, Yan06], but not the algorithm.

On the other hand, previous algorithms did not yield an explicit rounding, i.e. a separable state $\sigma$ with $\operatorname{tr}M\sigma\approx h_{\operatorname{Sep}}(M)$. The only exception to this [BH13] also required an explicit decomposition in order to produce a rounding.

In general any bipartite measurement $M$ can be written in the form $\sum_{i}X_{i}\otimes Y_{i}$, with individual terms that are not necessarily positive semidefinite. Finding some such decomposition is straightforward, e.g. using the operator Schmidt decomposition or even writing $M=\sum_{ijkl}M_{ijkl}\left|i\right\rangle\left\langle j\right|\otimes\left|k\right\rangle\left\langle l\right|$. Our algorithm can be readily modified to incorporate non-positive $X_{i}$ (along the lines of Section 4), but the run-time will then include a factor of $\sum_{i}\|X_{i}\|_{1}$ in the exponent. In general this will be $O(1)$ only if $M$ is close to 1-LOCC and the decomposition is close to the correct one.

This raises an interesting open question: given $M$, find a decomposition $M=\sum_{i}X_{i}\otimes Y_{i}$ that (approximately) minimizes $\sum_{i}\|X_{i}\|_{1}$. We are not aware of nontrivial algorithms or hardness results for this problem.

Generalized algorithm for arbitrary norms

An important step in the algorithm of the previous section was the identity,

where, as before, $S_{X}$ is given by Eq. (11).

Also this generalization is of interest in quantum information theory. As we discuss more in the next subsection, it includes as a particular case the well-studied problem of computing the maximum output $\alpha$-norms of an entanglement-breaking channel. Consider a general entanglement-breaking quantum channel $\Lambda:{\cal D}_{d_{1}}\rightarrow{\cal D}_{d_{2}}$ given by [HSR04]:

with $Y_{i}\geq 0$, $\operatorname{tr}(Y_{i})=1$, $X_{i}\geq 0$, and $\sum_{i}X_{i}=I$. Then

In order to find an algorithm for computing Eq. (23), we need to replace the quantum Hoeffding bound (Lemma 3) by more sophisticated concentration bounds. Since in Lemma 5 all we needed was a bound in expectation, the right concept will turn out to be the Rademacher type-$\gamma$ constant of the space $\mathcal{B}$, which we now define:

We say a Banach space $\mathcal{B}$ has Rademacher type-$\gamma$ constant $C$ if for every $Z_{1},\ldots,Z_{k}\in\mathcal{B}$ and Rademacher random variables $\varepsilon_{1},\ldots,\varepsilon_{k}$ (i.e. independent and uniformly distributed on $\pm 1$) ,

It is known that Schatten-$\alpha$ spaces with norm $\|X\|_{\alpha}:=\operatorname{tr}(|X|^{\alpha})^{1/\alpha}$ have type-2 constant $\sqrt{\alpha-1}$ for $\alpha\geq 2$ [BCL94], and type-$\alpha$ constant 1 for every $\alpha\in$ [KPT00, Thm 3.3].

For sparsification (the analogue of Lemma 7) we will actually need a slightly stronger condition than a bound on the type-$\gamma$ constant:

The modulus of uniform smoothness of a Banach space $\mathcal{B}$ is defined to be the function

The algorithm for approximating the optimization problem given by Eq. (23) is the following:

Algorithm 13 (Algorithm for computing $\max_{p\in S_{X}}\|p\|_{\mathcal{B},Y}$ for $\mathcal{B}$ of type-$\gamma$ constant $C$ and modulus of uniform smoothness $\rho_{\mathcal{B}}(\tau)\leq s\tau^{2}$, with $X:=\{X_{i}\}$ and $Y:=\{Y_{i}\}$). Input: $\{X_{i}\}_{i=1}^{n},\{Y_{i}\}_{i=1}^{n}$ Output: $p\in{\cal S}$ 1. Use Lemma 22 to replace $X=\{X_{i}\}$ and $Y=\{Y_{i}\}$ with $X^{\prime}:=\{X^{\prime}_{i}\}$ and $Y^{\prime}:=\{Y^{\prime}_{i}\}$. 2. Enumerate over all $p\in\Delta_{n}(k)$, with $k=\left(\frac{2C^{\gamma}}{\delta^{\gamma}}\max_{i}\|Y_{i}\|_{\mathcal{B}}^{\gamma}\right)^{1/(\gamma-1)}$. (a) For each $p$, check (using Lemma 21) whether there exists $q\in S$ with $\|p-q\|_{\mathcal{B},Y}\leq\delta$. (b) If so, compute $\|p\|_{Y}$. 3. Output $p$ such that $\|p\|_{\mathcal{B},Y}$ is the maximum.

Let $\mathcal{B}$ be a Banach space with norm $\|\cdot\|_{\mathcal{B}}$. Suppose the type-$\gamma$ constant of $\mathcal{B}$ is $C$ and that there is $s>0$ such that the modulus of uniform smoothness satisfies $\rho_{\mathcal{B}}(\tau)\leq s\tau^{2}$. Suppose one can compute $\|\cdot\|_{\mathcal{B}}$ in time $T$. Consider $\{X_{i}\}_{i=1}^{n}$ with $X_{i}$ $d\times d$ matrices satisfying $X_{i}\geq 0$, $\sum X_{i}\leq I$, and $\{Y_{i}\}_{i=1}^{n}$ with $Y_{i}\in\mathcal{B}$. Algorithm 13 runs in time

As an example, suppose $\mathcal{B}$ is ${\cal S}_{\infty}^{d_{2}}$. Then the type-2 constant is $O(\sqrt{\log(d_{2})})$, $\max_{i}\|Y_{i}\|\leq 1$, and Theorem 2 shows one can compute $\max_{p\in S_{X}}\|p\|_{Y}$ in time $\exp(O(\delta^{-2}\log(d_{1})\log(d_{1}d_{2})))$.

In the next subsection we discuss a few particular cases of the theorem worth emphasizing. Then we prove the theorem.

The next lemma shows that for subclasses of one-way LOCC measurements one has a PTAS for computing $h_{Sep}$. The class include in particular one-way LOCC measurements in which Bob’s measurements are low rank.

Let $M=\sum_{i}X_{i}\otimes Y_{i}$ be such that $X_{i}\geq 0$, $\sum_{i}X_{i}\leq I$ and $\|Y_{i}\|_{2}\leq r$. Then one can compute $\alpha\in{\cal D}_{d_{1}}$ and $\beta\in{\cal D}_{d_{2}}$ such that

We use Theorem 14 and Algorithm 13 to estimate the optimal $p$ and then find $\alpha$ and $\beta$ by semidefinite programming. ∎

If instead we use the multipartite version of the algorithm (see Algorithm 10), we find that for $M=\sum_{i}X_{i}\otimes Y_{i_{1}}\otimes\ldots\otimes Y_{i_{l}}$, with $X_{i}\geq 0$, $\sum_{i}X_{i}\leq I$ and $\|Y_{i}\|_{2}\leq r$, we can compute $\alpha\in{\cal D}_{d}$ and $\beta_{1},\ldots,\beta_{l}\in{\cal D}_{d}$ such that

1.2 Maximum output norm of entanglement-breaking channels

The next corollary shows that for all $\alpha>1$, there is a PTAS for computing the maximum output Schatten-$\alpha$ norm of an entanglement-breaking channel.

Let $\Lambda:{\cal D}_{d_{1}}\rightarrow{\cal D}_{d_{2}}$ be an entanglement-breaking channel with decomposition $\Lambda(\rho):=\sum_{i}\operatorname{tr}(X_{i}\rho)Y_{i}$ (where $X_{i}\geq 0$, $\sum_{i}X_{i}=I$, $Y_{i}\in{\cal D}_{d_{2}}$).

For every $\alpha\geq 2$ one can compute in time $\operatorname{poly}(d_{2})d_{1}^{O\left(\delta^{-2}\alpha\right)}$ a number $r$ such that

For every $1<\alpha\leq 2$ one can compute in time $\operatorname{poly}(d_{2})d_{1}^{O\left(\left(\alpha\delta^{-\alpha}\right)^{\frac{1}{\alpha-1}}\right)}$ a number $r$ such that

Part 1 follows from Theorem 14 and the fact that $S_{\alpha}$, with $\alpha\geq 2$, has type-2 constant $\sqrt{\alpha-1}$ [BCL94] and $\rho_{S_{\alpha}}(\tau)\leq\frac{\alpha-1}{2}\tau^{2}$ for $\alpha>1$. Part 2, in turn, follows from Theorem 14 and the fact that for $S_{\alpha}$, with $\alpha\geq 2$, has type-$\alpha$ constant one [KPT00, Thm 3.3]. ∎

We note that computing maximum output $\alpha$-norms for general quantum channels is harder. In particular it was shown in [HM10, HM13] that there is no algorithm that run in time $\exp\left(O\left(\log^{2-\varepsilon}{d}\right)\right)$ for any $\varepsilon>0$ and can decide if $\max_{\rho}\|\Lambda(\rho)\|$ is one or smaller than $\delta$ (for any fixed $\delta>0$) for a general quantum channel $\Lambda:{\cal D}_{d}\rightarrow{\cal D}_{d}$, unless the exponential time hypothesis (ETH) is wrong (meaning there is a subexponential time algorithm for 3-SAT).

What is known about hardness results for entanglement-breaking channels? Using the results of [BBH+12] one can show that to determine if $\max_{\rho}\|\Lambda(\rho)\|$ is $\geq C/d$ or $\leq c/d$ (for any two constants $C>c>0$) cannot be done in time $\exp\left(O\left(\log^{2-\varepsilon}{d}\right)\right)$ assuming ETH. So one cannot hope to find a polynomial-time algorithm for a multiplicative approximation of the maximum output norm.

Note that the complexity of the algorithm blows up when $\alpha\rightarrow 1$. This is not only an artifact of the proof. Computing the quantity for $\alpha$ close to one allow us to estimate the von Neumann minimum output entropy of the channel. However to estimate it we need a number of samples of order $O(d)$ and so the net-based approach we explore in this paper does not lead to efficient algorithms.

1.3 Hypercontractive norms

Our third corollary concerns the problem of computing hypercontractive norms, in particular computing the $2\rightarrow s$ norm of a $d\times d$ matrix $A$, for $s>2$, defined as

This norms are important in several applications, e.g. bounding the mixing time of Markov chains and determining if a graph is a small-set expander [BBH+12]. In [BBH+12] it was also shown that to compute any constant-factor multiplicative approximation to the $2\rightarrow 4$ norm of a $n\times n$ matrix is as hard as solving 3-SAT with $O(\log^{2}(n))$ variables. In Appendix B we extend the approach of [BBH+12] to show hardness results for multiplicatively approximating all $2\rightarrow q$ norms, for even $q\geq 4$.

In [BBH+12] it was shown that the result of [BCY11] implies that for any $d\times d$ matrix $A$ the Sum-of-Squares hierarchy computes in time $d^{O(\log(d)\delta^{-2})}$ an additive approximation $x$ s.t.

where $\|A\|_{2\rightarrow 2}$ is the largest singular value of $A$ and $\|A\|_{2\rightarrow\infty}$ the largest 2-norm of any row of $A$.

Using Theorem 14 we can improve this algorithm in two ways: First we can compute an approximation to $\|.\|_{2\rightarrow s}$ for any $s>2$. Second the running time for fixed error is polynomial, instead of quasipolynomial.

For any $s\geq 2$ one can compute in time $d^{O(s\delta^{-2})}$ a number $x$ such that

Let $X_{i}:=A^{\dagger}\left|i\right\rangle\left\langle i\right|A/||A||_{2\rightarrow 2}^{2}$. Note $X_{i}\geq 0$ and $\sum_{i}X_{i}\leq I$. We can write

in time $\exp\left(O\left(s\delta^{-2}\log(d)\right)\right)$ with additive error $\delta$. ∎

Although the corollary above gives an approximation for every $s>2$ that can be computed in polynomial time for every fixed error, it gives a worse approximation to the $2\rightarrow 4$ than [BBH+12] (given by Eq. (35)). We now show a second corollary that strictly improves the result of [BBH+12] for $2\rightarrow 4$ and generalizes it to $2\rightarrow s$ norms for every even $\geq 4$.

For any even $s\geq 4$ one can compute in time $d^{O(s\delta^{-2})}$ a number $x$ such that

Observe that $X_{i},Y_{i}\geq 0$, $\sum_{i}X_{i}\leq I$ and $Y_{i}\leq I$. Additionally

This last term can be approximated to additive error $\varepsilon$ in time

using the multipartite results of Section 3.1.1. ∎

2 Proof of Theorem 14

The proof of Theorem 14 will follow from three lemmas, the first showing that it is enough to search over a net of small size, the second showing that one can decide membership of $\{q:\|p-q\|_{\mathcal{B},Y}\leq\delta\}$ efficiently (assuming that $\|.\|_{\mathcal{B}}$ can be computed efficiently), and the third giving a sparsification for the number of $\{X_{i}\}_{i}^{n}$ and $\{Y_{i}\}_{i=1}^{n}$.

We first show how the type-$\gamma$ constant gives a concentration bound. This uses a standard argument.

Suppose we are given $p\in\Delta_{n}$, $Z_{i},\ldots,Z_{n}$ elements of a Banach space $\mathcal{B}$ with norm $\|\cdot\|_{\mathcal{B}}$, and $\varepsilon_{1},\ldots,\varepsilon_{k}$ Rademacher distributed random variables. Then for every $\gamma\geq 1$

Then we have the following generalization of Lemma 5:

Let the Banach space $\mathcal{B}$ have type-$\gamma$ constant $C$. Then for any $p\in\Delta_{n}$ there exists $q\in N_{k}$ with

Sample $i_{1},\ldots,i_{k}$ according to $p$ and set $q=(e_{i_{1}}+\ldots+e_{i_{k}})/k$. Then Definition 11 and Lemma 20 give

The first inequality follows from the convexity of $x\mapsto x^{\gamma}$, the second inequality from Lemma 19, and the third from the fact that $\mathcal{B}$ has type-$\gamma$ constant $C$. ∎

The next lemma is an analogue of Lemma 5:

Let the Banach space $\mathcal{B}$ be such that $\|.\|_{\mathcal{B}}$ can be computed in time $T$. Given $p\in\Delta_{n}$ and $\varepsilon>0$, we can decide in time $\operatorname{poly}(T,d,n)$ whether the following set is nonempty

Since we have an efficient algorithm for $\|\cdot\|_{\mathcal{B}}$ we can efficiently test membership in the set $\{q:\|p-q\|_{\mathcal{B},Y}\leq\varepsilon\}$. Thus we can determine if Eq. (50) is nonempty using the ellipsoid algorithm [GLS93]. ∎

We now state an analogous sparsification result of Lemma 7 for the more general case we consider in this section. The proof is in Appendix A.

Suppose $\Lambda$ is a map from $d\times d$ Hermitian matrices to a Banach space $\mathcal{B}$ and is given by $\Lambda(\rho)=\sum_{i=1}^{n}\langle X_{i},\rho\rangle Y_{i}$ where each $X_{i}\geq 0$, $\sum_{i=1}^{n}X_{i}\leq I$ and each $\|Y_{i}\|_{\mathcal{B}}\leq 1$. Suppose that $\mathcal{B}$ has modulus of smoothness $\rho_{\mathcal{B}}(\tau)\leq s\tau^{2}$. Then there exists $\Lambda^{\prime}$ such that $\Lambda^{\prime}(\rho)=\sum_{i=1}^{k}\langle X_{i}^{\prime},\rho\rangle Y_{i}^{\prime}$ where each $X_{i}^{\prime}\geq 0$, $\sum_{i=1}^{k}X_{i}^{\prime}\leq I$ and each $\|Y_{i}^{\prime}\|_{\mathcal{B}}\leq 1$. Additionally $k\leq cd^{2}(d+s)/\delta^{2}$ for some constant $c>0$,

and $\Lambda^{\prime}$ can be found efficiently.

With the lemmas in hand the proof of Theorem 14 follows along the same lines as Theorem 6.

Algorithm for injective tensor norm

In this section we present one further generalization, this time on the input space. While this final generalization does not have natural applications in quantum information (to our knowledge), it does give perspective on why it is natural to consider 1-LOCC measurements and entanglement-breaking channels.

First, we introduce some more definitions. Suppose that $\|\cdot\|_{\mathcal{A}}$ and $\|\cdot\|_{\mathcal{B}}$ are two norms. For $\Lambda$ an operator from $\mathcal{A}\rightarrow\mathcal{B}$ define the operator norm

Define the injective tensor norm $\mathcal{A}\otimes_{\operatorname{inj}}\mathcal{B}$ by

For example, consider $h_{\operatorname{Sep}}$, which we considered in Section 2. In our new notation

where $\hat{M}$ is the map defined by $\hat{M}(X)=\operatorname{tr}_{A}[M(X\otimes I)]$. The requirement that $M$ is 1-LOCC is roughly equivalent to the requirement that

The algorithm follows similar lines to the earlier algorithms. It lacks only the sparsification step since we do not know how to extend Lemma 22 to this case.

Algorithm 24 (Algorithm for computing $\|\Lambda\|_{\mathcal{A}\rightarrow\mathcal{B}}$). Input: $\{x_{i}\}_{i=1}^{n},\{y_{i}\}_{i=1}^{n}$ Output: $p\in{\cal S}$ 1. Enumerate over all $p\in N_{k}$, with $k=(2\lambda/\delta)^{\frac{\gamma}{\gamma-1}}$. (a) For each $p$, check whether there exists $q\in S$ with $\|p-q\|_{\mathcal{B},Y}\leq\delta$. (b) If so, compute $\|p\|_{Y}$. 2. Output $p$ such that $\|p\|_{\mathcal{B},Y}$ is the maximum.

The proof of Theorem 23 is almost the same as that of Theorem 14. The only new ingredient is checking whether $p\in S_{X}$. This is equivalent to asking whether $\exists a\in B(\mathcal{A})$ such that $p_{i}=x_{i}^{*}(a)$. This is a convex program which can be decided in time $\operatorname{poly}(d)T_{\mathcal{A}}$ using the ellipsoid algorithm along with our assumption that $\|\cdot\|_{\mathcal{A}}$ can be computed in time $T_{\mathcal{A}}$.

Acknowledgments

We thank Jop Briet, Pablo Parrilo and Ben Recht for interesting discussions. FGSLB is supported by EPSRC. AWH was funded by NSF grants CCF-1111382 and CCF-1452616, ARO contract W911NF-12-1-0486 and a Leverhulme Trust Visiting Professorship VP2-2013-041. Part of this work was done while A.W. was visiting UCL.

Appendix A Sparsification

In this appendix we prove two Lemmas about sparsification: one (Lemma 7) for the problem of $h_{\operatorname{Sep}}$ and the second (Lemma 22) for the estimate $S_{1}\rightarrow\mathcal{B}$ norms. While the former is a special case of the latter, it is also far more self-contained (requiring only the operator Hoeffding bound), so we recommend reading it first.

Assume initially that each $\|Y_{i}\|=1$. This is possible because we can always drop terms with $Y_{i}=0$ and then rewrite $M$ as

Redefining $X_{i}$ appropriately we see that $\sum_{i}X_{i}\leq I$ still holds.

Now write $M=\sum_{i=1}^{n}p_{i}W_{i}$ with $p_{i}=\frac{\operatorname{tr}(X_{i}\otimes Y_{i})}{\operatorname{tr}(M)}$ and $W_{i}=\frac{X_{i}\otimes Y_{i}}{p_{i}}$. Sample $i_{1},\ldots,i_{n^{\prime}}$ according to $p$ and define

for some $\delta$ to be chosen later. We can use Lemma 3 here. To do so, note that

Now we find that the probability that Eq. (60) fails to hold is

Taking $n^{\prime}=8d_{1}^{2}d_{2}^{2}\log(2d_{1}d_{2})/\delta^{2}$ we have that (60) holds with positive probability. Fix the corresponding $i_{1},\ldots,i_{n^{\prime}}$. Choose $M^{\prime}=A/(1+\delta)$. Together with Eq. (60) this means that $M^{\prime}$ is a valid 1-LOCC measurement. By Eq. (60a) we can achieve our result by choosing $\delta=\varepsilon/3$. Indeed

We now turn to the proof of Lemma 22, covering the case of general Banach spaces with bounded modulus of smoothness.

We will need the following Azuma-type inequality from Naor [Nao12], who attributes it to Pisier. We will state a weaker Hoeffding-type formulation that suffices for our purposes.

Suppose $X_{1},\ldots,X_{k}$ are independent random variables on $B(\mathcal{B})$ for $\mathcal{B}$ a Banach space with $\rho_{\mathcal{B}}(\tau)\leq s\tau^{2}$. Then

First we introduce notation. For a matrix $X$, define the map $\hat{X}$ by $\hat{X}(A):=\langle X,A\rangle$. Thus $\Lambda=\sum_{i=1}^{n}Y_{i}\hat{X}_{i}$.

As in Lemma 7 we first drop terms with $Y_{i}=0$ and rewrite $\Lambda=\sum_{i=1}^{n}\frac{Y_{i}}{\|Y_{i}\|_{\mathcal{B}}}\cdot\|Y_{i}\|_{\mathcal{B}}\hat{X}_{i}$. Redefine $X_{i},Y_{i}$ appropriately and assume from now on that each $\|Y_{i}\|_{\mathcal{B}}=1$.

Next we attempt to bound the LHS of Eq. (51). First we can relax $\mathcal{D}_{d}$ to $B(S_{1})$ and obtain

This formulation allows to apply the symmetrization trick (Lemma 19) to obtain

We will bound this last quantity for any fixed $i_{1},\ldots,i_{k}$. For $\rho\in B(S_{1})$, define $q_{j}:=\langle X_{i_{j}},\rho\rangle/kp_{i_{j}}$. Denote the set of feasible $q$ by $S_{X,\vec{i}}$ where this notation emphasizes the dependence on both $X$ and $i_{1},\ldots,i_{k}$. Then $\sum_{j}|q_{j}|\leq 1$, each $|q_{j}|\leq d/k$ and

Now let us fix $\rho$ (or equivalently $q$). Observe that $\|Y_{i_{j}}q_{j}\|_{\mathcal{B}}\leq d/k$. Then Lemma 25 implies that

According to Lemma II.2 of [HLSW04] there exists a net of pure states $\rho_{1},\ldots,\rho_{m}\in\mathcal{D}_{d}$ such that $m\leq 10^{2d}$ and for any pure state $\rho$, we have $\min_{l}\|\rho-\rho_{l}\|_{1}\leq 1/2$. Say that $\varepsilon_{1},\ldots,\varepsilon_{k}$ is a good sequence if $\|\sum_{j}\varepsilon_{j}Y_{i_{j}}\langle X_{i_{j}},\rho_{l}\rangle/kp_{i_{j}}\|\leq\delta$ for all $l\in[m]$. By Eq. (69) and the union bound the probability that $\varepsilon_{1},\ldots,\varepsilon_{k}$ is bad (i.e. not good) is $\leq 10^{2d}e^{s+2-ck\delta^{2}/d^{2}}$. For a bad sequence we still have that Eq. (68) is $\leq d$ by the triangle inequality. For a good sequence, let $\alpha$ denote Eq. (68) and let $\beta$ be the corresponding maximum with $\rho$ restricted to the set $\{\rho_{1},\ldots,\rho_{m}\}$. By our assumption that the sequence is good we have $\beta\leq\delta$. Observe that $\alpha=\max_{\rho\in B(S_{1})}\|\Lambda^{\prime}_{\varepsilon}(\rho)\|_{\mathcal{B}}$ and by convexity (and symmetry of the $\|\cdot\|_{\mathcal{B}}$ norm) this $\max$ is achieved for $\rho$ a pure state. Let $\rho_{l}$ satisfy $\|\rho-\rho_{l}\|_{1}\leq 1/2$. Then

Maximizing the LHS over $\rho$ we obtain $\alpha\leq\beta+\alpha/2$, or equivalently $\alpha\leq 2\beta\leq 2\delta$. Thus Eq. (67) is

Redefining $c$, this is $\leq 5\delta$ when $k\geq cd^{3}/\delta^{2}$.

Since Eq. (67) controls the expectation with respect to $i_{1},\ldots,i_{k}$, we conclude that for at least half of the $i_{1},\ldots,i_{k}$, the LHS of Eq. (51) is $\leq 10\delta$. Since Eq. (65) holds with high probability ($\geq 1-d\exp(-cd/8)$) it follows that there exists a sequence of $i_{1},\ldots,i_{k}$ that simultaneously fulfills both criteria. Fix this choice. Finally we choose $\Lambda^{\prime}=\Lambda^{\prime\prime}/(1+\delta)$ so that the normalization condition on $\sum_{j}X_{j}^{\prime}$ is satisfied. This increases the error by at most a further factor of $\delta$. We conclude the proof by redefining $\delta$ to be $11\delta$. ∎

Appendix B Hardness of computing 2→q→2𝑞2\rightarrow q norms

In this section we extend the hardness results of [BBH+12] (Theorem 9.4, part 2) for estimating the $2\rightarrow 4$ norm to general $2\rightarrow q$ norms for even $q\geq 4$.

The next lemma is an extension from Lemma 9.5 from [BBH+12].

with $P_{A_{1},\ldots,A_{q/2}}$ the projector onto the symmetric subspace over $A_{1},...,A_{q/2}$. We will first relate $h_{\text{Sep}^{q/2}(d^{2})}(N)$ to $h_{\text{Sep}(d,d)}(M)$, and then relate $h_{\text{Sep}^{q/2}(d^{2})}(N)$ to $\|A\|_{2\rightarrow q}$ for a matrix $A$ of size $d^{4kq}\times d^{2kq}$.

In case $N$ we show that $h_{\operatorname{Sep}^{q/2}(d^{2})}(N)\leq 1-\delta/2$. Note that

where the last inequality follows from Lemma 9.6 of [BBH+12].

To construct a matrix $A$ of size $d^{4kq}\times d^{2kq}$ s.t. $\|A\|_{2\rightarrow q}=h_{\operatorname{Sep}^{q/2}(d^{2})}(N)$ we follow the proof of Lemma 9.5 of [BBH+12], the only difference being that we apply Wick’s theorem to $P_{A_{1},\ldots A_{q/2}}$, i.e. there is a measure $\mu$ over unit vectors s.t.

The basic idea of the Lemma is to use the product test of [HM10] to force $v_{1},\ldots,v_{q/2}$ to be product states. Our proof can be summarized as saying that $q/2$ copies can enforce this more effectively than 2 copies (assuming $q/2\geq 2$), and therefore we obtain soundness at least as sharp as in [BBH+12]. This analysis may be wasteful, since using more copies should improve the effectiveness of the product test.

The main result of this section is the following analogue of Theorem 9.4, part 2, of [BBH+12]:

Let $\phi$ be a $3$-SAT instance with $n$ variables and $O(n)$ clauses and $q\geq 4$ an even integer. Determining whether $\phi$ is satisfiable can be reduced in polynomial time to determining whether $\|A\|_{2\rightarrow q}\geq C$ or $\|A\|_{2\rightarrow q}\leq c$ where $0\leq c<C$ and $A$ is an $m\times m$ matrix, where $m=\exp(q\sqrt{n}\operatorname{polylog}(n)\log(C/c))$.

Corollary 14 of [HM10] gives a reduction from determining satisfiability of $\phi$ to distinguishing between $h_{\text{Sep}(d,d)}(M)=1$ and $h_{\text{Sep}(d,d)}(M)\leq 1/2$, with $0\leq M\leq I$ that can be constructed in time $\operatorname{poly}(d)$ from $\phi$ with $d=\exp(\sqrt{n}\operatorname{polylog}(n))$. Applying Lemma 26 gives the result. ∎

References