Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #𝖯. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients. Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. This includes the result that plethysm coefficients are in #BQP, which was only known in certain cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, thus unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform; recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures the approaches of our and previous work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.

Tensors play a central role in various areas of computer science and mathematics, such as algebraic complexity theory (matrix multiplication), quantum information theory (entanglement), and additive combinatorics (slice rank). Fundamental problems about tensors are strongly tied to well-known questions in computational complexity - such as the problem of determining the matrix multiplication exponent via asymptotic rank, and the stronger Strassen asymptotic rank conjecture, which has recently been intimately linked to a whole range of computational problems. Unlike matrices, which are often well understood through their rank, tensors have such intricate structure that understanding them (and aforementioned problems) requires information of a more subtle nature. The moment polytope, going back decades to work in symplectic geometry, invariant theory, and representation theory, is a mathematical object associated to any tensor that collects such "rank-like"information. Their relevance has become apparent in several areas: (1) through applications in geometric complexity theory (GCT), (2) in the construction of functions in Strassen's asymptotic spectrum of tensors, (3) as entanglement polytopes in quantum information theory, and (4) in optimization via scaling algorithms. Despite their fundamental role and interest from many angles, little is known about these polytopes, and in particular for tensors beyondC2λ-λ.,⊗2λ-λ.,⊗2 andC2λ-λ.,⊗2λ-λ.,⊗2λ-λ.,⊗2 only sporadically have they been computed. Even less is known about the polytopes' inclusions and separations (which are particularly relevant for applications). We give a new algorithm for computing moment polytopes of tensors (and in fact moment polytopes for a natural general class of reductive algebraic groups) based on a mathematical characterization of moment polytopes by Franz. This algorithm enables us to compute moment polytopes of tensors of dimension an order of magnitude larger than previous methods, allowing us to compute with certainty, for the first time, all moment polytopes of tensors inC3λ-λ.,⊗3λ-λ.,⊗3, and with high probability those inC4λ-λ.,⊗4λ-λ.,⊗4. Towards an open problem in geometric complexity theory, we prove (guided by moment polytopes computed with our algorithm) separations between the moment polytopes of matrix multiplication tensors and unit tensors, showing in particular that the matrix multiplication moment polytopes are not maximal (i.e., not equal to the corresponding Kronecker polytopes). As a consequence of the above, we obtain a no-go result for a certain operational characterization of moment polytope inclusion, by proving that Strassen's asymptotic restriction on tensors does not imply moment polytope inclusion. Finally, based on our algorithmic observations, we construct explicit (concise) non-free tensors in every formatCn λ-Cn λ-Cn, thus solving a "hay in a haystack"problem for this generic property that plays an important role in Strassen's theory of asymptotic spectra.

Asymptotic tensor rank, originally developed to characterize the complexity of matrix multiplication, is a parameter that plays a fundamental role in problems in mathematics, computer science and quantum information. This parameter is notoriously difficult to determine; indeed, determining its value for the 2× 2 matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem. Strassen's asymptotic rank conjecture, on the other hand, makes the bold statement that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Recent works have proved strong consequences of Strassen's asymptotic rank conjecture in computational complexity theory. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank; for instance whether it is computable. We prove that asymptotic tensor rank is "computable from above", that is, for any real number r there is an (efficient) algorithm that determines, given a tensor T, if the asymptotic tensor rank of T is at most r. The algorithm has a simple structure; it consists of evaluating a finite list of polynomials on the tensor. Indeed, we prove that the sublevel sets of asymptotic rank are Zariski-closed (just like matrix rank). While we do not exhibit these polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank. As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. In other words, any non-increasing sequence of asymptotic ranks stabilizes ("discreteness from above"). In particular, for the matrix multiplication exponent (which is the base-2 logarithm of an asymptotic rank) there is no sequence of exponents of bilinear maps that approximates it arbitrarily closely from above without being eventually constant. In other words, any such upper bound on the matrix multiplication exponent that is close enough, will "snap"to it. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers. We prove our result more generally for a large class of functions on tensors, and in particular obtain similar properties for all functions in Strassen's asymptotic spectrum of tensors. We prove a variety of related structural results on the way. For instance, we prove that for any converging sequence of asymptotic ranks, the limit is also an asymptotic rank for some tensor. We leave open whether asymptotic rank is also discrete from below (which would be implied by Strassen's asymptotic rank conjecture).

Abstract We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give algorithms with complexity $$n^{p + 1}$$ n p + 1 for $$n \times n$$ n × n by $$n \times n^p$$ n × n p matrix multiplication. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $$\alpha$$ α via the big Coppersmith-Winograd tensors cannot exceed $$0.6218$$ 0.6218 .

Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication algorithms), quantum information (entanglement cost and distillable entanglement), and additive combinatorics (bounds on cap sets, sunflower-free sets, etc.). Examples are the asymptotic tensor rank, asymptotic slice rank and asymptotic subrank. Recent works (Costa-Dalai, Blatter-Draisma-Rupniewski, Christandl-Gesmundo-Zuiddam) have investigated notions of discreteness (no accumulation points) or "gaps" in the values of such tensor parameters. We prove a general discreteness theorem for asymptotic tensor parameters of order-three tensors and use this to prove that (1) over any finite field (and in fact any finite set of coefficients in any field), the asymptotic subrank and the asymptotic slice rank have no accumulation points, and (2) over the complex numbers, the asymptotic slice rank has no accumulation points. Central to our approach are two new general lower bounds on the asymptotic subrank of tensors, which measures how much a tensor can be diagonalized. The first lower bound says that the asymptotic subrank of any concise three-tensor is at least the cube-root of the smallest dimension. The second lower bound says that any concise three-tensor that is "narrow enough" (has one dimension much smaller than the other two) has maximal asymptotic subrank. Our proofs rely on new lower bounds on the maximum rank in matrix subspaces that are obtained by slicing a three-tensor in the three different directions. We prove that for any concise tensor, the product of any two such maximum ranks must be large, and as a consequence there are always two distinct directions with large max-rank.

Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which the sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.

Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel$T$and every$\epsilon >0$there exists a threshold$p(\epsilon,T)$for the gate error probability below which rates larger than$C-\epsilon $are fault-tolerantly achievable with vanishing overall communication error, where$C$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.

Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.

In 2004, Horodecki et al., showed that the amount of secret key that can be extracted from noisy bipartite quantum states may exceed the amount of distillable maximally entangled quantum bits. Their work was based on the intuition of quantum data hiding, but did not offer a quantitative relationship to this phenomenon.In this work, which is set in a one-way classical communication scenario, we define a rate of quantum data hiding and provide entropic bounds on it. We then relate the quantum data hiding rate to the gap between the rates at which secret key and entanglement can be extracted, improving on earlier work on this topic.

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in F₂ⁿ × F₂ⁿ of size Ω(3.39ⁿ/poly(n)), which improves the previous lower bound Ω(2.82ⁿ) of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound 4^{n - o(n)}. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group G, three players need to determine whether their inputs x₁, x₂, x₃ ∈ G sum to zero. We find that the NOF communication complexity of the Eval problem over F₂ⁿ is at most 0.24n + 𝒪(log n), which improves the previous upper bound 0.5n + 𝒪(log n).

The study of properties of randomly chosen quantum states has in recent years led to many insights into quantum entanglement. In this work, we study private quantum states from this point of view. Private quantum states are bipartite quantum states characterised by the property that carrying out simple local measurements yields a secret bit. This feature is shared by the maximally entangled pair of quantum bits, yet private quantum states are more general and can in their most extreme form be almost bound entangled. In this work, we study the entanglement properties of random private quantum states and show that they are hardly distinguishable from separable states and thus have low repeatable key, despite containing one bit of key. The technical tools we develop are centred around the concept of locally restricted measurements and include a new operator ordering, bounds on norms under tensoring with entangled states and a continuity bound for a relative entropy measure.

Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent ω, is a central problem in algebraic complexity theory. The best upper bounds on ω, leading to the state-of-the-art ω ≤ 2.37.., have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on ω. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of “irreversibility” of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give ω = 2. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith–Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of “monomial” irreversibility.

We prove a lower bound on the rate of Greenberger-Horne-Zeilinger states distillable from pure multipartite states by local operations and classical communication (LOCC). Our proof is based on a modification of a combinatorial argument used in the fast matrix multiplication algorithm of Coppersmith and Winograd. Previous use of methods from algebraic complexity in quantum information theory concerned transformations with stochastic LOCC (SLOCC), resulting in an asymptotically vanishing success probability. In contrast, our new protocol works with an asymptotically vanishing error.

The study of properties of randomly chosen quantum states has in recent years led to many insights into quantum entanglement. In this work, we study private quantum states from this point of view. Private quantum states are bipartite quantum states characterized by the property that carrying out simple local measurements yields a secret bit. This feature is shared by the maximally entangled pair of quantum bits, yet private quantum states are more general and can in their most extreme form be almost bound entangled. In this work, we study the entanglement properties of random private quantum states and show that they are hardly distinguishable from separable states and thus have low repeatable key, despite containing one bit of key. The technical tools we develop are centered around the concept of locally restricted measurements and include a new operator ordering, bounds on norms under tensoring with entangled states and continuity bounds for relative entropy measures. A full version of this paper is accessible at: http://arxiv.org/abs/1801.2861 [1].

We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication complexity of a Boolean function in this communication model equals the logarithm of the support rank of the corresponding tensor, whereas the approximation complexity in this model equals the logarithm of the border support rank. This characterisation allows us to prove a log-rank conjecture posed by Villagra et al. for nondeterministic multiparty quantum communication with message passing. The support rank characterization of the communication model connects quantum communication complexity intimately to the theory of asymptotic entanglement transformation and algebraic complexity theory. In this context, we introduce the graphwise equality problem. For a cycle graph, the complexity of this communication problem is closely related to the complexity of the computational problem of multiplying matrices, or more precisely, it equals the logarithm of the support rank of the iterated matrix multiplication tensor. We employ Strassen's laser method to show that asymptotically there exist nontrivial protocols for every odd-player cyclic equality problem. We exhibit an efficient protocol for the 5-player problem for small inputs, and we show how Young flattenings yield nontrivial complexity lower bounds.

We show that the problem of deciding membership in the moment polytope associated with a finite-dimensional unitary representation of a compact, connected Lie group is in NP and coNP. This is the first nontrivial result on the computational complexity of this problem, which naively amounts to a quadratically constrained program. Our result applies in particular to the Kronecker polytopes, and therefore to the problem of deciding positivity of the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard, in general [C. Ikenmeyer, K. D. Mulmuley, and M. Walter, preprint, arXiv:1507.02955, 2015]. We discuss the consequences of our work in the context of complexity theory and the quantum marginal problem.

In quantum state redistribution as introduced by Luo and Devetak and Devetak and Yard, there are four systems of interest: the A system held by Alice; the B system held by Bob; the C system that is to be transmitted from Alice to Bob; and the R system that holds a purification of the state in the ABC registers. We give upper and lower bounds on the amount of quantum communication and entanglement required to perform the task of quantum state redistribution in a one-shot setting. Our bounds are in terms of the smooth conditional minand max-entropy, and the smooth max-information. The protocol for the upper bound has a clear structure, building on the work of Oppenheim: it decomposes the quantum state redistribution task into two simpler coherent state merging tasks by introducing a coherent relay. In the independent and identical (i.i.d.) asymptotic limit our bounds for the quantum communication cost converge to the quantum conditional mutual information I(C; R|B), and our bounds for the total cost converge to the conditional entropy H(C|B). This yields an alternative proof of optimality of these rates for quantum state redistribution in the i.i.d. asymptotic limit. In particular, we obtain a strong converse for quantum state redistribution, which even holds when allowing for feedback.

We analyze a cryptographic protocol for generating a distributed secret key from correlations that violate a Bell inequality by a sufficient amount, and prove its security against eavesdroppers, constrained only by the assumption that any information accessible to them must be compatible with the non-signaling principle. The claim holds with respect to the state-of-the-art security definition used in cryptography, known as universally-composable security. The non-signaling assumption only refers to the statistics of measurement outcomes depending on the choices of measurements; hence security is independent of the internal workings of the devices - they do not even need to follow the laws of quantum theory. This is relevant for practice as a correct and complete modeling of realistic devices is generally impossible. The techniques developed are general and can be applied to other Bell inequality-based protocols. In particular, we provide a scheme for estimating Bell-inequality violations when the samples are not independent and identically distributed.

The entanglement cost of a quantum channel is the minimal rate at which entanglement (between sender and receiver) is needed in order to simulate many copies of a quantum channel in the presence of free classical communication. In this paper, we show how to express this quantity as a regularized optimization of the entanglement formation over states that can be generated between sender and receiver. Our formula is the channel analog of a well-known formula for the entanglement cost of quantum states in terms of the entanglement of formation and shares a similar relation to the recently shattered hope for additivity. The entanglement cost of a quantum channel can be seen as the analog of the quantum reverse Shannon theorem in the case where free classical communication is allowed. The techniques used in the proof of our result are then also inspired by a recent proof of the quantum reverse Shannon theorem and feature the one-shot formalism for quantum information theory, the postselection technique for quantum channels as well as Sion's minimax theorem. We discuss two applications of our result. First, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only improves the range of parameters where security can be shown, but also allows us to prove security for storage devices for which no results were known before. Second, our result has consequences for the study of the strong converse quantum capacity. Here, we show that any coding scheme that sends quantum information through a quantum channel at a rate larger than the entanglement cost of the channel has an exponentially small fidelity.

For fixed compact connected Lie groups H ⊆ G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Nonasymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory.

A natural question in characterizing the information theoretic power of quantum channels is to ask at what rate entanglement is needed in order to asymptotically simulate a quantum channel in the presence of free classical communication. We call this the entanglement cost of a channel, and prove a formula describing it for all channels. We discuss two applications. Firstly, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only greatly improves the range of parameters where security could be shown previously, but allows us to prove security for storage devices for which no non-trivial statements were known before. Secondly, our result has consequences for the study of the strong converse quantum capacity. Here, we show that any coding scheme that sends quantum information through a quantum channel at a rate larger than the entanglement cost of the channel has an exponentially small fidelity.

We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is ε-away from the set of the separable states in time exp(O(ε-2 log|A| log|B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al. (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP.

Squashed entanglement and entanglement of purification are quantum mechanical correlation measures and defined as certain minimisations of entropic quantities. In this paper, we present the first non-trivial calculations of both quantities. Our results lead to the conclusion that both measures can drop by an arbitrary amount when only a single qubit of a local system is lost. This property is known as "locking" and has previously been observed for other correlation measures such as accessible information, entanglement cost and logarithmic negativity. In the case of squashed entanglement, the results are obtained using an inequality that can be understood as a quantum channel analogue of well-known entropic uncertainty relations. This inequality may prove a useful tool in quantum information theory. The regularised entanglement of purification is known to equal the entanglement needed to prepare many copies of a quantum state by local operations and a sublinear amount of communication. Here, monogamy of quantum entanglement (i.e., the impossibility of a system being maximally entangled with two others at the same time) leads to an exact calculation for all quantum states that are supported either on the symmetric or on the antisymmetric subspace of a d times d-dimensional system

Squashed entanglement and entanglement of purification are quantum-mechanical correlation measures and are defined as certain minimizations of entropic quantities. In this paper, we present the first nontrivial calculations of both quantities. Our results lead to the conclusion that both measures can drop by an arbitrary amount when only a single qubit of a local system is lost. This property is known as "locking" and has previously been observed for other correlation measures such as accessible information, entanglement cost, and logarithmic negativity. In the case of squashed entanglement, the results are obtained using an inequality that can be understood as a quantum channel analogue of well-known entropic uncertainty relations. This inequality may prove a useful tool in quantum information theory. The regularized entanglement of purification is known to equal the entanglement needed to prepare many copies of a quantum state by local operations and a sublinear amount of communication. Here, monogamy of quantum entanglement (i.e., the impossibility of a system being maximally entangled with two others at the same time) leads to an exact calculation for all quantum states that are supported either on the symmetric or on the antisymmetric subspace of a d/spl times/d-dimensional system.

This paper introduces the public Eve scenario and shows that the secret key rate in this scenario is bounded by the intrinsic information. This elucidates previous results and gives new insights in the gap between formation and extraction of secret information. Intrinsic information, in its function as an upper bound on the secret key rate, is generalized to secret key agreement from arbitrary tripartite quantum states.