Eric Holland

A provable quantum advantage for approximate optimization via decoded quantum interferometry scirate.com/arxiv/2610.02145 This is a piece of work I am particularly happy with. We prove a quantum advantage for approximate #optimization: in an oracle setting, a quantum algorithm achieves a strictly better approximation ratio than any polynomial-time classical algorithm. Our problem is folded optimal polynomial intersection: find a low-degree polynomial whose grouped evaluations pass as many acceptance tests as possible. The folded Reed–Solomon code is given explicitly. Independently sampled acceptance sets, each containing half the block alphabet, are accessed through separate membership oracles. Each query tests whether a proposed symbol is accepted in one classically chosen block. Quantum algorithms can query that block’s membership predicate coherently, over a superposition of input symbols. #Decodedquantuminterferometry (DQI) connects optimization and coding theory through Fourier interference and decoding. At code rate 0.3, it achieves an asymptotic expected score of approximately 0.857 using one coherent query per block. Exceeding the classical threshold of 0.65 by any fixed amount, with constant probability on sampled instances, requires super-polynomially many classical membership queries—even with unlimited computation between queries. A modified quantum algorithm reaches a score of 0.95 with constant success probability on typical sampled instances. For me, the particularly satisfying point is that the classical lower bound covers every algorithm in this oracle model, including algorithms we have not yet discovered. Warm thanks to Maximilian Johannes Kramer, @EliesMiquel, Benjamin D.M. Jones and @FJSchreiber.

Quantum coding schemes typically rely on knowing the underlying state or channel. In “Universal quantum coding,” we show how to distil entanglement and communicate quantum information without this prior knowledge. scirate.com/arxiv/2609.38038 The key is the good old Schur–Weyl duality, but with a new twist: the symmetry structure of many identical copies provides quantum code spaces whose errors can be identified and corrected through representation theory. The resulting protocols require no tomography and achieve coherent-information rates, with exponentially vanishing error and optimal second-order corrections. Their sample complexity depends on relevant spectral ranks rather than the full Hilbert-space dimensions. Symmetry thus provides a common mechanism for entanglement distillation, quantum error correction and quantum communication—even when the state or channel is unknown. Thanks to the dream team of @jacoporz, @LamiLudovico, and @lorenzo_leone_ for the wonderful collaboration.

How much does a quantum algorithm gain from access to the circuit that prepares its input, rather than just copies of the resulting state? How does the oracle access matter? scirate.com/arxiv/2609.35656 In our new work on the state hidden subgroup problem, we give a sharp answer for finite abelian groups. We establish optimal bounds in both settings and find a quadratic improvement when the algorithm can coherently use the preparation circuit and its inverse. Even the most general collective measurement on state copies cannot match it. The result also gives faster ways to learn stabilizer groups, locate unentanglement, and identify hidden translation symmetries. It is a concrete example of how the way we access an input can change the complexity of a quantum problem. Warm thanks to Yuhan Liu, Jose Carrasco, and @ikiga1 for this wonderful @FU_Berlin-@maxplanckpress-collaboration.