Welcome to the website of the 2nd NRW Quantum Theoretical CS Workshop! This workshop brings together researchers in quantum TCS in Germany and neighboring countries for an informal day of stimulating talks, friendly discussions, and if we're lucky, a few spirited (but civil) scientific quarrels. The first edition was held in 2023 at Ruhr University Bochum.
 

Date: Wednesday, December 18, 2024
Place: Paderborn University, Building O, Lecture hall O2

Organizing Committee: Dorian Rudolph (Chair), Sevag Gharibian (U Paderborn), Michael Walter (U Bochum)
Contact: dorian dot rudolph at upb dot de

Speakers

Simon Apers (Université Paris Cité, CNRS, IRIF)
Jens Eisert (FU Berlin)
Otfried Gühne (University of Siegen)
Robert König (TU Munich)
Tobias Stollenwerk (FZ Jülich)
Maarten Stroeks (Delft University of Technology)
Michael Walter (Ruhr University Bochum)
Ronald de Wolf (QuSoft, CWI and University of Amsterdam)

Schedule (further details to be posted soon)

Talks

Simon Apers: Directed st-connectivity with few paths is in quantum logspace

We present a $BQSPACE(O(\log(n)))$-procedure to count st-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in s and polynomially many paths ending in t. For comparison, the best known classical upper bound in this case just to decide st-connectivity is $DSPACE(O(\log^2(n)/\log\log(n)))$. The result establishes a new relationship between BQL and unambiguity and fewness subclasses of NL. Further, some preprocessing in our approach also allows us to verify whether there are at most polynomially many paths between any two nodes in $BQSPACE(O(\log(n)))$. This yields the first natural candidate for a language problem separating BQL from L and BPL. Until now, all candidates separating these classes were promise problems.

Joint work with Roman Edenhofer.

Jens Eisert: Quo vadis, quantum machine learning?

Quantum machine learning promises advantages in machine learning in terms of sample complexity, computational complexity or generalization, and the field has been enjoying substantial progress in the last few years. Yet, a core aim - to arrive at quantum algorithms that feature proven separations of quantum over classical learners for practically relevant unstructured data - seems elusive to date. In this talk, we will try to come closer to this aim from a number of different angles. We will see that for the training of classical networks using quantum algorithms [1], for abstract instances of density modeling [2], for quantum training of classical networks [3] and for short quantum circuits [4], rigorous separations can be found. At the same time, we will elaborate on obstructions that arise from notions of dequantization in noise-free [5] and (non-unital) noisy settings [6,7]. These insights can also be seen as invitations to think outside the box, and we will rethink generalization [8] and look at instances of explainable quantum machine learning [9] or single-shot quantum machine learning [10].

[1] Nature Comm. 15, 434 (2024).
[2] Phys. Rev. A 107, 042416 (2023).
[3] arXiv:2309.11647 (2023).
[4] arXiv:2411.15548 (2024).
[5] Phys. Rev. Lett. 131, 100803 (2023).
[6] arXiv:2403.13927 (2024).
[7] Nature Phys. 20, 1648 (2024).
[8] Nature Comm. 15, 2277 (2024).
[9] arXiv:today (2024).
[10] arXiv:2404.03585 (2024).

Otfried Gühne: Quantifying entanglement from the geometric perspective

Quantifying entanglement is difficult, especially in the multiparticle scenario. One possible quantifier is the geometric measure of entanglement. For pure states, this is essentially given by the maximal overlap of a given pure state with product states. In the mathematical literature, this is also known as the injective tensor norm. In my talk I will discuss three topics: First, I will discuss how one can find quantum states with the maximal geometric measure. Second I will present some results on subspaces where all states are highly entangled. Third, I will discuss methods to compute the geometric measure by considering multiple copies of quantum states. This talk is partly based on arXiv:2210.13475.

Robert Koenig: Factoring an integer with three oscillators and a qubit

A common starting point of  traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating finite sets of symbols, and allows for a device-independent development of algorithmic primitives.

Here we advocate an alternative approach centered on the physical setup and the associated set of natively available operations. We show that these can be leveraged to great benefit by sidestepping the standard approach of reasoning about computation  in terms of individual qubits.

As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous-variable (CV) Fourier transform has a native realization in such systems in the form of homodyne momentum measurements. We show that this fact can be put to algorithmic use. Specifically, we give a polynomial-time quantum algorithm in this setup which finds a factor of an n-bit integer N.  Unlike Shor's algorithm, or CV implementations thereof based on qubit-to-oscillator encodings, our algorithm relies on the CV (rather than discrete) Fourier transform. The physical system used is independent of  the number N to be factored: It consists of a single qubit and three oscillators only.

This is joint work with Lukas Brenner, Libor Caha and Xavier Coiteux-Roy.

Tobias Stollenwerk: Quantum Algorithm for Modal Analysis in Structural Mechanics

Inspired by a real-world problem from computational engineering, this work investigates quantum algorithms for addressing key computational challenges in simulating coupled harmonic oscillators within the context of finite element methods.
Specifically, we present a quantum algorithm to estimate frequency response functions of classical harmonic oscillator networks based on quantum phase estimation.
Our approach does not suffer from the infamous state preparation bottleneck and can as such potentially achieve large quantum speedups compared to relevant classical methods.
We provide an analysis of the worst-case query complexity and qubit requirements as functions of the problem parameters and desired precision.

Joint work with Sven Danz, Mario Berta, Stefan Schröder, Pascal Kienast, Frank Wilhelm, Alessandro Ciani (arXiv:2405.08694)

Maarten Stroeks: Complexity of Fermionic 2-SAT

We introduce the fermionic satisfiability problem Fermionic k-SAT: this problem amounts to checking whether there is a fermionic state which is in the null-space of a collection of fermionic projectors on n fermionic modes, where each fermionic projector involves k fermionic modes. We investigate the complexity of this problem for k = 2, where, in addition, each projector is either (1) particle-number conserving or (2) merely particle-parity conserving. We prove that this problem can be solved efficiently classically. In addition, we show that deciding whether there exists a satisfying assignment for a given fixed particle parity can also be solved efficiently classically: this problem is a quantum-fermionic extension of simply asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity, which we also show can be decided efficiently. We prove that, in contrast, deciding whether there exists a satisfying assignment for Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA_1-hard.

Michael Walter: Trading Space for Time in Nonlocal Games

Nonlocal games are a foundational tool in quantum information and complexity. They give an operational perspective on entanglement, which in turn has led to powerful protocols in settings with spatially-separated quantum devices. A recent line of work initiated by Kalai et al (STOC'23) investigates to which extent spatial separation can be replaced by time-like separation, by using cryptography. I will give an introduction to this line of work and its motivations, and present a general result that bounds the performance of efficient players in the time-like setting by the quantum commuting operator value, which describes the optimal performance of space-like players in general quantum theory. For XOR games, this achieves a computational version of Tsirelson's theorem. These results show rigorously how spatial separation can emerge through the lens of computational complexity. Based on 2408.06711 and 2402.17301.

Ronald de Wolf: Quantum Algorithms for Optimization

Faster algorithms for optimization problems are among the main potential applications for future quantum computers. There has been interesting progress in this area in recent years, for instance improved quantum algorithms for gradient descent and for solving linear and semidefinite programs. In this talk I will survey what we know about quantum speed-ups both for discrete and for continuous optimization, with a bit more detail about two speed-ups I worked on recently: for regularized linear regression and for Principal Component Analysis. I'll also discuss some issues with this line of work, in particular that quadratic or subquadratic quantum speed-ups will only kick in for very large instance sizes and that many of these algorithms require some kind of quantum RAM.