15 Search Results for "Wilde, Mark M."

Volume

LIPIcs, Volume 73

12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

TQC 2017, June 14-16, 2017, Paris, France

Editors: Mark M. Wilde

Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2017
LIPIcs, Volume 73, TQC'17, Complete Volume

Authors: Mark M. Wilde

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
LIPIcs, Volume 73, TQC'17, Complete Volume
Cite as

Mark M. Wilde. LIPIcs, Volume 73, TQC'17, Complete Volume. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{wilde:LIPIcs.TQC.2017,
  title =	{{LIPIcs, Volume 73, TQC'17, Complete Volume}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017},
  URN =		{urn:nbn:de:0030-drops-86203},
  doi =		{10.4230/LIPIcs.TQC.2017},
  annote =	{Keywords: Data Encryption, Coding and Information Theory, Theory of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2017.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mark M. Wilde

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

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

Mark M. Wilde. Front Matter, Table of Contents, Preface, Conference Organization. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 0:i-0:x, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{wilde:LIPIcs.TQC.2017.0,
  author =	{Wilde, Mark M.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{0:i--0:x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.0},
  URN =		{urn:nbn:de:0030-drops-85742},
  doi =		{10.4230/LIPIcs.TQC.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.1
A Single Entangled System Is an Unbounded Source of Nonlocal Correlations and of Certified Random Numbers

Authors: Florian J. Curchod, Markus Johansson, Remigiusz Augusiak, Matty J. Hoban, Peter Wittek, and Antonio Acín

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
The outcomes of local measurements made on entangled systems can be certified to be random provided that the generated statistics violate a Bell inequality. This way of producing randomness relies only on a minimal set of assumptions because it is independent of the internal functioning of the devices generating the random outcomes. In this context it is crucial to understand both qualitatively and quantitatively how the three fundamental quantities – entanglement, non-locality and randomness – relate to each other. To explore these relationships, we consider the case where repeated (non projective) measurements are made on the physical systems, each measurement being made on the post-measurement state of the previous measurement. In this work, we focus on the following questions: Given a single entangled system, how many nonlocal correlations in a sequence can we obtain? And from this single entangled system, how many certified random numbers is it possible to generate? In the standard scenario with a single measurement in the sequence, it is possible to generate non-local correlations between two distant observers only and the amount of random numbers is very limited. Here we show that we can overcome these limitations and obtain any amount of certified random numbers from a single entangled pair of qubit in a pure state by making sequences of measurements on it. Moreover, the state can be arbitrarily weakly entangled. In addition, this certification is achieved by near-maximal violation of a particular Bell inequality for each measurement in the sequence. We also present numerical results giving insight on the resistance to imperfections and on the importance of the strength of the measurements in our scheme.
Cite as

Florian J. Curchod, Markus Johansson, Remigiusz Augusiak, Matty J. Hoban, Peter Wittek, and Antonio Acín. A Single Entangled System Is an Unbounded Source of Nonlocal Correlations and of Certified Random Numbers. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 1:1-1:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{curchod_et_al:LIPIcs.TQC.2017.1,
  author =	{Curchod, Florian J. and Johansson, Markus and Augusiak, Remigiusz and Hoban, Matty J. and Wittek, Peter and Ac{\'\i}n, Antonio},
  title =	{{A Single Entangled System Is an Unbounded Source of Nonlocal Correlations and of Certified Random Numbers}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.1},
  URN =		{urn:nbn:de:0030-drops-85809},
  doi =		{10.4230/LIPIcs.TQC.2017.1},
  annote =	{Keywords: Randomness certification, Nonlocality, Entanglement, Sequences of measurements}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.2
The Complexity of Simulating Local Measurements on Quantum Systems

Authors: Sevag Gharibian and Justin Yirka

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete. P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.
Cite as

Sevag Gharibian and Justin Yirka. The Complexity of Simulating Local Measurements on Quantum Systems. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 2:1-2:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gharibian_et_al:LIPIcs.TQC.2017.2,
  author =	{Gharibian, Sevag and Yirka, Justin},
  title =	{{The Complexity of Simulating Local Measurements on Quantum Systems}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.2},
  URN =		{urn:nbn:de:0030-drops-85776},
  doi =		{10.4230/LIPIcs.TQC.2017.2},
  annote =	{Keywords: Complexity theory, Quantum Merlin Arthur (QMA), local Hamiltonian, local measurement, spectral gap}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.3
Provably Secure Key Establishment Against Quantum Adversaries

Authors: Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.
Cite as

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably Secure Key Establishment Against Quantum Adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 3:1-3:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belovs_et_al:LIPIcs.TQC.2017.3,
  author =	{Belovs, Aleksandrs and Brassard, Gilles and H{\o}yer, Peter and Kaplan, Marc and Laplante, Sophie and Salvail, Louis},
  title =	{{Provably Secure Key Establishment Against Quantum Adversaries}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.3},
  URN =		{urn:nbn:de:0030-drops-85816},
  doi =		{10.4230/LIPIcs.TQC.2017.3},
  annote =	{Keywords: Merkle puzzles, Key establishment schemes, Quantum cryptography, Adversary method, Average-case analysis}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.4
Quantum Coin Hedging, and a Counter Measure

Authors: Maor Ganz and Or Sattath

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with winning probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis. We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.
Cite as

Maor Ganz and Or Sattath. Quantum Coin Hedging, and a Counter Measure. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganz_et_al:LIPIcs.TQC.2017.4,
  author =	{Ganz, Maor and Sattath, Or},
  title =	{{Quantum Coin Hedging, and a Counter Measure}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.4},
  URN =		{urn:nbn:de:0030-drops-85767},
  doi =		{10.4230/LIPIcs.TQC.2017.4},
  annote =	{Keywords: quantum coin hedging, quantum board games}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.5
Quantum Hedging in Two-Round Prover-Verifier Interactions

Authors: Srinivasan Arunachalam, Abel Molina, and Vincent Russo

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either "win" or "lose". Molina and Watrous previously studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in the prior work of Molina and Watrous. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.
Cite as

Srinivasan Arunachalam, Abel Molina, and Vincent Russo. Quantum Hedging in Two-Round Prover-Verifier Interactions. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 5:1-5:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2017.5,
  author =	{Arunachalam, Srinivasan and Molina, Abel and Russo, Vincent},
  title =	{{Quantum Hedging in Two-Round Prover-Verifier Interactions}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{5:1--5:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.5},
  URN =		{urn:nbn:de:0030-drops-85782},
  doi =		{10.4230/LIPIcs.TQC.2017.5},
  annote =	{Keywords: prover-verifier interactions, parallel repetition, quantum information}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.6
Multiparty Quantum Communication Complexity of Triangle Finding

Authors: François Le Gall and Shogo Nakajima

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
Triangle finding (deciding if a graph contains a triangle or not) is a central problem in quantum query complexity. The quantum communication complexity of this problem, where the edges of the graph are distributed among the players, was considered recently by Ivanyos et al. in the two- party setting. In this paper we consider its k-party quantum communication complexity with k >= 3. Our main result is a ~O(m^(7/12))-qubit protocol, for any constant number of players k, deciding with high probability if a graph with m edges contains a triangle or not. Our approach makes connections between the multiparty quantum communication complexity of triangle finding and the quantum query complexity of graph collision, a well-studied problem in quantum query complexity.
Cite as

François Le Gall and Shogo Nakajima. Multiparty Quantum Communication Complexity of Triangle Finding. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 6:1-6:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.TQC.2017.6,
  author =	{Le Gall, Fran\c{c}ois and Nakajima, Shogo},
  title =	{{Multiparty Quantum Communication Complexity of Triangle Finding}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.6},
  URN =		{urn:nbn:de:0030-drops-85793},
  doi =		{10.4230/LIPIcs.TQC.2017.6},
  annote =	{Keywords: Quantum communication complexity, triangle finding, graph collision}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.7
Improved reversible and quantum circuits for Karatsuba-based integer multiplication

Authors: Alex Parent, Martin Roetteler, and Michele Mosca

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from O(n^1.585) to O(n^1.427). This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than 2 and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.
Cite as

Alex Parent, Martin Roetteler, and Michele Mosca. Improved reversible and quantum circuits for Karatsuba-based integer multiplication. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{parent_et_al:LIPIcs.TQC.2017.7,
  author =	{Parent, Alex and Roetteler, Martin and Mosca, Michele},
  title =	{{Improved reversible and quantum circuits for Karatsuba-based integer multiplication}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.7},
  URN =		{urn:nbn:de:0030-drops-85841},
  doi =		{10.4230/LIPIcs.TQC.2017.7},
  annote =	{Keywords: Quantum algorithms, reversible circuits, quantum circuits, integer multiplication, pebble games, Karatsuba's method}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.8
Fidelity of Quantum Strategies with Applications to Cryptography

Authors: Gus Gutoski, Ansis Rosmanis, and Jamie Sikora

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
We introduce a definition of the fidelity function for multi-round quantum strategies, which we call the strategy fidelity, that is a generalization of the fidelity function for quantum states. We provide many interesting properties of the strategy fidelity including a Fuchs-van de Graaf relationship with the strategy norm. We illustrate an operational interpretation of the strategy fidelity in the spirit of Uhlmann's Theorem and discuss its application to the security analysis of quantum protocols for interactive cryptographic tasks such as bit-commitment and oblivious string transfer. Our analysis is very general in the sense that the actions of the protocol need not be fully specified, which is in stark contrast to most other security proofs. Lastly, we provide a semidefinite programming formulation of the strategy fidelity.
Cite as

Gus Gutoski, Ansis Rosmanis, and Jamie Sikora. Fidelity of Quantum Strategies with Applications to Cryptography. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 8:1-8:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gutoski_et_al:LIPIcs.TQC.2017.8,
  author =	{Gutoski, Gus and Rosmanis, Ansis and Sikora, Jamie},
  title =	{{Fidelity of Quantum Strategies with Applications to Cryptography}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.8},
  URN =		{urn:nbn:de:0030-drops-85830},
  doi =		{10.4230/LIPIcs.TQC.2017.8},
  annote =	{Keywords: Quantum strategies, cryptography, fidelity, semidefinite programming}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.9
Minimum Quantum Resources for Strong Non-Locality

Authors: Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
We analyse the minimum quantum resources needed to realise strong non-locality, as exemplified e.g. by the classical GHZ construction. It was already known that no two-qubit system, with any finite number of local measurements, can realise strong non-locality. For three-qubit systems, we show that strong non-locality can only be realised in the GHZ SLOCC class, and with equatorial measurements. However, we show that in this class there is an infinite family of states which are pairwise non LU-equivalent that realise strong non-locality with finitely many measurements. These states have decreasing entanglement between one qubit and the other two, necessitating an increasing number of local measurements on the latter.
Cite as

Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield. Minimum Quantum Resources for Strong Non-Locality. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 9:1-9:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abramsky_et_al:LIPIcs.TQC.2017.9,
  author =	{Abramsky, Samson and Barbosa, Rui Soares and Car\`{u}, Giovanni and de Silva, Nadish and Kishida, Kohei and Mansfield, Shane},
  title =	{{Minimum Quantum Resources for Strong Non-Locality}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.9},
  URN =		{urn:nbn:de:0030-drops-85822},
  doi =		{10.4230/LIPIcs.TQC.2017.9},
  annote =	{Keywords: strong non-locality, maximal non-locality, quantum resources, three-qubit states}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.10
Approximate Reversal of Quantum Gaussian Dynamics

Authors: Ludovico Lami, Siddhartha Das, and Mark M. Wilde

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
Recently, there has been focus on determining the conditions under which the data processing inequality for quantum relative entropy is satisfied with approximate equality. The solution of the exact equality case is due to Petz, who showed that the quantum relative entropy between two quantum states stays the same after the action of a quantum channel if and only if there is a reversal channel that recovers the original states after the channel acts. Furthermore, this reversal channel can be constructed explicitly and is now called the Petz recovery map. Recent developments have shown that a variation of the Petz recovery map works well for recovery in the case of approximate equality of the data processing inequality. Our main contribution here is a proof that bosonic Gaussian states and channels possess a particular closure property, namely, that the Petz recovery map associated to a bosonic Gaussian state \sigma and a bosonic Gaussian channel N is itself a bosonic Gaussian channel. We furthermore give an explicit construction of the Petz recovery map in this case, in terms of the mean vector and covariance matrix of the state \sigma and the Gaussian specification of the channel N.
Cite as

Ludovico Lami, Siddhartha Das, and Mark M. Wilde. Approximate Reversal of Quantum Gaussian Dynamics. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lami_et_al:LIPIcs.TQC.2017.10,
  author =	{Lami, Ludovico and Das, Siddhartha and Wilde, Mark M.},
  title =	{{Approximate Reversal of Quantum Gaussian Dynamics}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.10},
  URN =		{urn:nbn:de:0030-drops-85751},
  doi =		{10.4230/LIPIcs.TQC.2017.10},
  annote =	{Keywords: Gaussian dynamics, Petz recovery map}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.52
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.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
DOI: 10.4230/LIPIcs.TQC.2013.157
Towards Efficient Decoding of Classical-Quantum Polar Codes

Authors: Mark M. Wilde, Olivier Landon-Cardinal, and Patrick Hayden

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Known strategies for sending bits at the capacity rate over a general channel with classical input and quantum output (a cq channel) require the decoder to implement impractically complicated collective measurements. Here, we show that a fully collective strategy is not necessary in order to recover all of the information bits. In fact, when coding for a large number N uses of a cq channel W, N*I(W_{acc}) of the bits can be recovered by a non-collective strategy which amounts to coherent quantum processing of the results of product measurements, where I(W_{acc}) is the accessible information of the channel W. In order to decode the other N(I(W)-I(W_{acc})) bits, where I(W) is the Holevo rate, our conclusion is that the receiver should employ collective measurements. We also present two other results: 1) collective Fuchs-Caves measurements (quantum likelihood ratio measurements) can be used at the receiver to achieve the Holevo rate and 2) we give an explicit form of the Helstrom measurements used in small-size polar codes. The main approach used to demonstrate these results is a quantum extension of Arikan's polar codes.
Cite as

Mark M. Wilde, Olivier Landon-Cardinal, and Patrick Hayden. Towards Efficient Decoding of Classical-Quantum Polar Codes. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 157-177, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{wilde_et_al:LIPIcs.TQC.2013.157,
  author =	{Wilde, Mark M. and Landon-Cardinal, Olivier and Hayden, Patrick},
  title =	{{Towards Efficient Decoding of Classical-Quantum Polar Codes}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{157--177},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.157},
  URN =		{urn:nbn:de:0030-drops-43141},
  doi =		{10.4230/LIPIcs.TQC.2013.157},
  annote =	{Keywords: classical-quantum channel, classical-quantum polar codes, quantum likelihood ratio, quantum successive cancellation decoder}
}
  • Refine by Author
  • 5 Wilde, Mark M.
  • 1 Abramsky, Samson
  • 1 Acín, Antonio
  • 1 Arunachalam, Srinivasan
  • 1 Augusiak, Remigiusz
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Adversary method
  • 1 Average-case analysis
  • 1 Complexity theory
  • 1 Conference Organization
  • 1 Data Encryption, Coding and Information Theory, Theory of Computation
  • Show More...

  • Refine by Type
  • 14 document
  • 1 volume

  • Refine by Publication Year
  • 13 2018
  • 1 2013
  • 1 2014

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact