Monday, October 6

Haferkamp, Jonas - Random unitaries in extremely low depth

We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over qubits in depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in depth, and in all-to-all-connected circuits in depth. In all three cases, the dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on -sized or -sized patches of qubits to form a global random unitary on all qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary -designs, and hence also inherit an optimal scaling in . In the case of PRUs, the local unitaries are drawn from existing PRU constructions. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.

Werner, Albert - Quantum Algorithms for Steiner Trees and Binary Near-Perfect Phylogenies

An important goal in quantum computing is to identify algorithmic frameworks that yield provable speedups for computationally hard problems. In this talk, we present an end-to-end quantum algorithm for the Minimum Steiner Tree problem in the circuit model. The key ingredients are a global Grover search over Dreyfus–Wagner recursion choices combined with efficient Dicke state preparation to encode recursive subspaces. We illustrate the approach with a problem from bioinformatics and evolutionary biology: the Binary Near-Perfect Phylogeny problem.

Apers, Simon - Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers

Spectral gaps play a fundamental role in quantum computing and physics (as well as in many other areas of science). In quantum mechanics, the spectral gap of Schrödinger operators has a long history of study due to its physical relevance, while in quantum computing spectral gaps are an important proxy for efficiency, such as in the quantum adiabatic algorithm. Motivated by convex optimization, we study Schrödinger operators associated with self-concordant barriers over convex domains and prove non-asymptotic lower bounds on the spectral gap for this class of operators. Significantly, we find that the spectral gap does not display any condition-number dependence when the usual Laplacian is replaced by the Laplace–Beltrami operator, which takes the curvature of the barrier into account. As an algorithmic application, we construct a novel quantum interior point method that applies to arbitrary self-concordant barriers and shows no condition-number dependence. To achieve this we combine techniques from semiclassical analysis, convex optimization, and quantum annealing.

Gross, David - "It sounded like a good idea" -- Non-asymptotic running-time analysis of quantum convex optimization algorithms

Which practical problems would a scaled-up quantum computer be useful for? This is a challenging question, because hardware capable of running real-world benchmarks is unavailable, and theoretical works typically make only asymptotic statements. In this talk, I'll report on non-asymptotic analyses of quantum convex optimization algorithms. The focus will be on a proposal by Brandão, França, and Kueng for SDP relaxations of QUBO problems. It felt particularly attractive: SDPs seem like a natural match for quantum methods; the algorithm, targeting combinatorial problems, includes a rounding step that mitigates the unfavorable precision of quantum SDP solvers; and the proposal came with a rigorous asymptotic running time estimate. After having optimized their proposal for performance on realistic instances, we proceeded to estimate the smallest problem size for which the proven asymptotic advantage manifests. To learn the results, come to the talk! (Or have a sneak peek at arXiv:2502.15426).

Gachechiladze, Mariami - Quantum computer certification in theory and experiments

The rapid advancement of quantum hardware makes the development of reliable certification methods essential. We present an approach that is inherently free from state preparation and measurement (SPAM) errors and provide sound guarantees under the sole assumption of finite system dimension. In a server-user scenario, we introduce a certification method for quantum gates, including single-qubit universal sets, and prove that for the experimentally relevant phase gate, the sample complexity scales as O(1/ϵ) with the average gate infidelity ϵ. In a single-device setup, we propose quantum system quizzing, a protocol that self-tests an entire quantum model in a black-box scenario. By identifying deterministic input-output correlations, we recover the tensor-product structure of multi-qubit systems without computational assumptions and establish the first certification tool for universal multi-qubit gate sets in memory-bounded quantum computers. Together, these approaches offer efficient, scalable, and experimentally relevant tools for certifying full-scale quantum computation. We test the theory on Ion traps in Mainz and the H1 architecture of Quantinuum. 

Witteveen , Freek- Hamiltonian simulation with partially randomized product formulas

One of the most important algorithmic primitives for applications of quantum computing to problems in chemistry and physics is Hamiltonian simulation, and a standard way to do so is Trotterization. Based on arXiv:2503.05647 I will explain how randomness can help speed up Trotterization and can be used to improve phase estimation algorithms for energies.

Zimboras, Zoltan - Will it glue? On short-depth designs beyond the unitary group

We provide a range of results on several groups of broad interest in quantum information science: the Clifford group, the orthogonal group, the unitary symplectic groups, and the matchgate group. For all of these groups, we prove that analogues of unitary designs cannot be generated by any circuit ensemble with light-cones that are smaller than the system size. This implies linear lower bounds on the circuit depth in one-dimensional systems. For the Clifford, orthogonal, and unitary symplectic group, we moreover show that commonly considered circuit ensembles cannot generate designs in sub-linear depth on any circuit architecture. We show this by exploiting observables in the higher-order commutants of each group, which allow one to distinguish any short-depth circuit from truly random. While these no-go results rule out short-depth unitary designs, we prove that slightly weaker forms of randomness---including additive-error state designs and anti-concentration in sampling distributions---nevertheless emerge at logarithmic depths in many cases. Our results reveal that the onset of randomness in shallow quantum circuits is a widespread yet subtle phenomenon, dependent on the interplay between the group itself and the context of its application.

