The first Israel Quantum Information Theory Day workshop was held on 21/12/2022 at the Weizmann Institute of Science.
The goal of the workshop is to bring together the Israeli scientific commnunty interested in the theoretical aspects of quantum information theory. The topics include quantum computation, cryptography, complexity, information theory and more. The workshop will include several invited talks, a students' poster session, and free time to engage with one another. We hope to increase the connections and collaborations of scientists within Israel by having several such meetings, hosted in a different university each time.
See the workshop's photo gallery here.
The speakers of the workshop at 2022:
- Dorit Aharonov (Hebrew University)
- Amit Behera (Ben-Gurion University)
- Nir Bitansky (Tel-Aviv University)
- Rahul Jain (National University of Singapore)
- Serge Rosemblum (Weizmann Institute of Science)
Local organization: Rotem Arnon-Friedman, Zvika Brakerski & Thomas Vidick
Contact person: thomas.vidick@weizmann.ac.il
Schedule
The conference will be held at The David Lopatie Conference Center at Weizmann Institute of Science.
Schedule:
-- 9:30-10 Registration & Coffee
-- 10-10:45 Dorit Aharonov: A polynomial-time classical algorithm for noisy random circuit
sampling
-- 10:45-11:15 Break
-- 11:15-12:00 Serge Rosenblum: Low-overhead quantum error correction with bosonic qubits
-- 12-1:15 Lunch
-- 1:15-2:00 Nir Bitansky: Constructive Post-Quantum Reductions
-- 2:00-2:40 Amit Behera: Noise-Tolerant Quantum Tokens for MAC
-- 2:40-3:15 Break
-- 3:15-4:00 Rahul Jain: A direct product theorem for quantum communication complexity with applications to device-independent QKD
-- 4:00-5:30 Posters & snacks
Abstracts
Speaker: Dorit Aharonov
Title: A polynomial-time classical algorithm for noisy random circuit
sampling
Abstract:
The field of quantum computation heavily relies on the belief
that quantum computation violates the extended Church Turing thesis,
namely, that quantum many body systems cannot be simulated by classical
ones with only polynomially growing overhead. What experimental evidence
do we have for this assumption?
There is an inherent difficulty in collecting such evidence, as I will
remind us in the talk. A major effort towards providing evidence for
quantum advantage concentrate on "quantum supremacy" experiments via
quantum random circuit sampling (RCS). These experiments can be modeled
as sampling from a random quantum circuit where each gate is subject to
a small amount of noise. We give a polynomial time classical algorithm
for sampling from the output distribution of a noisy random quantum
circuit in the regime of anti-concentration to within inverse polynomial
total variation distance. It should be noted that our algorithm is not
practical in its current form, and does not address finite-size RCS
based quantum supremacy experiments. Our result gives strong evidence
that random circuit sampling (RCS) cannot be the basis of a scalable
experimental violation of the extended Church-Turing thesis.
Based on recent joint work with Xun Gao, Zeph Landau Yunchao Liu and
Umesh Vazirani, arXiv: 2211.03999
Speaker: Nir Bitansky
Title: Constructive Post-Quantum Reductions
Abstract:
Is it possible to convert classical cryptographic reductions
into post-quantum ones? It is customary to argue that while this is
problematic in the interactive setting, non-interactive reductions do
carry over. However, when considering quantum auxiliary input, this
conversion results in a non-constructive post-quantum reduction that
requires duplicating the quantum auxiliary input, which is in general
inefficient or even impossible. This violates the win-win premise of
provable cryptography: an attack against a cryptographic primitive
should lead to an algorithmic advantage.
We initiate the study of constructive quantum reductions and present
positive and negative results for converting large classes of classical
reductions to the post-quantum setting in a constructive manner. We show
that any non-interactive non-adaptive reduction from assumptions with a
polynomial solution space (such as decision assumptions) can be made
post-quantum constructive. In contrast, assumptions with
super-polynomial solution space (such as general search assumptions)
cannot be generally converted.
Along the way, we make several additional contributions:
1. We put forth a framework for reductions (or general interaction) with
stateful solvers for a computational problem, that may change their
internal state between consecutive calls. We show that such solvers can
still be utilized. This framework and our results are meaningful even in
the classical setting.
2. A consequence of our negative result is that quantum auxiliary input
that is useful against a problem with a super-polynomial solution space
cannot be generically “restored” post-measurement. This shows that the
novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the
sense that it cannot be extended beyond a polynomial measurement space.
Joint work with Zvika Brakerski and Yael Kalai.
Speaker: Amit Behera
Title: Noise-Tolerant Quantum Tokens for MAC
Abstract:
Message Authentication Code, or MAC, is a well-studied cryptographic
primitive that is used to authenticate communication between two parties
who share a secret key. A Tokenized MAC or TMAC is a related
cryptographic primitive, introduced by Ben-David & Sattath (QCrypt’17),
which allows a limited signing authority to be delegated to third
parties via the use of single-use quantum signing tokens. These tokens
can be issued using the secret key, such that each token can be used to
sign at most one document.
In this talk, I am going to talk about new construction for TMAC based
on BB84 states which can tolerate up to 14% noise, making it the first
noise-tolerant TMAC construction. The simplicity of the quantum states
required for our construction, combined with its noise tolerance, makes
it practically more feasible than the previous TMAC construction. The
TMAC presented is existentially unforgeable against adversaries with
signing and verification oracles (i.e., it is analogous to EUF-CMA
security for MAC), assuming that post-quantum one-way functions exist.
Based on joint work with Dr. Or Sattath and Uriel Shinar, arXiv:2105.05016
Speaker: Rahul Jain
Title: A direct product theorem for quantum communication complexity
with applications to device-independent QKD.
Abstract:
We give a direct product theorem for the entanglement-assisted
interactive quantum communication complexity of an l-player predicate V.
In particular we show that for a distribution p that is product across
the input sets of the l players, the success probability of any
entanglement-assisted quantum communication protocol for computing n
copies of V, whose communication is o(log(eff∗(V,p))⋅n), goes down
exponentially in n. Here eff∗(V,p) is a distributional version of the
quantum efficiency or partition bound introduced by Laplante, Lerays and
Roland (2014), which is a lower bound on the distributional quantum
communication complexity of computing a single copy of V with respect to p.
As an application of our result, we show that it is possible to do
device-independent quantum key distribution (DIQKD) without the
assumption that devices do not leak any information after inputs are
provided to them. We analyze the DIQKD protocol given by Jain, Miller
and Shi (2017), and show that when the protocol is carried out with
devices that are compatible with n copies of the Magic Square game, it
is possible to extract Ω(n) bits of key from it, even in the presence of
O(n) bits of leakage. Our security proof is parallel, i.e., the honest
parties can enter all their inputs into their devices at once, and works
for a leakage model that is arbitrarily interactive, i.e., the devices
of the honest parties Alice and Bob can exchange information with each
other and with the eavesdropper Eve in any number of rounds, as long as
the total number of bits or qubits communicated is bounded.
The talk is based on:
A direct product theorem for quantum communication complexity with
applications to device-independent QKD. Rahul Jain, Srijita Kundu.
Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021.
Conference on Quantum Information Processing (QIP), 2022 (short plenary
talk).
The event is sponsored by the Center for Quantum Science and Technology at the Weizmann Institute of Science.