On Relating One-way Classical And Quantum Communication Complexities

Genudgivet af Platon

Abonnenter: 0

Naresh Goud Boddu¹, Rahul Jain²og Han-Hsuan Lin³

¹NTT Research, Sunnyvale, Californien, USA
²Center for Quantum Technologies og Department of Computer Science, National University of Singapore og MajuLab, UMI 3654, Singapore
³National Tsing Hua University, Taiwan

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Kommunikationskompleksitet er mængden af kommunikation, der er nødvendig for at beregne en funktion, når funktionsinputs er fordelt over flere parter. I sin enkleste form, envejskommunikationskompleksitet, beregner Alice og Bob en funktion $f(x,y)$, hvor $x$ gives til Alice og $y$ gives til Bob, og kun én besked fra Alice til Bob får lov. Et grundlæggende spørgsmål i kvanteinformation er forholdet mellem envejs kvante og klassisk kommunikationskompleksitet, dvs. hvor meget kortere beskeden kan være, hvis Alice sender en kvantetilstand i stedet for bitstrenge? Vi gør nogle fremskridt hen imod dette spørgsmål med følgende resultater.
Lad $f :mathcal{X} gange mathcal{Y} højrepil mathcal{Z} cup {bot}$ være en delfunktion og $mu$ være en fordeling med støtte indeholdt i $f^{-1}(mathcal{Z} )$. Angiv $d=|mathcal{Z}|$. Lad $mathsf{R}^{1,mu}_epsilon(f)$ være den klassiske envejskommunikationskompleksitet af $f$; $mathsf{Q}^{1,mu}_epsilon(f)$ være kvanteenvejskommunikationskompleksiteten af $f$ og $mathsf{Q}^{1,mu, *}_epsilon(f)$ være sammenfiltringen -assisteret kvante-envejskommunikationskompleksitet på $f$, hver med fordelingsfejl (gennemsnitlig fejl over $mu$) højst $epsilon$. Vi viser:

1) Hvis $mu$ er en produktdistribution, $eta gt 0$ og $0 leq epsilon leq 1-1/d$, så,

$mathsf{R}^{1,mu}_{2epsilon -depsilon^2/(d-1)+ eta}(f) leq 2mathsf{Q}^{1,mu, *}_{epsilon}(f) + O(loglog (1/eta))enspace.$

2)Hvis $mu$ er en ikke-produktdistribution og $mathcal{Z}={ 0,1}$, så $forall epsilon, eta gt 0$, således at $epsilon/eta + eta lt 0.5$,

$mathsf{R}^{1,mu}_{3eta}(f) = O(mathsf{Q}^{1,mu}_{epsilon}(f) cdot mathsf{CS}(f)/eta^3 )enspace,$

hvor

$mathsf{CS}(f) = max_{y} min_{zin{0,1}} vert {x~|~f(x,y)=z} vert enspace.$

► BibTeX-data

