Invited Talks/Speakers

  • Varun Jog, University of Cambridge, UK. Estimating location parameters in sample-heterogeneous distributions

Abstract:

Estimating the mean of a probability distribution using i.i.d. samples is a classical problem in statistics, wherein finite-sample optimal estimators are sought under various distributional assumptions. In this work, we consider the problem of mean estimation when independent samples are drawn from d-dimensional non-identical distributions possessing a common mean. When the distributions are radially symmetric and unimodal, we propose a novel estimator, which is a hybrid of the modal interval, shorth, and median estimators, and whose performance adapts to the level of heterogeneity in the data. We show that our estimator is near-optimal when data are i.i.d. and when the fraction of ``low-noise'' distributions is as small as $\Omega\left(\frac{d \log n}{n}\right)$, where $n$ is the number of samples.

We also derive minimax lower bounds on the expected error of any estimator that is agnostic to the scales of individual data points. Finally, we extend our theory to linear regression. In both the mean estimation and regression settings, we present computationally feasible versions of our estimators that run in time polynomial in the number of data points. This is joint work with Ankit Pensia (UW-Madison) and Po-Ling Loh (Cambridge).

  • Daniel Stilck França and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. [arXiv:2009.05532]

Abstract:

Recent technological developments have focused the interest of the quantum computing community on investigating how near-term devices could outperform classical computers for practical applications. A central question that remains open is whether their noise can be overcome or it fundamentally restricts any potential quantum advantage. We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices for a large family of problems that include optimization problems and approximations to the ground state energy of Hamiltonians. Our approach is based on the combination of entropic inequalities that determine how fast the quantum computation state converges to the fixed point of the noise model, together with established classical methods of Gibbs state sampling. The approach is extremely versatile and allows for its application to a large variety of problems, noise models and quantum computing architectures. We use our result to provide estimates for a variety of problems and architectures that have been the focus of recent experiments, such as quantum annealers, variational quantum eigensolvers, and quantum approximate optimization. The bounds we obtain indicate that substantial quantum advantages are unlikely for classical optimization unless the current noise rates are decreased by orders of magnitude or the topology of the problem matches that of the device. This is the case even if the number of qubits increases substantially. We reach similar but less stringent conclusions for quantum Hamiltonian problems.

  • Arne Heimendahl, Markus Heinrich, David Gross. The axiomatic and the operational approaches to resource theories of magic do not coincide. [arXiv:2011.11651]

Abstract:

Stabiliser operations occupy a prominent role in the theory of fault-tolerant quantum computing. They are defined operationally: by the use of Clifford gates, Pauli measurements and classical control. Within the stabiliser formalism, these operations can be efficiently simulated on a classical computer, a result which is known as the Gottesman-Knill theorem. However, an additional supply of magic states is enough to promote them to a universal, fault-tolerant model for quantum computing. To quantify the needed resources in terms of magic states, a resource theory of magic has been developed during the last years. Stabiliser operations (SO) are considered free within this theory, however they are not the most general class of free operations. From an axiomatic point of view, these are the completely stabiliser-preserving (CSP) channels, defined as those that preserve the convex hull of stabiliser states. It has been an open problem to decide whether these two definitions lead to the same class of operations. In this work, we answer this question in the negative, by constructing an explicit counter-example. This indicates that recently proposed stabiliser-based simulation techniques of CSP maps are strictly more powerful than Gottesman-Knill-like methods. The result is analogous to a well-known fact in entanglement theory, namely that there is a gap between the class of local operations and classical communication (LOCC) and the class of separable channels. Along the way, we develop a number of auxiliary techniques which allow us to better characterise the set of CSP channels.

Abstract:

In this talk, we discuss an alternative to the conventional random coding technique, which uses a Poisson process instead of i.i.d. codebook generation. The Poisson process can be regarded as a black box where the encoders and decoders can perform queries using partial information on the messages and/or channel inputs, in order to obtain the full information. This technique can greatly simplify the analysis and give sharp bounds for various settings. We also discuss some methods and challenges in applying this technique to multiuser coding settings.

This talk is partly based on a joint work with Venkat Anantharam: C.T. Li and V. Anantharam, "A Unified Framework for One-Shot Achievability via the Poisson Matching Lemma," in IEEE Transactions on Information Theory, vol. 67, no. 5, pp. 2624-2651, May 2021.

  • Euijung Chang, Jaeyoung Kim, Hyesun Kwak, Hun Hee Lee, Sang-Gyun Youn (speaker). Irreducibly SU(2)-covariant quantum channels of low rank. [arXiv:2105.00709]

Abstract:

We investigate information theoretic properties of low rank (less than or equal to 3) quantum channels with SU(2)-symmetry, where we have a complete description. We prove that PPT property coincides with entanglement-breaking property and that degradability seldomly holds in this class. In connection with these results we will demonstrate how we can compute Holevo and coherent information of those channels. In particular, we exhibit a strong form of additivity violation of coherent information, which resembles the superactivation of coherent information of depolarizing channels.