Agenda

Département
Langue
Date
Thématique
2024

septembre

  • 10:45
    11:45

    Quentin Buzet (Télécom Paris) Can quantum walk search be useful for solving problems in the CONGEST and CONGEST-CLIQUE model?

    The k-distinctness problem is a major problem in quantum computing. The best quantum centralized (i.e., non-distributed) algorithms for the k-distinctness problem are based on quantum walk search. In this work, we investigate the complexity of this problem in the distributed setting.
    By slightly modifying the algorithm by Le Gall and Magniez (PODC 2018) for network diameter computation in the quantum CONGEST model, we derive a distributed quantum algorithm that efficiently solves a natural distributed version of k-distinctness without using a quantum walk search.
    By studying the complexity of a more general problem (k-subset-finding), we obtain a lower bound which suggests that quantum walk search might be a useful technique for solving certain difficult instances of this problem.
    Finally, we study what happens in the CONGEST-CLIQUE model and gives a framework to transform a quantum parallel query algorithm into a distributed one in the CONGEST-CLIQUE model.

    If time allows, we could discuss a little bit the multiplication of rectangular matrices in the CONGEST-CLIQUE model.

    https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

    Room 178
  • 12:45
    13:45

    Séminaire de François Pellegrini. Intitulé de son exposé : "Liberté(s) à l’ère numérique"

    François Pellegrini interviendra dans le cadre des séminaires Numerics.

    Amphi LaBRI
  • 13:00
    14:00

    [MTV] Aditya Prakash (U. Warwick) - Recognising history-deterministic parity atutomata

    A nondeterministic parity automaton is history-deterministic if there is a resolver that can resolve the nondeterminism on the fly while reading a word, based on the prefix read so far. The notion of history-determinism has been studied extensively over the recent years, yet the complexity of deciding history-determinism for parity automata has remained open since 2006.

    In this talk, I will present some recent progress we have made on this problem. This is based on part published and part ongoing works, together with Rohan Acharya, Marcin Jurdziński, and Karoliina Lehtinen.

    076
  • 14:00
    15:00

    [gt.go][gdr-ifm-gt-graphes] by Paul Bastide

    N/A

    Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

    Remarks / Remarques

    Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
    Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

    LaBRI/178

octobre

  • 10:45
    11:45

    [ICQ] Gerard Valenti-Rojas (Naquidis-IMB)

    Towards “Good-Enough” Quantum Low-Density Parity-Check Codes

    The accumulation of errors in quantum computers obstructs the execution of powerful algorithms. Hence,
    current quantum computers require Quantum Error Correction (QEC) in order to be functional and reliable
    even in the presence of such errors, something known as Fault-Tolerant Quantum Computation (FTQC).
    Conventional strategies for protecting and correcting against qubit errors, such as Surface Codes, suffer
    from large overheads in the number of physical qubits that are used to encode logical information. In other
    words, practical implementation of quantum error-correcting codes requires a better ratio between the
    number of logical and physical qubits, something known as a high encoding rate. Quantum Tanner Codes
    have been shown to be optimal in the asymptotic limit due to their rich structure, providing a potential
    solution to this conundrum. However, “good-enough” finite explicit constructions have not been found so
    far. In this work, we reformulate Tanner codes as unconventional lattice gauge theories describing spin
    many-body systems. Preliminary results indicate the potential for an unusually robust relative of
    topologically ordered matter as a key element for the outstanding capabilities of this family of codes.

    https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

    Room 178
  • 13:00
    14:00

    [MTV] Clotilde Bizière (LaBRI) - TBA

    178
  • 10:45
    12:00

    [ICQ] David Casanova (DIPC San Sébastien)

    Room 178

novembre