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

Locally undetermined states: characterization and an application in distributed computing

Yuan Feng, Runyao Duan, Mingsheng Ying

Published Aug 21, 2008• 0 citations
OpenAlex

Abstract

Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit ‘high-order ’ correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computation. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable and they are not allowed to use local ancillary quantum systems, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state. 1

Related papers

Locally undetermined states, generalized Schmidt decomposition, and an application in distributed computing

Yuan Feng, Runyao Duan, Mingsheng Ying

Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit `high-order' correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, local determinability of pure states is closely related to a generalized notion of Schmidt decomposition. Furthermore, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computation. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable and they are not allowed to use local ancillary quantum systems, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state.

arXiv:0808.2938•Aug 21, 2008•0 citations

Locally undetermined states, generalized Schmidt decomposition, and application in distributed computing

Yuan Feng, Runyao Duan, Mingsheng Ying

Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit `high-order' correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, local determinability of pure states is closely related to a generalized notion of Schmidt decomposition. Furthermore, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computing. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state.

Quantum Information and Computation•Nov 1, 2009•1 citation

Undetermined states: How to find them and their applications

Min-Hsiu Hsieh, Yen, WT, Hsu, LY

We investigate the undetermined sets consisting of two-level, multi-partite pure quantum states, whose reduced density matrices give absolutely no information of their original states. Two approached of finding these quantum states are proposed. One is to establish the relation between codewords of the stabilizer quantum error correction codes (SQECCs) and the undetermined states. The other is to study the local complementation rules of the graph states. As an application, the undetermined states can be exploited in the quantum secret sharing scheme. The security is guaranteed by their undetermineness. © 2010 EDP Sciences, SIF, Springer-Verlag Berlin Heidelberg.

•Jan 1, 2011•0 citations

Quantum Distributed Consensus

Louie Helm, Christine Julien

Distributed consensus is possible for asynchronous communication networks when assisted by quantum mechanical effects. Previous results are extended to show that consensus is possible even in the presence of byzantine process failures. This result directly contradicts the FLP impossibility result which states that distributed consensus is impossible when even one faulty networked process exists in the group. PODC’08, August 18–21, 2008, p445, Toronto, Ontario, Canada. ACM 978-1-59593-9890/08/08. 1. DISTRIBUTED COMPUTING IS PHYSICAL Distributed computing is concerned with what can be accomplished using systems of networked processors. As with all information processing devices, these systems are necessarily physical and ultimately bound by the laws of physics[Land88]. Therefore, when proving impossibility results and bounds on algorithmic efficiency, it only makes sense to consider the possibilities offered, not only by classical information processing, but also the effects of quantum mechanics[NC00]. Recent results have shown that shared quantum resources make problems like anonymous leader election and distributed consensus possible under conditions where no classical algorithm could perform the same tasks[DP06]. These results are extended here to show that shared quantum resources allow fault-tolerant consensus in direct contradiction of previous impossibility results[FLP85]. Although this research is largely self-contained, a basic understanding of distributed computing is assumed of the reader along with a passing understanding of linear algebra which is necessary to understand the reasoning behind the algorithm detailed in section 4. A thorough understanding of quantum mechanics is recommended, although a reference of the specific quantum mechanical notation required to follow later reasoning in section 4 is detailed in section 3. A computer scientist unfamiliar with quantum mechanics would be well served to reference chapter 2 of [NC00] in order to gain a deeper understanding of the notation covered in section 3 of this paper. Likewise, a quantum physicist would be well served to reference chapter 15 of [Garg04] to more deeply understand the fault modeling of distributed computing covered in section 2 and section 5.

•Jan 1, 2007•0 citations

Distinguishability of Quantum States by Separable Operations

Runyao Duan, Yuan Feng, Yu Xin +1 more

In this paper, we study the distinguishability of multipartite quantum states by separable operations. We first present a necessary and sufficient condition for a finite set of orthogonal quantum states to be distinguishable by separable operations. An analytical version of this condition is derived for the case of(D-1) pure states, whereDis the total dimension of the state space under consideration. A number of interesting consequences of this result are then carefully investigated. Remarkably, we show there exists a large class of 2 otimes 2 separable operations not being realizable by local operations and classical communication. Before our work, only a class of 3 otimes 3 nonlocal separable operations was known [Bennett , Phys. Rev. A 59, 1070 (1999)]. We also show that any basis of the orthogonal complement of a multipartite pure state is indistinguishable by separable operations if and only if this state cannot be a superposition of one or two orthogonal product states, i.e., has an orthogonal Schmidt number not less than three, thus generalize the recent work about indistinguishable bipartite subspaces [Watrous, Phys. Rev. Lett. 95, 080505 (2005)]. Notably, we obtain an explicit construction of indistinguishable subspaces of dimension 7 (or 6) by considering a composite quantum system consisting of two qutrits (resp., three qubits), which is slightly better than the previously known indistinguishable bipartite subspace with dimension 8.

arXiv:0705.0795•IEEE Transactions on Information Theory•Feb 26, 2009•99 citations

