DROPS

Volume

LIPIcs, Volume 61

11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

TQC 2016, September 27-29, 2016, Berlin, Germany

Editors: Anne Broadbent

Document

DOI: 10.4230/LIPIcs.ITCS.2023.28

Rigidity for Monogamy-Of-Entanglement Games

Authors: Anne Broadbent and Eric Culf

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee’s measurement outcome on a shared quantum state they prepared. We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis and informs the players of her choice. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. That is, in order to win optimally, the players' strategy must be of a specific form, namely a convex combination of four unentangled optimal strategies generated by the Breidbart state. We extend this to show that strategies that win near-optimally must also be near an optimal state of this form. We also show rigidity for multiple copies of the game played in parallel. We give three applications: (1) We construct for the first time a weak string erasure (WSE) scheme where the security does not rely on limitations on the parties' hardware. Instead, we add a prover, which enables security via the rigidity of this MoE game. (2) We show that the WSE scheme can be used to achieve bit commitment in a model where it is impossible classically. (3) We achieve everlasting-secure randomness expansion in the model of trusted but leaky measurement and untrusted preparation and measurements by two isolated devices, while relying only on the temporary assumption of pseudorandom functions. This achieves randomness expansion without the need for shared entanglement.

Cite as

Anne Broadbent and Eric Culf. Rigidity for Monogamy-Of-Entanglement Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 28:1-28:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{broadbent_et_al:LIPIcs.ITCS.2023.28,
  author =	{Broadbent, Anne and Culf, Eric},
  title =	{{Rigidity for Monogamy-Of-Entanglement Games}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{28:1--28:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.28},
  URN =		{urn:nbn:de:0030-drops-175319},
  doi =		{10.4230/LIPIcs.ITCS.2023.28},
  annote =	{Keywords: Rigidity, Self-Testing Monogamy-of-Entanglement Games, Bit Commitment, Randomness Expansion}
}

Document

DOI: 10.4230/LIPIcs.CCC.2021.30

On Query-To-Communication Lifting for Adversary Bounds

Authors: Anurag Anshu, Shalev Ben-David, and Srijita Kundu

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract

We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1) We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2) Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain "honest-but-curious" model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3) Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.

