We consider the problem of optimal transport between two high-dimensional distributions μ,ν in ℝⁿ from a new algorithmic perspective, in which we are given a sample x ∼ μ and we have to find a close y ∼ ν while running in poly(n) time, where n is the size/dimension of x,y. In other words, we are interested in making the running time bounded in dimension of the spaces rather than bounded in the total size of the representations of the two distributions. Our main result is a general algorithmic transport result between any product distribution μ and an arbitrary distribution ν of total cost Δ + δ under 𝓁_p^p cost; here Δ is the cost of the so-called Knothe–Rosenblatt transport from μ to ν, while δ is a computational error that goes to zero for larger running time in the transport algorithm. For this result, we need ν to be "sequentially samplable" with a "bounded average sampling cost" which is a novel but natural notion of independent interest. In addition, we prove the following. - We prove an algorithmic version of the celebrated Talagrand’s inequality for transporting the standard Gaussian distribution Φⁿ to an arbitrary ν under the Euclidean-squared cost. When ν is Φⁿ conditioned on a set S of measure ε, we show how to implement the needed sequential sampler for ν in expected time poly(n/ε), using membership oracle access to S. Hence, we obtain an algorithmic transport that maps Φⁿ to Φⁿ|S in time poly(n/ε) and expected Euclidean-squared distance O(log 1/ε), which is optimal for a general set S of measure ε. - As corollary, we find the first computational concentration (Etesami et al. SODA 2020) result for the Gaussian measure under the Euclidean distance with a dimension-independent transportation cost, resolving a question of Etesami et al. More precisely, for any set S of Gaussian measure ε, we map most of Φⁿ samples to S with Euclidean distance O(√{log 1/ε}) in time poly(n/ε).

We introduce a new quantum decoder based on a variant of the pretty good measurement, but defined via an alternative matrix quotient. We then use this novel decoder to derive new lower bounds on the error exponent both in the one-shot and asymptotic regimes for the classical-quantum and the entanglement-assisted channel coding problems. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the asymptotic bounds) channel Rényi mutual information of order between 1/2 and 1. The bounds are not comparable with some previously established bounds for general channels, yet they are tight (for rates close to capacity) when the channel is classical. Finally, we also use our new decoder to rederive Cheng’s recent tight bound on the decoding error probability, which implies that most existing asymptotic results also hold for the new decoder.

Parties connected to independent sources through a network can generate correlations among themselves. Notably, the space of feasible correlations for a given network, depends on the physical nature of the sources and the measurements performed by the parties. In particular, quantum sources give access to nonlocal correlations that cannot be generated classically. In this paper, we derive a universal limit on correlations in networks in terms of their covariance matrix. We show that in a network satisfying a certain condition, the covariance matrix of any feasible correlation can be decomposed as a summation of positive semidefinite matrices each of whose terms corresponds to a source in the network. Our result is universal in the sense that it holds inanyphysical theory of correlation in networks, including the classical, quantum and all generalized probabilistic theories.

It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).

In this paper, a new measure of correlation is introduced. This measure depends on a parameter α, and is defined in terms of vector-valued Lpnorms. The measure is within a constant of the exponential of α-Rényi mutual information, and reduces to the trace norm (total variation distance) for α = 1. We provide some properties and applications of this measure of correlation. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the α-Rényi mutual information according to Csiszár's proposal.

In this paper, we introduce a new measure of correlation for bipartite quantum states. This measure depends on a parameter$\alpha $, and is defined in terms of vector-valued$\textit {L}_{\textit {p}}$-norms. The measure is within a constant of the exponential of$\alpha $-Rényi mutual information, and reduces to the trace norm (total variation distance) for$\alpha =1$. We will prove some decoupling type theorems in terms of this measure of correlation, and present some applications in privacy amplification as well as in bounding the random coding exponents. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the$\alpha $-Rényi mutual information according toCsiszár’s proposal.

Let F be a finite alphabet and D be a finite set of distributions over F. A Generalized Santha-Vazirani (GSV) source of type (F, D), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, ..., F_n) in F^n, where F_i is a sample from some distribution d in D whose choice may depend on F_1, ..., F_{i-1}. We show that all GSV source types (F, D) fall into one of three categories: (1) non-extractable; (2) extractable with error n^{-Theta(1)}; (3) extractable with error 2^{-Omega(n)}. We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts one bit with error epsilon from n = poly(1/epsilon) samples in time linear in n. Our algorithm for category (3) sources extracts m bits with error epsilon from n = O(m + log 1/epsilon) samples in time min{O(m2^m * n),n^{O(|F|)}}. We also give algorithms for classifying a GSV source type (F, D): Membership in category (1) can be decided in NP, while membership in category (3) is polynomial-time decidable.

A measure of correlation is said to have the tensorization property if it does not change when computed for i.i.d. copies. More precisely, a measure of correlation between two random variables X, Y denoted by p(X, Y), has the tensorization property if p(Xn, Yn) = p(X, Y) where (Xn, Yn) denotes n i.i.d. copies of (X, Y). Two well-known examples of such measures are the maximal correlation and the hypercontractivity ribbon (HC ribbon). We show that the maximal correlation and the HC ribbon are special cases of the new notion of Φ-ribbons, defined in this paper for a class of convex functions Φ. Φ-ribbon reduces to the HC ribbon and the maximal correlation for special choices of Φ, and is a measure of correlation with the tensorization property. We show that the Φ-ribbon also characterizes the recently introduced Φ-strong data processing inequality constant. We further study the Φ-ribbon for the choice of Φ(t) = t2and introduce an equivalent characterization of this ribbon.

