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:2609.32024

Robust Entanglement Witnessing via Dense Network Coding with Graph States

Brian Doolittle, Ian George

quant-phSubmitted Sep 25, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

Practical tests for witnessing entanglement in the presence of noise are needed to verify and apply entanglement-based applications in real-world communication networks. Quantum dense network coding is a communication protocol that uses an entangled state preparation together with quantum communication to halve the amount of communication needed to evaluate certain bijective functions in networks having multiple senders and one receiver. In this work, we consider a dense network coding protocol that uses graph state entanglement to implement a family of affine transformations, we derive a bound on the success probability that can be achieved by classical networks, and we show that the noise robustness exponentially amplifies with the number of senders. We apply our results in a semi-device-independent protocol for robustly estimating the effective visibility of graph states and measurement bases. Overall, our approaches are robust to noise, can support the usage of uncharacterized state preparations or measurements, and can be applied to any graph state.

AI Summary

The paper studies whether graph-state-assisted distributed computation can certify entanglement under communication-dimension constraints, including with uncharacterized preparations or measurements. It considers $n$ senders, each receiving $(x_i,y_i)\in\mathbb Z_d^2$, and one receiver tasked with computing $g^{A}(x,y)=y-Ax\pmod d$ for a weighted graph adjacency matrix $A$. A shared graph state, local Weyl encodings, transmission of one qudit per sender, and a joint graph-basis measurement compute this function perfectly. For graphs without isolated vertices, zero-error classical computation requires $2n$ dits, versus $n$ transmitted qudits. The central claimed bound is $P_S\le d^{-m}$ for $m$ the maximum induced-matching size, covering classical communication even with nonsignaling assistance and quantum communication without sender entanglement. Its derivation combines conditional-bijectivity bounds for individual edges with a claimed multiplicative decomposition over induced-matching edges. Explicit classical encodings establish tightness for several graph families. Under global depolarizing noise, success is $v+(1-v)d^{-n}$, giving the sufficient visibility threshold $v>(d^{n-m}-1)/(d^n-1)$. This decreases exponentially when $m=\Theta(n)$, but approaches $1/d$ for GHZ and uniformly weighted complete graphs. The score also defines an effective visibility; with ideal graph-basis measurements it equals graph-state fidelity after rescaling. Certification assumes the network topology and communication dimensions, excluding hidden side channels and sender–receiver entanglement. Communication advantage does not generally certify genuine multipartite entanglement. Interpreting effective visibility as preparation or measurement visibility uses a depolarizing model. Joint entangled measurements, synchronization, loss handling, and error correction remain implementation challenges.

Little sign of AI-generated textIncrementalOverclaimsStrong assumptionsPossible error

Error found: Exponential improvement with sender number is established for graph families whose maximum induced matching grows linearly, whereas GHZ and uniformly weighted complete graphs have thresholds tending to 1/d. The demonstrated exponential noise tolerance concerns global depolarization and does not establish comparable scaling under independent local noise or loss. The appendix's guessing-probability factorization is not justified by output independence alone, although grouping matching endpoints and applying conditional bijectivity directly repairs the MIM bound. The visibility-calibration discussion incorrectly treats division by a lower bound on measurement visibility as an improved lower bound on preparation visibility; within its noise model, it instead gives an upper bound.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages, 5 figures, 3 tables

Related papers

Communication Advantages from Quantum Dense Network Coding

Ian George, Brian Doolittle

A central problem in quantum information theory is understanding how quantum resources can be used to communicate information more efficiently than classical resources. We introduce quantum dense network coding -- a protocol that transmits the output of a non-Boolean function to a receiver using provably half as many qubits as bits for each sender by not transmitting the entirety of the function inputs. We show this advantage requires both shared entanglement and quantum communication, is robust to noise, and the gap in success probability between quantum and classical communication can be amplified exponentially in the number of senders. Finally, we show that dense network coding gives rise to a novel, information-theoretically secure, quantum cryptographic protocol, which we call measurement-device-independent quantum key growing.

quant-pharXiv:2607.08133•Jul 10, 2026•1 citation

Verification of blind quantum computation with entanglement witnesses

Qingshan Xu, Xiaoqing Tan, Rui Huang +1 more

Verifiable blind quantum computation provides a cloud scenario for scalable quantum information processing. However, constructing one resource-efficient verification protocol is still an open problem. In this paper, the context of verification we consider is the measurement-based model, in which the client receives the graph state prepared by the server and performs single-qubit measurements on it to drive the computation. We first utilize three entanglement witnesses to estimate the fidelity of the prepared graph state. Applying entanglement witnesses to design the test phase, we propose verification protocols. Our protocol requires overhead in terms of copies of the graph state that scales as $O({n}^{2}logn)$, where $n$ is the number of qubits of the graph state. Furthermore, the soundness of our protocol is improved. The advantages of our protocol are derived from the fact that each entanglement witness can be implemented by the client with a fixed number of measurement settings.

Physical Review A•Oct 12, 2021•20 citations

Measurement-device-independent entanglement and randomness estimation in quantum networks

Ivan Šupić, Paul Skrzypczyk, Daniel Cavalcanti

Detection of entanglement in quantum networks consisting of many parties is one of the important steps toward building quantum communication and computation networks. We consider a scenario where the measurement devices used for this certification are uncharacterized. In this case, it is well known that by using quantum states as inputs for the measurement devices it is possible to detect any entangled state (a situation known as measurement-device-independent entanglement witnessing). Here we go beyond entanglement detection and provide methods to estimate the amount of entanglement in a quantum network. We also consider the task of randomness certification and show that randomness can be certified in a variety of cases, including single-partite experiments or setups using only separable states.

arXiv:1702.04752•Physical Review A•Apr 26, 2017•45 citations

Deterministic Quantum Dense Coding Based on Non-Maximal Entangled Channel

Xuanxuan Xin, Zhixing Li, Zhen Wang

In quantum communication, the concept of dense coding traditionally relies on maximally entangled states as quantum channels. Recent advancements have expanded this framework to include non-maximally entangled states within the probabilistic dense coding paradigm. However, such schemes introduce a significant limitation: the receiver cannot always retrieve the complete dense coding information sent by the sender. Consequently, the receiver must inform the sender of the amount of information successfully received. Based on this feedback, the sender determines whether retransmission is necessary, leading to inefficient use of the quantum channel and reduced communication efficiency. To address these shortcomings, we propose an alternative deterministic quantum dense coding scheme that utilizes non-maximally entangled states as the quantum channel. This deterministic approach eliminates the need for retransmissions and significantly enhances communication efficiency while maintaining compatibility with non-maximally entangled states. Our scheme represents a substantial improvement over existing probabilistic methods and paves the way for more efficient quantum communication protocols.

Entropy•Jan 22, 2025•1 citation

Entanglement detection under coherent noise: Greenberger-Horne-Zeilinger-like states

You Zhou

Entanglement is an essential resource in many quantum information tasks and the entanglement witness is a widely used tool for its detection. In experiments the prepared state generally deviates from the target state due to some noise. Normally the white-noise model is applied to quantifying such a derivation and at the same time reveals the robustness of the witness. However, there may exist other kinds of noise, in which the coherent noise can dramatically ``rotate'' the prepared state. In this way, coherent noise is likely to lead to a failure of detection, even though the underlying state is actually entangled. In this work, we propose an efficient entanglement detection protocol for $N$-partite Greenberger-Horne-Zeilinger (GHZ)--like states. The protocol can eliminate the effect of coherent noise and at the same time feedback the corresponding noise parameters, which are beneficial to further improvements of the experiment system. In particular, we consider two experiment-relevant coherent noise models; one is from the unconscious phase accumulation on $N$ qubits, and the other is from the rotation on the control qubit. The protocol effectively realizes a family of entanglement witnesses by postprocessing the measurement results from $N+2$ local measurement settings, which adds only one more setting than the original witness specialized for the GHZ state. Moreover, by considering the trade-off between the detection efficiency and the white-noise robustness, we further reduce the number of local measurements to three without altering the performance under the coherent noise. Our protocol can enhance entanglement detection under coherent noises and act as a benchmark for state-of-the-art quantum devices.