Eisert, Jens - The unbearable difficulty of finding near-term quantum advantages

Quantum computers promise computational advantages for a number of tasks, but most of these require a fault-tolerant quantum computer. For this reason, the question has arisen whether we can hope for near-term quantum computers that could be realized soon. For paradigmatic sampling problems, this seems to be the case, but they do not relate much to the practically minded applications we foresee. In this talk, we will discuss the potential and limitations of achieving such applications. We will see that mid-circuit measurements can help in achieving quantum advantages in constant depth [1] and in quantum SAT solvers [2]. We will look at mathematically meaningful PAC learning advantages at constant depth [3]. We will discuss the state hidden subgroup problem [4], which could well be realized in the near term, and hint at methods of entanglement manipulation [5]. We will see how in the shadow of the Hadamard test and using the garbage state for good and further modifications, one may hope for near-term quantum advantages [6]. At the same time, we will explore significant limitations: in the absence of quantum error correction, only logarithmically deep circuitscan be realized [7] in a precise sense, and quantum error mitigation faces information-theoretic obstructions already at log-log depth [8]. We will emphasize that having quantum advantages at isolated points is not enough; instead, we must have robust advantages across large families of instances [9]. Much of the talk will be a high-level discussion of what we know about bridging the gap between the noisy intermediate-scale quantum (NISQ) regime and the fault-tolerant application-scale quantum (FASQ) regime [10].

[1] arXiv:2505.04705 (2025).
[2] In preparation (2025).
[3] arXiv:2411.15548 (2024).
[4] arXiv:2505.15770 (2025).
[5] arXiv:2502.12284, Nature Physics, in press (2025).
[6] arXiv:2505.15913, Physical Review Letters, in press (2025).
[7] arXiv:2403.13927 (2024).
[8] Nature Physics 20, 1648 (2024).
[9] Nature Communications 15, 434 (2024).
[10] Perspectives article with John Preskill in preparation (2025). 

Oszmaniec, Michał - Hardness of Boson Sampling with linear number of modes

BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of {particles} to modes -- all current hardness evidence assumes a dilute regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a saturated regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a new worst-to-average-case reduction for computing the Permanent which is robust to both large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime. The talk will be based on [1].

[1] Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez and Michał Oszmaniec,  Complexity-theoretic foundations of BosonSampling with a linear number of modes, arXiv: 2312.00286v1

Walter, Michael - Robust tests of Gaussian states 

Gaussian bosonic quantum states arise naturally in physical systems and play a key role in quantum technologies. This motivates the following fundamental question: How can we efficiently test if an unknown quantum state is Gaussian? We will discuss algorithms that solve this problem robustly and efficiently for pure states (one based on symmetries and another based on learning theory), as well as a lower bound that shows that for mixed states exponentially many samples are required.

Tuesday, October 7

Chabaud, Ulysse - On the computational power of bosons

Bosonic quantum systems operate in an infinite-dimensional Hilbert space, unlike discrete-variable quantum systems. This distinct mathematical structure leads to fundamental differences in quantum information processing, such as an exponentially greater complexity of state tomography [Anna Mele et al. (2024)] or a factoring algorithm in constant space [Brenner et al. (2024)]. Yet, any real-world computation necessarily uses limited energy, and it remains unclear whether the structural difference of bosonic systems may also translate to a computational advantage over finite-dimensional quantum computers when taking such constraints into account. In this talk, we address this question from a complexity-theoretic point of view by characterizing the computational power of energy in bosonic quantum computations. 

