Showing all papers from arXiv author **natarajan_a_1**

- Jan 12 2018 quant-ph arXiv:1801.03821v1For 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.
- 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.
- We show that the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length is NP-hard to approximate to within constant factors. As a corollary, the inclusion $\mathrm{NEXP}\subseteq\mathrm{MIP}^*$, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.
- Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no $\omega(1)$-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the $2 \rightarrow 4$ norm of a matrix, and the set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.
- We introduce a simple two-player test which certifies that the players apply tensor products of Pauli $\sigma_X$ and $\sigma_Z$ observables on the tensor product of $n$ EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive $\varepsilon$ of the optimal must be $\mathrm{poly}(\varepsilon)$-close, in the appropriate distance measure, to the honest $n$-qubit strategy. The test involves $2n$-bit questions and $2$-bit answers. The key technical ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld. As applications of our result we give (i) the first robust self-test for $n$ EPR pairs; (ii) a quantum multiprover interactive proof system for the local Hamiltonian problem with a constant number of provers and classical questions and answers, and a constant completeness-soundness gap independent of system size; (iii) a robust protocol for delegated quantum computation.
- Sep 21 2016 quant-ph arXiv:1609.06306v1We show that the $n$-round parallel repetition of the Magic Square game of Mermin and Peres is rigid, in the sense that for any entangled strategy succeeding with probability $1 -\varepsilon$, the players' shared state is $O(\mathrm{poly}(n\varepsilon))$-close to $2n$ EPR pairs under a local isometry. Furthermore, we show that, under local isometry, the players' measurements in said entangled strategy must be $O(\mathrm{poly}(n\varepsilon))$ close to the "ideal" strategy when acting on the shared state.
- $ \newcommand{\Xlin}{\mathcal{X}} \newcommand{\Zlin}{\mathcal{Z}} \newcommand{\C}{\mathbb{C}} $We give a quantum multiprover interactive proof system for the local Hamiltonian problem in which there is a constant number of provers, questions are classical of length polynomial in the number of qubits, and answers are of constant length. The main novelty of our protocol is that the gap between completeness and soundness is directly proportional to the promise gap on the (normalized) ground state energy of the Hamiltonian. This result can be interpreted as a concrete step towards a quantum PCP theorem giving entangled-prover interactive proof systems for QMA-complete problems. The key ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld, where the function $f:\{0,1\}^n\to\{0,1\}$ is replaced by a pair of functions $\Xlin, \Zlin:\{0,1\}^n\to \text{Obs}_d(\C)$, the set of $d$-dimensional Hermitian matrices that square to identity. The test enforces that (i) each function is exactly linear, $\Xlin(a)\Xlin(b)=\Xlin(a+b)$ and $\Zlin(a) \Zlin(b)=\Zlin(a+b)$, and (ii) the two functions are approximately complementary, $\Xlin(a)\Zlin(b)\approx (-1)^{a\cdot b} \Zlin(b)\Xlin(a)$.
- We present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy of approximations for the set of separable states. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm for separability testing which is singly exponential in dimension and polylogarithmic in accuracy. Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints.

- Supported by Silverpond.