September 2021 - ITP-quantumseminare

No QIT Seminar this week (Group members: group meeting instead)
by Joe Renes 28 Sep '21

28 Sep '21

Hi all, There's no QIT Seminar this week. Next week we'll hear from Christophe Piveteau on his latest research -- see below. That will be at 2pm on zoom: https://ethz.zoom.us/j/362994444 Best, Joe Speaker: Christophe Piveteau Title: Quantum message-passing algorithm for optimal and efficient decoding Abstract: Recently, Renes 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 [Renes, NJP 19 072001 (2017)]. 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. [npj Quantum Information 7 97 (2021)] 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/ϵ), where n is the code length and ϵ 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.

1 0

Today's QIT Seminar
by Joe Renes 14 Sep '21

14 Sep '21

Hi all, Apologies, I'm terribly late with this week's email. Today at 2pm we hear from Arne Thomson on "Comparing Quantum Neural Networks and Quantum Support Vector Machines". See below for the abstract. The talk will be on zoom: https://ethz.zoom.us/j/362994444 Best, Joe %%% We prove a polynomial speedup compared to [Liu, Arunachalam, and Temme “A rigorous and robust quantum speed-up in supervised machine learning <https://www.nature.com/articles/s41567-021-01287-z>”] for training of noisy quantum support vector machines via the dual optimization problem. We introduce the Pegasos algorithm as an alternative and derive bounds on its runtime, which scales favorably. In addition, we analyze quantum neural networks numerically from the same perspective.

1 0

Tomorrow's QIT Seminar 11 am
by Joe Renes 09 Sep '21

09 Sep '21

Hi all, Sorry for the late notice, I'm only slowly coming out of summer mode! Tomorrow at 11 am we will have our first talk of the QIT Seminar in a while, from Noah Berner on "Quantum Bayesian Neural Networks". See below for the abstract. There's also a preprint available already, in case you want to read more: https://arxiv.org/abs/2107.09599. We're in the usual zoom room for the QIT Seminar: https://ethz.zoom.us/j/362994444. Next week we return to our usual time on Tuesdays at 2pm. Best, Joe %%%%% Quantum machine learning promises great speedups over classical algorithms, but it often requires repeated computations to achieve a desired level of accuracy for its point estimates. Bayesian learning focuses more on sampling from posterior distributions than on point estimation, thus it might be more forgiving in the face of additional quantum noise. We propose a quantum algorithm for Bayesian neural network inference, drawing on recent advances in quantum deep learning, and simulate its empirical performance on several tasks. We find that already for small numbers of qubits, our algorithm approximates the true posterior well, while it does not require any repeated computations and thus fully realizes the quantum speedups.

1 0