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

A solution to two party typicality using representation theory of the symmetric group

Janis Nötzel

Published Sep 23, 2012• 6 citations
arXivHTMLPDF

Abstract

We give a proof of the multi-party typicality conjecture for the first nontrivial case when there are only two parties. The conjecture itself is motivated by the study of multi-party state merging protocols on quantum systems. Our approach is based on fundamental group-theoretical properties, thereby providing an opportunity to study the problem from a more systematic perspective. Our proof also covers an extended multiparty typicality conjecture that we state in this work. This extended multiparty typicality conjecture is formulated using arbitrary $k$-norms instead of only the $2$-norm as in the original conjecture.

DOI
10.48550/arxiv.1209.5094

Related papers

The Failure of Simultaneous Quantum Typicality

Benoit Collins

We establish exact thresholds for the failure of simultaneous quantum typicality: three parties for mixed states and four for pure states. For the four-qubit Higuchi--Sudbery state, every sequence satisfying the expected purity bounds on three overlapping marginals, with sufficiently small fixed positive entropy slack, is asymptotically perfectly distinguishable from the tensor powers of the input: its trace distance from them tends to the maximum value $2$. This maximal separation persists, with a common positive slack, throughout an open neighborhood in the full four-qubit state space. Tracing out one party yields a mixed tripartite example. The proof connects simultaneous quantum smoothing with polynomial concentration on $\CP^1$. Symmetry reduces the problem to a frame inequality on $\Sym^n(\mathbb C^2)$, where a linear entropy deficit competes with a quadratic cost of polynomial concentration. Bernstein--Markov estimates and a subharmonic barrier control this cost, yielding an exponential obstruction to simultaneous typicality. These results disprove Dutil's multiparty quantum typicality conjecture, formulated in 2011, and the one-shot simultaneous min-entropy-smoothing conjectures of Drescher--Fawzi and Colomer--Winter. Together with the positive results for smaller systems, they determine the smallest numbers of parties at which simultaneous typicality can fail.

quant-pharXiv:2609.25726•Sep 23, 2026•0 citations

On simultaneous min-entropy smoothing

Lukas Drescher, Omar Fawzi

In the context of network information theory, one often needs a multiparty probability distribution to be typical in several ways simultaneously. When considering quantum states instead of classical ones, it is in general difficult to prove the existence of a state that is jointly typical. Such a difficulty was recently emphasized and conjectures on the existence of such states were formulated. In this paper, we consider a one-shot multiparty typicality conjecture. The question can then be stated easily: is it possible to smooth the largest eigenvalues of all the marginals of a multipartite state ρ simultaneously while staying close to ρ? We prove the answer is yes whenever the marginals of the state commute. In the general quantum case, we prove that simultaneous smoothing is possible if the number of parties is two or more generally if the marginals to optimize satisfy some non-overlap property.

arXiv:1312.7642•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•22 citations

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•21 citations

Comment on “Quantum secret sharing between multiparty and multiparty without entanglement”

Chuan-Ming Li, Chi-Chao Chang, Tzonelih Hwang

Recently, Yan and Gao [Phys. Rev. A 72, 012304 (2005)] presented a quantum secret sharing protocol which allows a secret message to be shared between two groups of parties ($m$ parties in group 1 and $n$ parties in group 2). Their protocol is claimed to be secure that, except with the cooperation of the entire group 1 or group 2, no subgroup of either group 1 or group 2 can extract the secret message. However, this study points out that the $m\text{th}$ party (the last party to process the quantum state) of group 1 can maliciously replace the secret message with an arbitrary message without the detection of the other parties.

Physical Review A•Jan 6, 2006•35 citations

On the multiplicativity conjecture for quantum channels

Grigori Gennadievich Amosov, Alexander Semenovich Holevo

A multiplicativity conjecture for quantum communication channels is formulated, validity of which for the values of parameter $p$ close to 1 is related to the solution of the fundamental problem of additivity of the channel capacity in quantum information theory. The proof of the conjecture is given for the case of natural numbers $p$.

arXiv:math-ph/0103015•Mar 12, 2001•31 citations

Combinatorial Approaches in Quantum Information Theory

Sudhir Kumar Singh

