What can we compute in the presence of noise? Both less and morethan you think. Noise limits our ability to error-mitigate, a term that refers to near-term schemes where errors that arise in a quantum computation are dealt with in classical pre-processing. I present a unifying framework for error mitigation and an analysis that strongly limits the degree to which quantum noise can be effectively `undone' for larger system sizes, and shows that current error mitigation schemes are more or less as good as they can be. After presenting this negative result, I'll switch to discussing how noise can be a friendly foe: non-unital noise, unlike its unital counterparts, surprisingly results in absence of barren plateaus in quantum machine learning.

We show how to use iterative refinement techniques, which is a technique from the 60’s suited for computers with low-precision arithmetic, for more efficient pure quantum state tomography, and for more efficient quantum linear equation solving via a divide and conquer strategy, which quadratically improves the condition number dependence of earlier methods and matches that of the conjugate gradient method for generic non-Hermitian matrices.

With the Hadamard test, you can estimate Tr(U rho) for Unitaries U and states rho or define a new complexity class (DQC1). However, you can also deal with linear combinations of Unitaries, which can be useful for implementing spectral functions. In this talk, I will float some ideas in that direction and discuss how these can be used for variational algorithms to obtain surrogate cost functions or reduce the number of samples for energy estimation in certain cases.

We present preliminary results on hybrid quantum-classical computation in the query model. The model that we consider is the one in which the algorithm can perform blocks of quantum computation that involve at most k queries. After each such block the state of a quantum algorithm is measured. I will survey the previous results on this model and describe our results on a complexity of various problems (such as search and element distinctness) in it.

Following an introduction to existing unconditional quantum advantage proposals based on shallow circuits, we introduce a new computational problem with the following properties:
(a) Every instance can be solved with near-certainty by a shallow quantum circuit using only nearest neighbor gates in 3D even when its implementation is corrupted by noise.
(b) Any constant-depth classical circuit of polynomial (even a certain subexponential) size composed of unbounded fan-in AND, OR, as well as NOT gates (i.e., an AC0 circuit) fails to solve a uniformly random instance with probability greater than a constant.
Previously, such an advantage against AC0 was only known in the noise-free case, and in the case where geometric locality considerations were ignored. Such separations against subexponential-size circuits have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.

This is joint work with Xavier Coiteux-Roy.

The framework of Quantum Singular Value Transformation [Gilyén, Su, Low, Wiebe, 2019] unifies many ideas in quantum linear algebra. We argue that QSVTs (and, in particular, their restricted form of Quantum Signal Processing) are moreover a powerful tool to reason about algorithms based on limited quantum processing and classical post-processing. In this talk, we will introduce the notion of "interpolation" as a description of a QSP-based approach to trading off coherent quantum queries by overall query count, modelling quantum/classical resource trade off in a query model. We will show the usefulness of this perspective by presenting a generalization of the α-Quantum Phase Estimation algorithm [Wang, Higgott, Brierley, 2019] to the problem of Eigenvalue Estimation (following [Magano, Murça, 2022]).We will then contrast "interpolation" with the problem-specific approach of partitioning the problem domain into independent smaller problem instances (following [Murça, Magano, Omar, 2023]). We will show that, for some problems, the "oblivious" approach of interpolation yields almost as good performance (in the query model) as exploiting structure to distribute the computation over smaller quantum computations.

We investigate circuit complexity of unitaries generated by time evolution of randomly chosen strongly interacting Hamiltonians in finite dimensional Hilbert spaces. Specifically, we focus on two ensembles of random generators -- the so called Gaussian Unitary Ensemble (GUE) and the ensemble of diagonal Gaussian matrices conjugated by Haar random unitary transformations. In both scenarios we prove that the complexity of exp(−itH) exhibits a surprising behaviour -- with high probability it reaches the maximal allowed value on the same time scale as needed to escape the neighborhood of the identity consisting of unitaries with trivial (zero) complexity. We furthermore observe similar behaviour for quantum states originating from time evolutions generated by above ensembles and for diagonal unitaries generated from the ensemble of diagonal Gaussian Hamiltonians. To establish these results we rely heavily on structural properties of the above ensembles (such as unitary invariance) and concentration of measure techniques. This gives us a much finer control over the time evolution of complexity compared to techniques previously employed in this context: high-degree moments and frame potentials.

In quantum theory general measurements are described by so-called Positive Operator-Valued Measures (POVMs). In this work we show that in d-dimensional quantum systems an application of depolarizing noise with constant (independent of d) visibility parameter makes any POVM simulable by a randomized implementation of projective measurements that do not require any auxiliary systems to be realized. This result significantly limits the asymptotic advantage that POVMs can offer over projective measurements in various information-processing tasks, including state discrimination, shadow tomography or quantum metrology. We also apply our findings to questions originating from quantum foundations. First, we asymptotically improve the range of parameters for which Werner and isotropic states have local models for generalized measurements (by factors of d and log(d) respectively). Second, we give asymptotically tight (in terms of dimension) bounds on critical visibility for which all POVMs are jointly measurable. On the technical side we use recent advances in POVM simulation, the solution to the celebrated Kadison-Singer problem, and a method of approximate implementation of a class of "nearly rank one" POVMs by a convex combination of projective measurements, which we call dimension-deficient Naimark extension theorem.

The talk will be based on upcoming joint work with Michał Kotowski (MIM UW).

Despite many years of research it is still unclear to which extend quantum computers can aid or outperform classical computers on combinatorial optimization problems. Often classical heuristics perform vastly better than one would expect from complexity theoretic considerations. In this talk I will introduce a constructed subset of integer linear programming problems, which provably permit a quantum advantage in the approximation sense. That is, they are not only hard to solve, but also hard to approximate up to a polynomial factor on a classical computer. Using techniques from learning theory the quantum advantage is derived from Shor's algorithm to invert the RSA function and, as such, the result can not be considered to showcase a practical quantum advantage, but rather a conceptual and rigorous construction.