2 Search Results for "Landon-Cardinal, Olivier"


Document
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-dev.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}
}
Document
The Determinacy of Context-Free Games

Authors: Olivier Finkel

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).

Cite as

Olivier Finkel. The Determinacy of Context-Free Games. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 555-566, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{finkel:LIPIcs.STACS.2012.555,
  author =	{Finkel, Olivier},
  title =	{{The Determinacy of Context-Free Games}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{555--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.555},
  URN =		{urn:nbn:de:0030-drops-33897},
  doi =		{10.4230/LIPIcs.STACS.2012.555},
  annote =	{Keywords: Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games}
}
  • Refine by Author
  • 1 Finkel, Olivier
  • 1 Hayden, Patrick
  • 1 Landon-Cardinal, Olivier
  • 1 Wilde, Mark M.

  • Refine by Classification

  • Refine by Keyword
  • 1 Automata and formal languages
  • 1 Gale-Stewart games
  • 1 Wadge games
  • 1 classical-quantum channel
  • 1 classical-quantum polar codes
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2013

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