Local Distinguishability of Multipartite Orthogonal Quantum States

Jonathan Walgate, Anthony J. Short, Lucién Hardy +1 more

We consider one copy of a quantum system prepared in one of two orthogonal pure states, entangled or otherwise, and distributed between any number of parties. We demonstrate that it is possible to identify which of these two states the system is in by means of local operations and classical communication alone. The protocol we outline is both completely reliable and completely general; it will correctly distinguish any two orthogonal states 100% of the time.

arXiv:quant-ph/0007098•Physical Review Letters•Dec 4, 2000•474 citations
Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit ‘high-order ’ correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computation. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable and they are not allowed to use local ancillary quantum systems, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state. 1
Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit `high-order' correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, local determinability of pure states is closely related to a generalized notion of Schmidt decomposition. Furthermore, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computation. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable and they are not allowed to use local ancillary quantum systems, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state.
Multipartite quantum states that cannot be uniquely determined by their reduced states of all proper subsets of the parties exhibit some inherit `high-order' correlation. This paper elaborates this issue by giving necessary and sufficient conditions for a pure multipartite state to be locally undetermined, and moreover, characterizing precisely all the pure states sharing the same set of reduced states with it. Interestingly, local determinability of pure states is closely related to a generalized notion of Schmidt decomposition. Furthermore, we find that locally undetermined states have some applications to the well-known consensus problem in distributed computing. To be specific, given some physically separated agents, when communication between them, either classical or quantum, is unreliable, then there exists a totally correct and completely fault-tolerant protocol for them to reach a consensus if and only if they share a priori a locally undetermined quantum state.
We investigate the undetermined sets consisting of two-level, multi-partite pure quantum states, whose reduced density matrices give absolutely no information of their original states. Two approached of finding these quantum states are proposed. One is to establish the relation between codewords of the stabilizer quantum error correction codes (SQECCs) and the undetermined states. The other is to study the local complementation rules of the graph states. As an application, the undetermined states can be exploited in the quantum secret sharing scheme. The security is guaranteed by their undetermineness. © 2010 EDP Sciences, SIF, Springer-Verlag Berlin Heidelberg.
Distributed consensus is possible for asynchronous communication networks when assisted by quantum mechanical effects. Previous results are extended to show that consensus is possible even in the presence of byzantine process failures. This result directly contradicts the FLP impossibility result which states that distributed consensus is impossible when even one faulty networked process exists in the group. PODC’08, August 18–21, 2008, p445, Toronto, Ontario, Canada. ACM 978-1-59593-9890/08/08. 1. DISTRIBUTED COMPUTING IS PHYSICAL Distributed computing is concerned with what can be accomplished using systems of networked processors. As with all information processing devices, these systems are necessarily physical and ultimately bound by the laws of physics[Land88]. Therefore, when proving impossibility results and bounds on algorithmic efficiency, it only makes sense to consider the possibilities offered, not only by classical information processing, but also the effects of quantum mechanics[NC00]. Recent results have shown that shared quantum resources make problems like anonymous leader election and distributed consensus possible under conditions where no classical algorithm could perform the same tasks[DP06]. These results are extended here to show that shared quantum resources allow fault-tolerant consensus in direct contradiction of previous impossibility results[FLP85]. Although this research is largely self-contained, a basic understanding of distributed computing is assumed of the reader along with a passing understanding of linear algebra which is necessary to understand the reasoning behind the algorithm detailed in section 4. A thorough understanding of quantum mechanics is recommended, although a reference of the specific quantum mechanical notation required to follow later reasoning in section 4 is detailed in section 3. A computer scientist unfamiliar with quantum mechanics would be well served to reference chapter 2 of [NC00] in order to gain a deeper understanding of the notation covered in section 3 of this paper. Likewise, a quantum physicist would be well served to reference chapter 15 of [Garg04] to more deeply understand the fault modeling of distributed computing covered in section 2 and section 5.
In this paper, we study the distinguishability of multipartite quantum states by separable operations. We first present a necessary and sufficient condition for a finite set of orthogonal quantum states to be distinguishable by separable operations. An analytical version of this condition is derived for the case of(D-1) pure states, whereDis the total dimension of the state space under consideration. A number of interesting consequences of this result are then carefully investigated. Remarkably, we show there exists a large class of 2 otimes 2 separable operations not being realizable by local operations and classical communication. Before our work, only a class of 3 otimes 3 nonlocal separable operations was known [Bennett , Phys. Rev. A 59, 1070 (1999)]. We also show that any basis of the orthogonal complement of a multipartite pure state is indistinguishable by separable operations if and only if this state cannot be a superposition of one or two orthogonal product states, i.e., has an orthogonal Schmidt number not less than three, thus generalize the recent work about indistinguishable bipartite subspaces [Watrous, Phys. Rev. Lett. 95, 080505 (2005)]. Notably, we obtain an explicit construction of indistinguishable subspaces of dimension 7 (or 6) by considering a composite quantum system consisting of two qutrits (resp., three qubits), which is slightly better than the previously known indistinguishable bipartite subspace with dimension 8.