Quantum Engineering Grenoble Seminar || Quantum Computing || Joseph Renes: "Quantum message-passing algorithm for optimal and efficient decoding"

on the October 26, 2021

At 2pm
Quantum Engineering Grenoble Seminar Team is pleased to announce that Joseph Renes (ETH Zürich) will give a QuEnG Quantum Computing seminar on Tuesday 26 October at 2pm at LIG (room 482, IMAG building), as well as on Zoom as a hybrid event (link below) for those unable to attend in person. It is once again possible to have an in-person seminar, and I strongly encourage those able to attend in person to do so (note: pass sanitaire required). Nonetheless, we have decided to trial a hybrid format so that those unable to attend in person can still participate. We plan to use Zoom for this (link below). We will review the format (and location of the seminar) for future seminars.
Title: Quantum message-passing algorithm for optimal and efficient decoding
Abstract (from https://arxiv.org/abs/2109.08170): Recently, we proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel. This algorithm presents a genuine quantum counterpart to decoding based on classical belief propagation, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. numerically observed that, for a small example code, BPQM implements the optimal decoder for determining the entire input codeword. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code size. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has circuit complexity O(poly n, polylog 1/epsilon), where n is the code length and epsilon is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder.
Access (in person)
The seminar will take place in room at LIG, in room 482 of the IMAG building on the campus. Someone will wait in the entrance to provide participants with access to the 4th floor. 
Zoom link + details:
Meeting ID: 985 1551 2137
Passcode: 436965
Published on November 3, 2021

Practical informations


on Zoom as a hybrid event (read on for details)