Quantum Advantage for Shared Randomness Generation

Tamal Guha; Mir Alimuddin; Sumit Rout; Amit Mukherjee; Some Sankar Bhattacharya; Manik Banik

doi:10.22331/q-2021-10-27-569

Quantum Advantage for Shared Randomness Generation

Tamal Guha¹, Mir Alimuddin², Sumit Rout³, Amit Mukherjee⁴, Some Sankar Bhattacharya⁵, and Manik Banik²

¹Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B.T. Road, Kolkata 700108, India.
²School of Physics, IISER Thiruvanathapuram, Vithura, Kerala 695551, India.
³International Centre for Theory of Quantum Technologies (ICTQT), University of Gdańsk, 80-308 Gdańsk, Poland.
⁴S.N. Bose National Center for Basic Sciences, Block JD, Sector III, Salt Lake, Kolkata 700098, India.
⁵Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong.

Published:	2021-10-27, volume 5, page 569
Eprint:	arXiv:2001.01889v4
Doi:	https://doi.org/10.22331/q-2021-10-27-569
Citation:	Quantum 5, 569 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: Non-monopolizing social subsidy game: advantage of shared quoin over shared coin.

Popular summary

A classical coin can simulate the input-output statistics obtained from a quoin – a two level quantum system. However, in their multiple temporal occurrences, such as generation of Bernoulli factory, a quoin exhibits advantage over its classical counterpart. Present work depicts such an advantage for their multiple spatial occurrence i.e. for a shared two quoin. The non-monopolizing social subsidy game, involving two distant non-communicating players, quantifies such an advantage. Quite counterintuitively, a noisy quantum transmission line turns out to be more effective than its perfect classical counterpart when used to distribute such a two level system. The present work is a potential candidate to understand the resource content of shared randomness.

► BibTeX data

