Distributed source simulation is the task where two (or more) parties share some correlated randomness and use local operations and no communication to convert this into some target correlation. Wyner’s seminal result showed that asymptotically the rate of uniform shared randomness needed for this task is given by a mutual information induced measure, now referred to as Wyner’s common information. This asymptotic result was extended by Hayashi in the quantum setting to separable states, the largest class of states for which this task can be performed to vanishing error. In this work we characterize this task in a near-tight manner in the one-shot setting using the smooth entropy framework. We do this by introducing one-shot operational quantities and correlation measures that characterize them. We establish asymptotic equipartition properties for our correlation measures thereby recovering the previous vanishing-error asymptotic results. In doing so, we consider technical points in one-shot network information theory and provide methods for cardinality bounds in the smooth entropy calculus. We also introduce entangled state versions of the distributed source simulation task and determine bounds in this setting via quantum embezzling. This provides a strong characterization of this network task in the one-shot, quantum regime.
We study a random sampling technique to approximate integrals ∫[0, 1]s f(x) dx by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function f and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order N−1/2 (where N is the number of samples) for functions f with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order N−3/2+ε under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order N−3/2−1/s+ε (where s ≥ 1 is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order N−α−1/2+ε provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order α > 1 in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order N−5/2 and N−7/2, in accordance with the theoretical upper bound.
We prove lower bounds for the error of optimal cubature formulas for
d-variate functions from Besov spaces of mixed smoothness
Bp,θα(Gd) in the case
01/p, and upper bounds for QMC methods on the Fibonacci lattice for two-variate periodic functions from
Bp,θα(G2) in the case
1≤p≤∞,
01/p, where
Gd is either the
d-dimensional torus
Td or the
d-dimensional cube
[0,1]d. In combination these results yield the correct asymptotic of the error of optimal cubature formulas for functions from
Bp,θα(G2) and indicate that a corresponding results is most likely also true in case
d>2. This is compared to the obtained correct asymptotic of optimal cubature formulas on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.