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:2212.09239 · IEEE Information Theory Workshop (ITW)

On Non-Interactive Source Simulation via Fourier Transform

Farhad Shirani, Mohsen Heidari

Published Apr 23, 2023• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/itw55543.2023.10161618

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•0 citations

Quantum Advantage in Non-Interactive Source Simulation

Hojat Allah Salehi, Farhad Shirani, S. Sandeep Pradhan

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ($X^{d}, Y^{d}$) generated based on the joint distribution$P_{X, Y}$. The agents wish to produce a pair of discrete random variables$\left(U_{d}, V_{d}\right)$with joint distribution$P_{U_{d}, V_{d}}$, such that$P_{U_{d}, V_{d}}$converges in total variation distance to a target distribution$Q_{U, V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to$\left(X^{d}, Y^{d}\right)$, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with$\left(X^{d}, Y^{d}\right)$to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit$Z$, in addition to ($X^{d}, Y^{d}$). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

arXiv:2402.00242•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•4 citations

Distributed Source Simulation With No Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences$U^{n}$and$V^{n}$respectively, drawn from a joint distribution$p_{UV}^ {\otimes n}$, and wish to locally generate sequences$X^{n}$and$Y^{n}$respectively with a joint distribution that is close (in KL divergence) to$p_{XY}^ {\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between$U$and$V$is nonzero, and we conjecture that only scalar Markov chains$X-U-V-Y$can be simulated otherwise. Motivated by this conjecture, we further examine the case where both$p_{UV}$and$p_{XY}$are doubly symmetric binary sources with parameters$p,q\leq 1/2$respectively. While it is trivial that in this case$p\leq q$is both necessary and sufficient, we use Fourier analytic tools to show that when$p$is close to$q$then any successful simulation is close to being scalar in the total variation sense.

arXiv:1906.06970•IEEE Transactions on Information Theory•Oct 28, 2020•2 citations

Some Results on Distributed Source Simulation with no Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•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•27 citations

On Non-Interactive Simulation of Joint Distributions

Sudeep Kamath, Venkat Anantharam

We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.

arXiv:1505.00769•IEEE Transactions on Information Theory•Apr 13, 2016•39 citations
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.
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.
This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source (Xd,YdX^{d}, Y^{d}Xd,Yd) generated based on the joint distributionPX,YP_{X, Y}PX,Y​. The agents wish to produce a pair of discrete random variables(Ud,Vd)\left(U_{d}, V_{d}\right)(Ud​,Vd​)with joint distributionPUd,VdP_{U_{d}, V_{d}}PUd​,Vd​​, such thatPUd,VdP_{U_{d}, V_{d}}PUd​,Vd​​converges in total variation distance to a target distributionQU,VQ_{U, V}QU,V​. Two variations of the standard NISS scenario are considered. In the first variation, in addition to(Xd,Yd)\left(X^{d}, Y^{d}\right)(Xd,Yd), the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with(Xd,Yd)\left(X^{d}, Y^{d}\right)(Xd,Yd)to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bitZZZ, in addition to (Xd,YdX^{d}, Y^{d}Xd,Yd). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequencesUnU^{n}UnandVnV^{n}Vnrespectively, drawn from a joint distributionpUV⊗np_{UV}^ {\otimes n}pUV⊗n​, and wish to locally generate sequencesXnX^{n}XnandYnY^{n}Ynrespectively with a joint distribution that is close (in KL divergence) topXY⊗np_{XY}^ {\otimes n}pXY⊗n​. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information betweenUUUandVVVis nonzero, and we conjecture that only scalar Markov chainsX−U−V−YX-U-V-YX−U−V−Ycan be simulated otherwise. Motivated by this conjecture, we further examine the case where bothpUVp_{UV}pUV​andpXYp_{XY}pXY​are doubly symmetric binary sources with parametersp,q≤1/2p,q\leq 1/2p,q≤1/2respectively. While it is trivial that in this casep≤qp\leq qp≤qis both necessary and sufficient, we use Fourier analytic tools to show that whenpppis close toqqqthen any successful simulation is close to being scalar in the total variation sense.
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution pUV⊗np_{UV}^{\otimes n}pUV⊗n​, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to pXY⊗np_{XY}^{\otimes n}pXY⊗n​. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X−U−V−YX-U-V-YX−U−V−Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters p,q≤1/2p, q\leq 1/2p,q≤1/2 respectively. While it is trivial that in this case p≤qp\leq qp≤q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
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.
We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.