Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguish ability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.

The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n -bit message is encoded in a quantum system using a classical key of size much smaller than n . Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be “locked”. Furthermore, knowing the key, it is possible to recover, that is “unlock”, the message. In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the ℓ 1 norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of ℓ 2 into ℓ 1 . A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give efficient constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of n -qubit states. We prove that this task can be performed by a single message protocol using O (log 2 n ) qubits and n bits of communication, where the computation of the sender is efficient.

Calculating the capacity of interference channels is a notorious open problem in classical information theory. Such channels have two senders and two receivers, and each sender would like to communicate with a partner receiver. The capacity of such channels is known exactly in the settings of “very strong” and “strong” interference, while the Han-Kobayashi coding strategy gives the best known achievable rate region in the general case. Here, we introduce and study the quantum interference channel, a natural generalization of the interference channel to the setting of quantum information theory. We restrict ourselves for the most part to channels with two classical inputs and two quantum outputs in order to simplify the presentation of our results (though generalizations of our results to channels with quantum inputs are straightforward). We are able to determine the exact classical capacity of this channel in the settings of “very strong” and “strong” interference, by exploiting Winter's successive decoding strategy and a novel two-sender quantum simultaneous decoder, respectively. We provide a proof that a Han-Kobayashi strategy is achievable with Holevo information rates, up to a conjecture regarding the existence of a three-sender quantum simultaneous decoder. This conjecture holds for a special class of quantum multiple-access channels with average output states that commute, and we discuss some other variations of the conjecture that hold. Finally, we detail a connection between the quantum interference channel and prior work on the capacity of bipartite unitary gates.

If a quantum system is subject to noise, it is possible to perform quantum error correction reversing the action of the noise if and only if no information about the system's quantum state leaks to the environment. In this paper, we develop an analogous duality in the case that the environment approximately forgets the identity of the quantum state, a weaker condition satisfied by -randomizing maps and approximate unitary designs. Specifically, we show that the environment approximately forgets quantum states if and only if the original channel approximately preserves pairwise fidelities of pure inputs, an observation we call weak decoupling duality. Using this tool, we then go on to study the task of using the output of a channel to simulate restricted classes of measurements on a space of input states. The case of simulating measurements that test whether the input state is an arbitrary pure state is known as equality testing or quantum identification. An immediate consequence of weak decoupling duality is that the ability to perform quantum identification cannot be cloned. We, furthermore, establish that the optimal amortized rate at which quantum states can be identified through a noisy quantum channel is equal to the entanglement-assisted classical capacity of the channel, despite the fact that the task is quantum, not classical, and entanglement-assistance is not allowed. In particular, this rate is strictly positive for every nonconstant quantum channel, including classical channels.

Quantum uncertainty relations are at the heart of many quantum cryptographic protocols performing classically impossible tasks. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message (the message is "locked"). Furthermore, knowing the key, it is possible to recover (or "unlock") the message.

We consider quantum channels with one sender and two receivers, used in several different ways for the simultaneous transmission of independent messages. We begin by extending the technique of superposition coding to quantum channels with a classical input to give a general achievable region. We also give outer bounds to the capacity regions for various special cases from the classical literature and prove that superposition coding is optimal for a class of channels. We then consider extensions of superposition coding for channels with a quantum input, where some of the messages transmitted are quantum instead of classical, in the sense that the parties establish bipartite or tripartite GHZ entanglement. We conclude by using state merging to give achievable rates for establishing bipartite entanglement between different pair of parties with the assistance of free classical communication.

A new protocol for quantum broadcast channels based on the fully quantum Slepian-Wolf protocol is presented. The protocol yields an achievable rate region for entanglement-assisted transmission of quantum information through a quantum broadcast channel that can be considered the quantum analogue of Marton's region for classical broadcast channels. The protocol can be adapted to yield achievable rate regions for unassisted quantum communication and for entanglement-assisted classical communication; in the case of unassisted transmission, the region we obtain has no independent constraint on the sum rate, only on the individual transmission rates. Regularized versions of all three rate regions are provably optimal.

We consider quantum channels with two senders and one receiver. For an arbitrary such channel, we give multiletter characterizations of two different two-dimensional capacity regions. The first region comprises the rates at which it is possible for one sender to send classical information, while the other sends quantum information. The second region consists of the rates at which each sender can send quantum information. For each region, we give an example of a channel for which the corresponding region has a single-letter description. One of our examples relies on a new result proved here, perhaps of independent interest, stating that the coherent information over any degradable channel is concave in the input density operator. We conclude with connections to other work and a discussion on generalizations where each user simultaneously sends classical and quantum information.

In this paper, we present a one-shot method for preparing pure entangled states between a sender and a receiver at a minimal cost of entanglement and quantum communication. In the case of preparing unentangled states, an earlier paper showed that a$2l$-qubit quantum state could be communicated to a receiver by physically transmitting only$l+o(l)$qubits in addition to consuming$l$ebits of entanglement and some shared randomness. When the states to be prepared are entangled, we find that there is a reduction in the number of qubits that need to be transmitted, interpolating between no communication at all for maximally entangled states and the earlier two-for-one result of the unentangled case, all without the use of any shared randomness. We also present two applications of our result: a direct proof of the achievability of the optimal superdense coding protocol for entangled states produced by a memoryless source, and a demonstration that the quantum identification capacity of an ebit is two qubits.

The problem of distributed compression for correlated quantum sources is considered. The classical version of this problem was solved by Slepian and Wolf, who showed that distributed compression could take full advantage of redundancy in the local sources created by the presence of correlations. Here it is shown that, in general, this is not the case for quantum sources, by proving a lower bound on the rate sum for irreducible sources of product states which is stronger than the one given by a naive application of Slepian–Wolf. Nonetheless, strategies taking advantage of correlation do exist for some special classes of quantum sources. For example, Devetak and Winter demonstrated the existence of such a strategy when one of the sources is classical. Optimal nontrivial strategies for a different extreme, sources of Bell states, are presented here. In addition, it is explained how distributed compression is connected to other problems in quantum information theory, including information-disturbance questions, entanglement distillation and quantum error correction.

We consider quantum channels with two senders and one receiver. For an arbitrary such channel, we give multi-letter characterizations of two different two-dimensional capacity regions. The first region characterizes the rates at which it is possible for one sender to send classical information while the other sends quantum information. The second region gives the rates at which each sender can send quantum information. We give an example of a channel for which each region has a single-letter description, concluding with a characterization of the rates at which each user can simultaneously send classical and quantum information

Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various choices one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this "universal" formulation, these ebit and cbit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding.