25 Search Results for "Harrow, Aram W."


Volume

LIPIcs, Volume 27

9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

TQC 2014, May 21-23, 2014, Singapore

Editors: Steven T. Flammia and Aram W. Harrow

Document
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion

Authors: Matthew Coudron and Aram W. Harrow

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
In this work we consider the role of entanglement assistance in quantum communication protocols, focusing, in particular, on whether the type of shared entangled state can affect the quantum communication complexity of a function. This question is interesting because in some other settings in quantum information, such as non-local games, or tasks that involve quantum communication between players and referee, or simulating bipartite unitaries or communication channels, maximally entangled states are known to be less useful as a resource than some partially entangled states. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a partial or total function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using Q qubits of communication and arbitrary shared entanglement can be epsilon-approximated by a protocol using O(Q/epsilon+log(1/epsilon)/epsilon) qubits of communication and only EPR pairs as shared entanglement. This conclusion is opposite of the common wisdom in the study of non-local games, where it has been shown, for example, that the I3322 inequality has a non-local strategy using a non-maximally entangled state, which surpasses the winning probability achievable by any strategy using a maximally entangled state of any dimension [Vidick and Wehner, 2011]. We leave open the question of how much the use of a shared maximally entangled state can reduce the quantum communication complexity of a function. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We give simple and efficiently computable upper and lower bounds. Given two bipartite states |chi> and |upsilon>, we define a natural quantity, d_{infty}(|chi>, |upsilon>), which we call the l_{infty} Earth Mover’s distance, and we show that the communication cost of converting between |chi> and |upsilon> is upper bounded by a constant multiple of d_{infty}(|chi>, |upsilon>). Here d_{infty}(|chi>, |upsilon>) may be informally described as the minimum over all transports between the log of the Schmidt coefficients of |chi> and those of |upsilon>, of the maximum distance that any amount of mass must be moved in that transport. A precise definition is given in the introduction. Furthermore, we prove a complementary lower bound on the cost of state conversion by the epsilon-Smoothed l_{infty}-Earth Mover’s Distance, which is a natural smoothing of the l_{infty}-Earth Mover’s Distance that we will define via a connection with optimal transport theory.

Cite as