arXiv:1907.11495•Physical Review A•Jan 2, 2020•18 citations

Optimal dense coding with arbitrary pure entangled states

Yuan Feng, Runyao Duan, Zhengfeng Ji

We examine dense coding with an arbitrary pure entangled state sharing between the sender and the receiver. Upper bounds on the average success probability in approximate dense coding and on the probability of conclusive results in unambiguous dense coding are derived. We also construct the optimal protocol which saturates the upper bound in each case.

arXiv:quant-ph/0604149•Physical Review A•Jul 13, 2006•18 citations
Practical tests for witnessing entanglement in the presence of noise are needed to verify and apply entanglement-based applications in real-world communication networks. Quantum dense network coding is a communication protocol that uses an entangled state preparation together with quantum communication to halve the amount of communication needed to evaluate certain bijective functions in networks having multiple senders and one receiver. In this work, we consider a dense network coding protocol that uses graph state entanglement to implement a family of affine transformations, we derive a bound on the success probability that can be achieved by classical networks, and we show that the noise robustness exponentially amplifies with the number of senders. We apply our results in a semi-device-independent protocol for robustly estimating the effective visibility of graph states and measurement bases. Overall, our approaches are robust to noise, can support the usage of uncharacterized state preparations or measurements, and can be applied to any graph state.
The paper studies whether graph-state-assisted distributed computation can certify entanglement under communication-dimension constraints, including with uncharacterized preparations or measurements. It considers nnn senders, each receiving (xi,yi)∈Zd2(x_i,y_i)\in\mathbb Z_d^2(xi​,yi​)∈Zd2​, and one receiver tasked with computing gA(x,y)=y−Ax(modd)g^{A}(x,y)=y-Ax\pmod dgA(x,y)=y−Ax(modd) for a weighted graph adjacency matrix AAA.
A shared graph state, local Weyl encodings, transmission of one qudit per sender, and a joint graph-basis measurement compute this function perfectly. For graphs without isolated vertices, zero-error classical computation requires 2n2n2n dits, versus nnn transmitted qudits. The central claimed bound is PS≤d−mP_S\le d^{-m}PS​≤d−m for mmm the maximum induced-matching size, covering classical communication even with nonsignaling assistance and quantum communication without sender entanglement. Its derivation combines conditional-bijectivity bounds for individual edges with a claimed multiplicative decomposition over induced-matching edges. Explicit classical encodings establish tightness for several graph families.
Under global depolarizing noise, success is v+(1−v)d−nv+(1-v)d^{-n}v+(1−v)d−n, giving the sufficient visibility threshold v>(dn−m−1)/(dn−1)v>(d^{n-m}-1)/(d^n-1)v>(dn−m−1)/(dn−1). This decreases exponentially when m=Θ(n)m=\Theta(n)m=Θ(n), but approaches 1/d1/d1/d for GHZ and uniformly weighted complete graphs. The score also defines an effective visibility; with ideal graph-basis measurements it equals graph-state fidelity after rescaling.
Certification assumes the network topology and communication dimensions, excluding hidden side channels and sender–receiver entanglement. Communication advantage does not generally certify genuine multipartite entanglement. Interpreting effective visibility as preparation or measurement visibility uses a depolarizing model. Joint entangled measurements, synchronization, loss handling, and error correction remain implementation challenges.
A central problem in quantum information theory is understanding how quantum resources can be used to communicate information more efficiently than classical resources. We introduce quantum dense network coding -- a protocol that transmits the output of a non-Boolean function to a receiver using provably half as many qubits as bits for each sender by not transmitting the entirety of the function inputs. We show this advantage requires both shared entanglement and quantum communication, is robust to noise, and the gap in success probability between quantum and classical communication can be amplified exponentially in the number of senders. Finally, we show that dense network coding gives rise to a novel, information-theoretically secure, quantum cryptographic protocol, which we call measurement-device-independent quantum key growing.
Verifiable blind quantum computation provides a cloud scenario for scalable quantum information processing. However, constructing one resource-efficient verification protocol is still an open problem. In this paper, the context of verification we consider is the measurement-based model, in which the client receives the graph state prepared by the server and performs single-qubit measurements on it to drive the computation. We first utilize three entanglement witnesses to estimate the fidelity of the prepared graph state. Applying entanglement witnesses to design the test phase, we propose verification protocols. Our protocol requires overhead in terms of copies of the graph state that scales as O(n2logn)O({n}^{2}logn)O(n2logn), where nnn is the number of qubits of the graph state. Furthermore, the soundness of our protocol is improved. The advantages of our protocol are derived from the fact that each entanglement witness can be implemented by the client with a fixed number of measurement settings.
Detection of entanglement in quantum networks consisting of many parties is one of the important steps toward building quantum communication and computation networks. We consider a scenario where the measurement devices used for this certification are uncharacterized. In this case, it is well known that by using quantum states as inputs for the measurement devices it is possible to detect any entangled state (a situation known as measurement-device-independent entanglement witnessing). Here we go beyond entanglement detection and provide methods to estimate the amount of entanglement in a quantum network. We also consider the task of randomness certification and show that randomness can be certified in a variety of cases, including single-partite experiments or setups using only separable states.
In quantum communication, the concept of dense coding traditionally relies on maximally entangled states as quantum channels. Recent advancements have expanded this framework to include non-maximally entangled states within the probabilistic dense coding paradigm. However, such schemes introduce a significant limitation: the receiver cannot always retrieve the complete dense coding information sent by the sender. Consequently, the receiver must inform the sender of the amount of information successfully received. Based on this feedback, the sender determines whether retransmission is necessary, leading to inefficient use of the quantum channel and reduced communication efficiency. To address these shortcomings, we propose an alternative deterministic quantum dense coding scheme that utilizes non-maximally entangled states as the quantum channel. This deterministic approach eliminates the need for retransmissions and significantly enhances communication efficiency while maintaining compatibility with non-maximally entangled states. Our scheme represents a substantial improvement over existing probabilistic methods and paves the way for more efficient quantum communication protocols.
Entanglement is an essential resource in many quantum information tasks and the entanglement witness is a widely used tool for its detection. In experiments the prepared state generally deviates from the target state due to some noise. Normally the white-noise model is applied to quantifying such a derivation and at the same time reveals the robustness of the witness. However, there may exist other kinds of noise, in which the coherent noise can dramatically ``rotate'' the prepared state. In this way, coherent noise is likely to lead to a failure of detection, even though the underlying state is actually entangled. In this work, we propose an efficient entanglement detection protocol for NNN-partite Greenberger-Horne-Zeilinger (GHZ)--like states. The protocol can eliminate the effect of coherent noise and at the same time feedback the corresponding noise parameters, which are beneficial to further improvements of the experiment system. In particular, we consider two experiment-relevant coherent noise models; one is from the unconscious phase accumulation on NNN qubits, and the other is from the rotation on the control qubit. The protocol effectively realizes a family of entanglement witnesses by postprocessing the measurement results from N+2N+2N+2 local measurement settings, which adds only one more setting than the original witness specialized for the GHZ state. Moreover, by considering the trade-off between the detection efficiency and the white-noise robustness, we further reduce the number of local measurements to three without altering the performance under the coherent noise. Our protocol can enhance entanglement detection under coherent noises and act as a benchmark for state-of-the-art quantum devices.