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:2402.00242 · IEEE International Symposium on Information Theory (ISIT)

Quantum Advantage in Non-Interactive Source Simulation

Hojat Allah Salehi, Farhad Shirani, S. Sandeep Pradhan

Published Jun 22, 2025• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit63088.2025.11195605

Related papers

Beyond Common Randomness: Quantum Resources in Decentralized Control

Shashank A. Deshpande, Ankur A. Kulkarni

Ananthram and Borkar [1] showed that there exist strategies that are consistent with the requirements of a decentralized information structure but are unattainable through the use of common randomness. This opens the question of discovering physically realisable mechanisms that provide access to this region of the strategic space. In our previous work we introduced a class of quantum strategies that allow such access in a two-agent setting. In this paper, we consider the problem of optimal allocation of a$k$-partite quantum resource amongst$n$agents,$k < n$. We study the problem of decentralized estimation of a binary source by agents that are informed through independent binary symmetric channels, and face a cost that is homogeneous in their actions. We show a$k$-partite quantum resource produces the maximum advantage over classical strategies when allocated to the agents with the$k$most reliable channels.

IEEE Conference on Decision and Control (CDC)•Dec 13, 2023•1 citation

Quantum Advantage for Shared Randomness Generation

Tamal Guha, Mir Alimuddin, Sumit Rout +3 more

Sharing correlated random variables is a resource for a number of information theoretic tasks such as privacy amplification, simultaneous message passing, secret sharing and many more. In this article, we show that to establish such a resource called shared randomness, quantum systems provide an advantage over their classical counterpart. Precisely, we show that appropriate albeit fixed measurements on a shared two-qubit state can generate correlations which cannot be obtained from any possible state on two classical bits. In a resource theoretic set-up, this feature of quantum systems can be interpreted as an advantage in winning a two players co-operative game, which we call the `non-monopolize social subsidy' game. It turns out that the quantum states leading to the desired advantage must possess non-classicality in the form of quantum discord. On the other hand, while distributing such sources of shared randomness between two parties via noisy channels, quantum channels with zero capacity as well as with classical capacity strictly less than unity perform more efficiently than the perfect classical channel. Protocols presented here are noise-robust and hence should be realizable with state-of-the-art quantum devices.

arXiv:2001.01889•Quantum•Oct 27, 2021•13 citations

Measurement incompatibility and quantum advantage in communication

Debashis Saha, Debarshi Das, Arun Kumar Das +2 more

Measurement incompatibility stipulates the existence of quantum measurements that cannot be carried out simultaneously on single systems. We show that the set of input-output probabilities obtained from $d$-dimensional classical systems assisted with shared randomness is the same as the set obtained from $d$-dimensional quantum strategies restricted to compatible measurements with shared randomness in any communication scenario. Thus, measurement incompatibility is necessary for quantum advantage in communication, and any quantum advantage (with or without shared randomness) in communication acts as a witness to the incompatibility of the measurements at the receiver's end in a semi-device-independent way. We introduce a class of communication tasks---a general version of random access codes---to witness incompatibility of an arbitrary number of quantum measurements with arbitrary outcomes acting on $d$-dimensional systems and provide generic upper bounds on the success metric of these tasks for compatible measurements. We identify all sets of three incompatible rank-one projective qubit measurements that random access codes can witness. Finally, we present the generic relationship between different sets of probability distributions---classical, quantum with or without shared randomness, and quantum restricted to compatible measurements with or without shared randomness---produced in communication scenarios.

arXiv:2209.14582•Physical Review A•Jun 12, 2023•21 citations

The Quantum Advantage in Binary Teams and the Coordination Dilemma: Part I

Shashank A. Deshpande, Ankur A. Kulkarni

We have shown that entanglement assisted stochastic strategies allow access to strategic measures beyond the classically correlated measures accessible through passive common randomness, and thus attain a quantum advantage in decentralised control. In this two part series of articles, we investigate the decision theoretic origins of the quantum advantage within a broad superstructure of problem classes. Each class in our binary team superstructure corresponds to a parametric family of cost functions with a distinct algebraic structure. In this part, identify the only problem classes that benefit from quantum strategies. We find that these cost structures admit a special decision-theoretic feature -- `the coordination dilemma'. Our analysis hence reveals some intuition towards the utility of non-local quantum correlations in decentralised control.

arXiv:2307.01762•Jul 4, 2023•1 citation

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

Approximate simulation of quantum channels

Cédric Bény, Ognyan Oreshkov

Earlier, we proved a duality between two optimizations problems [Phys. Rev. Lett. 104, 120501 (2010)]. The primary one is, given two quantum channels $\mathcal{M}$ and $\mathcal{N}$, to find a quantum channel $\mathcal{R}$ such that $\mathcal{R}\ensuremath{\circ}\mathcal{N}$ is optimally close to $\mathcal{M}$ as measured by the worst-case entanglement fidelity. The dual problem involves the information obtained by the environment through the so-called complementary channels $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{M}}$ and $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{N}}$, and consists in finding a quantum channel ${\mathcal{R}}^{\ensuremath{'}}$ such that ${\mathcal{R}}^{\ensuremath{'}}\ensuremath{\circ}\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{M}}$ is optimally close to $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{N}}$. It turns out to be easier to find an approximate solution to the dual problem in certain important situations, notably when $\mathcal{M}$ is the identity channel---the problem of quantum error correction---yielding a good near-optimal worst-case entanglement fidelity as well as the corresponding near-optimal correcting channel. Here we provide more detailed proofs of these results. In addition, we generalize the main theorem to the case where there are certain constraints on the implementation of $\mathcal{R}$, namely, on the number of Kraus operators. We also offer a simple algebraic form for the near-optimal correction channel in the case $\mathcal{M}=\mathrm{id}$. For approximate error correction, we show that any $\ensuremath{\varepsilon}$-correctable channel is, up to appending an ancilla, $\ensuremath{\varepsilon}$-close to an exactly correctable one. We also demonstrate an application of our theorem to the problem of minimax state discrimination.

