Multi-party local quantum operations with shared quantum entanglement or shared classical randomness are studied. The following facts are established: * There is a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. * The existence of the ball of local operations with shared randomness is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. * Local operations with shared entanglement are characterized in terms of linear functionals that are "completely'' positive on a certain cone K of separable Hermitian operators, under a natural notion of complete positivity appropriate to that cone. Local operations with shared randomness (but not entanglement) are also characterized in terms of linear functionals that are merely positive on that same cone K. * Existing characterizations of no-signaling operations are generalized to the multi-party setting and recast in terms of the Choi-Jamio\l kowski representation for quantum super-operators. It is noted that the standard nonlocal box is an example of a no-signaling operation that is separable, yet cannot be implemented by local operations with shared entanglement.
Multi-party local quantum operations with shared quantum entanglement or shared classical randomness are studied. The following facts are established: * There is a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. * The existence of the ball of local operations with shared randomness is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. * Local operations with shared entanglement are characterized in terms of linear functionals that are "completely'' positive on a certain cone K of separable Hermitian operators, under a natural notion of complete positivity appropriate to that cone. Local operations with shared randomness (but not entanglement) are also characterized in terms of linear functionals that are merely positive on that same cone K. * Existing characterizations of no-signaling operations are generalized to the multi-party setting and recast in terms of the Choi-Jamio\l kowski representation for quantum super-operators. It is noted that the standard nonlocal box is an example of a no-signaling operation that is separable, yet cannot be implemented by local operations with shared entanglement.
Multi-party local quantum operations with shared quantum entanglement or shared classical randomness are studied. The following facts are established: (i) There is a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. (ii) The existence of the ball of local operations with shared randomness is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. (iii) Local operations with shared entanglement are characterized in terms of linear functionals that are ``completely'' positive on a certain cone K of separable Hermitian operators, under a natural notion of complete positivity appropriate to that cone. Local operations with shared randomness (but not entanglement) are also characterized in terms of linear functionals that are merely positive on that same cone K. (iv) Existing characterizations of no-signaling operations are generalized to the multi-party setting and recast in terms of the Choi-Jamiolkowski representation for quantum super-operators. It is noted that the standard nonlocal box is an example of a no-signaling operation that is separable, yet cannot be implemented by local operations with shared entanglement.
This thesis is divided into two parts. In Part I we introduce a new formalism for quantum strategies, which specify the actions of one party in any multi-party interaction involving the exchange of multiple quantum messages among the parties. This formalism associates with each strategy a single positive semidefinite operator acting only upon the tensor product of the input and output message spaces for the strategy. We establish three fundamental properties of this new representation for quantum strategies and we list several applications, including a quantum version of von Neumann's celebrated 1928 Min-Max Theorem for zero-sum games and an efficient algorithm for computing the value of such a game. In Part II we establish several properties of a class of quantum operations that can be implemented locally with shared quantum entanglement or classical randomness. In particular, we establish the existence of a ball of local operations with shared randomness lying within the space spanned by the no-signaling operations and centred at the completely noisy channel. The existence of this ball is employed to prove that the weak membership problem for local operations with shared entanglement is strongly NP-hard. We also provide characterizations of local operations in terms of linear functionals that are positive and "completely" positive on a certain cone of Hermitian operators, under a natural notion of complete positivity appropriate to that cone. We end the thesis with a discussion of the properties of no-signaling quantum operations.
Nonlocality and its connections to entanglement are fundamental features of quantum mechanics that have found numerous applications in quantum information science. A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. An important practical consideration is that the runtime of the parties has to be shorter than the time it takes light to travel between them. One way to model this restriction is to assume that the parties are computationally bounded. We therefore initiate the study of nonlocality under computational assumptions and derive the following results: (a) We define the set NeL (not-efficiently-local) as consisting of all bipartite states whose correlations arising from local measurements cannot be reproduced with shared randomness and \emph{polynomial-time} local operations. (b) Under the assumption that the Learning With Errors problem cannot be solved in \emph{quantum} polynomial-time, we show that NeL=ENT, where ENT is the set of \emph{all} bipartite entangled states (pure and mixed). This is in contrast to the standard notion of nonlocality where it is known that some entangled states, e.g. Werner states, are local. In essence, we show that there exist (efficient) local measurements producing correlations that cannot be reproduced through shared randomness and quantum polynomial-time computation. (c) We prove that if NeL=ENT unconditionally, then BQP=PP. In other words, the ability to certify all bipartite entangled states against computationally bounded adversaries gives a non-trivial separation of complexity classes. (d) Using (c), we show that a certain natural class of 1-round delegated quantum computation protocols that are sound against PP provers cannot exist.
Departing from the usual paradigm of local operations and classical communication adopted in entanglement theory, we study here the interconversion of quantum states by means of local operations and shared randomness. A set of necessary and sufficient conditions for the existence of such a transformation between two given quantum states is given in terms of the payoff they yield in a suitable class of nonlocal games. It is shown that, as a consequence of our result, such a class of nonlocal games is able to witness quantum entanglement, however weak, and reveal nonlocality in any entangled quantum state. An example illustrating this fact is provided.
A state over time (stote) pairs a state ρ with a channel E as the Hermitian, generally non-positive operator (ρ⊗1)⋆JE. Characterizing the convex cone Q these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Winter (2026). We exhibit a linear copy of the bipartite separable cone as an exposed face of Q: for output systems of the form B=A′R with A′ a copy of the input, there is an explicit witness W0∈Q∗ and an explicit injective linear map L with σ∈SEP+(A:R)⟺L(σ)∈Q(A:A′R). Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for Q and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless P=NP. Independently of this complexity assumption, Fawzi's theorem implies that Q(A:A′R) admits no finite semidefinite representation when d=dimA≥2, r=dimR≥2, and d+r>5.
Departing from the usual paradigm of local operations and classical communication adopted in entanglement theory, here we study the interconversion of quantum states by means of local operations and shared randomness. A set of necessary and sufficient conditions for the existence of such a transformation between two given quantum states is given in terms of the payoff they yield in a suitable class of nonlocal games. It is shown that, as a consequence of our result, such a class of nonlocal games is able to witness quantum entanglement, however weak, and reveal nonlocality in any entangled quantum state. An example illustrating this fact is provided.