Anand Natarajan

Anand Natarajan435

Feb 15 2018 14:54 UTC
Feb 09 2018 03:25 UTC
Feb 08 2018 04:14 UTC
Anand Natarajan scited Black Holes and Complexity Classes
Jan 31 2018 13:56 UTC
Jan 30 2018 14:28 UTC
Jan 30 2018 14:28 UTC
Jan 26 2018 14:13 UTC
Jan 26 2018 14:13 UTC
Jan 26 2018 14:13 UTC
Jan 22 2018 15:57 UTC
Jan 18 2018 08:26 UTC
Jan 12 2018 02:00 UTC
Anand Natarajan published Low-degree testing for quantum states
For any integer $n\geq 2$ we construct a one-round two-player game $G_n$, with communication that scales poly-logarithmically with $n$, having the following properties. First, there exists an entangled strategy that wins with probability $1$ in $G_n$ and in which the players' outcomes are determined by performing generalized Pauli measurements on their respective share of an $n$-qudit maximally entangled state, with qudits of local dimension $q = \mathrm{poly}\log(n)$. Second, any strategy that succeeds with probability at least $1-\varepsilon$ in $G_n$ must be within distance $O((\log n)^c\varepsilon^{1/d})$, for universal constants $c,d\geq 1$, of the perfect strategy, up to local isometries. This is an exponential improvement on the size of any previously known game certifying $\Omega(n)$ qudits of entanglement with comparable robustness guarantees. The construction of the game $G_n$ is based on the classical test for low-degree polynomials of Raz and Safra, which we extend to the quantum regime. Combining this game with a variant of the sum-check protocol, we obtain the following consequences. First, we show that is QMA-hard, under randomized reductions, to approximate up to a constant factor the maximum acceptance probability of a multiround, multiplayer entangled game with $\mathrm{poly}\log(n)$ bits of classical communication. Second, we give a quasipolynomial reduction from the multiplayer games quantum PCP conjecture to the constraint satisfaction quantum PCP conjecture. Third, we design a multiplayer protocol with polylogarithmic communication and constant completeness-soundness gap for deciding the minimal energy of a class of frustration-free nonlocal Hamiltonians up to inverse polynomial accuracy.
Jan 10 2018 20:41 UTC
Jan 04 2018 05:49 UTC
Jan 04 2018 02:00 UTC
We study the complexity of computing the commuting-operator value $\omega^*$ of entangled XOR games with any number of players. We introduce necessary and sufficient criteria for an XOR game to have $\omega^* = 1$, and use these criteria to derive the following results: 1. An algorithm for symmetric games that decides in polynomial time whether $\omega^* = 1$ or $\omega^* < 1$, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2. A family of games with three players and with $\omega^* < 1$, where it takes doubly exponential time for the ncSoS algorithm to witness this (in contrast with our algorithm which runs in polynomial time). 3. A family of games achieving a bias difference $2(\omega^* - \omega)$ arbitrarily close to the maximum possible value of $1$ (and as a consequence, achieving an unbounded bias ratio), answering an open question of Briët and Vidick. 4. Existence of an unsatisfiable phase for random (non-symmetric) XOR games: that is, we show that there exists a constant $C_k^{\text{unsat}}$ depending only on the number $k$ of players, such that a random $k$-XOR game over an alphabet of size $n$ has $\omega^* < 1$ with high probability when the number of clauses is above $C_k^{\text{unsat}} n$. 5. A lower bound of $\Omega(n \log(n)/\log\log(n))$ on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the $n$-th level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.
Dec 31 2017 22:51 UTC
Dec 31 2017 22:51 UTC