Based on joint works with Varun Upreti and Dorian Rudolph (https://arxiv.org/abs/2503.03600), and Saeed Mehraban, Sevag Gharibian, Hamid Reza Naeij, Dorian Rudolph and Dhruva Sambrani (upcoming).

Leverrier, Anthony - Bosonic quantum Fourier codes 

While 2-level systems, aka qubits, are a natural choice to perform a logical quantum computation, the situation is less clear at the physical level. Encoding information in higher-dimensional physical systems can indeed provide a first level of redundancy and error correction that simplifies the overall fault-tolerant architecture. A challenge then is to ensure universal control over the encoded qubits. Here, we explore an approach where information is encoded in an irreducible representation of a finite subgroup of U(2) through an inverse quantum Fourier transform. We illustrate this idea by applying it to the real Pauli group ⟨X,Z⟩ in the bosonic setting. The resulting two-mode Fourier cat code displays good error correction properties and admits an experimentally-friendly universal gate set that we discuss in detail.

https://arxiv.org/abs/2505.16618

Browe, Dan - The AutDEC decoder - Improved Belief Propagation by ensembling and code symmetry

We introduce AutDEC, a fast and accurate decoder for quantum error-correcting codes with large automorphism groups. Our decoder employs a set of automorphisms of the quantum code and an ensemble of belief propagation (BP) decoders. Each BP decoder is given a syndrome which is transformed by one of the automorphisms, and is run in parallel. For quantum codes, the accuracy of BP decoders is limited because short cycles occur in the Tanner graph and our approach mitigates this effect. We demonstrate decoding accuracy comparable to BP-OSD-0 with a lower time overhead for Quantum Reed-Muller (QRM) codes in the code capacity setting, and Bivariate Bicycle (BB) codes under circuit level noise. We provide a Python repository for use by the community and the results of our simulations. Ref.: arXiv:2503.01738

Fawzi, Omar - The computational complexity of optimally encoding a bit 

We consider the problem of encoding a bit in a quantum system undergoing noise modeled as a quantum channel. We show that determining the optimal success probability is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. Equivalently, we show that approximating the trace norm contraction coefficient of a quantum channel is hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient. Based on joint work with Idris Delsol, Jan Kochanowski and Akshay Ramachandran available https://arxiv.org/abs/2507.16737.

Gharibian, Sevag - How hard is it to verify a classical shadow?

Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ in the size of P . In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be “dequantized” for low-rank observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class.

Quek, Yihui - Hamiltonian Decoded Quantum Interferometry, aka Decoding is All You Need

We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that reduces Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian H and any degree-l polynomial P, HDQI prepares a purification of the density matrix \rho_P(H) = P^2(H)/\Tr[P^2(H)] by solving a combination of two tasks: decoding l errors on a classical code defined by H, and preparing a pilot state that encodes the anti-commutation structure of H. Choosing P appropriately yields approximate Gibbs states,  ground states, microcanonical ensembles and spectral filters.

The decoding problem inherits structural properties of H; in particular, local Hamiltonians map to LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for a class of nearly commuting Pauli Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. For a non-commuting semiclassical spin glass and commuting stabilizer code Hamiltonians with quantum defects, HDQI provably prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical preprocessing. These results position HDQI as a versatile new algorithmic primitive, connecting quantum state preparation to classical decoding.

Weil, Ryohei - Quantifying resource states and efficient regimes of measurement-based quantum computation on a superconducting processor

Recent theory has clarified the computational power of finite symmetric short-range entangled spin chains as resources for measurement-based quantum computation (MBQC) and the most efficient regimes of computation therein. We report on attempts to experimentally demonstrate these advancements on IBM’s superconducting quantum processor. We variationally prepare resource states with tunable computational order and experimentally confirm the effects of logical decoherence on the encoded quantum information. We then demonstrate the equivalence of computational order and string order, and confirm the scaling relation of logical decoherence with system size. We then construct a family of states with a length scale to study the ``counterintuitive’’ regime of computation, wherein the densest possible packing of symmetry-breaking measurements is predicted to be the most efficient. Our work demonstrates the capacity for noisy intermediate-scale quantum devices for showcasing the phenomenology of MBQC on resource states beyond the cluster state.

Sutter, David - Circuit cutting

What is the optimal cost for doing non-local quantum computing with local operations and classical communication? In this talk, I will give an overview about how the "quasiprobability simulation method" can be used to perform this task --- at the cost of a sampling overhead. I will show that for some non-local gates (e.g. Clifford gates or arbitrary 2qubit gates) the optimal sampling overhead is known, whereas in general it is still unknown.

Berta, Mario - Quantum algorithm design for many-body simulation

Quantum technologies promise transformative computational capabilities, with quantum computers offering super-polynomial speed-ups for specific problems. While such advantages are far from generic, quantum many-body simulation remains a promising application. Motivated by applications in condensed matter physics and quantum chemistry, I will introduce a quantum algorithm for preparing thermal states of interacting lattice fermions with provable polynomial runtime. Building on recent extensions of classical Markov chain Monte Carlo techniques to the quantum domain, I will demonstrate that the generator of the quantum Markovian dynamics remains gapped up to a critical interaction strength, yielding rigorous bounds on the mixing time. This enables efficient preparation of low-temperature states of weakly interacting fermions and allows for the computation of free energies. Join work with Štěpán Šmíd, Richard Meister, and Roberto Bondesan, partly based on arXiv:2501.01412.