Quantum Information Workshop (November 2023)

Date: Thursday, November 23, 2023
Place: Ruhr University Bochum, Building MC, “Open Space” (ground floor, see here for directions to the building)

We organized a one-day workshop, with a fantastic set of speakers, covering recent directions in quantum information, algorithms, complexity, and cryptography. Video recordings are now available on YouTube 🍿!

Schedule

Abstracts

Mario Berta, Quantum algorithms for the early fault-tolerance regime

As improvements in hardware increase the number and quality of qubits, we seek quantum algorithms that can showcase practical quantum advantage in the earliest possible time frame. Looking beyond noisy intermediate-scale quantum technologies, it is reasonable to assume that, given continued progress in quantum hardware, so-called fault-tolerant algorithms will have an important place in the gamut of quantum computing applications. Thus, it is pertinent to ask how soon such algorithms can be useful for real-life applications, and how much can we accelerate this timeline by constructing algorithms with lower and more flexible finite quantum resource costs. I will present a selection of qubit efficient quantum algorithms that allow for a flexible trading between quantum circuit depth and sample complexity, and outsource all but the critical quantum sub-routines to classical pre- and post-processing.

Christian Majenz, Post-quantum security of the (tweakable) Even-Mansour cipher

The Even-Mansour cipher is arguably the simplest block cipher construction, based on a public cryptographic permutation. The cipher and its variants enjoy provable “pre-quantum” security in a number of models, including the ideal permutation model where the cryptographic permutation is modelled as a uniformly random permutation, and all agents have oracle access to this permutation and its inverse. In this talk, based on joint work with Gorjan Alagic, Chen Bai, Jonathan Katz and Patrick Struck (https://eprint.iacr.org/2021/160, https://eprint.iacr.org/2022/1097), I will begin by describing the Even-Mansour cipher and its variants and illustrating what challenges arise when trying to prove post-quantum security in the quantum-accessible ideal permutation model. I will then describe how we tackle these challenges via a judiciously chosen hybrid sequence and a permutation version of a lemma called “resampling” or “adaptive reprogramming”. Finally, I will show how our result for the tweakable Even-Mansour cipher is applied to prove post-quantum security of a number of real-world cryptographic schemes.

Sevag Gharibian, The optimal depth of variational quantum algorithms is QCMA-hard to approximate

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational ansatz used - the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ε > 0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N^(1-ε), for N denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even “simpler” QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.

Joint work with Lennart Bittel (FU Berlin) and Martin Kliesch (TU Hamburg).

Gláucia Murta, Device-independent entanglement certification with dishonest parties

We consider the task of device-independent certification of the quantum state distributed in a network when some of the nodes in this network may collude and act dishonestly. In this talk I will introduce the paradigm of self-testing with dishonest parties and show that this can be used for state certification in a network with dishonest parties and also provide robust statements about the fidelity of the distributed quantum state.

Giulio Malavolta, Robust Quantum Public-Key Encryption with Applications to Quantum Key Distribution

Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. Compared to classical key exchange, it has two main advantages:
(i) The key is unconditionally hidden to the eyes of any attacker, and
(ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures.
On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages using public-key encryption. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange. In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions. That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new construction of quantum public-key encryption (QPKE) whose security, much like its classical counterpart, only relies on authenticated classical channels.

Laurens Ligthart, Quantum correlations in the bilocal scenario

It is a fundamental but difficult problem to characterize the set of correlations that can be obtained by performing measurements on quantum mechanical systems. In this talk, I will show that there are two convergent semidefinite programming hierarchies for the quantum bilocal scenario, a much-studied abstract model of entanglement swapping experiments. The first hierarchy is based on the quantum inflation technique, while the second uses a trick known as polarization. In addition, both hierarchies make use of the theory of non-commutative polynomial optimization. I will also argue that the polarization technique can be interpreted more generally as giving rise to an SDP hierarchy that is complete for the problem of optimizing polynomial functions in the states of operator algebras defined by generators and relations. The completeness of this polarization hierarchy follows from a quantum de Finetti theorem for states on maximal C*-tensor products.