Matthew Coudron and Aram W. Harrow. Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{coudron_et_al:LIPIcs.CCC.2019.20,
  author =	{Coudron, Matthew and Harrow, Aram W.},
  title =	{{Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{20:1--20:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.20},
  URN =		{urn:nbn:de:0030-drops-108421},
  doi =		{10.4230/LIPIcs.CCC.2019.20},
  annote =	{Keywords: Entanglement, quantum communication complexity}
}
Document
Algorithms, Bounds, and Strategies for Entangled XOR Games

Authors: Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, 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. By contrast, our algorithm runs in polynomial time. 3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{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^{unsat} n. 4) 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 (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.

Cite as

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{benewatts_et_al:LIPIcs.ITCS.2019.10,
  author =	{Bene Watts, Adam and Harrow, Aram W. and Kanwar, Gurtej and Natarajan, Anand},
  title =	{{Algorithms, Bounds, and Strategies for Entangled XOR Games}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.10},
  URN =		{urn:nbn:de:0030-drops-101032},
  doi =		{10.4230/LIPIcs.ITCS.2019.10},
  annote =	{Keywords: Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement}
}
Document
Lower Bound on Expected Communication Cost of Quantum Huffman Coding

Authors: Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)


Abstract
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.

Cite as

Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao. Lower Bound on Expected Communication Cost of Quantum Huffman Coding. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.TQC.2016.3,
  author =	{Anshu, Anurag and Garg, Ankit and Harrow, Aram W. and Yao, Penghui},
  title =	{{Lower Bound on Expected Communication Cost of Quantum Huffman Coding}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.3},
  URN =		{urn:nbn:de:0030-drops-66843},
  doi =		{10.4230/LIPIcs.TQC.2016.3},
  annote =	{Keywords: Quantum information, quantum communication, expected communica- tion cost, huffman coding}
}
Document
Complete Volume
LIPIcs, Volume 27, TQC'14, Complete Volume

Authors: Steven T. Flammia and Aram W. Harrow

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
LIPIcs, Volume 27, TQC'14, Complete Volume

Cite as

9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Proceedings{flammia_et_al:LIPIcs.TQC.2014,
  title =	{{LIPIcs, Volume 27, TQC'14, Complete Volume}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014},
  URN =		{urn:nbn:de:0030-drops-48241},
  doi =		{10.4230/LIPIcs.TQC.2014},
  annote =	{Keywords: Data Encryption, Coding and Information Theory, Theory of Computation}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Steven T. Flammia and Aram W. Harrow

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{flammia_et_al:LIPIcs.TQC.2014.i,
  author =	{Flammia, Steven T. and Harrow, Aram W.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.i},
  URN =		{urn:nbn:de:0030-drops-48197},
  doi =		{10.4230/LIPIcs.TQC.2014.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
More Randomness From Noisy Sources

Authors: Jean-Daniel Bancal and Valerio Scarani

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
Bell experiments can be used to generate private random numbers. An ideal Bell experiment would involve measuring a state of two maximally entangled qubits, but in practice any state produced is subject to noise. Here we consider how the techniques presented in Refs [Bancal et al., New J. Phys., 2014] and [Nieto-Silleras, New J. Phys., 2014], i.e. using an optimized Bell inequality, and taking advantage of the fact that the device provider is not our adversary, can be used to improve the rate of randomness generation in Bell-like tests performed on singlet states subject to either white or dephasing noise.

Cite as

Jean-Daniel Bancal and Valerio Scarani. More Randomness From Noisy Sources. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{bancal_et_al:LIPIcs.TQC.2014.1,
  author =	{Bancal, Jean-Daniel and Scarani, Valerio},
  title =	{{More Randomness From Noisy Sources}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{1--6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.1},
  URN =		{urn:nbn:de:0030-drops-48015},
  doi =		{10.4230/LIPIcs.TQC.2014.1},
  annote =	{Keywords: Randomness, Bell inequalities, Trusted provider assumption}
}
Document
Exact Classical Simulation of the GHZ Distribution

Authors: Gilles Brassard, Luc Devroye, and Claude Gravel

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than twenty years and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n*log(n)) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve earlier results with a protocol that needs only O(n*log(n)) bits of communication and O(log^2(n)) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.

Cite as

Gilles Brassard, Luc Devroye, and Claude Gravel. Exact Classical Simulation of the GHZ Distribution. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 7-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{brassard_et_al:LIPIcs.TQC.2014.7,
  author =	{Brassard, Gilles and Devroye, Luc and Gravel, Claude},
  title =	{{Exact Classical Simulation of the GHZ Distribution}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{7--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.7},
  URN =		{urn:nbn:de:0030-drops-48025},
  doi =		{10.4230/LIPIcs.TQC.2014.7},
  annote =	{Keywords: Entanglement simulation, Greenberger-Horne-Zeilinger (GHZ) state, Multiparty entanglement, von Neumann's rejection algorithm, Knuth-Yao's sampling alg}
}
Document
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case

Authors: Harry Buhrman, Serge Fehr, and Christian Schaffner

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value < 1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game G has a non-signaling value v_{ns}(G) < 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n. Stronger than that, we prove that the probability of winning more than (v_{ns}(G) + delta) * n parallel repetitions is exponentially small in n (for any delta > 0). Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.

Cite as

Harry Buhrman, Serge Fehr, and Christian Schaffner. On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 24-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2014.24,
  author =	{Buhrman, Harry and Fehr, Serge and Schaffner, Christian},
  title =	{{On the Parallel Repetition of Multi-Player Games: The No-Signaling Case}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{24--35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.24},
  URN =		{urn:nbn:de:0030-drops-48034},
  doi =		{10.4230/LIPIcs.TQC.2014.24},
  annote =	{Keywords: Parallel repetition, non-signaling value, multi-player non-local games}
}
Document
Quantum Communication Complexity with Coherent States and Linear Optics

Authors: Juan Miguel Arrazola and Norbert Lütkenhaus

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We introduce a general mapping for encoding quantum communication protocols involving pure states of multiple qubits, unitary transformations, and projective measurements into another set of protocols that employ coherent states of light in a superposition of optical modes, linear optics transformations and measurements with single-photon threshold detectors. This provides a general framework for transforming a wide class of protocols in quantum communication into a form in which they can be implemented with current technology. In particular, we apply the mapping to quantum communication complexity, providing general conditions under which quantum protocols can be implemented with coherent states and linear optics while retaining exponential separations in communication complexity compared to the classical case. Finally, we make use of our results to construct a protocol for the Hidden Matching problem that retains the known exponential gap between quantum and classical one-way communication complexity.

Cite as

Juan Miguel Arrazola and Norbert Lütkenhaus. Quantum Communication Complexity with Coherent States and Linear Optics. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 36-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{arrazola_et_al:LIPIcs.TQC.2014.36,
  author =	{Arrazola, Juan Miguel and L\"{u}tkenhaus, Norbert},
  title =	{{Quantum Communication Complexity with Coherent States and Linear Optics}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{36--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.36},
  URN =		{urn:nbn:de:0030-drops-48044},
  doi =		{10.4230/LIPIcs.TQC.2014.36},
  annote =	{Keywords: Quantum Communication Complexity, Quantum Optics}
}
Document
Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants

Authors: Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if theta(G) <= theta(H) where theta represents the Lovász number. We also obtain similar inequalities for the related Schrijver theta^- and Szegedy theta^+ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: alpha^*(G) <= theta^-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity beta as an upper bound on alpha^* and posed the question of whether beta(G) = \lfloor theta(G) \rfloor. We answer this in the affirmative and show that a related quantity is equal to \lceil theta(G) \rceil. We show that a quantity chi_{vect}(G) recently introduced in the context of Tsirelson's conjecture is equal to \lceil theta^+(G) \rceil.

Cite as

Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter. Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 48-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{cubitt_et_al:LIPIcs.TQC.2014.48,
  author =	{Cubitt, Toby and Mancinska, Laura and Roberson, David and Severini, Simone and Stahlke, Dan and Winter, Andreas},
  title =	{{Bounds on Entanglement Assisted Source-channel Coding Via the Lov\'{a}sz Theta Number and Its Variants}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{48--51},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.48},
  URN =		{urn:nbn:de:0030-drops-48054},
  doi =		{10.4230/LIPIcs.TQC.2014.48},
  annote =	{Keywords: source-channel coding, zero-error capacity, Lov\'{a}sz theta}
}
Document
Strong Converse for the Quantum Capacity of the Erasure Channel for Almost All Codes

Authors: Mark M. Wilde and Andreas Winter

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
A strong converse theorem for channel capacity establishes that the error probability in any communication scheme for a given channel necessarily tends to one if the rate of communication exceeds the channel's capacity. Establishing such a theorem for the quantum capacity of degradable channels has been an elusive task, with the strongest progress so far being a so-called "pretty strong converse." In this work, Morgan and Winter proved that the quantum error of any quantum communication scheme for a given degradable channel converges to a value larger than 1/sqrt(2) in the limit of many channel uses if the quantum rate of communication exceeds the channel's quantum capacity. The present paper establishes a theorem that is a counterpart to this "pretty strong converse." We prove that the large fraction of codes having a rate exceeding the erasure channel's quantum capacity have a quantum error tending to one in the limit of many channel uses. Thus, our work adds to the body of evidence that a fully strong converse theorem should hold for the quantum capacity of the erasure channel. As a side result, we prove that the classical capacity of the quantum erasure channel obeys the strong converse property.

Cite as

Mark M. Wilde and Andreas Winter. Strong Converse for the Quantum Capacity of the Erasure Channel for Almost All Codes. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 52-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{wilde_et_al:LIPIcs.TQC.2014.52,
  author =	{Wilde, Mark M. and Winter, Andreas},
  title =	{{Strong Converse for the Quantum Capacity of the Erasure Channel for Almost All Codes}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{52--66},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.52},
  URN =		{urn:nbn:de:0030-drops-48068},
  doi =		{10.4230/LIPIcs.TQC.2014.52},
  annote =	{Keywords: strong converse, quantum erasure channel, quantum capacity}
}
Document
Graph-theoretical Bounds on the Entangled Value of Non-local Games

Authors: André Chailloux, Laura Mancinska, Giannicola Scarpa, and Simone Severini

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We introduce a novel technique to give bounds to the entangled value of non-local games. The technique is based on a class of graphs used by Cabello, Severini and Winter in 2010. The upper bound uses the famous Lovàsz theta number and is efficiently computable; the lower one is based on the quantum independence number, which is a quantity used in the study of entanglement-assisted channel capacities and graph homomorphism games.

Cite as

André Chailloux, Laura Mancinska, Giannicola Scarpa, and Simone Severini. Graph-theoretical Bounds on the Entangled Value of Non-local Games. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 67-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.67,
  author =	{Chailloux, Andr\'{e} and Mancinska, Laura and Scarpa, Giannicola and Severini, Simone},
  title =	{{Graph-theoretical Bounds on the Entangled Value of Non-local Games}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{67--75},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.67},
  URN =		{urn:nbn:de:0030-drops-48074},
  doi =		{10.4230/LIPIcs.TQC.2014.67},
  annote =	{Keywords: Graph theory, non-locality, entangled games}
}
Document
Optimal Bounds for Parity-Oblivious Random Access Codes with Applications

Authors: André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i. We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].

Cite as

André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora. Optimal Bounds for Parity-Oblivious Random Access Codes with Applications. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.76,
  author =	{Chailloux, Andr\'{e} and Kerenidis, Iordanis and Kundu, Srijita and Sikora, Jamie},
  title =	{{Optimal Bounds for Parity-Oblivious Random Access Codes with Applications}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{76--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.76},
  URN =		{urn:nbn:de:0030-drops-48084},
  doi =		{10.4230/LIPIcs.TQC.2014.76},
  annote =	{Keywords: quantum information theory, contextuality, semidefinite programming}
}
Document
Convexity Properties of the Quantum Rényi Divergences, with Applications to the Quantum Stein's Lemma

Authors: Milán Mosonyi

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)


Abstract
We show finite-size bounds on the deviation of the optimal type II error from its asymptotic value in the quantum hypothesis testing problem of Stein's lemma with composite null-hypothesis. The proof is based on some simple properties of a new notion of quantum Rènyi divergence, recently introduced in [Müller-Lennert, Dupuis, Szehr, Fehr and Tomamichel, J. Math. Phys. 54, 122203, (2013)], and [Wilde, Winter, Yang, arXiv:1306.1586].

Cite as

Milán Mosonyi. Convexity Properties of the Quantum Rényi Divergences, with Applications to the Quantum Stein's Lemma. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 88-98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{mosonyi:LIPIcs.TQC.2014.88,
  author =	{Mosonyi, Mil\'{a}n},
  title =	{{Convexity Properties of the Quantum R\'{e}nyi Divergences, with Applications to the Quantum Stein's Lemma}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{88--98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.88},
  URN =		{urn:nbn:de:0030-drops-48094},
  doi =		{10.4230/LIPIcs.TQC.2014.88},
  annote =	{Keywords: Quantum R\'{e}nyi divergences, Stein's lemma, composite null-hypothesis, second-order asymptotics}
}
  • Refine by Author
  • 6 Harrow, Aram W.
  • 3 Mancinska, Laura
  • 3 Winter, Andreas
  • 2 Alagic, Gorjan
  • 2 Chailloux, André
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Quantum communication complexity
  • 1 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 2 Lovász theta
  • 2 quantum
  • 1 Anyon
  • 1 Bell inequalities
  • 1 Braid
  • Show More...

  • Refine by Type
  • 24 document
  • 1 volume

  • Refine by Publication Year
  • 21 2014
  • 2 2019
  • 1 2010
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail