Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Oberwolfach Reports

Mini-Workshop: Mathematical Physics meets Sparse Recovery

David Gross, Felix Krahmer, Rachel Ward, Andreas Winter

Published Feb 27, 2015• 0 citations
Publisher

Abstract

In recent years, there have been several fruitful interchanges of methods between the fields of sparse and low-rank recovery on the one hand and quantum information theory on the other hand. One way to understand this seemingly surprising coincidence is that the analysis of vector- and matrix-valued randomized constructions plays an important role in both fields. An example is the realization that certain matrix-valued large deviation bounds can be employed to substantially simplify and generalize the analysis of low-rank matrix recovery schemes. In this workshop, the participants worked to identify and collaborate on further mathematical problems that are being researched in parallel by the two communities. Topics that have been discussed include • Tools for the analysis of vector- and matrix-valued randomized constructions and their application to phase retrieval problems • Conversely, tools for de-randomizing such protocols, based, e.g., on spherical designs. • Uncertainty relations, e.g., for the task of lower-bounding the number of measurements required for signal identification. • Time-frequency methods (known as phase-space methods in physics). • Matrix- and tensor norms: computational tools, complexity, relaxations and their application to tensor recovery.

DOI
10.4171/owr/2014/18

Related papers

Workshop on Field Theoretic Simulations in Particle Physics and Condensed Matter

Richard C. Brower

A two and half day workshop at Boston University, devoted to a discussion of common problems in the theoretical and computational study of particle physics and condensed matter. The phase structure of strongly coupled quantum field theories are of great interest in condensed matter and high energy physics. For example, the study of strongly correlated systems, such as frustrated quantum anti-ferromagnets, have suggested the existence of phases in which the low energy excitations do not have the quantum numbers of electrons but are fractionalized. The field description of such systems are typically topological quantum field theories. The latter have also proved important in constructing supersymmetric lattice gauge theories. Quantum critical systems in condensed matter are described by conformal field theories which have the subject of much recent work in the context of theories of Beyond Standard Model physics. Finally, theoretical holographic techniques originating in string theory may offer a new tool to investigate strongly interacting electrons. In parallel with these theoretical developments there has been rapid progress in computational methods in both fields; from tensor networks and density matrix renormalization group techniques to the rational hybrid Monte Carlo algorithm and techniques to ameliorate the famous sign problem. It is thus a propitious time to bring both communities together to stimulate an exchange of ideas and facilitate possible future collaborations.

•Sep 28, 2023•0 citations

Correlations and Interactions for Random Quantum Systems

Peter D. Hislop, Werner Kirsch, Peter Müller +1 more

Random quantum systems cover a broad range of mathematical models from random Schr¨odinger operators to random matrices and quantum spin models with random parameters. Their understanding requires techniques which combine functional analysis and probability. The workshop brought together researchers from these various branches which discussed new results, methods and future challenges. This is a report on the meeting containing extended abstracts of the lectures.

Oberwolfach Reports•Jul 25, 2012•3 citations

Stable low-rank matrix recovery from 3-designs

Gilles, Timm

We study the recovery of low-rank Hermitian matrices from rank-one measurements obtained by uniform sampling from complex projective 3-designs, using nuclear-norm minimization. This framework includes phase retrieval as a special case via the PhaseLift method. In general, complex projective $t$-designs provide a practical means of partially derandomizing Gaussian measurement models. While near-optimal recovery guarantees are known for $4$-designs, and it is known that $2$-designs do not permit recovery with a subquadratic number of measurements, the case of $3$-designs has remained open. In this work, we close this gap by establishing recovery guarantees for (exact and approximate) $3$-designs that parallel the best-known results for $4$-designs. In particular, we derive bounds on the number of measurements sufficient for stable and robust low-rank recovery via nuclear-norm minimization. Our results are especially relevant in practice, as explicit constructions of $4$-designs are significantly more challenging than those of $3$-designs.

arXiv:2512.11642•Dec 12, 2025•0 citations

Due to, or in spite of? The effect of constraints on efficiency in quantum estimation problems

Daniel Süß

In this thesis, we study the interplay of constraints and complexity in quantum estimation. We investigate three inference problems, where additional structure in the form of constraints is exploited to reduce the sample and/or computational complexity. The first example is concerned with uncertainty quantification in quantum state estimation, where the positive-semidefinite constraint is used to construct more powerful, that is smaller, error regions. However, as we show in this work, doing so in an optimal way constitutes a computationally hard problem, and therefore, is intractable for larger systems. The second inference problem deals with phase retrieval and its application to characterizing linear optical circuits. The main chal- lenge here is the fact that the measurements are insensitive to complex phases, and hence, reconstruction requires deliberate utilization of interference. We propose a reconstruction algorithm based on ideas from low-rank matrix recovery. More specifically, we map the problem of reconstruction from phase-insensitive measurements to the problem of recovering a rank-one matrix from linear measurements. For the efficient solution of the latter it is crucial to exploit the rank-one constraint. Finally, we investigate low-rank tensor recovery – the problem of reconstructing a low-complexity tensor embedded in an exponentially large space. We provide evidence that with high probability succesful recovery is feasible by Gaussian product tensors with the number of measurements only depending on the target’s intrinsic complexity, and hence, scaling polynomially in the order of tensor. Therefore, the low-rank constraint can be exploited to dramatically reduce the sample complexity of the problem. Additionally, the use of measurement tensors with an efficient representation is necessary for computational efficiency.

•Nov 13, 2018•0 citations

Mini-Workshop: New Directions in Correlated Quantum Systems

Emanuela L. Giacomelli, Jinyeop Lee, Marius Lemm

The mathematical study of quantum many-body physics has seen significant breakthroughs in the past 15–20 years. Mathematical physicists have approached these systems from different perspectives with different methods. The mini-workshop aimed to connect two rapidly growing fields: the mathematical analysis of many-body systems in scaling regimes (which has led to precise asymptotic formulas of the ground state energy and time evolution, e.g., of Bose gases) and the study of strongly correlated quantum systems via Lieb-Robinson bounds (which provide fundamental insights into the spreading of quantum information).

Oberwolfach Reports•Aug 29, 2025•1 citation

04401 Summary – Algorithms and Complexity for Continuous Problems

Thomas Müller-Gronbach, Erich Novak, Knut Petras +1 more

The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.

Dagstuhl Seminar Proceedings•Jan 1, 2005•0 citations
In recent years, there have been several fruitful interchanges of methods between the fields of sparse and low-rank recovery on the one hand and quantum information theory on the other hand. One way to understand this seemingly surprising coincidence is that the analysis of vector- and matrix-valued randomized constructions plays an important role in both fields. An example is the realization that certain matrix-valued large deviation bounds can be employed to substantially simplify and generalize the analysis of low-rank matrix recovery schemes. In this workshop, the participants worked to identify and collaborate on further mathematical problems that are being researched in parallel by the two communities. Topics that have been discussed include • Tools for the analysis of vector- and matrix-valued randomized constructions and their application to phase retrieval problems • Conversely, tools for de-randomizing such protocols, based, e.g., on spherical designs. • Uncertainty relations, e.g., for the task of lower-bounding the number of measurements required for signal identification. • Time-frequency methods (known as phase-space methods in physics). • Matrix- and tensor norms: computational tools, complexity, relaxations and their application to tensor recovery.
A two and half day workshop at Boston University, devoted to a discussion of common problems in the theoretical and computational study of particle physics and condensed matter. The phase structure of strongly coupled quantum field theories are of great interest in condensed matter and high energy physics. For example, the study of strongly correlated systems, such as frustrated quantum anti-ferromagnets, have suggested the existence of phases in which the low energy excitations do not have the quantum numbers of electrons but are fractionalized. The field description of such systems are typically topological quantum field theories. The latter have also proved important in constructing supersymmetric lattice gauge theories. Quantum critical systems in condensed matter are described by conformal field theories which have the subject of much recent work in the context of theories of Beyond Standard Model physics. Finally, theoretical holographic techniques originating in string theory may offer a new tool to investigate strongly interacting electrons. In parallel with these theoretical developments there has been rapid progress in computational methods in both fields; from tensor networks and density matrix renormalization group techniques to the rational hybrid Monte Carlo algorithm and techniques to ameliorate the famous sign problem. It is thus a propitious time to bring both communities together to stimulate an exchange of ideas and facilitate possible future collaborations.
We study the recovery of low-rank Hermitian matrices from rank-one measurements obtained by uniform sampling from complex projective 3-designs, using nuclear-norm minimization. This framework includes phase retrieval as a special case via the PhaseLift method. In general, complex projective ttt-designs provide a practical means of partially derandomizing Gaussian measurement models. While near-optimal recovery guarantees are known for 444-designs, and it is known that 222-designs do not permit recovery with a subquadratic number of measurements, the case of 333-designs has remained open. In this work, we close this gap by establishing recovery guarantees for (exact and approximate) 333-designs that parallel the best-known results for 444-designs. In particular, we derive bounds on the number of measurements sufficient for stable and robust low-rank recovery via nuclear-norm minimization. Our results are especially relevant in practice, as explicit constructions of 444-designs are significantly more challenging than those of 333-designs.
In this thesis, we study the interplay of constraints and complexity in quantum estimation. We investigate three inference problems, where additional structure in the form of constraints is exploited to reduce the sample and/or computational complexity. The first example is concerned with uncertainty quantification in quantum state estimation, where the positive-semidefinite constraint is used to construct more powerful, that is smaller, error regions. However, as we show in this work, doing so in an optimal way constitutes a computationally hard problem, and therefore, is intractable for larger systems. The second inference problem deals with phase retrieval and its application to characterizing linear optical circuits. The main chal- lenge here is the fact that the measurements are insensitive to complex phases, and hence, reconstruction requires deliberate utilization of interference. We propose a reconstruction algorithm based on ideas from low-rank matrix recovery. More specifically, we map the problem of reconstruction from phase-insensitive measurements to the problem of recovering a rank-one matrix from linear measurements. For the efficient solution of the latter it is crucial to exploit the rank-one constraint. Finally, we investigate low-rank tensor recovery – the problem of reconstructing a low-complexity tensor embedded in an exponentially large space. We provide evidence that with high probability succesful recovery is feasible by Gaussian product tensors with the number of measurements only depending on the target’s intrinsic complexity, and hence, scaling polynomially in the order of tensor. Therefore, the low-rank constraint can be exploited to dramatically reduce the sample complexity of the problem. Additionally, the use of measurement tensors with an efficient representation is necessary for computational efficiency.
The mathematical study of quantum many-body physics has seen significant breakthroughs in the past 15–20 years. Mathematical physicists have approached these systems from different perspectives with different methods. The mini-workshop aimed to connect two rapidly growing fields: the mathematical analysis of many-body systems in scaling regimes (which has led to precise asymptotic formulas of the ground state energy and time evolution, e.g., of Bose gases) and the study of strongly correlated quantum systems via Lieb-Robinson bounds (which provide fundamental insights into the spreading of quantum information).
The goal of this workshop was to bring together researchers from different communities working on computational aspects of continuous problems. Continuous computational problems arise in many areas of science and engineering. Examples include path and multivariate integration, function approximation, optimization, as well as differential, integral, and operator equations. Understanding the complexity of such problems and constructing efficient algorithms is both important and challenging. The workshop was of a very interdisciplinary nature with invitees from, e.g., computer science, numerical analysis, discrete, applied, and pure mathematics, physics, statistics, and scientific computation. Many of the lectures were presented by Ph.D. students. Compared to earlier meetings, several very active research areas received more emphasis. These include Quantum Computing, Complexity and Tractability of high-dimensional problems, Stochastic Computation, and Quantization, which was an entirely new field for this workshop. Due to strong connections between the topics treated at this workshop many of the participants initiated new cooperations and research projects. For more details, see the pdf-file with the same title.