How far quantum entanglement can substitute to communication?

How far quantum entanglement can substitute to communication? Ask Question Asked 5 days ago Modified 5 days ago Viewed 205 times 2 I ran into this medium post Beyond Messages: How Quantum Entanglement Could Revolutionize AI Agent Coordination which has an attracting subtitle : "What if AI agents could coordinate without ever sending a message?". The post does not bring any further references, I wonder how far this can be true. What I am aware of is that quantum Entanglement can reduce communications in some cases. Here is an example taken from Josep Gruzka's book on Quantum Computing, especially the section entitled "[Entanglement] Substituting To Multipartite Communication". Assume we have P 1 ,…, P k 𝑃 1 , … , 𝑃 𝑘 parties. Each party P j 𝑃 𝑗 holds a string x j 𝑥 𝑗 and all parties want to compute a function f 𝑓 of all strings : f( x 1 ,…, x k ) 𝑓 ( 𝑥 1 , … , 𝑥 𝑘 ) We assume that x j 𝑥 𝑗 are bitstrings encoded on n 𝑛 bits, then : x j ∈{0,1 } n or x j ∈{0,…, 2 n −1} 𝑥 𝑗 ∈ { 0 , 1 } 𝑛 or 𝑥 𝑗 ∈ { 0 , … , 2 𝑛 − 1 } The simplest function f 𝑓 to be considered is for example the sum : f( x 1 ,…, x k )= ∑ j=1 k x j 𝑓 ( 𝑥 1 , … , 𝑥 𝑘 ) = ∑ 𝑗 = 1 𝑘 𝑥 𝑗 and the goal of parties is to compute the sum and broadcast it between them with as few possible messages as possible. Here are the following steps with entanglement : Share a Cat State : |ψ⟩= 1 2 – √ [| 0 k ⟩+| 1 k ⟩] | 𝜓 ⟩ = 1 2 [ | 0 𝑘 ⟩ + | 1 𝑘 ⟩ ] encoded on k 𝑘 qubits and each party P j 𝑃 𝑗 is given one of the qubits. Each party P j 𝑃 𝑗 achieves a Phase operation : [I⊗⋯⊗ U j ⊗⋯⊗I]|ψ⟩= 1 2 – √ [| 0 k ⟩+ e 2πi x j 2 n | 1 k ⟩] [ 𝐼 ⊗ ⋯ ⊗ 𝑈 𝑗 ⊗ ⋯ ⊗ 𝐼 ] | 𝜓 ⟩ = 1 2 [ | 0 𝑘 ⟩ + 𝑒 2 𝜋 𝑖 𝑥 𝑗 2 𝑛 | 1 𝑘 ⟩ ] with a phase gate : U j =[ 1 0 0 e 2πi x j 2 n ] 𝑈 𝑗 = [ 1 0 0 𝑒 2 𝜋 𝑖 𝑥 𝑗 2 𝑛 ] It finally ends up with : | ψ ′ ⟩=[ U 1 ⊗⋯⊗ U j ⊗⋯⊗ U k ]|ψ⟩= = 1 2 – √ [| 0 k ⟩+exp( 2πi 2 n ∑ j=1 k x j )| 1 k ⟩] 1 2 – √ [| 0 k ⟩+ e 2πikθ | 1 k ⟩] | 𝜓 ′ ⟩ = [ 𝑈 1 ⊗ ⋯ ⊗ 𝑈 𝑗 ⊗ ⋯ ⊗ 𝑈 𝑘 ] | 𝜓 ⟩ = 1 2 [ | 0 𝑘 ⟩ + exp ⁡ ( 2 𝜋 𝑖 2 𝑛 ∑ 𝑗 = 1 𝑘 𝑥 𝑗 ) | 1 𝑘 ⟩ ] = 1 2 [ | 0 𝑘 ⟩ + 𝑒 2 𝜋 𝑖 𝑘 𝜃 | 1 𝑘 ⟩ ] with θ= 1 k ∑ j=1 k θ j , θ j = x j 2 n ∈[0,1] 𝜃 = 1 𝑘 ∑ 𝑗 = 1 𝑘 𝜃 𝑗 , 𝜃 𝑗 = 𝑥 𝑗 2 𝑛 ∈ [ 0 , 1 ] and from previous notations we have : f( x 1 ,…, x k )=kθ 𝑓 ( 𝑥 1 , … , 𝑥 𝑘 ) = 𝑘 𝜃 Each party performs an Hadamard Gate on its qubit, this results in a "wall" of Hadamard : | ψ ′′ ⟩= H ⊗k | ψ ′ ⟩= 1 2 – √ [ H ⊗k | 0 k ⟩+ e 2πikθ H ⊗k | 1 k ⟩] | 𝜓 ′ ′ ⟩ = 𝐻 ⊗ 𝑘 | 𝜓 ′ ⟩ = 1 2 [ 𝐻 ⊗ 𝑘 | 0 𝑘 ⟩ + 𝑒 2 𝜋 𝑖 𝑘 𝜃 𝐻 ⊗ 𝑘 | 1 𝑘 ⟩ ] which can be further developed into | ψ ′′ ⟩ = 1 2 k+1 − − − − √ ∑ x=0 2 k −1 (1+ e πi(2kθ+ ⊕ k−1 j=0 y j ) )|y⟩ =[ 1+ e 2πikθ 2 ( 1 2 k−1 − − − − √ ∑ y∈{0,1 } k / ⊕ j y j =0 |y⟩) + 1− e 2πikθ 2 ( 1 2 k−1 − − − − √ ∑ y∈{0,1 } k / ⊕ j y j =1 |y⟩)] | 𝜓 ′ ′ ⟩ = 1 2 𝑘 + 1 ∑ 𝑥 = 0 2 𝑘 − 1 ( 1 + 𝑒 𝜋 𝑖 ( 2 𝑘 𝜃 + ⊕ 𝑗 = 0 𝑘 − 1 𝑦 𝑗 ) ) | 𝑦 ⟩ = [ 1 + 𝑒 2 𝜋 𝑖 𝑘 𝜃 2 ( 1 2 𝑘 − 1 ∑ 𝑦 ∈ { 0 , 1 } 𝑘 / ⊕ 𝑗 𝑦 𝑗 = 0 | 𝑦 ⟩ ) + 1 − 𝑒 2 𝜋 𝑖 𝑘 𝜃 2 ( 1 2 𝑘 − 1 ∑ 𝑦 ∈ { 0 , 1 } 𝑘 / ⊕ 𝑗 𝑦 𝑗 = 1 | 𝑦 ⟩ ) ] and given that quantum states are defined up to a Global Phase : | ψ ′′ ⟩=cos(πkθ)( 1 2 k−1 − − − − √ ∑ y∈{0,1 } k / ⊕ j y j =0 |y⟩)−isin (πkθ)( 1 2 k−1 − − − − √ ∑ y∈{0,1 } k / ⊕ j y j =1 |y⟩)] | 𝜓 ′ ′ ⟩ = cos ⁡ ( 𝜋 𝑘 𝜃 ) ( 1 2 𝑘 − 1 ∑ 𝑦 ∈ { 0 , 1 } 𝑘 / ⊕ 𝑗 𝑦 𝑗 = 0 | 𝑦 ⟩ ) − 𝑖 sin ⁡ ( 𝜋 𝑘 𝜃 ) ( 1 2 𝑘 − 1 ∑ 𝑦 ∈ { 0 , 1 } 𝑘 / ⊕ 𝑗 𝑦 𝑗 = 1 | 𝑦 ⟩ ) ] party P j 𝑃 𝑗 performs a standard basis {|0⟩,|1⟩} { | 0 ⟩ , | 1 ⟩ } measurement and gets an outcome b j ∈{0,1} 𝑏 𝑗 ∈ { 0 , 1 } . More relevant are the probabilities for events ⊕ j y j =0 ⊕ 𝑗 𝑦 𝑗 = 0 and ⊕ j y j =1 ⊕ 𝑗 𝑦 𝑗 = 1 : Pr[ ⊕ j y j =0]= cos 2 (πkθ),Pr[ ⊕ j y j =1]= sin 2 (πkθ) Pr [ ⊕ 𝑗 𝑦 𝑗 = 0 ] = cos 2 ⁡ ( 𝜋 𝑘 𝜃 ) , Pr [ ⊕ 𝑗 𝑦 𝑗 = 1 ] = sin 2 ⁡ ( 𝜋 𝑘 𝜃 ) These steps could also have been taken from the distributed sensing litterature as the problem is nearly the same, except that the data ( x j 𝑥 𝑗 ) encoded on a qubit may come from a quantum sensor. But no party can retrieve the value of kθ 𝑘 𝜃 directly from outcomes { b j } { 𝑏 𝑗 } unless kθ 𝑘 𝜃 is bound to some specific values : cos 2 (πkθ)=1⇒πkθ=0modπ⇒kθ=0mod1 cos 2 ⁡ ( 𝜋 𝑘 𝜃 ) = 1 ⇒ 𝜋 𝑘 𝜃 = 0 mod 𝜋 ⇒ 𝑘 𝜃 = 0 mod 1 or sin 2 (πkθ)=1⇒πkθ= π 2 modπ⇒kθ= 1 2 mod1 sin 2 ⁡ ( 𝜋 𝑘 𝜃 ) = 1 ⇒ 𝜋 𝑘 𝜃 = 𝜋 2 mod 𝜋 ⇒ 𝑘 𝜃 = 1 2 mod 1 so that if parties broadcast their respective outcomes to other parties, they can directly distinguish whether f( x 1 ,…, x k )=kθ 𝑓 ( 𝑥 1 , … , 𝑥 𝑘 ) = 𝑘 𝜃 is either an Integer of a Half-Integer. The article : Buhrman, Harry and van Dam, Wim and Høyer, Peter and Tapp, Alain (1999) Multiparty quantum communication complexity, Physical Review A. demonstrates with this framework that quantum entanglement reduces communication complexity compared to classical case and also quantum not entangled case, in order to compute function f 𝑓 out of outcomes, but for a restricted case of function f 𝑓 . Do you think that this framework could be extended to allow coordination without ever sending a message ? as claimed by the medium post. entanglementcommunication-complexity Share Improve this question Follow edited May 28 at 9:31 asked May 28 at 9:23 deb2014 6773 3 silver badges 8 8 bronze badges Add a comment 1 Answer Sorted by: Highest score (default) Date modified (newest first) Date created (oldest first) 2 Entanglement can reduce communication in some distributed tasks, but it cannot replace communication in the sense suggested by the Medium article.The distinction is between coordination and communication. If several parties share entanglement in advance, then after receiving local inputs they can perform local measurements and obtain outcomes with correlations that are impossible classically. This is the setting of Bell/CHSH games and quantum communication complexity. In that limited sense, entanglement can help parties “coordinate without messages” during the execution of the protocol. But entanglement does not allow one party to transmit new information to another. This is the no-signalling theorem. If party (A) chooses a measurement or operation depending on its local input (x_A), party (B)’s local outcome distribution is unchanged. Only the joint distribution of all outcomes contains the nonclassical correlation. To access that joint information, the parties must later compare outcomes, which is classical communication. Your GHZ/cat-state example illustrates exactly this point. The phase exp(2πi ∑ j x j 2 n ) exp ⁡ ( 2 𝜋 𝑖 ∑ 𝑗 𝑥 𝑗 2 𝑛 ) is encoded globally. After Hadamards and measurements, each party obtains a local bit (b_j). But no single party can read ( ∑ j x j ) ( ∑ 𝑗 𝑥 𝑗 ) from its own bit. The useful information is in the parity ⨁ j b j , ⨁ 𝑗 𝑏 𝑗 , and computing that parity requires the parties to communicate their outcomes, or to send them to some referee. So entanglement can sometimes reduce the number of communicated bits, or increase the success probability of a no-communication nonlocal game. It cannot make arbitrary distributed computation or belief synchronization message-free. Therefore the Medium claim is true only in the sense: pre-shared entanglement + local measurements = nonclassical correlated actions It is false in the stronger sense: one agent observes new information = another agent learns it without communication The latter would violate no-signalling. For AI-agent coordination, entanglement could at most act as a special pre-shared correlation resource for restricted tasks. It cannot replace message passing,or communication Share Improve this answer Follow edited May 28 at 17:26 answered May 28 at 17:02 Bram 1,6799 9 silver badges 10 10 bronze badges Yes, I was indeed aware of the barrier that the no-signalling theorem puts to the medium post. The CHSH game shows that with entanglement two parties can correlate their inputs beyond classical strategies. It is even shown that the probability reached by entanglement for the CHSH game is the highest ever possible ( ≈0.85 ≈ 0.85 - Tsirelson bound). I wonder if there are some similar results in terms of communication complexity, i.e. a lower bound for the ability of entanglement to reduce communication complexity (?) –  deb2014 Commented May 29 at 7:07 Add a comment Your Answer Sign up or log in Sign up using Google Sign up using Email and Password Post as a guest Name Email Required, but never shown Post Your Answer By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy. Start asking to get answers Find the answer to your question by asking. Ask question Explore related questions entanglementcommunication-complexity See similar questions with these tags. The Overflow Blog Best of the Heap: First post of the... What it takes to be a player in the international AI... Featured on Meta Native Ads Coming To Comments Related 2 How to prove the following bosonic entanglement expression? 2 In the CHSH inequality, how can I know which term is supposed to have the minus sign? 1 Understanding quantum computing power of entanglement 1 Entangled qubit systems always maximally entangled? 1 Dimension of tensored spaces and power of entanglement 0 Calculation of CKW inequality for Bell states 1 Quantum Teleportation and Quantum Internet Hot Network Questions How to change return column name for SHOW DATABASES? How do temporary HP work with Animal Shapes in 5.5e? Is metaphysical solipsism a coherent position? An intuitive explanation of formula about the distance of a point to a plane in 3D If a piece of writing is done well with the use of AI, does it automatically get rejected if it is established AI was used? How to get the meta information of a tex file into the pdf meta information? What is the ontology of truth? Why is only the Sergeant issued a pistol, in addition to his rifle? Why, how, and how often to grease a bicycle chain? Does it make sense to respond "two diamonds" to Stayman bids with some four card major holdings? Journalctl disk-usage vs Actual disk usage is wildly wrong How can I increase throughput between two instances connected with 1 Gbit/s Ethernet adapter each? Fourier series of primary current of a transfomer and HF of input current Tag questions with main clauses or subordinate clauses? Source for quoted Vilna Gaon on the difference between זימרה and שירה? Interpretation of subjects lost to follow-up in a trial as missing data? Was Nietzsche the first psychologist? Why do all brushes seem to only project onto the model and not actually use projection in depth? There exists elementary topos E whose Sub(1) is not complete? My new senior colleague self-invited himself to work on my research problem Is continuity in general just an illusion or does it exist and we're just aware of it? Failed to Lchown: for UID 304185, GID 89939 (Hint: try increasing the number of subordinate IDs in /etc/subuid and /etc/subgid) Are DC-DC buck converters usually less noisy at the output than boost converters? Resources or Platforms for Questions on Daf Yomi Question feed By continuing to use this website, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. By exiting this window, default cookies will be accepted. To reject cookies, select an option from below. Customize settings Cookie consent preference center When you visit any of our websites, it may store or retrieve information on your browser, mostly in the form of cookies. This information might be about you, your preferences, or your device and is mostly used to make the site work as you expect it to. The information does not usually directly identify you, but it can give you a more personalized experience. Because we respect your right to privacy, you can choose not to allow some types of cookies. Click on the different category headings to find out more and manage your preferences. Please note, blocking some types of cookies may impact your experience of the site and the services we are able to offer. Cookie policy Accept all cookies Manage consent preferences Strictly Necessary Cookies Always Active These cookies are necessary for the website to function and cannot be switched off in our systems. They are usually only set in response to actions made by you which amount to a request for services, such as setting your privacy preferences, logging in or filling in forms. You can set your browser to block or alert you about these cookies, but some parts of the site will not then work. These cookies do not store any personally identifiable information. Targeting Cookies Targeting Cookies These cookies are used to make advertising messages more relevant to you and may be set through our site by us or by our advertising partners. They may be used to build a profile of your interests and show you relevant advertising on our site or on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. Performance Cookies Performance Cookies These cookies allow us to count visits and traffic sources so we can measure and improve the performance of our site. They help us to know which pages are the most and least popular and see how visitors move around the site. All information these cookies collect is aggregated and therefore anonymous. If you do not allow these cookies we will not know when you have visited our site, and will not be able to monitor its performance. Functional Cookies Functional Cookies These cookies enable the website to provide enhanced functionality and personalisation. They may be set by us or by third party providers whose services we have added to our pages. If you do not allow these cookies then some or all of these services may not function properly. Cookie List Clear checkbox label label Apply Cancel Consent Leg.Interest checkbox label label checkbox label label checkbox label label Necessary cookies only Confirm my choices