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.
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.
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.