Cite as

Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30,
  author =	{Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita},
  title =	{{On Query-To-Communication Lifting for Adversary Bounds}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{30:1--30:39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30},
  URN =		{urn:nbn:de:0030-drops-143042},
  doi =		{10.4230/LIPIcs.CCC.2021.30},
  annote =	{Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2021.61

Communication Memento: Memoryless Communication Complexity

Authors: Srinivasan Arunachalam and Supartha Podder

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].

Cite as

Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61,
  author =	{Arunachalam, Srinivasan and Podder, Supartha},
  title =	{{Communication Memento: Memoryless Communication Complexity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.61},
  URN =		{urn:nbn:de:0030-drops-136007},
  doi =		{10.4230/LIPIcs.ITCS.2021.61},
  annote =	{Keywords: Communication complexity, space complexity, branching programs, garden-hose model, quantum computing}
}

Document

DOI: 10.4230/LIPIcs.TQC.2020.4

Uncloneable Quantum Encryption via Oracles

Authors: Anne Broadbent and Sébastien Lord

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

Quantum information is well known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by introducing a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but isolated adversaries are prevented from simultaneously recovering the message, even when the encryption key is revealed. Clearly, such functionality is unattainable using classical information alone. We formally define uncloneable encryption, and show how to achieve it using Wiesner’s conjugate coding, combined with a quantum-secure pseudorandom function (qPRF). Modelling the qPRF as an oracle, we show security by adapting techniques from the quantum one-way-to-hiding lemma, as well as using bounds from quantum monogamy-of-entanglement games.

Cite as

Anne Broadbent and Sébastien Lord. Uncloneable Quantum Encryption via Oracles. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{broadbent_et_al:LIPIcs.TQC.2020.4,
  author =	{Broadbent, Anne and Lord, S\'{e}bastien},
  title =	{{Uncloneable Quantum Encryption via Oracles}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.4},
  URN =		{urn:nbn:de:0030-drops-120639},
  doi =		{10.4230/LIPIcs.TQC.2020.4},
  annote =	{Keywords: Quantum Cryptography, Symmetric Key, Monogamy-of-Entanglement}
}

Document

DOI: 10.4230/LIPIcs.TQC.2020.6

Towards Quantum One-Time Memories from Stateless Hardware

Authors: Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver, against a linear number of adaptive queries to the token, in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also show our scheme is "tight" according to two scenarios.

Cite as

Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou. Towards Quantum One-Time Memories from Stateless Hardware. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{broadbent_et_al:LIPIcs.TQC.2020.6,
  author =	{Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng},
  title =	{{Towards Quantum One-Time Memories from Stateless Hardware}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.6},
  URN =		{urn:nbn:de:0030-drops-120654},
  doi =		{10.4230/LIPIcs.TQC.2020.6},
  annote =	{Keywords: quantum cryptography, one-time memories, semi-definite programming}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.TQC.2016

LIPIcs, Volume 61, TQC'16, Complete Volume

Authors: Anne Broadbent

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

Abstract

LIPIcs, Volume 61, TQC'16, Complete Volume

Cite as

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

Copy BibTex To Clipboard

@Proceedings{broadbent:LIPIcs.TQC.2016,
  title =	{{LIPIcs, Volume 61, TQC'16, Complete Volume}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016},
  URN =		{urn:nbn:de:0030-drops-66984},
  doi =		{10.4230/LIPIcs.TQC.2016},
  annote =	{Keywords: Data Encryption, Coding and Information Theory, Theory of Computation}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.TQC.2016.0

Front Matter, Table of Contents, Preface, List of Contributed Talks, Conference Organization

Authors: Anne Broadbent

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

Abstract

Front Matter, Table of Contents, Preface, List of Contributed Talks, Conference Organization

Cite as

11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{broadbent:LIPIcs.TQC.2016.0,
  author =	{Broadbent, Anne},
  title =	{{Front Matter, Table of Contents, Preface, List of Contributed Talks, Conference Organization}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{0:i--0:xii},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.0},
  URN =		{urn:nbn:de:0030-drops-66816},
  doi =		{10.4230/LIPIcs.TQC.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, List of Contributed Talks, Conference Organization}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.1

On the Power of Quantum Fourier Sampling

Authors: Bill Fefferman and Christopher Umans

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

Abstract

A line of work initiated by Terhal and DiVincenzo [Terhal/DiVincenzo, arXiv, 2002] and Bremner, Jozsa, and Shepherd [Bremner/Jozsa/Sheperd, Proc. Royal Soc. A, 2010], shows that restricted classes of quantum computation can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov [Aaronson/Arkhipov, J. Theory of Comp., 2013] take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled exactly by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson-Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, as well as many other familiar #P-hard polynomials. Since our distribution likely requires the full power of universal quantum computation, while the Aaronson-Arkhipov distribution uses only linear optical quantum computation with noninteracting bosons, why is our result interesting? We can think of at least three reasons: 1. Since the conjectures required in [Aaronson/Arkhipov, J. Theory of Comp., 2013] have not yet been proven, it seems worthwhile to weaken them as much as possible. We do this in two ways, by weakening both conjectures to apply to any "Efficiently Specifiable" polynomial, and by weakening the so-called Anti-Concentration conjecture so that it need only hold for one distribution in a broad class of distributions. 2. Our construction can be understood without any knowledge of linear optics. While this may be a disadvantage for experimentalists, in our opinion it results in a very clean and simple exposition that may be more immediately accessible to computer scientists. 3. It is extremely common for quantum computations to employ “Quantum Fourier Sampling” in the following way: first apply a classically efficient function to a uniform superposition of inputs, then apply a Quantum Fourier Transform followed by a measurement. Our distributions are obtained in exactly this way, where the classically efficient function is related to a (presumed) hard polynomial. Establishing rigorously a robust sense in which the central primitive of Quantum Fourier Sampling is classically hard seems a worthwhile goal in itself.

Cite as

Bill Fefferman and Christopher Umans. On the Power of Quantum Fourier Sampling. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fefferman_et_al:LIPIcs.TQC.2016.1,
  author =	{Fefferman, Bill and Umans, Christopher},
  title =	{{On the Power of Quantum Fourier Sampling}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{1:1--1:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.1},
  URN =		{urn:nbn:de:0030-drops-66829},
  doi =		{10.4230/LIPIcs.TQC.2016.1},
  annote =	{Keywords: Quantum Complexity Theory, Sampling Complexity}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.2

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Authors: Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz

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

Abstract

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.

Cite as

Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz. Quantum-Proof Multi-Source Randomness Extractors in the Markov Model. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 2:1-2:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arnonfriedman_et_al:LIPIcs.TQC.2016.2,
  author =	{Arnon-Friedman, Rotem and Portmann, Christopher and Scholz, Volkher B.},
  title =	{{Quantum-Proof Multi-Source Randomness Extractors in the Markov Model}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{2:1--2:34},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.2},
  URN =		{urn:nbn:de:0030-drops-66830},
  doi =		{10.4230/LIPIcs.TQC.2016.2},
  annote =	{Keywords: Quantum proof randomness extractors, multisource extractors, device independent quantum cryptography}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.3

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

DOI: 10.4230/LIPIcs.TQC.2016.4

Simple, Near-Optimal Quantum Protocols for Die-Rolling

Authors: Jamie Sikora

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

Abstract

Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols which are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling which have decent (and sometimes optimal) security which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols which are very close to Kitaev's lower bound for any D >= 3.

Cite as

Jamie Sikora. Simple, Near-Optimal Quantum Protocols for Die-Rolling. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sikora:LIPIcs.TQC.2016.4,
  author =	{Sikora, Jamie},
  title =	{{Simple, Near-Optimal Quantum Protocols for Die-Rolling}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{4:1--4:14},
  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.4},
  URN =		{urn:nbn:de:0030-drops-66851},
  doi =		{10.4230/LIPIcs.TQC.2016.4},
  annote =	{Keywords: Quantum Cryptography, Semidefinite Programming, Die-Rolling, Integer-Commitment}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.5

Robust Bell Inequalities from Communication Complexity

Authors: Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno

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

Abstract

The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bounds. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.

Cite as

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno. Robust Bell Inequalities from Communication Complexity. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.TQC.2016.5,
  author =	{Laplante, Sophie and Lauri\`{e}re, Mathieu and Nolin, Alexandre and Roland, J\'{e}r\'{e}mie and Senno, Gabriel},
  title =	{{Robust Bell Inequalities from Communication Complexity}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{5:1--5:24},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.5},
  URN =		{urn:nbn:de:0030-drops-66867},
  doi =		{10.4230/LIPIcs.TQC.2016.5},
  annote =	{Keywords: Communication complexity, Bell inequalities, nonlocality, detector efficiency}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.6

How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?

Authors: Nai-Hui Chia and Sean Hallgren

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

Abstract

We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density > 1 and also to quantum sampling subset sum solutions. We examine a decision version of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density >1. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density >1 but approaching 1 as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.

Cite as

Nai-Hui Chia and Sean Hallgren. How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.TQC.2016.6,
  author =	{Chia, Nai-Hui and Hallgren, Sean},
  title =	{{How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{6:1--6:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.6},
  URN =		{urn:nbn:de:0030-drops-66877},
  doi =		{10.4230/LIPIcs.TQC.2016.6},
  annote =	{Keywords: Quantum algorithms, hidden subgroup problem, random subset sum problem}
}

Document

DOI: 10.4230/LIPIcs.TQC.2016.7

The Structure of Promises in Quantum Speedups

Authors: Shalev Ben-David

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

Abstract

In 1998, Beals, Buhrman, Cleve, Mosca, and de Wolf showed that no super-polynomial quantum speedup is possible in the query complexity setting unless there is a promise on the input. We examine several types of "unstructured" promises, and show that they also are not compatible with super-polynomial quantum speedups. We conclude that such speedups are only possible when the input is known to have some structure. Specifically, we show that there is a polynomial relationship of degree 18 between D(f) and Q(f) for any Boolean function f defined on permutations (elements of [n]^n in which each alphabet element occurs exactly once). More generally, this holds for all f defined on orbits of the symmetric group action (which acts on an element of [M]^n by permuting its entries). We also show that any Boolean function f defined on a "symmetric" subset of the Boolean hypercube has a polynomial relationship between R(f) and Q(f) - although in that setting, D(f) may be exponentially larger.

Cite as

Shalev Ben-David. The Structure of Promises in Quantum Speedups. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bendavid:LIPIcs.TQC.2016.7,
  author =	{Ben-David, Shalev},
  title =	{{The Structure of Promises in Quantum Speedups}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{7:1--7:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.7},
  URN =		{urn:nbn:de:0030-drops-66882},
  doi =		{10.4230/LIPIcs.TQC.2016.7},
  annote =	{Keywords: Quantum computing, quantum query complexity, decision tree complexity, lower bounds, quantum adversary method}
}

17 Search Results for "Broadbent, Anne"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message