We develop a connection between tripartite information I3, quantum secret sharing protocols and multi-unitaries. This leads to a general framework of constructing ((2, 3)) threshold schemes in arbitrary dimension. As an application, we propose a class of random codes generated by Haar-distributed random unitaries, in which all states have bounded tripartite information with high probability. Moreover, using the I3criteria for imperfect sharing schemes, we discover examples of VIP secret sharing schemes.

There are various ways to quantify the communication capabilities of a quantum channel. In this work we introduce the communication value (cv) of quantum channel, which describes the optimal probability of guessing the channel input from its output. By connecting to prior work on zero-error channel simulation, we show that the cv and its entanglement-assisted variant also offer dual interpretations as the classical communication cost for perfectly simulating different aspects of a channel using non-signaling resources. Our study involves characterizing the communication value as a generalized conditional min-entropy over the cone of separable operators. Using this characterization, we evaluate the cv for all qubit channels and higher-dimensional channels with certain symmetries. We find that the any entanglement-breaking channel has multiplicative cv when used in parallel with any other channel; the same is shown to hold for Pauli channels and partially depolarizing channels. In contrast, the cv is found to be non-multiplicative for a subset of the well-known Werner-Holevo channels. A final component of this work investigates relaxations of the channel cv to other cones such as the set of operators having a positive partial transpose (PPT).

There are various ways to quantify the communication capabilities of a quantum channel. In this work we study the communication value (cv) of channel, which describes the optimal success probability of transmitting a randomly selected classical message over the channel. The cv also offers a dual interpretation as the classical communication cost for zero-error channel simulation using non-signaling resources. We first provide an entropic characterization of the cv as a generalized conditional min-entropy over the cone of separable operators. We evaluate the cv exactly for all qubit channels and the Werner-Holevo family of channels. The latter is shown to have non-multiplicative cv when d > 2. On the other hand, we prove that any pair of qubit channels have multiplicative cv when used in parallel. Even stronger, all entanglement-breaking channels and the partially depolarizing channel are shown to have multiplicative cv when used in parallel with any channel. We then turn to the entanglement-assisted cv and prove that it is equivalent to the conditional min-entropy of the Choi matrix of the channel. Combining with previous work on zero-error channel simulation, this implies that the entanglement-assisted cv is the classical communication cost for perfectly simulating a channel using quantum non-signaling resources. A final component of this work investigates relaxations of the channel cv to other cones such as the set of operators having a positive partial transpose (PPT).

Capacities of quantum channels and decoherence times both quantify the extent to which quantum information can withstand degradation by interactions with its environment. However, calculating capacities directly is known to be intractable in general. Much recent work has focused on upper bounding certain capacities in terms of more tractable quantities such as specific norms from operator theory. In the meantime, there has also been substantial recent progress on estimating decoherence times with techniques from analysis and geometry, even though many hard questions remain open. In this article, we introduce a class of continuous-time quantum channels that we called transferred channels, which are built through representation theory from a classical Markov kernel defined on a compact group. In particular, we study two subclasses of such kernels: Hörmander systems on compact Lie-groups and Markov chains on finite groups. Examples of transferred channels include the depolarizing channel, the dephasing channel, and collective decoherence channels acting on d qubits. Some of the estimates presented are new, such as those for channels that randomly swap subsystems. We then extend tools developed in earlier work by Gao, Junge and LaRacuente to transfer estimates of the classical Markov kernel to the transferred channels and study in this way different non-commutative functional inequalities. The main contribution of this article is the application of this transference principle to the estimation of decoherence time, of private and quantum capacities, of entanglement-assisted classical capacities as well as estimation of entanglement breaking times, defined as the first time for which the channel becomes entanglement breaking. Moreover, our estimates hold for non-ergodic channels such as the collective decoherence channels, an important scenario that has been overlooked so far because of a lack of techniques.

We address a low-rank matrix recovery problem where each column of a rank-r matrix X of size (d1,d2) is compressed beyond the point of recovery to size L with L << d1. Leveraging the joint structure between the columns, we propose a method to recover the matrix to within an epsilon relative error in the Frobenius norm from a total of O(r(d1 + d2)\log^6(d1 + d2)/\epsilon^2) observations. This guarantee holds uniformly for all incoherent matrices of rank r. In our method, we propose to use a novel matrix norm called the mixed-norm along with the maximum l2 norm of the columns to design a novel convex relaxation for low-rank recovery that is tailored to our observation model. We also show that our proposed mixed-norm, the standard nuclear norm, and the max-norm are particular instances of convex regularization of low-rankness via tensor norms. Finally, we provide a scalable ADMM algorithm for the mixed-norm based method and demonstrate its empirical performance via large-scale simulations.

