test_moissonnage_selune
type: Agent

Two-player interaction in quantum computing : cryptographic primitives & query complexity
type: Dataset
contact point: Organization
  fn: CCSD
keyword: complexite-en-requete
keyword: methode-par-adversaire
keyword: polynomial-method
keyword: quantum-query-complexity
keyword: quantum-bit-commitment
keyword: theoreme-fort-de-produit-direct
keyword: primitives-cryptographiques-quantique
keyword: quantum-computing
keyword: methode-polynomiale
keyword: tirage-quantique-a-pile-ou-face
keyword: quantum-coin-flipping
keyword: mise-en-gage-quantique
keyword: quantum-cryptographic-primitives
keyword: theses
keyword: strong-direct-product-theorem
keyword: adversary-method
keyword: infoinfo-ohcomputer-science-csother-csoh
keyword: infoeu-reposemanticsdoctoralthesis
landing page: https://theses.hal.science/tel-00676922
description: This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``…
identifier: NNT: 2011PA112275
issued: 2026-05-25T14:16:01.274283
language: en
modified: 2026-05-25T14:16:01.274300

Two-player interaction in quantum computing : cryptographic primitives & query complexity
type: Distribution
access URL: https://theses.hal.science/tel-00676922
format: HTML
issued: 2026-05-25T14:16:01.432148
modified: 2026-05-25T14:16:01.182953