arXiv:1103.0649•Physical Review A•Aug 25, 2011•27 citations
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.
Ananthram and Borkar [1] showed that there exist strategies that are consistent with the requirements of a decentralized information structure but are unattainable through the use of common randomness. This opens the question of discovering physically realisable mechanisms that provide access to this region of the strategic space. In our previous work we introduced a class of quantum strategies that allow such access in a two-agent setting. In this paper, we consider the problem of optimal allocation of akkk-partite quantum resource amongstnnnagents,k<nk < nk<n. We study the problem of decentralized estimation of a binary source by agents that are informed through independent binary symmetric channels, and face a cost that is homogeneous in their actions. We show akkk-partite quantum resource produces the maximum advantage over classical strategies when allocated to the agents with thekkkmost reliable channels.
Sharing correlated random variables is a resource for a number of information theoretic tasks such as privacy amplification, simultaneous message passing, secret sharing and many more. In this article, we show that to establish such a resource called shared randomness, quantum systems provide an advantage over their classical counterpart. Precisely, we show that appropriate albeit fixed measurements on a shared two-qubit state can generate correlations which cannot be obtained from any possible state on two classical bits. In a resource theoretic set-up, this feature of quantum systems can be interpreted as an advantage in winning a two players co-operative game, which we call the `non-monopolize social subsidy' game. It turns out that the quantum states leading to the desired advantage must possess non-classicality in the form of quantum discord. On the other hand, while distributing such sources of shared randomness between two parties via noisy channels, quantum channels with zero capacity as well as with classical capacity strictly less than unity perform more efficiently than the perfect classical channel. Protocols presented here are noise-robust and hence should be realizable with state-of-the-art quantum devices.
Measurement incompatibility stipulates the existence of quantum measurements that cannot be carried out simultaneously on single systems. We show that the set of input-output probabilities obtained from ddd-dimensional classical systems assisted with shared randomness is the same as the set obtained from ddd-dimensional quantum strategies restricted to compatible measurements with shared randomness in any communication scenario. Thus, measurement incompatibility is necessary for quantum advantage in communication, and any quantum advantage (with or without shared randomness) in communication acts as a witness to the incompatibility of the measurements at the receiver's end in a semi-device-independent way. We introduce a class of communication tasks---a general version of random access codes---to witness incompatibility of an arbitrary number of quantum measurements with arbitrary outcomes acting on ddd-dimensional systems and provide generic upper bounds on the success metric of these tasks for compatible measurements. We identify all sets of three incompatible rank-one projective qubit measurements that random access codes can witness. Finally, we present the generic relationship between different sets of probability distributions---classical, quantum with or without shared randomness, and quantum restricted to compatible measurements with or without shared randomness---produced in communication scenarios.
We have shown that entanglement assisted stochastic strategies allow access to strategic measures beyond the classically correlated measures accessible through passive common randomness, and thus attain a quantum advantage in decentralised control. In this two part series of articles, we investigate the decision theoretic origins of the quantum advantage within a broad superstructure of problem classes. Each class in our binary team superstructure corresponds to a parametric family of cost functions with a distinct algebraic structure. In this part, identify the only problem classes that benefit from quantum strategies. We find that these cost structures admit a special decision-theoretic feature -- `the coordination dilemma'. Our analysis hence reveals some intuition towards the utility of non-local quantum correlations in decentralised control.
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.
Earlier, we proved a duality between two optimizations problems [Phys. Rev. Lett. 104, 120501 (2010)]. The primary one is, given two quantum channels M\mathcal{M}M and N\mathcal{N}N, to find a quantum channel R\mathcal{R}R such that $\mathcal{R}\ensuremath{\circ}\mathcal{N}$ is optimally close to M\mathcal{M}M as measured by the worst-case entanglement fidelity. The dual problem involves the information obtained by the environment through the so-called complementary channels $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{M}}$ and $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{N}}$, and consists in finding a quantum channel ${\mathcal{R}}^{\ensuremath{'}}$ such that ${\mathcal{R}}^{\ensuremath{'}}\ensuremath{\circ}\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{M}}$ is optimally close to $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\mathcal{N}}$. It turns out to be easier to find an approximate solution to the dual problem in certain important situations, notably when M\mathcal{M}M is the identity channel---the problem of quantum error correction---yielding a good near-optimal worst-case entanglement fidelity as well as the corresponding near-optimal correcting channel. Here we provide more detailed proofs of these results. In addition, we generalize the main theorem to the case where there are certain constraints on the implementation of R\mathcal{R}R, namely, on the number of Kraus operators. We also offer a simple algebraic form for the near-optimal correction channel in the case M=id\mathcal{M}=\mathrm{id}M=id. For approximate error correction, we show that any $\ensuremath{\varepsilon}$-correctable channel is, up to appending an ancilla, $\ensuremath{\varepsilon}$-close to an exactly correctable one. We also demonstrate an application of our theorem to the problem of minimax state discrimination.