NDLI: Quantum de finetti theorems under local measurements with applications

Please wait, while we are loading the content...

A PRG for lipschitz functions of polynomials with applications to sparsest cut

Coevolutionary opinion formation games

Low rank approximation and regression in input sparsity time

Equivalence of deterministic one-counter automata is NL-complete

The complexity of non-monotone markets

Non-black-box simulation in the fully concurrent setting

Quasipolynomial-time canonical form for steiner designs

Quasi-polynomial hitting-set for set-depth-Δ formulas

Bottom-k and priority sampling, set similarity and subset sums with minimal independence

A o(n) monotonicity tester for boolean functions over the hypercube

Approximation resistance from pairwise independent subgroups

A node-capacitated okamura-seymour theorem

Attribute-based encryption for circuits

Extending continuous maps: polynomiality and undecidability

Solving large optimization problems using spectral graph theory

Optimal euclidean spanners: really short, thin and lanky

Constraint satisfaction, packet routing, and the lovasz local lemma

Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]

Succinct sampling from discrete distributions

New bounds for matching vector families

Quantum de finetti theorems under local measurements with applications

Approximating k-median via pseudo-approximation

The orbit problem in higher dimensions

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap

Prior-independent mechanisms for scheduling

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

Explicit lower bounds via geometric complexity theory

Tatonnement beyond gross substitutes?: gradient descent to the rescue

Non-black-box simulation from one-way functions and applications to resettable security

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems

Beyond worst-case analysis in private singular vector computation

Fast routing table construction using small messages: extended abstract

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

Approximation resistance on satisfiable instances for predicates with few accepting inputs

Structured recursive separator decompositions for planar graphs in linear time

Reusable garbled circuits and succinct functional encryption

Net and prune: a linear time algorithm for euclidean distance problems

Statistical algorithms and a lower bound for detecting planted cliques

The complexity of finite-valued CSPs

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

New independent source extractors with exponential improvement

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Product-state approximations to quantum ground states

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

The loss of serving in the dark

Natural proofs versus derandomization

Combinatorial walrasian equilibrium

Sparsity lower bounds for dimensionality reducing maps

From information to exact communication

Simultaneous auctions are (almost) efficient

On the impossibility of approximate obfuscation and applications to resettable cryptography

Sparsest cut on bounded treewidth graphs: algorithms and hardness results

Differential privacy for the analyst via private equilibrium computation

Multidimensional approximate agreement in Byzantine asynchronous systems

Every locally characterized affine-invariant property is testable

Witness encryption and its applications

Fast approximation algorithms for the diameter and radius of sparse graphs

Delegation for bounded space

Random lattice triangulations: structure and algorithms

Low-rank matrix completion using alternating minimization

Going after the k-SAT threshold

Simple deterministic algorithms for fully dynamic maximal matching

Interactive proofs of proximity: delegating computation in sublinear time

List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound

Inverting well conditioned matrices in quantum logspace

Communication lower bounds using directional derivatives

Tight bounds for online vector bin packing

On the complexity of trial and error

Efficient rounding for the noncommutative grothendieck inequality

Recursive composition and bootstrapping for SNARKS and proof-carrying data

An information complexity approach to extended formulations

Composable and efficient mechanisms

Shielding circuits with groups

Large-treewidth graph decompositions and applications

The geometry of differential privacy: the sparse and approximate cases

Byzantine agreement in polynomial expected time: [extended abstract]

Testing subdivision-freeness: property testing meets structural graph theory

Majority is stablest: discrete and SoS

The power of deferral: maintaining a constant-competitive steiner tree online

Classical hardness of learning with errors

Lee-Yang theorems and the complexity of computing averages

The approximate rank of a matrix and its algorithmic applications: approximate rank

Interactive channel capacity

A new approach to computing maximum flows using electrical flows

Lower bounds for RAMs and quantifier elimination

On the list decodability of random linear codes with large error rates

Superlinear advantage for exact quantum algorithms

Homomorphic fingerprints under misalignments: sketching edit and shift distances

Stochastic combinatorial optimization via poisson approximation

How robust are linear sketches to adaptive inputs?

Average-case lower bounds for formula size

Fast hamiltonicity checking via bases of perfect matchings

Answering $n_{\{2+o(1)\}}$ counting queries with differential privacy is hard

Strong ETH holds for regular resolution

Simplex partitioning via exponential clocks and the multiway cut problem

On the concrete efficiency of probabilistically-checkable proofs

A complete dichotomy rises from the capture of vanishing signatures: extended abstract

Max flows in O(nm) time, or better

Some trade-off results for polynomial calculus: extended abstract

Polynomial-time perfect matchings in dense hypergraphs

Quantum de finetti theorems under local measurements with applications

Content Provider	ACM Digital Library
Author	Brandao, Fernando G.S.L. Harrow, Aram W.
Abstract	Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log\|Q\| + $log^{2}\|A\|/ε^{2})$ ), with \|Q\| and \|A\| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a $O(k^{-1/2})$ advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables \$n\$ by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.
Starting Page	861
Ending Page	870
Page Count	10
File Format	PDF
ISBN	9781450320290
DOI	10.1145/2488608.2488718
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Sdp hierarchy Quantum information theory De finetti
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in