It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr ² /ε ² ) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε ² )ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr ² /δ ² )/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.

We explicitly exhibit a set of four ququad-ququad orthogonal maximally entangled states that cannot be perfectly distinguished by means of local operations and classical communication. Before our work, it was unknown whether there is a set of d locally indistinguishable d$\bigotimes${}d orthogonal maximally entangled states for some positive integer d. We further show that a 2$\bigotimes${}2 maximally entangled state can be used to locally distinguish this set of states without being consumed, thus demonstrate a novel phenomenon of entanglement discrimination catalysis. Based on this set of states, we construct a new set K consisting of four locally indistinguishable states such that K$\bigotimes${}m (with 4m members) is locally distinguishable for some m greater than one. As an immediate application, we construct a noisy quantum channel with one sender and two receivers whose local zero-error classical capacity can achieve the full dimension of the input space but only with a multi-shot protocol.

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples. Previously, it was known only that estimating states to error є in trace distance required O(dr²/є²) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ δ ) ln(d/δ) ) copies to estimate ρ to error δ in infidelity. This implies O( (dr / є²)· ln(d/є) ) copies suffice to achieve error є in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n. We also use the Holevo bound from quantum information theory to prove a lower bound of Ω(dr/є²)/ log(d/rє) copies needed to achieve error є in trace distance. This implies a lower bound Ω(dr/δ)/log(d/rδ) for the estimation error δ in infidelity. These match our upper bounds up to log factors. Our techniques can also show an Ω(r²d/δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r.

We prove limitations on LOCC and separable measurements in bipartite state discrimination problems using techniques from convex optimization. Specific results that we prove include: an exact formula for the optimal probability of correctly discriminating any set of either three or four Bell states via LOCC or separable measurements when the parties are given an ancillary partially entangled pair of qubits; an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements; and an optimal bound on the success probability for any LOCC or separable measurement for the recently proposed state discrimination problem of Yu, Duan, and Ying.

We study the distinguishability of bipartite quantum states by positive operator-valued measures with positive partial transpose (PPT POVMs). The contributions of this paper include: 1) we give a negative answer to an open problem of showing a limitation of a previous known method for detecting nondistinguishability; 2) we show that a maximally entangled state and its orthogonal complement, no matter how many copies are supplied, cannot be distinguished by the PPT POVMs, even unambiguously. This result is much stronger than the previous known ones; and 3) we study the entanglement cost of distinguishing quantum states. It is proved that √{2/3}|00〉+√{1/3}|11〉 is sufficient and necessary for distinguishing three Bell states by the PPT POVMs. An upper bound of entanglement cost of distinguishing a d ⊗ d pure state and its orthogonal complement is obtained for separable operations. Based on this bound, we are able to construct two orthogonal quantum states, which cannot be distinguished unambiguously by separable POVMs, but finite copies would make them perfectly distinguishable by local operations and classical communication. We further observe that a two-qubit maximally entangled state is always enough for distinguishing a d ⊗ d pure state and its orthogonal complement by the PPT POVMs, no matter the value of d. In sharp contrast, an entangled state with Schmidt number at least d is always needed for distinguishing such two states by separable POVMs. As an application, we show that the entanglement cost of distinguishing a d ⊗ d maximally entangled state and its orthogonal complement must be a maximally entangled state for d=2, which implies that teleportation is optimal, and in general, it could be chosen as O(logd/d).

In this Rapid Communication, we consider the open problem of the minimum cost of two-qubit gates for simulating the Toffoli gate and show that five two-qubit gates are necessary. Before our work, it was known that five two-qubit gates are sufficient to implement the Toffoli gate, and numerical evidence indicates that five two-qubit gates are also necessary. The idea introduced here can also be used to solve the problem of optimal simulation of Deutsch three-qubit gates.