Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum entanglement, sum of squares, and the log rank conjecture
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For every $epsilon>0$, we give an $exp(tilde{O}(sqrt{n}/epsilon^2))$-time algorithm for the $1$ vs $1-epsilon$ emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2times n^2$ matrix $mathcal{M}$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $rho$ that $mathcal{M}$ accepts with probability $1$, and the case that every separable state is accepted with probability at most $1-epsilon$. Equivalently, our algorithm takes the description of a subspace $mathcal{W} subseteq mathbb{F}^{n^2}$ (where $mathbb{F}$ can be either the real or complex field) and distinguishes between the case that $mathcal{W}$ contains a rank one matrix, and the case that every rank one matrix is at least $epsilon$ far (in $ell_2$ distance) from $mathcal{W}$. To the best of our knowledge, this is the first improvement over the brute-force $exp(n)$-time algorithm for this problem. Our algorithm is based on the emph{sum-of-squares} hierarchy and its analysis is inspired by Lovetts proof (STOC 14, JACM 16) that the communication complexity of every rank-$n$ Boolean matrix is bounded by $tilde{O}(sqrt{n})$.
rate research
Read More
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this question and issues arising in quantum information theory and the study of Khots Unique Games Conjecture (UGC). We show the following: 1. For any constant even integer q>=4, a graph $G$ is a small-set expander if and only if the projector into the span of the top eigenvectors of Gs adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture--a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n^(2/q)) time, thus obtaining a different proof of the known subexponential algorithm for Small Set Expansion. 2. Constant rounds of the Sum of Squares semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low-degree polynomials over the Boolean cube, as well certify the unsatisfiability of the noisy cube and short code based instances of Unique Games considered by prior works. This improves on the previous upper bound of exp(poly log n) rounds (for the short code), as well as separates the Sum of Squares/Lasserre hierarchy from weaker hierarchies that were known to require omega(1) rounds. 3. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(sqrt(n) polylog(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in $mathbb{R}^d$ that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., $2^{-{operatorname{polylog}(d)}}$) fraction of the incidences. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank-$d$ matrix containing at most $O(1)$ distinct entries in each column contains a submatrix of fractional size $2^{-{operatorname{polylog}(d)}}$, in which each column contains one distinct entry. We prove that our conjecture is equivalent to the log-rank conjecture. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density $Omega(epsilon^{2d}/d)$ in any $d$-dimensional configuration with incidence density $epsilon$. We also improve an upper-bound construction of Apfelbaum and Sharir (SIAM J. Discrete Math. 07), yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is $Omega(1/sqrt d)$. Finally, we discuss various constructions (due to others) which yield configurations with incidence density $Omega(1)$ and bipartite subgraph density $2^{-Omega(sqrt d)}$. Our framework and results may help shed light on the difficulty of improving Lovetts $tilde{O}(sqrt{operatorname{rank}(f)})$ bound (J. ACM 16) for the log-rank conjecture; in particular, any improvement on this bound would imply the first bipartite subgraph size bounds for parallel $3$-partitioned configurations which beat our generic bounds for unstructured configurations.
In the noisy tensor completion problem we observe $m$ entries (whose location is chosen uniformly at random) from an unknown $n_1 times n_2 times n_3$ tensor $T$. We assume that $T$ is entry-wise close to being rank $r$. Our goal is to fill in its missing entries using as few observations as possible. Let $n = max(n_1, n_2, n_3)$. We show that if $m = n^{3/2} r$ then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our estimate agrees with almost all of $T$s entries almost exactly and works even when our observations are corrupted by noise. This is also the first algorithm for tensor completion that works in the overcomplete case when $r > n$, and in fact it works all the way up to $r = n^{3/2-epsilon}$. Our proofs are short and simple and are based on establishing a new connection between noisy tensor completion (through the language of Rademacher complexity) and the task of refuting random constant satisfaction problems. This connection seems to have gone unnoticed even in the context of matrix completion. Furthermore, we use this connection to show matching lower bounds. Our main technical result is in characterizing the Rademacher complexity of the sequence of norms that arise in the sum-of-squares relaxations to the tensor nuclear norm. These results point to an interesting new direction: Can we explore computational vs. sample complexity tradeoffs through the sum-of-squares hierarchy?
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM 20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
The goal of this article is to prove the Sum of Squares Conjecture for real polynomials $r(z,bar{z})$ on $mathbb{C}^3$ with diagonal coefficient matrix. This conjecture describes the possible values for the rank of $r(z,bar{z}) |z|^2$ under the hypothesis that $r(z,bar{z})|z|^2=|h(z)|^2$ for some holomorphic polynomial mapping $h$. Our approach is to connect this problem to the degree estimates problem for proper holomorphic monomial mappings from the unit ball in $mathbb{C}^2$ to the unit ball in $mathbb{C}^k$. DAngelo, Kos, and Riehl proved the sharp degree estimates theorem in this setting, and we give a new proof using techniques from commutative algebra. We then complete the proof of the Sum of Squares Conjecture in this case using similar algebraic techniques.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