We investigate the exploitation of various combinatorial properties of graphs and set systems to study several issues in quantum information theory. We characterize the combinatorics of distributed EPR pairs for preparing multi-partite entanglement in a real communication network. This combinatorics helps in the study of various problems in multi-party case by just reducing to the two-party case. Particularly, we use this combinatorics to (1) study various possible and impossible transformations of multi-partite states under LOCC, thus presenting an entirely new approach, not based on entropic criterion, to study such state transformations. (2) present a protocol and proof of its unconditional security for quantum key distribution amongst several trusted parties. (3) propose an idea to combine the features of quantum key distribution and quantum secret sharing. We investigate all the above issues in great detail and finally conclude briefly with some open research directions based on our research.

arXiv:quant-ph/0405089•May 16, 2004•8 citations
We give a proof of the multi-party typicality conjecture for the first nontrivial case when there are only two parties. The conjecture itself is motivated by the study of multi-party state merging protocols on quantum systems. Our approach is based on fundamental group-theoretical properties, thereby providing an opportunity to study the problem from a more systematic perspective. Our proof also covers an extended multiparty typicality conjecture that we state in this work. This extended multiparty typicality conjecture is formulated using arbitrary kkk-norms instead of only the 222-norm as in the original conjecture.
We establish exact thresholds for the failure of simultaneous quantum typicality: three parties for mixed states and four for pure states. For the four-qubit Higuchi--Sudbery state, every sequence satisfying the expected purity bounds on three overlapping marginals, with sufficiently small fixed positive entropy slack, is asymptotically perfectly distinguishable from the tensor powers of the input: its trace distance from them tends to the maximum value 222. This maximal separation persists, with a common positive slack, throughout an open neighborhood in the full four-qubit state space. Tracing out one party yields a mixed tripartite example. The proof connects simultaneous quantum smoothing with polynomial concentration on $\CP^1$. Symmetry reduces the problem to a frame inequality on $\Sym^n(\mathbb C^2)$, where a linear entropy deficit competes with a quadratic cost of polynomial concentration. Bernstein--Markov estimates and a subharmonic barrier control this cost, yielding an exponential obstruction to simultaneous typicality. These results disprove Dutil's multiparty quantum typicality conjecture, formulated in 2011, and the one-shot simultaneous min-entropy-smoothing conjectures of Drescher--Fawzi and Colomer--Winter. Together with the positive results for smaller systems, they determine the smallest numbers of parties at which simultaneous typicality can fail.
In the context of network information theory, one often needs a multiparty probability distribution to be typical in several ways simultaneously. When considering quantum states instead of classical ones, it is in general difficult to prove the existence of a state that is jointly typical. Such a difficulty was recently emphasized and conjectures on the existence of such states were formulated. In this paper, we consider a one-shot multiparty typicality conjecture. The question can then be stated easily: is it possible to smooth the largest eigenvalues of all the marginals of a multipartite state ρ simultaneously while staying close to ρ? We prove the answer is yes whenever the marginals of the state commute. In the general quantum case, we prove that simultaneous smoothing is possible if the number of parties is two or more generally if the marginals to optimize satisfy some non-overlap property.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
Recently, Yan and Gao [Phys. Rev. A 72, 012304 (2005)] presented a quantum secret sharing protocol which allows a secret message to be shared between two groups of parties (mmm parties in group 1 and nnn parties in group 2). Their protocol is claimed to be secure that, except with the cooperation of the entire group 1 or group 2, no subgroup of either group 1 or group 2 can extract the secret message. However, this study points out that the mthm\text{th}mth party (the last party to process the quantum state) of group 1 can maliciously replace the secret message with an arbitrary message without the detection of the other parties.
A multiplicativity conjecture for quantum communication channels is formulated, validity of which for the values of parameter ppp close to 1 is related to the solution of the fundamental problem of additivity of the channel capacity in quantum information theory. The proof of the conjecture is given for the case of natural numbers ppp.
We investigate the exploitation of various combinatorial properties of graphs and set systems to study several issues in quantum information theory. We characterize the combinatorics of distributed EPR pairs for preparing multi-partite entanglement in a real communication network. This combinatorics helps in the study of various problems in multi-party case by just reducing to the two-party case. Particularly, we use this combinatorics to (1) study various possible and impossible transformations of multi-partite states under LOCC, thus presenting an entirely new approach, not based on entropic criterion, to study such state transformations. (2) present a protocol and proof of its unconditional security for quantum key distribution amongst several trusted parties. (3) propose an idea to combine the features of quantum key distribution and quantum secret sharing. We investigate all the above issues in great detail and finally conclude briefly with some open research directions based on our research.