A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to $s$ “nondegenerate” dice that are $c$-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if $s

In this paper, we study the problem of simulating a discrete memoryless channel (DMC) from another DMC under an average-case and an exact model. We present several achievability and infeasibility results, with tight characterizations in special cases. In particular, for the exact model, we fully characterize when a binary symmetric channel can be simulated from a binary erasure channel when there is no shared randomness. We also provide infeasibility and achievability results for the simulation of a binary channel from another binary channel in the case of no shared randomness. To do this, we use the properties of Rényi capacity of a given order. We also introduce a notion of “channel diameter” which is shown to be additive and satisfy a data processing inequality.

We study the optimality of Gaussian signaling (with power control) for the two-user scalar Gaussian interference channel. The capacity region is shown to exhibit a discontinuity of slope around the sum-rate point for a subset of the very weak interference channel. We also show that using colored Gaussians (multi-letter) does not improve on the single-letter region of Gaussian signaling with power control. Finally, we also present an approach to test the optimality of Gaussian signaling motivated by some calculations of the slope of Han-Kobayashi region near the corner point of the Z-interference channel.

We derive an equivalent characterization, using information measures, for a class of reverse Brascamp-Lieb type inequalities. These inequalities contain, in particular, the family of reverse hypercontractive inequalities.

A function is said to be additive if, similar to mutual information, expands by a factor of n, when evaluated on n i.i.d. repetitions of a source or channel. On the other hand, a function is said to satisfy the tensorization property if it remains unchanged when evaluated on i.i.d. repetitions. Additive rate regions are of fundamental importance in network information theory, serving as capacity regions or upper bounds thereof. Tensorizing measures of correlation have also found applications in distributed source and channel coding problems as well as the distribution simulation problem. Prior to our work only two measures of correlation, namely the hypercontractivity ribbon and maximal correlation (and their derivatives), were known to have the tensorization property. In this paper, we provide a general framework to obtain a region with the tensorization property from any additive rate region. We observe that hypercontractivity ribbon indeed comes from the dual of the rate region of the Gray-Wyner source coding problem, and generalize it to the multipartite case. Then we define other measures of correlation with similar properties from other source coding problems.

Non-locality is the phenomenon of observing strong correlations among the outcomes of local measurements of a multipartite physical system. No-signaling boxes are the abstract objects for studying non-locality, and wirings are local operations on the space of no-signaling boxes. This means that, no matter how non-local the nature is, the set of physical non-local correlations must be closed under wirings. Then, one approach to identify the non-locality of nature is to characterize the closed sets of non-local correlations. Although non-trivial examples of wirings of no-signaling boxes are known, there is no systematic way to study wirings. In particular, given a set of no-signaling boxes, we do not know a general method to prove that it is closed under wirings. In this paper, we propose the first general method to construct such closed sets of non-local correlations. We show that a well-known measure of correlation, called maximal correlation, when appropriately defined for non-local correlations, is monotonically decreasing under wirings. This establishes a conjecture about the impossibility of simulating isotropic boxes from each other, implying the existence of a continuum of closed sets of non-local boxes under wirings. To prove our main result, we introduce some mathematical tools that may be of independent interest: we define a notion of maximal correlation ribbon as a generalization of maximal correlation, and provide a connection between it and a known object called hypercontractivity ribbon; we show that these two ribbons are monotone under wirings too.

Expressions of several capacity regions in quantum information theory involve an optimization over auxiliary quantum registers. Evaluating such expressions requires bounds on the dimension of the Hilbert space of these auxiliary registers, for which no nontrivial technique is known; we lack a quantum analog of the Carathéodory theorem. In this paper, we develop a new non-Carathéodory-type tool for evaluating expressions involving a single quantum auxiliary register and several classical random variables. As we show, such expressions appear in problems of entanglement-assisted Gray-Wyner and entanglement-assisted channel simulation, where the question of whether entanglement helps in these settings is related to that of evaluating expressions with a single quantum auxiliary register. To evaluate such expressions, we argue that developing a quantum analog of the Carathéodory theorem requires a better understanding of a notion which we call “quantum conditioning.” We then proceed by proving a few results about quantum conditioning, one of which is that quantum conditioning is strictly richer than the usual classical conditioning.

In this paper, we provide a simple framework for deriving one-shot achievable bounds for some problems in quantum information theory. Our framework is based on the joint convexity of the exponential of the collision relative entropy and is a (partial) quantum generalization of the technique of Yassaee et al. from classical information theory. Based on this framework, we derive one-shot achievable bounds for the problems of communication over classical-quantum channels, quantum hypothesis testing, and classical data compression with quantum side information. We argue that our one-shot achievable bounds are strong enough to give the asymptotic achievable rates of these problems even up to the second order.

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.