61 citations · 215 across the 16 of their papers we have counts for
17 papers
Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
Finn Holler, Anand Natarajan
Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first arg…
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
Anand Natarajan, Tina Zhang
We present a step towards the goal of producing a general cryptographic 'compilation' procedure which can translate any entangled nonlocal game into a single-prover interactive pro…
Quantum free games
Anand Natarajan, Tina Zhang
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC'14). There are two complexity classes that can…
Quantum Locally Testable Code with Constant Soundness
Andrew Cross, Zhiyang He, Anand Natarajan +2
In this paper, we present two constructions of quantum locally testable codes (QLTC) with constant soundness. In the first approach, we introduce an operation called check product,…
Quantum soundness of testing tensor codes
Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2
A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial construction…
Quantum search-to-decision reductions and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de…
Quantum soundness of the classical low individual degree test
Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as [BFL91] and the…
Quantum Blackjack or Can MIT Bring Down the House Again?
Joseph X. Lin, Joseph A. Formaggio, Aram W. Harrow +1
We examine the advantages that quantum strategies afford in communication-limited games. Inspired by the card game blackjack, we focus on cooperative, two-party sequential games in…
NEEXP in MIP*
Anand Natarajan, John Wright
We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a…
Algorithms, Bounds, and Strategies for Entangled XOR Games
Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar +1
We study the complexity of computing the commuting-operator value of entangled XOR games with any number of players. We introduce necessary and sufficient criteria for an XOR…
Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
Anand Natarajan, Thomas Vidick
We show that given an explicit description of a multiplayer game, with a classical verifier and a constant number of players, it is QMA-hard, under randomized reductions, to distin…
Two-player entangled games are NP-hard
Anand Natarajan, Thomas Vidick
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 co…
Limitations of semidefinite programs for separable states and entangled games
Aram W. Harrow, Anand Natarajan, Xiaodi Wu
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 usi…
Robust self-testing of many-qubit states
Anand Natarajan, Thomas Vidick
We introduce a simple two-player test which certifies that the players apply tensor products of Pauli and observables on the tensor product of EPR pairs. The test h…
The Parallel-Repeated Magic Square Game is Rigid
Matthew Coudron, Anand Natarajan
We show that the -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 -\…
Constant-Soundness Interactive Proofs for Local Hamiltonians
Anand Natarajan, Thomas Vidick
We give a quantum multiprover interactive proof system for the local Hamiltonian prob…
An improved semidefinite programming hierarchy for testing entanglement
Aram W. Harrow, Anand Natarajan, Xiaodi Wu
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…