Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.11974

Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets

Haoran Wang

Published Nov 9, 2026• 0 citations
arXivHTMLPDF

Abstract

We study noninteractive simulation from a finite correlated source. Alice and Bob observe independent copies of the source and generate outputs without communication. We give a quantitative construction for arbitrary finite output alphabets: for every fixed source, a joint law that is simulable with arbitrarily many samples can be approximated using a number of samples polynomial jointly in the output alphabet sizes and the inverse accuracy. We first study binary outputs. A one-sided Wright--Fisher comparison gives a source-dependent explicit exponent and a finite-head Gaussian-threshold representation. We then handle arbitrary finite output alphabets through averaged influence regularity, simplex-preserving Gaussian moment lifting, and a common Gaussian projection for all correlated-prefix states. The sample exponent is independent of the output alphabet sizes. For a concrete biased binary source we certify an explicit exponent below $19$.

DOI
10.48550/arxiv.2611.11974

Related papers

On Non-Interactive Simulation of Distributed Sources With Finite Alphabets

Hojat Allah Salehi, Farhad Shirani

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences$X^{d}$and$Y^{d}$drawn according to a joint distribution$P_{X^{d}Y^{d}}$. The agents aim to generate outputs$U=f_{d}(X^{d})$and$V=g_{d}(Y^{d})$with a joint distribution sufficiently close in total variation to a target distribution$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is$O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is$\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions$(f_{d}(X^{d}),g_{d}(Y^{d}))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.

arXiv:2403.00989•IEEE Transactions on Information Theory•Aug 11, 2025•1 citation

Non interactive simulation of correlated distributions is decidable

Anindya De, Elchanan Mossel, Joe Neeman

A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.

arXiv:1701.01485•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•24 citations

Finite Nonsignalling Resources Suffice to Simulate Entangled Qubits

Ziao Tang, Xin Wang, Ge Bai

A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most $128\cot^4θ$ calls for the Schmidt state $\cosθ|00\rangle+\sinθ|11\rangle$, $0<θ<π/4$. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.

quant-pharXiv:2610.32319•Oct 26, 2026•0 citations

Decidability of Non-interactive Simulation of Joint Distributions

Badih Ghazi, Pritish Kamath, Madhu Sudan

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to determine if two players, Alice and Bob, that observe sequences Xn and Yn respectively where {(Xi, Yi)}ni = 1 are drawn i.i.d. from P(x, y) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q(u, v). Even when P and Q are extremely simple: e.g., P is uniform on the triples (0, 0), (0,1), (1,0) and Q is a "doubly symmetric binary source", i.e., U and V are uniform ± 1 variables with correlation say 0.49, it is open if P can simulate Q. In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 × 2 distribution, then the non-interactive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a non-interactive simulation protocol that is δ-close to Q or asserts that no protocol gets O(δ)-close to Q. The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P(x, y) to get δ-close to Q. We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.

arXiv:1607.04322•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•30 citations

On Non-Interactive Source Simulation via Fourier Transform

Farhad Shirani, Mohsen Heidari

The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

arXiv:2212.09239•IEEE Information Theory Workshop (ITW)•Apr 23, 2023•3 citations

Common Randomness Generation from Sources with Countable Alphabet

Wafa Labidi, Rami Ezzine, Christian Deppe +2 more

We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.

arXiv:2210.04556•International Conference on Communications•May 28, 2023•2 citations
We study noninteractive simulation from a finite correlated source. Alice and Bob observe independent copies of the source and generate outputs without communication. We give a quantitative construction for arbitrary finite output alphabets: for every fixed source, a joint law that is simulable with arbitrarily many samples can be approximated using a number of samples polynomial jointly in the output alphabet sizes and the inverse accuracy. We first study binary outputs. A one-sided Wright--Fisher comparison gives a source-dependent explicit exponent and a finite-head Gaussian-threshold representation. We then handle arbitrary finite output alphabets through averaged influence regularity, simplex-preserving Gaussian moment lifting, and a common Gaussian projection for all correlated-prefix states. The sample exponent is independent of the output alphabet sizes. For a concrete biased binary source we certify an explicit exponent below 191919.
This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequencesXdX^{d}XdandYdY^{d}Yddrawn according to a joint distributionPXdYdP_{X^{d}Y^{d}}PXdYd​. The agents aim to generate outputsU=fd(Xd)U=f_{d}(X^{d})U=fd​(Xd)andV=gd(Yd)V=g_{d}(Y^{d})V=gd​(Yd)with a joint distribution sufficiently close in total variation to a target distributionQUVQ_{UV}QUV​. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which isO(exp⁡poly(1ϵ))O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)O(exppoly(ϵ1​)). In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity isΘ(log⁡1ϵ)\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)Θ(logϵ1​), thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions(fd(Xd),gd(Yd))(f_{d}(X^{d}),g_{d}(Y^{d}))(fd​(Xd),gd​(Yd)). The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.
A basic problem in information theory is the following: Let P = (X, Y) be an arbitrary distribution where the marginals X and Y are (potentially) correlated. Let Alice and Bob be two players where Alice gets samples {xi}i≥1 and Bob gets samples {yi}i≥i and for all i, (xi,yi) ∼ P. What joint distributions Q can be simulated by Alice and Bob without any interaction? Classical works in information theory by Gács-Körner and Wyner answer this question when at least one of P or Q is the distribution Eq (Eq is defined as uniform over the points (0, 0) and (1, 1)). However, other than this special case, the answer to this question is understood in very few cases. Recently, Ghazi, Kamath and Sudan showed that this problem is decidable for Q supported on {0, 1} × {0, 1}. We extend their result to Q supported on any finite alphabet. Moreover, we show that If Q can be simulated, our algorithm also provides a (non-interactive) simulation protocol. We rely on recent results in Gaussian geometry (by the authors) as well as a new smoothing argument inspired by the method of boosting from learning theory and potential function arguments from complexity theory and additive combinatorics.
A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most 128cot⁡4θ128\cot^4θ128cot4θ calls for the Schmidt state cos⁡θ∣00⟩+sin⁡θ∣11⟩\cosθ|00\rangle+\sinθ|11\ranglecosθ∣00⟩+sinθ∣11⟩, 0<θ<π/40<θ<π/40<θ<π/4. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.
We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to determine if two players, Alice and Bob, that observe sequences Xn and Yn respectively where {(Xi, Yi)}ni = 1 are drawn i.i.d. from P(x, y) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q(u, v). Even when P and Q are extremely simple: e.g., P is uniform on the triples (0, 0), (0,1), (1,0) and Q is a "doubly symmetric binary source", i.e., U and V are uniform ± 1 variables with correlation say 0.49, it is open if P can simulate Q. In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 × 2 distribution, then the non-interactive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a non-interactive simulation protocol that is δ-close to Q or asserts that no protocol gets O(δ)-close to Q. The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P(x, y) to get δ-close to Q. We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.
The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution PUd,Vd,{P_{{U_d},{V_d}}},PUd​,Vd​​, such that PUd,Vd{P_{{U_d},{V_d}}}PUd​,Vd​​ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets UandV{\mathcal{U}}{\text{and}}{\mathcal{V}}UandV have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.
We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.