@article{Guha2021quantumadvantage,
  doi = {10.22331/q-2021-10-27-569},
  url = {https://doi.org/10.22331/q-2021-10-27-569},
  title = {Quantum {A}dvantage for {S}hared {R}andomness {G}eneration},
  author = {Guha, Tamal and Alimuddin, Mir and Rout, Sumit and Mukherjee, Amit and Bhattacharya, Some Sankar and Banik, Manik},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {569},
  month = oct,
  year = {2021}
}

► References

[1] L. Jiang, J. M. Taylor, N. Khaneja, and M. D. Lukin, ``Optimal approach to quantum communication using dynamic programming,'' Proceedings of the National Academy of Sciences 104, 17291–17296 (2007).
https://doi.org/10.1073/pnas.0703284104

[2] A. R. Dixon, Z. L. Yuan, J. F. Dynes, A. W. Sharpe, and A. J. Shields, ``Gigahertz decoy quantum key distribution with 1 mbit/s secure key rate,'' Optics Express 16, 18790 (2008).
https://doi.org/10.1364/oe.16.018790

[3] S. Wengerowsky, et. al. ``Entanglement distribution over a 96-km-long submarine optical fiber,'' Proceedings of the National Academy of Sciences 116, 6684–6688 (2019).
https://doi.org/10.1073/pnas.1818752116

[4] J. Yin, et. al.,``Entanglement-based secure quantum cryptography over 1, 120 kilometres,'' Nature 582, 501–505 (2020).
https://doi.org/10.1038/s41586-020-2401-y

[5] Si-Hui Tan, Baris I. Erkmen, Vittorio Giovannetti, Saikat Guha, Seth Lloyd, Lorenzo Maccone, Stefano Pirandola, and Jeffrey H. Shapiro, ``Quantum illumination with gaussian states,'' Phys. Rev. Lett. 101, 253601 (2008).
https://doi.org/10.1103/PhysRevLett.101.253601

[6] R. Schneider, et. al., ``Quantum imaging with incoherently scattered light from a free-electron laser,'' Nature Physics 14, 126–129 (2017).
https://doi.org/10.1038/nphys4301

[7] Shahaf Asban, Konstantin E. Dorfman, and Shaul Mukamel, ``Quantum phase-sensitive diffraction and imaging using entangled photons,'' Proceedings of the National Academy of Sciences 116, 11673–11678 (2019), https://www.pnas.org/content/116/24/11673.full.pdf.
https://doi.org/10.1073/pnas.1904839116
arXiv:https://www.pnas.org/content/116/24/11673.full.pdf

[8] T. Gregory, P.-A. Moreau, E. Toninelli, and M. J. Padgett, ``Imaging through noise with quantum illumination,'' Science Advances 6, eaay2652 (2020).
https://doi.org/10.1126/sciadv.aay2652

[9] C. F. Roos, M. Chwalla, K. Kim, M. Riebe, and R. Blatt, ```designer atoms' for quantum metrology,'' Nature 443, 316–319 (2006).
https://doi.org/10.1038/nature05101

[10] J. Appel, P. J. Windpassinger, D. Oblak, U. B. Hoff, N. Kjaergaard, and E. S. Polzik, ``Mesoscopic atomic entanglement for precision measurements beyond the standard quantum limit,'' Proceedings of the National Academy of Sciences 106, 10960–10965 (2009).
https://doi.org/10.1073/pnas.0901550106

[11] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, ``Advances in quantum metrology,'' Nature Photonics 5, 222–229 (2011).
https://doi.org/10.1038/nphoton.2011.35

[12] Gershon Kurizki, Patrice Bertet, Yuimaru Kubo, Klaus Mølmer, David Petrosyan, Peter Rabl, and Jörg Schmiedmayer, ``Quantum technologies with hybrid systems,'' Proceedings of the National Academy of Sciences 112, 3866–3873 (2015).
https://doi.org/10.1073/pnas.1419326112

[13] S.-S. Li, G.-L. Long, F.-S. Bai, S.-L. Feng, and H.-Z. Zheng, ``Quantum computing,'' Proceedings of the National Academy of Sciences 98, 11847–11848 (2001).
https://doi.org/10.1073/pnas.191373698

[14] Mikkel V. Larsen, Xueshi Guo, Casper R. Breum, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen, ``Deterministic generation of a two-dimensional cluster state,'' Science 366, 369–372 (2019).
https://doi.org/10.1126/science.aay4354

[15] Abhinav Kandala, Kristan Temme, Antonio D. Córcoles, Antonio Mezzacapo, Jerry M. Chow, and Jay M. Gambetta, ``Error mitigation extends the computational reach of a noisy quantum processor,'' Nature 567, 491–495 (2019).
https://doi.org/10.1038/s41586-019-1040-7

[16] C. Flühmann, T. L. Nguyen, M. Marinelli, V. Negnevitsky, K. Mehta, and J. P. Home, ``Encoding a qubit in a trapped-ion mechanical oscillator,'' Nature 566, 513–517 (2019).
https://doi.org/10.1038/s41586-019-0960-6

[17] Frank Arute, et. al.``Quantum supremacy using a programmable superconducting processor,'' Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[18] Raúl García-Patrón, Jelmer J. Renema, and Valery Shchesnovich, ``Simulating boson sampling in lossy architectures,'' Quantum 3, 169 (2019).
https://doi.org/10.22331/q-2019-08-05-169

[19] P.W. Shor, ``Algorithms for quantum computation: discrete logarithms and factoring,'' in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE Comput. Soc. Press).
https://doi.org/10.1109/sfcs.1994.365700

[20] L. K. Grover; A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery: 212–219 (1996).
https://doi.org/10.1145/237814.237866

[21] D. R. Simon; On the Power of Quantum Computation, Journal on Computing, 26(5), 1474–1483 (1997).
https://epubs.siam.org/doi/10.1137/S0097539796298637

[22] C. H. Bennett, G. Brassard, and J. Robert, ``Privacy amplification by public discussion,'' SIAM Journal on Computing 17, 210–229 (1988).
https://doi.org/10.1137/0217014

[23] C.H. Bennett, G. Brassard, C. Crepeau, and U.M. Maurer, ``Generalized privacy amplification,'' IEEE Trans. Inf. Theory 41, 1915–1923 (1995).
https://doi.org/10.1109/18.476316

[24] I. Newman and M. Szegedy, ``Public vs. private coin flips in one round communication games (extended abstract),'' (ACM Press, 1996).
https://doi.org/10.1145/237814.238004

[25] L. Babai and P.G. Kimmel, ``Randomized simultaneous messages: solution of a problem of yao in communication complexity,'' (IEEE Comput. Soc).

[26] D. Gavinsky, T. Ito, and G. Wang, ``Shared randomness and quantum communication in the multi-party model,'' (2012), arXiv:1210.1535 [quant-ph].
arXiv:1210.1535

[27] R. Ahlswede and I. Csiszar, ``Common randomness in information theory and cryptography. i. secret sharing,'' IEEE Trans. Inf. Theory 39, 1121–1132 (1993).
https://doi.org/10.1109/18.243431

[28] G. Brassard, R. Cleve, and A. Tapp, ``Cost of exactly simulating quantum entanglement with classical communication,'' Phys. Rev. Lett. 83, 1874–1877 (1999).
https://doi.org/10.1103/PhysRevLett.83.1874

[29] B. F. Toner and D. Bacon, ``Communication cost of simulating bell correlations,'' Phys. Rev. Lett. 91, 187904 (2003).
https://doi.org/10.1103/PhysRevLett.91.187904

[30] J. Bowles, F. Hirsch, M. T. Quintino, and N. Brunner, ``Local hidden variable models for entangled quantum states using finite shared randomness,'' Phys. Rev. Lett. 114, 120401 (2015).
https://doi.org/10.1103/PhysRevLett.114.120401

[31] R. J. Aumann, ``Correlated equilibrium as an expression of bayesian rationality,'' Econometrica 55, 1 (1987).
https://doi.org/10.2307/1911154

[32] N. Brunner and N. Linden, ``Connection between bell nonlocality and bayesian game theory,'' Nat. Commun. 4, 2057 (2013).
https://doi.org/10.1038/ncomms3057

[33] Arup Roy, Amit Mukherjee, Tamal Guha, Sibasish Ghosh, Some Sankar Bhattacharya, and Manik Banik, ``Nonlocal correlations: Fair and unfair strategies in bayesian games,'' Phys. Rev. A 94, 032120 (2016).
https://doi.org/10.1103/PhysRevA.94.032120

[34] M. Banik, S. S. Bhattacharya, N. Ganguly, T. Guha, A. Mukherjee, A. Rai, and A. Roy, ``Two-qubit pure entanglement as optimal social welfare resource in bayesian game,'' Quantum 3, 185 (2019).
https://doi.org/10.22331/q-2019-09-09-185

[35] C. L. Canonne, V. Guruswami, R. Meka, and M. Sudan, ``Communication with imperfectly shared randomness,'' IEEE Trans. Inf. Theory 63, 6799–6818 (2017).
https://doi.org/10.1109/tit.2017.2734103

[36] C. E. Shannon, ``A mathematical theory of communication,'' Bell System Technical Journal 27, 379–423 (1948).
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[37] S. L. Braunstein and P. van Loock, ``Quantum information with continuous variables,'' Rev. Mod. Phys. 77, 513–577 (2005).
https://doi.org/10.1103/RevModPhys.77.513

[38] S. D. Bartlett, T. Rudolph, and R. W. Spekkens, ``Reference frames, superselection rules, and quantum information,'' Rev. Mod. Phys. 79, 555–609 (2007).
https://doi.org/10.1103/RevModPhys.79.555

[39] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, ``Quantum entanglement,'' Rev. Mod. Phys. 81, 865–942 (2009).
https://doi.org/10.1103/RevModPhys.81.865

[40] K. Modi, A. Brodutch, H. Cable, T. Paterek, and V. Vedral, ``The classical-quantum boundary for correlations: Discord and related measures,'' Rev. Mod. Phys. 84, 1655–1707 (2012).
https://doi.org/10.1103/RevModPhys.84.1655

[41] F. G. S. L. Brandão, M. Horodecki, J. Oppenheim, J. M. Renes, and R. W. Spekkens, ``Resource theory of quantum states out of thermal equilibrium,'' Phys. Rev. Lett. 111, 250404 (2013).
https://doi.org/10.1103/PhysRevLett.111.250404

[42] A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, R. Horodecki, P. Joshi, W. Kłobus, and A. Wójcik, ``Quantifying contextuality,'' Phys. Rev. Lett. 112, 120401 (2014).
https://doi.org/10.1103/PhysRevLett.112.120401

[43] Á. Rivas, S. F Huelga, and M. B. Plenio, ``Quantum non-markovianity: characterization, quantification and detection,'' Rep. Prog. Phys. 77, 094001 (2014).
https://doi.org/10.1088/0034-4885/77/9/094001

[44] V. Veitch, S. A. H. Mousavian, D. Gottesman, and J. Emerson, ``The resource theory of stabilizer quantum computation,'' New J. Phys. 16, 013009 (2014).
https://doi.org/10.1088/1367-2630/16/1/013009

[45] R. Gallego and L. Aolita, ``Resource theory of steering,'' Phys. Rev. X 5, 041008 (2015).
https://doi.org/10.1103/PhysRevX.5.041008

[46] A. Winter and D. Yang, ``Operational resource theory of coherence,'' Phys. Rev. Lett. 116, 120404 (2016).
https://doi.org/10.1103/PhysRevLett.116.120404

[47] Eric Chitambar and Gilad Gour, ``Quantum resource theories,'' Rev. Mod. Phys. 91, 025001 (2019).
https://doi.org/10.1103/RevModPhys.91.025001

[48] Elie Wolfe, David Schmid, Ana Belén Sainz, Ravi Kunjwal, and Robert W. Spekkens, ``Quantifying bell: the resource theory of nonclassicality of common-cause boxes,'' Quantum 4, 280 (2020).
https://doi.org/10.22331/q-2020-06-08-280

[49] D. Schmid, D. Rosset and F. Buschemi; The type-independent resource theory of local operations and shared randomness, Quantum, 4, 262 (2020).
https://doi.org/10.22331/q-2020-04-30-262

[50] D. Rosset, D. Schmid and F. Buschemi; Type-Independent Characterization of Spacelike Separated Resources, Phys. Rev. Lett. 125, 210402 (2020).
https://doi.org/10.1103/PhysRevLett.125.210402

[51] B. F. Toner and D. Bacon; Communication Cost of Simulating Bell Correlations, Phys. Rev. Lett. 91, 187904 (2003).
https://doi.org/10.1103/PhysRevLett.91.187904

[52] Harold Ollivier and Wojciech H. Zurek, ``Quantum discord: A measure of the quantumness of correlations,'' Phys. Rev. Lett. 88, 017901 (2001).
https://doi.org/10.1103/PhysRevLett.88.017901

[53] L Henderson and V Vedral, ``Classical, quantum and total correlations,'' Journal of Physics A: Mathematical and General 34, 6899–6905 (2001).
https://doi.org/10.1088/0305-4470/34/35/315

[54] D. Cavalcanti, L. Aolita, S. Boixo, K. Modi, M. Piani, and A. Winter; Operational interpretations of quantum discord, Phys. Rev. A 83, 032324 (2011).
https://doi.org/10.1103/PhysRevA.83.032324

[55] V. Madhok and A. Datta; Interpreting quantum discord through quantum state merging, Phys. Rev. A 83, 032323 (2011).
https://doi.org/10.1103/PhysRevA.83.032323

[56] A. Streltsov, H. Kampermann, and D. Bruß; Linking Quantum Discord to Entanglement in a Measurement, Phys. Rev. Lett. 106, 160401 (2011).
https://doi.org/10.1103/PhysRevLett.106.160401

[57] V. Madhok and A. Datta; Role of quantum discord in quantum communication, arXiv: 1107.0994[quant-ph] (2011).
arXiv:1107.0994

[58] B. Dakic et. al.; Quantum discord as resource for remote state preparation, Nature Physics volume 8, pages666–670(2012).
https://doi.org/10.1038/nphys2377

[59] T. K. C. Bobby and T. Paterek; Separable states improve protocols with finiterandomness, New J. Phys. 16, 093063 (2014).
https://doi.org/10.1088/1367-2630/16/9/093063/pdf

[60] A. S. Holevo, ``Bounds for the quantity of information transmitted by a quantum communication channel,'' Problems of Information Transmission 9, 177–183 (1973).

[61] P. E. Frenkel and M. Weiner, ``Classical information storage in an n-level quantum system,'' Commun. Math. Phys. 340, 563–574 (2015).
https://doi.org/10.1007/s00220-015-2463-0

[62] A.S. Holevo, ``The capacity of the quantum channel with general signal states,'' IEEE Trans. Inf. Theory 44, 269–273 (1998).
https://doi.org/10.1109/18.651037

[63] B. Schumacher and M. D. Westmoreland, ``Sending classical information via noisy quantum channels,'' Phys. Rev. A 56, 131–138 (1997).
https://doi.org/10.1103/PhysRevA.56.131

[64] S. Lloyd, ``Capacity of the noisy quantum channel,'' Phys. Rev. A 55, 1613–1622 (1997).
https://doi.org/10.1103/PhysRevA.55.1613

[65] P. W. Shor, ``The quantum channel capacity and coherent information,'' Lecture notes,MSRIWorkshop on Quantum Computation -, – (2002).

[66] I. Devetak, ``The private classical capacity and quantum capacity of a quantum channel,'' IEEE Trans. Inf. Theory 51, 44–55 (2005).
https://doi.org/10.1109/tit.2004.839515

[67] F. G. S. L. Brandão and G. Gour, ``Reversible framework for quantum resource theories,'' Phys. Rev. Lett. 115, 070503 (2015).
https://doi.org/10.1103/PhysRevLett.115.070503

[68] L. Hardy, ``Quantum theory from five reasonable axioms,'' (2001), arXiv:quant-ph/0101012 [quant-ph].
arXiv:quant-ph/0101012

[69] J. Barrett, ``Information processing in generalized probabilistic theories,'' Phys. Rev. A 75, 032304 (2007).
https://doi.org/10.1103/PhysRevA.75.032304

[70] G. Chiribella, G. M. D'Ariano, and P. Perinotti, ``Informational derivation of quantum theory,'' Phys. Rev. A 84, 012311 (2011).
https://doi.org/10.1103/PhysRevA.84.012311

[71] I. Namioka and R.Phelps, ``Tensor products of compact convex sets,'' Pac. J. Math 31, 469–480 (1969).
https://doi.org/10.2140/pjm.1969.31.469

[72] G. P. Barker, ``Monotone norms and tensor products,'' Linear and Multilinear Algebra 4, 191–199 (1976).
https://doi.org/10.1080/03081087608817150

[73] G. P. Barker, ``Theory of cones,'' Linear Algebra Its Appl 39, 263–291 (1981).
https://doi.org/10.1016/0024-3795(81)90310-4

[74] G. Aubrun, L. Lami, C. Palazuelos, and M. Plavala, ``Entangleability of cones,'' (2019), arXiv:1911.09663 [math.FA].
https://doi.org/10.1007/s00039-021-00565-5
arXiv:1911.09663

[75] K. Kraus, States, Effects, and Operations Fundamental Notions of Quantum Theory, edited by K. Kraus, A. Böhm, J. D. Dollard, and W. H. Wootters (Springer Berlin Heidelberg, 1983).
https://doi.org/10.1007/3-540-12732-1

[76] R. F. Werner, ``Quantum states with einstein-podolsky-rosen correlations admitting a hidden-variable model,'' Phys. Rev. A 40, 4277–4281 (1989).
https://doi.org/10.1103/PhysRevA.40.4277

[77] C. King, ``The capacity of the quantum depolarizing channel,'' IEEE Transactions on Information Theory 49, 221–229 (2003).
https://doi.org/10.1109/tit.2002.806153

[78] John S. Bell, ``On the problem of hidden variables in quantum mechanics,'' Rev. Mod. Phys. 38, 447–452 (1966).
https://doi.org/10.1103/RevModPhys.38.447

[79] Michael J. W. Hall, ``Local deterministic model of singlet state correlations based on relaxing measurement independence,'' Phys. Rev. Lett. 105, 250404 (2010).
https://doi.org/10.1103/PhysRevLett.105.250404

[80] Jonathan Barrett and Nicolas Gisin, ``How much measurement independence is needed to demonstrate nonlocality?'' Phys. Rev. Lett. 106, 100406 (2011).
https://doi.org/10.1103/PhysRevLett.106.100406

Cited by

[1] Gaurav Saxena and Gilad Gour, "Quantifying multiqubit magic channels with completely stabilizer-preserving operations", Physical Review A 106 4, 042422 (2022).

[2] Govind Lal Sidhardh, Mir Alimuddin, and Manik Banik, "Exploring superadditivity of coherent information of noisy quantum channels through genetic algorithms", Physical Review A 106 1, 012432 (2022).

[3] Dashiell LP Vitullo, Trevor Cook, Daniel E Jones, Lisa M Scott, Andrew Toth, and Brian T Kirby, "Simulating quantum key distribution in fiber-based quantum networks", The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology 154851292311549 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-09 09:18:45) and SAO/NASA ADS (last updated successfully 2023-06-09 09:18:45). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.