31,583 research outputs found
Retracted: Two-Player Entangled Games are NP-Hard
No full textThe article, published on June 4th, 2018 in the CCC 2018 proceedings, has been retracted by agreement between the authors, the editor(s), and the publisher Schloss Dagstuhl / LIPIcs. The retraction has been agreed due to an error in the proof of the main result. This error is carried over from an error in the referenced paper “Three-player entangled XOR games are NP-hard to approximate” by Thomas Vidick (SICOMP ’16). That paper was used in an essential way to obtain the present result, and the error cannot be addressed through an erratum. See Retraction Notice on the last page of the PDF.
We show that it is NP-hard to approximate, to within an additive constant, 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. As a corollary, the inclusion NEXP subseteq MIP^*, first shown by Ito and Vidick (FOCS'12) with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test of Raz and Safra (STOC'97) against two entangled provers
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk)
No full textThe study of multiprover interactive proof systems, of locally testable codes, and of property testing are deeply linked, conceptually if not formally, through their role in the proof of the PCP theorem in complexity theory. Recently there has been substantial progress on an analogous research programme in quantum complexity theory. Two years ago we characterized the power of multiprover interactive proof systems with provers sharing entanglement, showing that MIP^* = RE [Ji et al., 2020], a hugely surprising increase in power from the classical result MIP = NEXP of [Babai et al., 1991]. The following year Panteleev and Kalachev gave the first construction of quantum low-density parity-check codes (QLDPC) [Panteleev and Kalachev, 2022], thus marking a major step towards the possible realization of good quantum locally testable codes - the classical analogue of which was only constructed quite recently [Dinur et al., 2022]. And finally, less than a year ago Anshu, Breuckmann and Nirkhe used facts evidenced in the construction of good decoders for the new QLDPC codes to resolve the NLTS conjecture [Anshu et al., 2022], widely viewed as a crucial step on the way to a possible quantum PCP theorem.
In the talk I will survey these results, making an effort to motivate and present them to the non-expert. I will explain the connections between them and point to where, in my opinion, our understanding is currently lacking. Along the way I will highlight a number of open problems whose resolution could lead to further progress on one of the most important research programmes in quantum complexity theory
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
Self-testing of a single quantum device under computational assumptions
No full textSelf-testing is a method to characterise an arbitrary quantum system based
only on its classical input-output correlations, and plays an important role in
device-independent quantum information processing as well as quantum complexity
theory. Prior works on self-testing require the assumption that the system's
state is shared among multiple parties that only perform local measurements and
cannot communicate. Here, we replace the setting of multiple non-communicating
parties, which is difficult to enforce in practice, by a single computationally
bounded party. Specifically, we construct a protocol that allows a classical
verifier to robustly certify that a single computationally bounded quantum
device must have prepared a Bell pair and performed single-qubit measurements
on it, up to a change of basis applied to both the device's state and
measurements. This means that under computational assumptions, the verifier is
able to certify the presence of entanglement, a property usually closely
associated with two separated subsystems, inside a single quantum device. To
achieve this, we build on techniques first introduced by Brakerski et al.
(2018) and Mahadev (2018) which allow a classical verifier to constrain the
actions of a quantum device assuming the device does not break post-quantum
cryptography.Comment: 58 pages, published in Quantu
Explicit Lower and Upper Bounds on the Entangled Value of Multiplayer XOR Games
No full textThe study of quantum-mechanical violations of Bell inequalities is motivated by the investigation, and the eventual demonstration, of the nonlocal properties of entanglement. In recent years, Bell inequalities have found a fruitful re-formulation using the language of multiplayer games originating from Computer Science. This paper studies the nonlocal properties of entanglement in the context of the simplest such games, called XOR games. When there are two players, it is well known that the maximum bias—the advantage over random play—of players using entanglement can be at most a constant times greater than that of classical players. Recently, Pérez-García et al. (Commun. Mathe. Phys. 279:455, 2008) showed that no such bound holds when there are three or more players: the use of entanglement can provide an unbounded advantage, and scale with the number of questions in the game. Their proof relies on non-trivial results from operator space theory, and gives a non-explicit existence proof, leading to a game with a very large number of questions and only a loose control over the local dimension of the players’ shared entanglement. We give a new, simple and explicit (though still probabilistic) construction of a family of three-player XOR games which achieve a large quantum-classical gap (QC-gap). This QC-gap is exponentially larger than the one given by Pérez-García et. al. in terms of the size of the game, achieving a QC-gap of order √N with N[superscript 2] questions per player. In terms of the dimension of the entangled state required, we achieve the same (optimal) QC-gap of √N for a state of local dimension N per player. Moreover, the optimal entangled strategy is very simple, involving observables defined by tensor products of the Pauli matrices. Additionally, we give the first upper bound on the maximal QC-gap in terms of the number of questions per player, showing that our construction is only quadratically off in that respect. Our results rely on probabilistic estimates on the norm of random matrices and higher-order tensors which may be of independent interest.National Science Foundation (U.S.) (Grant No. 084462
Thomas Grisell letter to Thomas Rotch, 2nd mo 19th 1823
No full textThomas Grisell's letter reached the Rotch household several months before the unexpected death of Thomas Rotch in August, 1823. This is the last letter of the series and presumably the author learned of his friend's death before another letter was penned. 7.95" x 10" (20.2 by 25.5 cm
Parallel Repetition via Fortification: Analytic View and the Quantum Case
No full textIn a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings.
First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest.
An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D
No full textOne of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance by Landau et al. gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unresolved, including whether there exist rigorous efficient algorithms when the ground space is degenerate (and poly(n) dimensional), or for the poly(n) lowest energy states for 1D systems, or even whether such states admit succinct classical descriptions or area laws.
In this paper we give a new algorithm for finding low energy states for 1D systems, based on a rigorously justified renormalization group (RG)-type transformation. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n^{O(\log n)} algorithm for the poly(n) lowest energy states for 1D systems (under a mild density condition). We note that for these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is O(nM(n)), where M(n) is the time required to multiply two n by n matrices
Failed Censures: Ecclesiastical Regulation of Women’s Clothing in Late Medieval Italy
No full textChurchmen in the late thirteenth and early fourteenth centuries tried to regulate the costume of Italian women. These efforts failed, and regulation was largely left thereafter to civic authorities.The published version was published as Chapter 3 in Medieval Clothing and Textiles 5Izbicki, Thomas M. (2009), "Failed Censures: Ecclesiastical Regulation of Women’s Clothing in Late Medieval Italy" in Netherton, Robin and Owen-Crocker, Gale R., eds., Medieval Clothing and Textiles 5 (Boydell Press), 37-53ISBN: 9781843834519 (published book)Peer reviewe
- …