@article{Boddu2023relatingoneway, doi = {10.22331/q-2023-05-22-1010}, url = {https://doi.org/10.22331/q-2023-05-22-1010}, title = {On relating one-way classical and quantum communication complexities}, author = {Boddu, Naresh Goud and Jain, Rahul and Lin, Han-Hsuan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1010}, month = may, year = {2023}<br /> }

► Referencer

[1] Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99, pages 376–383, New York, USA, 1999. Association for Computing Machinery. ISBN 1581130678. 10.1145/301250.301347.
https:///doi.org/10.1145/301250.301347

[2] H. Barnum og E. Knill. Vende kvantedynamik med næsten optimal kvante og klassisk troskab. Journal of Mathematical Physics, 43 (5): 2097–2106, 04 2002. ISSN 0022-2488. 10.1063/1.1459754.
https:///doi.org/10.1063/1.1459754

[3] Mario Berta, Matthias Christandl og Renato Renner. Kvante-reverse shannon-sætningen er baseret på one-shot informationsteori. Communications in Mathematical Physics, 306 (3): 579–615, 2011. 10.1007/s00220-011-1309-7.
https://doi.org/10.1007/s00220-011-1309-7

[4] Harry Buhrman, Wim van Dam, Peter Høyer og Alain Tapp. Flerparts kvantekommunikationskompleksitet. Physical Review A, 60: 2737–2741, oktober 1999. 10.1103/PhysRevA.60.2737.
https:///doi.org/10.1103/PhysRevA.60.2737

[5] Harry Buhrman, Richard Cleve, John Watrous og Ronald de Wolf. Kvantefingeraftryk. Phys. Rev. Lett., 87: 167902, sep 2001. 10.1103/PhysRevLett.87.167902. URL https:///link.aps.org/doi/10.1103/PhysRevLett.87.167902.
https:///doi.org/10.1103/PhysRevLett.87.167902

[6] Nilanjana Datta. Min- og maks-relative entropier og en ny entanglement monoton. IEEE Transactions on Information Theory, 55 (6): 2816–2826, juni 2009. 10.1109/tit.2009.2018325. URL https://doi.org/10.1109.
https:///doi.org/10.1109/tit.2009.2018325

[7] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pages 516–525, New York, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/1250790.1250866. URL https://doi.org/10.1145/1250790.1250866.
https:///doi.org/10.1145/1250790.1250866

[8] Hsin-Yuan Huang, Richard Kueng og John Preskill. Forudsige mange egenskaber ved et kvantesystem ud fra meget få målinger. Nature Physics, 16 (10): 1050–1057, 2020. ISSN 1745-2481. 10.1038/s41567-020-0932-7. URL https://doi.org/10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[9] Rahul Jain og Shengyu Zhang. Nye grænser for klassisk og kvante envejskommunikationskompleksitet. Teoretisk datalogi, 410 (26): 2463–2477, 2009. ISSN 0304-3975. https://doi.org/10.1016/j.tcs.2008.10.014. URL https://www.sciencedirect.com/science/article/pii/S0304397508007627.
https:///doi.org/10.1016/j.tcs.2008.10.014
https:///www.sciencedirect.com/science/article/pii/S0304397508007627

[10] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th international conference on Automata, languages and programming, ICALP’03, pages 300–315, Berlin, Heidelberg, 2003. Springer-Verlag. ISBN 3-540-40493-7. URL http://dl.acm.org/citation.cfm?id=1759210.1759242.
http:///dl.acm.org/citation.cfm?id=1759210.1759242

[11] Rahul Jain, Jaikumar Radhakrishnan og Pranab Sen. Tidligere sammenfiltring, meddelelseskomprimering og privatliv i kvantekommunikation. I Proceedings of the 20th Annual IEEE Conference on Computational Complexity, side 285-296, Washington, DC, USA, 2005. IEEE Computer Society. ISBN 0-7695-2364-1. 10.1109/CCC.2005.24. URL http:///dl.acm.org/citation.cfm?id=1068502.1068658.
https:///doi.org/10.1109/CCC.2005.24
http:///dl.acm.org/citation.cfm?id=1068502.1068658

[12] Rahul Jain, Hartmut Klauck, and Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds: Extended abstract. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 599–608, New York, USA, 2008. Association for Computing Machinery. ISBN 9781605580470. 10.1145/1374376.1374462. URL https://doi.org/10.1145/1374376.1374462.
https:///doi.org/10.1145/1374376.1374462

[13] Robert T. Konig og Barbara M. Terhal. Den afgrænsede lagringsmodel i nærværelse af en kvantemodstander. IEEE Transactions on Information Theory, 54 (2): 749–762, 2008. 10.1109/TIT.2007.913245.
https:///doi.org/10.1109/TIT.2007.913245

[14] Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 596–605, New York, USA, 1995. Association for Computing Machinery. ISBN 0897917189. 10.1145/225058.225277. URL https://doi.org/10.1145/225058.225277.
https:///doi.org/10.1145/225058.225277

[15] Eyal Kushilevitz og Noam Nisan. Kommunikationskompleksitet. Cambridge University Press, 1996. 10.1017/CBO9780511574948.
https:///doi.org/10.1017/CBO9780511574948

[16] Joseph M. Renes. Bedre grænser for optimal måling og genvinding af sammenfiltringer, med anvendelser på usikkerhed og monogamierelationer. Phys. Rev. A, 96: 042328, oktober 2017. 10.1103/PhysRevA.96.042328. URL https:///link.aps.org/doi/10.1103/PhysRevA.96.042328.
https:///doi.org/10.1103/PhysRevA.96.042328

[17] John Watrous. Teorien om kvanteinformation. Cambridge University Press, 2018. 10.1017/9781316848142.
https:///doi.org/10.1017/9781316848142

[18] Mark M. Wilde. Kvanteinformationsteori. Cambridge University Press, 2012. ISBN 9781139525343. 10.1017/CBO9781139525343.
https:///doi.org/10.1017/CBO9781139525343

[19] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79, pages 209–213, New York, USA, 1979. Association for Computing Machinery. ISBN 9781450374385. 10.1145/800135.804414. URL https://doi.org/10.1145/800135.804414.
https:///doi.org/10.1145/800135.804414

[20] Andrew Chi-Chih Yao. Kvantekredsløbskompleksitet. I Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, side 352–361, 1993. 10.1109/SFCS.1993.366852.
https:///doi.org/10.1109/SFCS.1993.366852

[21] Andrew Chi-Chin Yao. Probabilistiske beregninger: Mod et samlet mål for kompleksitet. I 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), side 222-227, 1977. 10.1109/SFCS.1977.24.
https:///doi.org/10.1109/SFCS.1977.24

Citeret af

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoAiStream. Web3 Data Intelligence. Viden forstærket. Adgang her.
Udmøntning af fremtiden med Adryenn Ashley. Adgang her.
Køb og sælg aktier i PRE-IPO-virksomheder med PREIPO®. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2023-05-22-1010/

Tidsstempel: Maj 22, 2023

Tidsstempel: December 7, 2022

Kohærensteoriens rolle i attraktor kvanteneurale netværk

Kildeklynge:

Quantum Journal

Kildeknude: 1659011

Tidsstempel: September 8, 2022

Genudgivet af Platon

Abstrakt

► BibTeX-data

► Referencer

Citeret af

Grænser til at tilnærme Max $k$XOR med kvante- og klassiske lokale algoritmer

Afledt prisfastsættelse ved hjælp af kvantesignalbehandling

Kvantekopibeskyttelse af compute-and-compare-programmer i den kvantetilfældige orakelmodel

Kvantificering af EPR: ressourceteorien om ikke-klassicitet af almindelige årsagssamlinger

Smedning af kvantedata: klassisk besejre en IQP-baseret kvantetest

Test af symmetri på kvantecomputere

Klassiske simuleringer af kommunikationskanaler

Prøveeffektiv verifikation af kontinuerligt parametriserede kvanteporte til små kvanteprocessorer

Quantum Liouvillian exceptionelle og djævelske punkter for bosoniske felter med kvadratiske Hamiltonianere: Heisenberg-Langevin ligningstilgangen

1000 kvantepapirer!

Optimal nonequilibrium termometri i Markovian miljøer

Kohærensteoriens rolle i attraktor kvanteneurale netværk

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto