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