Johannes Jakob Meyer

23h

What a time to be in computer science!

Ryan Williams@rrwilliams.bsky.social

An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4

@walruscomputing.bsky.social

I'm really looking forward to joining Walrus in November! 🚀

Walrus Computing@walruscomputing.bsky.social

Today, Walrus Computing is coming out of stealth. We’re on a mission to turn fault-tolerant quantum computers into engines of discovery. We build the software layer that makes them useful to anyone with a question worth asking.

Johannes Jakob Meyer reposted

Walrus Computing

Can people please stop to write that they "take full responsibility for the results" in their AI disclosures? You posted a paper on the arXiv. With your name on it.

9 May

I recently submitted my PhD thesis 🎉 I am now planning the next step of my journey. I will stay in Berlin for personal reasons, which makes me curious which research groups and companies would hire postdocs or equivalent for remote positions. If you have any leads, please DM!

scholar.google.comscholar.google.com

9 May

For an overview of my research, consider my Google Scholar: scholar.google.com/citations?us... My current focus is to merge quantum information theory with computational complexity, but I have very broad interests all across quantum information.

18 Mar

Such a well-deserved honor! Taking Gilles Brassard's quantum info course at UdeM is what got me into the field. It is still the best course I ever attended.

Association for Computing Machinery@acm.org

Congratulations to Charles H. Bennett and Gilles Brassard on receiving the 2025 ACM A.M. Turing Award! They are recognized for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing. awards.acm.org/turing @umontreal

scirate.comThe computational two-way quantum capacityQuantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the st...

23 Jan

Last year, I became interested in the question what happens if we impose computational efficiency onto information theory. In our latest paper, we analyze how this changes the amount of information that can be transmitted over a channel -- spoiler alert: a lot! scirate.com/arxiv/2601.1...

First, we show that there exists a nearly maximal separation between the computational and unbounded two-way quantum capacity. Second, we show a transition in computational capacity from nearly maximal to zero when the complexity (in terms of Choi rank) goes from polynomial to super-polynomial.

23 Jan

Our work shows that there is a need for quantum communication theory and computational complexity to converge more fully, with many more exciting questions ahead!

We give a first definition of a computational capacity measure and show that it related to computational distillable entanglement for "efficiently stretchable" channels. We give a channel model for which we can tightly bound these quantities to establish two key results:

You think we already have enough entropies and divergence measures? I don't think so! In our latest work (arxiv.org/abs/2509.20472), we introduce yet another information theoretic measure -- the computational relative entropy. Let's have a quick rundown👇

A big thanks to my coauthors Asad, Jacopo, Lorenzo, Sofiene and Jens.

arxiv.orgEfficient Quantum Measurements: Computational Max- and Measured Rényi Divergences and ApplicationsQuantum information processing is limited, in practice, to efficiently implementable operations. This motivates the study of quantum divergences that preserve their operational meaning while faithfull...

I also wanted to add a shout-out to Álvaro, Thomas and Jan who put out a work with similar mindset today: arxiv.org/abs/2509.21308. It turns out that our results mostly complement each other quite nicely, so please have a look there as well!

We believe that our definition has a nice level of abstraction that captures the essence of information theory under computational constraints while at the same time having the look and feel of unbounded information theory.

This is in stark contrast to how people approached computational information theory to date, where the approaches focused on single-shot statements. These are of course more exact, but also much more complicated to manipulate and build intuition for.

Another highlight is the fact that we can obtain separations in hypothesis testing, both between bounded and unbounded observers as well as classical-quantum separations. This means there exist classical distributions testable when having access to a quantum computer but not classically.

I invite you to discover many exciting things in the paper, like computationally measured divergences and a computational Stein's Lemma or a computational Rains bound on efficiently distillable entanglement.

For example, we obtain a computational version of Pinsker's inequality, which looks exactly like the unbounded relation only that the involved quantities carry underscores, marking them as computational quantities.

We can use the computational relative entropy as a mother quantity. We exemplify this by defining a computational entropy S̲(ρₙ):=−D(ρₙ‖𝕀) and show that it quantifies the best rate at which we can compress a state under complexity restrictions -- just like the entropy in the unbounded setting.

Of course, talking about polynomial scaling only makes sense when there is a scaling parameter. Therefore, all our results pertain to families of quantum states indexed by some parameter n. This is often the number of qubits, but need not be.

One of our main contributions is to turn this process of "polynomial regularization" into a rigorous notion. It allows us to reap the benefits of regularizing to obtain simpler expressions that closely resemble their counterparts from unbounded information theory.

But there is a catch! The connection between hypothesis testing and the relative entropy only holds if arbitrary tests can be performed. The optimal tests, however, could be exponentially complex to implement. We also need a large number of copies of the state to get sufficient statistics.

We propose the following remedy: we define the computational relative entropy D̲(ρₙ‖σₙ) as the best error exponent in asymmetric hypothesis testing when restricted to polynomially many copies and polynomial-time tests and take the polynomials to be arbitrarily large.

The relative entropy D(ρ‖σ) is a fundamental quantity in classical and quantum information theory. It appears in many important theorems and serves as a mother quantity to derive other important measures from -- for example mutual information or entropy.