We extend the quantum entropic uncertainty principle beyond measurements, to a pair of finite-dimensional quantum channels acting on the same input system. This also generalizes strong super-additivity inequality by giving a lower bound on generalizations of conditional mutual information. Moreover we show that the corresponding “squashed” conditional mutual information is additive in this general setting.

Subsampled blind deconvolution is the recovery of two unknown signals from samples of their convolution. To overcome the ill-posedness of this problem, solutions based on priors tailored to specific practical application have been developed. In particular, sparsity models have provided promising priors. However, in spite of the empirical success of these methods in many applications, existing analyses are rather limited in two main ways: by disparity between the theoretical assumptions on the signal and/or measurement model versus practical setups; or by failure to provide a performance guarantee for parameter values within the optimal regime defined by the information theoretic limits. In particular, it has been shown that a naive sparsity model is not a strong enough prior for identifiability in the blind deconvolution problem. Instead, in addition to sparsity, we adopt a conic constraint, which enforces spectral flatness of the signals. Under this prior together with random dictionary models, we show that the unknown sparse signals can be recovered from samples of their convolution at a rate scaling near optimally with the problem parameters. We also propose an iterative algorithm that is guaranteed to provide robust recovery at the same near optimal sample complexity provided that certain projection steps in the algorithm are successful. In our analysis, we have not verified the success of these projection steps, but these steps are inactive with high probability. Numerical results show the empirical performance of the iterative algorithm agrees with the performance guarantee.

Using a suitable algebraic setup, we find new estimates of the quantum capacity and the potential quantum capacity for non-degradable channels obtained by random unitaries associated with a finite group. This approach can be generalized to quantum groups and uses new tools from operator algebras and interpolation of Rényi-type entropies. As an application, we obtain new estimates for the depolarizing channel in high dimension.

The quantum relative entropy is well known to obey a monotonicity property (i.e., it does not increase under the action of a quantum channel). Here we present several refinements of this entropy inequality, some of which have a physical interpretation in terms of recovery from the action of the channel. The recovery channel given here is explicit and universal, depending only on the channel and one of the arguments to the relative entropy.

Compressed sensing enables universal, simple, and reduced-cost acquisition by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain random measurement models, which satisfy the so-called isotropy property. However, in real-world applications, this property is often not satisfied. We propose two related changes in the existing framework for the anisotropic case: (i) a generalized RIP called the restricted biorthogonality property (RBOP); and (ii) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits provide recovery guarantees via the RBOP without requiring the isotropy property; hence, these recovery guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform better than their conventional counterparts.

Compressed sensing is a new data acquisition paradigm enabling universal, simple, and reduced-cost acquisition, by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain randomized acquisition systems. However, there is a discrepancy between the theoretical guarantees and practical applications. In applications, including Fourier imaging in various modalities, the measurements are acquired by inner products with vectors selected randomly (sampled) from a frame. Currently available guarantees are derived using the so-called restricted isometry property (RIP), which has only been shown to hold under ideal assumptions. For example, the sampling from the frame needs to be independent and identically distributed with the uniform distribution, and the frame must be tight. In practice though, one or more of the ideal assumptions are typically violated and none of the RIP-based guarantees applies. Motivated by this discrepancy, we propose two related changes in the existing framework: 1) a generalized RIP called the restricted biorthogonality property (RBOP); and 2) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits are guaranteed using the RBOP without requiring ideal assumptions; hence, the guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform competitively with, or sometimes better than their conventional counterparts.

We propose robust and efficient algorithms for the joint sparse recovery problem in compressed sensing, which simultaneously recover the supports of jointly sparse signals from their multiple measurement vectors obtained through a common sensing matrix. In a favorable situation, the unknown matrix, which consists of the jointly sparse signals, has linearly independent nonzero rows. In this case, the MUltiple SIgnal Classification (MUSIC) algorithm, originally proposed by Schmidt for the direction of arrival estimation problem in sensor array processing and later proposed and analyzed for joint sparse recovery by Feng and Bresler, provides a guarantee with the minimum number of measurements. We focus instead on the unfavorable but practically significant case of rank defect or ill-conditioning. This situation arises with a limited number of measurement vectors, or with highly correlated signal components. In this case, MUSIC fails and, in practice, none of the existing methods can consistently approach the fundamental limit. We propose subspace-augmented MUSIC (SA-MUSIC), which improves on MUSIC such that the support is reliably recovered under such unfavorable conditions. Combined with a subspace-based greedy algorithm, known as Orthogonal Subspace Matching Pursuit, which is also proposed and analyzed in this paper, SA-MUSIC provides a computationally efficient algorithm with a performance guarantee. The performance guarantees are given in terms of a version of the restricted isometry property. In particular, we also present a non-asymptotic perturbation analysis of the signal subspace estimation step, which has been missing in the previous studies of MUSIC.