Search

Most previous efforts of quantum error correction focused on either extending classical error correction schemes to the quantum regime by performing a perfect correction on a subset of errors, or seeking a recovery operation to maximize the fidelity between a input state and its corresponding output state of a noisy channel. There are few results concerning quantum error pre-compensation. Here we design an error pre-compensated input state for an arbitrary quantum noisy channel and a given target output state. By following a procedure, the required input state, if it exists, can be analytically obtained in single-partite systems. Furthermore, we also present semidefinite programs to numerically obtain the error pre-compensated input states with maximal fidelities between the target state and the output state. The numerical results coincide with the analytical results., Comment: 10 pages, 3 figures

The quantum internet is envisioned as the ultimate stage of the quantum revolution, which surpasses its classical counterpart in various aspects, such as the efficiency of data transmission, the security of network services, and the capability of information processing. Given its disruptive impact on the national security and the digital economy, a global race to build scalable quantum networks has already begun. With the joint effort of national governments, industrial participants and research institutes, the development of quantum networks has advanced rapidly in recent years, bringing the first primitive quantum networks within reach. In this work, we aim to provide an up-to-date review of the field of quantum networks from both theoretical and experimental perspectives, contributing to a better understanding of the building blocks required for the establishment of a global quantum internet. We also introduce a newly developed quantum network toolkit to facilitate the exploration and evaluation of innovative ideas. Particularly, it provides dual quantum computing engines, supporting simulations in both the quantum circuit and measurement-based models. It also includes a compilation scheme for mapping quantum network protocols onto quantum circuits, enabling their emulations on real-world quantum hardware devices. We showcase the power of this toolkit with several featured demonstrations, including a simulation of the Micius quantum satellite experiment, a testing of a four-layer quantum network architecture with resource management, and a quantum emulation of the CHSH game. We hope this work can give a better understanding of the state-of-the-art development of quantum networks and provide the necessary tools to make further contributions along the way., Comment: 36 pages, 33 figures; comments are welcome

In 2004 Ambainis and Regev formulated a certain form of quantum adiabatic theorem and provided an elementary proof which is especially accessible to computer scientists. Their result is achieved by discretizing the total adiabatic evolution into a sequence of unitary transformations acting on the quantum system. Here we continue this line of study by providing another elementary and shorter proof with improved bounds. Our key finding is a succinct integral representation of the difference between the target and the actual states, which yields an accurate estimation of the approximation error. Our proof can be regarded as a "continuous" version of the work by Ambainis and Regev. As applications, we show how to adiabatically prepare an arbitrary qubit state from an initial state., Comment: 11 pages, no figures, preliminary version, comments are welcome

An unknown unitary gates, which is secretly chosen from several known ones, can always be distinguished perfectly. In this paper, we implement such a task on IBM's quantum processor. More precisely, we experimentally demonstrate the discrimination of two qubit unitary gates, the identity gate and the $\frac{2}{3}\pi$-phase shift gate, using two discrimination schemes -- the parallel scheme and the sequential scheme. We program these two schemes on the \emph{ibmqx4}, a $5$-qubit superconducting quantum processor via IBM cloud, with the help of the $QSI$ modules [S. Liu et al.,~arXiv:1710.09500, 2017]. We report that both discrimination schemes achieve success probabilities at least 85%., Comment: 5 pages, 6 figures

We introduce a novel generalization of the Clauser-Horne-Shimony-Holt (CHSH) game to a multiplayer setting, i.e., Hypercube game, where all $m$ players are required to assign values to vertices on corresponding facets of an $m$-dimensional hypercube. The players win if and only if their answers satisfy both parity and consistency conditions. We completely characterize the maximum winning probabilities (game value) under classical, quantum and no-signalling strategies, respectively. In contrast to the original CHSH game designed to demonstrate the superiority of quantumness, we find that the quantum advantages in the Hypercube game significantly decrease as the number of players increase. Notably, the quantum value decays exponentially fast to the classical value as $m$ increases, while the no-signalling value always remains to be one., Comment: 9 pages, 4 figures, comments are warmly welcome

It is NP-complete to find non-negative factors $W$ and $H$ with fixed rank $r$ from a non-negative matrix $X$ by minimizing $\|X-WH^\top\|_F^2$. Although the separability assumption (all data points are in the conical hull of the extreme rows) enables polynomial-time algorithms, the computational cost is not affordable for big data. This paper investigates how the power of quantum computation can be capitalized to solve the non-negative matrix factorization with the separability assumption (SNMF) by devising a quantum algorithm based on the divide-and-conquer anchoring (DCA) scheme. The design of quantum DCA (QDCA) is challenging. In the divide step, the random projections in DCA is completed by a quantum algorithm for linear operations, which achieves the exponential speedup. We then devise a heuristic post-selection procedure which extracts the information of anchors stored in the quantum states efficiently. Under a plausible assumption, QDCA performs efficiently, achieves the quantum speedup, and is beneficial for high dimensional problems.

We explore the classical communication over quantum channels with one sender and two receivers, or with two senders and one receiver, First, for the quantum broadcast channel (QBC) and the quantum multi-access channel (QMAC), we study the classical communication assisted by non-signalling and positive-partial-transpose-preserving codes, and obtain efficiently computable one-shot bounds to assess the performance of classical communication. Second, we consider the asymptotic communication capability of communication over the QBC and QMAC. We derive an efficiently computable strong converse bound for the capacity region, which behaves better than the previous semidefinite programming strong converse bound for point-to-point channels. Third, we obtain a converse bound on the one-shot capacity region based on the hypothesis testing divergence between the given channel and a certain class of subchannels. As applications, we analyze the communication performance for some basic network channels, including the classical broadcast channels and a specific class of quantum broadcast channels., Comment: 18 pages, 5 figures, comments are welcome

This paper describes a quantum programming environment, named $Q|SI\rangle$. It is a platform embedded in the .Net language that supports quantum programming using a quantum extension of the $\mathbf{while}$-language. The framework of the platform includes a compiler of the quantum $\mathbf{while}$-language and a suite of tools for simulating quantum computation, optimizing quantum circuits, and analyzing and verifying quantum programs. Throughout the paper, using $Q|SI\rangle$ to simulate quantum behaviors on classical platforms with a combination of components is demonstrated. The scalable framework allows the user to program customized functions on the platform. The compiler works as the core of $Q|SI\rangle$ bridging the gap from quantum hardware to quantum software. The built-in decomposition algorithms enable the universal quantum computation on the present quantum hardware., Comment: 30 pages, software available at http://www.qcompiler.com

We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bounds on the amount of quantum information that can be transmitted over a single use of a quantum channel, which improve the previous bound from [Tomamichel/Berta/Renes, Nat. Commun. 7, 2016]. As applications, we study quantum communication over depolarizing channels and amplitude damping channels with finite resources. Second, we find an SDP strong converse bound for the quantum capacity of an arbitrary quantum channel, which means the fidelity of any sequence of codes with a rate exceeding this bound will vanish exponentially fast as the number of channel uses increases. Furthermore, we prove that the SDP strong converse bound improves the partial transposition bound introduced by Holevo and Werner. Third, we prove that this SDP strong converse bound is equal to the so-called max-Rains information, which is an analog to the Rains information introduced in [Tomamichel/Wilde/Winter, IEEE Trans. Inf. Theory 63:715, 2017]. Our SDP strong converse bound is weaker than the Rains information, but it is efficiently computable for general quantum channels., Comment: 17 pages, extended version of arXiv:1601.06888. v3 is closed to the published version, IEEE Transactions on Information Theory, 2018

What does it mean for one quantum process to be more disordered than another? Here we provide a precise answer to this question in terms of a quantum-mechanical generalization of majorization. The framework admits a complete description in terms of single-shot entropies, and provides a range of significant applications. These include applications to the comparison of quantum statistical models and quantum channels, to the resource theory of asymmetry, and to quantum thermodynamics. In particular, within quantum thermodynamics, we apply our results to provide the first complete set of of necessary and sufficient conditions for arbitrary quantum state transformation under thermodynamic processes, and which rigorously accounts for quantum-mechanical properties, such as coherence. Our framework of generalized thermal processes extends thermal operations, and is based on natural physical principles, namely, energy conservation, the existence of equilibrium states, and the requirement that quantum coherence be accounted for thermodynamically. In the zero coherence case we recover thermo-majorization while in the asymptotic coherence regime we obtain a constraint that takes the form of a Page-Wootters clock condition., Comment: 11 pages main text + 12 pages appendix, 2 figures, v2 contains significant improvement of the presentation. Particularly, the appendix has been completely restructured and proofs expanded with more details, and with a re-derivation of thermo-majorization from quantum majorization

Entanglement distillation, an essential quantum information processing task, refers to the conversion from multiple copies of noisy entangled states to a smaller number of highly entangled states. In this work, we study the non-asymptotic fundamental limits for entanglement distillation. We investigate the optimal tradeoff between the distillation rate, the number of prepared states, and the error tolerance. First, we derive the one-shot distillable entanglement under completely positive partial transpose preserving operations as a semidefinite program and demonstrate an exact characterization via the quantum hypothesis testing relative entropy. Second, we establish efficiently computable second-order estimations of the distillation rate for general quantum states. In particular, we provide explicit as well as approximate evaluations for various quantum states of practical interest, including pure states, mixture of Bell states, maximally correlated states and isotropic states., Comment: 21 pages, 5 figures, comments are welcome; v3 close to published version

Broadcasting quantum and classical information is a basic task in quantum information processing, and is also a useful model in the study of quantum correlations including quantum discord. We establish a full operational characterization of two-sided quantum discord in terms of bilocal broadcasting of quantum correlations. Moreover, we show that both the optimal fidelity of unilocal broadcasting of the correlations in an arbitrary bipartite quantum state and that of broadcasting an arbitrary set of quantum states can be formulized as semidefinite programs (SDPs), which are efficiently computable. We also analyze some properties of these SDPs and evaluate the broadcasting fidelities for some cases of interest., Comment: 9 pages, comments are welcome; published version

A bipartite subspace $S$ is called strongly positive-partial-transpose-unextendible (PPT-unextendible) if for every positive integer $k$, there is no PPT operator supporting on the orthogonal complement of $S^{\otimes k}$. We show that a subspace is strongly PPT-unextendible if it contains a PPT-definite operator (a positive semidefinite operator whose partial transpose is positive definite). Based on these, we are able to propose a simple criterion for verifying whether a set of bipartite orthogonal quantum states is indistinguishable by PPT operations in the many copy scenario. Utilizing this criterion, we further point out that any entangled pure state and its orthogonal complement cannot be distinguished by PPT operations in the many copy scenario. On the other hand, we investigate that the minimum dimension of strongly PPT-unextendible subspaces in an $m\otimes n$ system is $m+n-1$, which involves a generalization of the result that non-positive-partial-transpose (NPT) subspaces can be as large as any entangled subspace [N. Johnston, Phys. Rev. A 87: 064302 (2013)]., Comment: 6 pages, comments are welcome!

We study the problem of transforming a tripartite pure state to a bipartite one using stochastic local operations and classical communication (SLOCC). It is known that the tripartite-to-bipartite SLOCC convertibility is characterized by the maximal Schmidt rank of the given tripartite state, i.e. the largest Schmidt rank over those bipartite states lying in the support of the reduced density operator. In this paper, we further study this problem and exhibit novel results in both multi-copy and asymptotic settings. In the multi-copy regime, we observe that the maximal Schmidt rank is strictly super-multiplicative, i.e. the maximal Schmidt rank of the tensor product of two tripartite pure states can be strictly larger than the product of their maximal Schmidt ranks. We then provide a full characterization of those tripartite states whose maximal Schmidt rank is strictly super-multiplicative when taking tensor product with itself. In the asymptotic setting, we focus on determining the tripartite-to-bipartite SLOCC entanglement transformation rate, which turns out to be equivalent to computing the asymptotic maximal Schmidt rank of the tripartite state, defined as the regularization of its maximal Schmidt rank. Despite the difficulty caused by the super-multiplicative property, we provide explicit formulas for evaluating the asymptotic maximal Schmidt ranks of two important families of tripartite pure states, by resorting to certain results of the structure of matrix spaces, including the study of matrix semi-invariants. These formulas give a sufficient and necessary condition to determine whether a given tripartite pure state can be transformed to the bipartite maximally entangled state under SLOCC, in the asymptotic setting. Applying the recent progress on the non-commutative rank problem, we can verify this condition in deterministic polynomial time., Comment: 23 pages, v2 has improved presentation, numerous typos and proof corrected, and many more references. Comments are welcome!

We investigate the classical communication over quantum channels when assisted by no-signaling (NS) and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot $\epsilon$-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel., Comment: 26 pages; v2, v3 updated reference and results; v4 published in IEEE Transactions on Information Theory

Quantum Lov\'asz number is a quantum generalization of the Lov\'asz number in graph theory. It is the best known efficiently computable upper bound of the entanglement-assisted zero-error classical capacity of a quantum channel. However, it remains an intriguing open problem whether quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lov\'asz number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lov\'asz number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signalling correlations, which differs from the case of classical channels., Comment: v3 is closed to the published version; v2 improved the presentation

We demonstrate the irreversibility of asymptotic entanglement manipulation under quantum operations that completely preserve the positivity of partial transpose (PPT), resolving a major open problem in quantum information theory. Our key tool is a new efficiently computable additive lower bound for the asymptotic relative entropy of entanglement with respect to PPT states, which can be used to evaluate the entanglement cost under local operations and classical communication (LOCC). We find that for any rank-two mixed state supporting on the $3\otimes3$ antisymmetric subspace, the amount of distillable entanglement by PPT operations is strictly smaller than one entanglement bit (ebit) while its entanglement cost under PPT operations is exactly one ebit. As byproduct, we find that for this class of states, both the Rains' bound and its regularization, are strictly less than the asymptotic relative entropy of entanglement. So, in general, there is no unique entanglement measure for the manipulation of entanglement by PPT operations. We further show a computable sufficient condition for the irreversibility of entanglement distillation by LOCC (or PPT) operations., Comment: v2 presentation improved; v3 is closed to the published version

We find that the perfect distinguishability of two quantum operations by a parallel scheme depends only on an operator subspace generated from their Choi-Kraus operators. We further show that any operator subspace can be obtained from two quantum operations in such a way. This connection enables us to study the parallel distinguishability of operator subspaces directly without explicitly referring to the underlining quantum operations. We obtain a necessary and sufficient condition for the parallel distinguishability of an operator subspace that is either one-dimensional or Hermitian. In both cases the condition is equivalent to the non-existence of positive definite operator in the subspace, and an optimal discrimination protocol is obtained. Finally, we provide more examples to show that the non-existence of positive definite operator is sufficient for many other cases, but in general it is only a necessary condition., Comment: 5 pages, 1 figures, comments are welcome

Rains' bound is arguably the best known upper bound of the distillable entanglement by operations completely preserving positivity of partial transpose (PPT) and was conjectured to be additive and coincide with the asymptotic relative entropy of entanglement. We disprove both conjectures by explicitly constructing a special class of mixed two-qubit states. We then introduce an additive semidefinite programming lower bound ($E_M$) for the asymptotic Rains' bound, and it immediately becomes a computable lower bound for entanglement cost of bipartite states. Furthermore, $E_M$ is also proved to be the best known upper bound of the PPT-assisted deterministic distillable entanglement and gives the asymptotic rates for all pure states and some class of genuinely mixed states., Comment: 6 pages, title changed, closed to the published version

A new additive and semidefinite programming (SDP) computable entanglement measure is introduced to upper bound the amount of distillable entanglement in bipartite quantum states by operations completely preserving the positivity of partial transpose (PPT). This quantity is always smaller than or equal to the logarithmic negativity, the previously best known SDP bound on distillable entanglement, and the inequality is strict in general. Furthermore, a succinct SDP characterization of the one-copy PPT deterministic distillable entanglement for any given state is also obtained, which provides a simple but useful lower bound on the PPT distillable entanglement. Remarkably, there is a genuinely mixed state of which both bounds coincide with the distillable entanglement while being strictly less than the logarithmic negativity., Comment: 5 pages, 2 figures, v4 improved presentation and slightly changed title

Using one channel to simulate another exactly with the aid of quantum no-signalling correlations has been studied recently. The one-shot no-signalling assisted classical zero-error simulation cost of non-commutative bipartite graphs has been formulated as semidefinite programms [Duan and Winter, IEEE Trans. Inf. Theory 62, 891 (2016)]. Before our work, it was unknown whether the one-shot (or asymptotic) no-signalling assisted zero-error classical simulation cost for general non-commutative graphs is multiplicative (resp. additive) or not. In this paper we address these issues and give a general sufficient condition for the multiplicativity of the one-shot simulation cost and the additivity of the asymptotic simulation cost of non-commutative bipartite graphs, which include all known cases such as extremal graphs and classical-quantum graphs. Applying this condition, we exhibit a large class of so-called \emph{cheapest-full-rank graphs} whose asymptotic zero-error simulation cost is given by the one-shot simulation cost. Finally, we disprove the multiplicativity of one-shot simulation cost by explicitly constructing a special class of qubit-qutrit non-commutative bipartite graphs., Comment: 5 pages, 2 figures, small typos corrected

Recently the power of positive partial transpose preserving (PPTp) and no-signalling (NS) codes in quantum communication has been studied. We continue with this line of research and show that the NS/PPTp/NS$\cap$PPTp codes assisted zero-error quantum capacity depends only on the non-commutative bipartite graph of the channel and the one-shot case can be computed efficiently by semidefinite programming (SDP). As an example, the activated PPTp codes assisted zero-error quantum capacity is carefully studied. We then present a general SDP upper bound $Q_\Gamma$ of quantum capacity and show it is always smaller than or equal to the "Partial transposition bound" introduced by Holevo and Werner, and the inequality could be strict. This upper bound is found to be additive, and thus is an upper bound of the potential PPTp assisted quantum capacity as well. We further demonstrate that $Q_\Gamma$ is strictly better than several previously known upper bounds for an explicit class of quantum channels. Finally, we show that $Q_\Gamma$ can be used to bound the super-activation of quantum capacity., Comment: 5 pages, 1 figure, v2 has improved presentation, many typos corrected

Given a set of multipartite entangled states, can we find a common state to prepare them by local operations and classical communication? Such a state, if exists, will be a common resource for the given set of states. We completely solve this problem for bipartite pure states case by explicitly constructing a unique optimal common resource state for any given set of states. In the multipartite setting, the general problem becomes quite complicated, and we focus on finding nontrivial common resources for the whole multipartite state space of given dimensions. We show that GHZ_3 is a nontrivial common resource for three-qubit systems., Comment: 11 pages (7 pages for appendix)

We study the activated quantum no-signalling-assisted zero-error classical capacity by first allowing the assistance from some noiseless forward communication channel and later paying back the cost of the helper. This activated communication model considers the additional forward noiseless channel as a catalyst for communication. First, we show that the one-shot activated capacity can be formulated as a semidefinite program and we derive a number of striking properties of this capacity. We further present a sufficient condition under which a noisy channel can be activated. Second, we show that one-bit noiseless classical communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity, or the semidefinite (or fractional) packing number. Third, we prove that the asymptotic activated capacity cannot exceed the original asymptotic capacity of any quantum channel. We also show that the asymptotic no-signalling-assisted zero-error capacity does not equal to the semidefinite packing number for quantum channels, which differs from the case of classical-quantum channels., Comment: v2 improved presentation, comments are welcome!

We show that for any graph $G$, by considering "activation" through the strong product with another graph $H$, the relation $\alpha(G) \leq \vartheta(G)$ between the independence number and the Lov\'{a}sz number of $G$ can be made arbitrarily tight: Precisely, the inequality \[ \alpha(G \times H) \leq \vartheta(G \times H) = \vartheta(G)\,\vartheta(H) \] becomes asymptotically an equality for a suitable sequence of ancillary graphs $H$. This motivates us to look for other products of graph parameters of $G$ and $H$ on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that \[ \alpha(G \times H) \leq \alpha^*(G)\,\alpha(H), \] with the fractional packing number $\alpha^*(G)$, and for every $G$ there exists $H$ that makes the above an equality; conversely, for every graph $H$ there is a $G$ that attains equality. These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which $\alpha$ and $\alpha^*$ are dual to each other, and the Lov\'{a}sz number $\vartheta$ is self-dual. We also show duality of Schrijver's and Szegedy's variants $\vartheta^-$ and $\vartheta^+$ of the Lov\'{a}sz number, and explore analogous notions for the chromatic number under strong and disjunctive graph products., Comment: 16 pages, submitted to Discrete Applied Mathematics for a special issue in memory of Levon Khachatrian; v2 has a full proof of the duality between theta+ and theta- and a new author, some new references, and we corrected several small errors and typos

Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classical-quantum channels with a confusability graph $G$, is exactly $\log \vartheta(G)$, where $\vartheta(G)$ is the celebrated Lov\'{a}sz theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph $G$ defined by equal-sized cyclotomic cosets, is $\log \lfloor \vartheta(G) \rfloor$, which further implies that its asymptotic capacity is $\log \vartheta(G)$. This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This endows the Lov\'{a}sz $\theta$ function with a more straightforward operational meaning., Comment: 13 pages, 6 figures

We initiate the study of zero-error communication via quantum channels when the receiver and sender have at their disposal a noiseless feedback channel of unlimited quantum capacity, generalizing Shannon's zero-error communication theory with instantaneous feedback. We first show that this capacity is a function only of the linear span of Choi-Kraus operators of the channel, which generalizes the bipartite equivocation graph of a classical channel, and which we dub "non-commutative bipartite graph". Then we go on to show that the feedback-assisted capacity is non-zero (with constant activating noiseless communication) if and only if the non-commutative bipartite graph is non-trivial, and give a number of equivalent characterizations. This result involves a far-reaching extension of the "conclusive exclusion" of quantum states [Pusey/Barrett/Rudolph, Nature Phys. 8:475-478]. We then present an upper bound on the feedback-assisted zero-error capacity, motivated by a conjecture originally made by Shannon and proved later by Ahlswede. We demonstrate this bound to have many good properties, including being additive and given by a minimax formula. We also prove that this quantity is the entanglement-assisted capacity against an adversarially chosen channel from the set of all channels with the same Choi-Kraus span, which can also be interpreted as the feedback-assisted unambiguous capacity. The proof relies on a generalization of the "Postselection Lemma" [Christandl/Koenig/Renner, PRL 102:020504] that allows to reflect additional constraints, and which we believe to be of independent interest. We illustrate our ideas with a number of examples, including classical-quantum channels and Weyl diagonal channels, and close with an extensive discussion of open questions., Comment: 34 pages, 1 figure; v2 has improved presentation, numerous typos corrected and many more references; v3 equivalent to final, accepted journal version (IEEE Trans Inf Theory)

We study the one-shot zero-error classical capacity of a quantum channel assisted by quantum no-signalling correlations, and the reverse problem of exact simulation of a prescribed channel by a noiseless classical one. Quantum no-signalling correlations are viewed as two-input and two-output completely positive and trace preserving maps with linear constraints enforcing that the device cannot signal. Both problems lead to simple semidefinite programmes (SDPs) that depend only on the Kraus operator space of the channel. In particular, we show that the zero-error classical simulation cost is precisely the conditional min-entropy of the Choi-Jamiolkowski matrix of the given channel. The zero-error classical capacity is given by a similar-looking but different SDP; the asymptotic zero-error classical capacity is the regularization of this SDP, and in general we do not know of any simple form. Interestingly however, for the class of classical-quantum channels, we show that the asymptotic capacity is given by a much simpler SDP, which coincides with a semidefinite generalization of the fractional packing number suggested earlier by Aram Harrow. This finally results in an operational interpretation of the celebrated Lovasz $\vartheta$ function of a graph as the zero-error classical capacity of the graph assisted by quantum no-signalling correlations, the first information theoretic interpretation of the Lovasz number., Comment: 44 pages, 4 figures (eps); v2 has a new title, several small errors corrected and new results on channel simulation; v3 is the final (journal) version

In this paper, we study the entanglement transformation rate between multipartite states under stochastic local operations and classical communication (SLOCC). Firstly, we show that the entanglement transformation rate from $\ket{GHZ}=\tfrac{1}{\sqrt{2}}(\ket{000}+\ket{111})$ to $\ket{W}=\tfrac{1}{\sqrt{3}}(\ket{100}+\ket{010}+\ket{001})$ is 1, that is, one can obtain 1 copy of $W$-state, from 1 copy of $GHZ$-state by SLOCC, asymptotically. We then generalize this result to a lower bound on the rate that from $N$-partite $GHZ$-state to Dicke states. For some special cases, the optimality of this bound is proved. We then discuss the tensor rank of matrix permanent by evaluating the the tensor rank of Dicke state., Comment: 6 Pages, comments welcome

In this paper we consider the conditions under which a given ensemble of two-qubit states can be optimally distinguished by local operations and classical communication (LOCC). We begin by completing the \emph{perfect} distinguishability problem of two-qubit ensembles - both for separable operations and LOCC - by providing necessary and sufficient conditions for the perfect discrimination of one pure and one mixed state. Then for the well-known task of minimum error discrimination, it is shown that \textit{almost all} two-qubit ensembles consisting of three pure states cannot be optimally discriminated using LOCC. This is surprising considering that \textit{any} two pure states can be distinguished optimally by LOCC. Special attention is given to ensembles that lack entanglement, and we prove an easy sufficient condition for when a set of three product states cannot be optimally distinguished by LOCC, thus providing new examples of the phenomenon known as "non-locality without entanglement". We next consider an example of $N$ parties who each share the same state but who are ignorant of its identity. The state is drawn from the rotationally invariant "trine ensemble", and we establish a tight connection between the $N$-copy ensemble and Shor's "lifted" single-copy ensemble. For any finite $N$, we prove that optimal identification of the states cannot be achieved by LOCC; however as $N\to\infty$, LOCC can indeed discriminate the states optimally. This is the first result of its kind. Finally, we turn to the task of unambiguous discrimination and derive new lower bounds on the LOCC inconclusive probability for symmetric states. When applied to the double trine ensemble, this leads to a rather different distinguishability character than when the minimum-error probability is considered.

In this paper, we settle the long-standing open problem of the minimum cost of two-qubit gates for simulating a Toffoli gate. More precisely, we show that five two-qubit gates are necessary. Before our work, it is known that five gates are sufficient and only numerical evidences have been gathered, indicating that the five-gate implementation is necessary. The idea introduced here can also be used to solve the problem of optimal simulation of three-qubit control phase introduced by Deutsch in 1989., Comment: 5 Pages, comments welcome

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 [M. Horodecki $et. al$, Phys. Rev. Lett. 90, 047902(2003)] showing a limitation of their method for detecting nondistinguishability. (2). We show that a maximally entangled state and its orthogonal complement, no matter how many copies are supplied, can not be distinguished by PPT POVMs, even unambiguously. This result is much stronger than the previous known ones \cite{DUAN06,BAN11}. (3). We study the entanglement cost of distinguishing quantum states. It is proved that $\sqrt{2/3}\ket{00}+\sqrt{1/3}\ket{11}$ is sufficient and necessary for distinguishing three Bell states by PPT POVMs. An upper bound of entanglement cost of distinguishing a $d\otimes 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 LOCC. We further observe that a two-qubit maximally entangled state is always enough for distinguishing a $d\otimes d$ pure state and its orthogonal complement by 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\otimes 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 $\mathcal{O}(\frac{\log d}{d})$., Comment: Revtex4, 10 pages, no figures. Presented at AQIS12 as a long talk. Comments are welcome

Motivated by the recent resolution of Asymptotic Quantum Birkhoff Conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebras, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC. We also point out an interesting connection between the Grothendieck's inequality and AQBC., Comment: Revtex4, 13 pages, no figures. Preliminary versions presented at AQIS'2011 and QIP'2012

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\otimes d$ orthogonal maximally entangled states for some positive integer $d$. We further show that a $2\otimes 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 $\mathrm{K}$ consisting of four locally indistinguishable states such that $\mathrm{K}^{\otimes m}$ (with $4^m$ 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., Comment: 6 pages. Comments are welcome

This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold: 1. Sharir, Pnueli and Hart [SIAM J. Comput. 13(1984)292-314] presented a general method for proving properties of probabilistic programs, in which a probabilistic program is modeled by a Markov chain and an assertion on the output distribution is extended into an invariant assertion on all intermediate distributions. Their method is essentially a probabilistic generalization of the classical Floyd inductive assertion method. In this paper, we consider quantum programs modeled by quantum Markov chains which are defined by super-operators. It is shown that the Sharir-Pnueli-Hart method can be elegantly generalized to quantum programs by exploiting the Schr\"odinger-Heisenberg duality between quantum states and observables. In particular, a completeness theorem for the Sharir-Pnueli-Hart verification method of quantum programs is established. 2. As indicated by the completeness theorem, the Sharir-Pnueli-Hart method is in principle effective for verifying all properties of quantum programs that can be expressed in terms of Hermitian operators (observables). But it is not feasible for many practical applications because of the complicated calculation involved in the verification. For the case of finite-dimensional state spaces, we find a method for verification of quantum programs much simpler than the Sharir-Pnueli-Hart method by employing the matrix representation of super-operators and Jordan decomposition of matrices. In particular, this method enables us to compute easily the average running time and even to analyze some interesting long-run behaviors of quantum programs in a finite-dimensional state space.

A subspace of a multipartite Hilbert space is called \textit{locally indistinguishable} if any orthogonal basis of this subspace cannot be perfectly distinguished by local operations and classical communication. Previously it was shown that any $m\otimes n$ bipartite system such that $m>2$ and $n>2$ has a locally indistinguishable subspace. However, it has been an open problem since 2005 whether there is a locally indistinguishable bipartite subspace with a qubit subsystem. We settle this problem by showing that any $2\otimes n$ bipartite subspace is locally distinguishable in the sense it contains a basis perfectly distinguishable by LOCC. As an interesting application, we show that any quantum channel with two Kraus operations has optimal environment-assisted classical capacity., Comment: 3 pages (Revtex 4).Comments are welcomed

We study optimal perfect distinguishability between a unitary and a general quantum operation. In 2-dimensional case we provide a simple sufficient and necessary condition for sequential perfect distinguishability and an analytical formula of optimal query time. We extend the sequential condition to general d-dimensional case. Meanwhile, we provide an upper bound and a lower bound for optimal sequential query time. In the process a new iterative method is given, the most notable innovation of which is its independence to auxiliary systems or entanglement. Following the idea, we further obtain an upper bound and a lower bound of (entanglement-assisted) q-maximal fidelities between a unitary and a quantum operation. Thus by the recursion in [1] an upper bound and a lower bound for optimal general perfect discrimination are achieved. Finally our lower bound result can be extended to the case of arbitrary two quantum operations., Comment: 11 pages, 0 figures. Comments are welcome

In this paper we introduce a novel notion of probabilistic bisimulation for quantum processes and prove that it is congruent with respect to various process algebra combinators including parallel composition even when both classical and quantum communications are present. We also establish some basic algebraic laws for this bisimulation. In particular, we prove uniqueness of the solutions to recursive equations of quantum processes, which provides a powerful proof technique for verifying complex quantum protocols., Comment: Journal version

One-way quantum computing achieves the full power of quantum computation by performing single particle measurements on some many-body entangled state, known as the resource state. As single particle measurements are relatively easy to implement, the preparation of the resource state becomes a crucial task. An appealing approach is simply to cool a strongly correlated quantum many-body system to its ground state. In addition to requiring the ground state of the system to be universal for one-way quantum computing, we also want the Hamiltonian to have non-degenerate ground state protected by a fixed energy gap, to involve only two-body interactions, and to be frustration-free so that measurements in the course of the computation leave the remaining particles in the ground space. Recently, significant efforts have been made to the search of resource states that appear naturally as ground states in spin lattice systems. The approach is proved to be successful in spin-5/2 and spin-3/2 systems. Yet, it remains an open question whether there could be such a natural resource state in a spin-1/2, i.e., qubit system. Here, we give a negative answer to this question by proving that it is impossible for a genuinely entangled qubit states to be a non-degenerate ground state of any two-body frustration-free Hamiltonian. What is more, we prove that every spin-1/2 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states, a stronger result that is interesting independent of the context of one-way quantum computing., Comment: 5 pages, 1 figure

The tensor rank (also known as generalized Schmidt rank) of multipartite pure states plays an important role in the study of entanglement classifications and transformations. We employ powerful tools from the theory of homogeneous polynomials to investigate the tensor rank of symmetric states such as the tripartite state $\ket{W_3}=\tfrac{1}{\sqrt{3}}(\ket{100}+\ket{010}+\ket{001})$ and its $N$-partite generalization $\ket{W_N}$. Previous tensor rank estimates are dramatically improved and we show that (i) three copies of $\ket{W_3}$ has rank either 15 or 16, (ii) two copies of $\ket{W_N}$ has rank $3N-2$, and (iii) $n$ copies of $\ket{W_N}$ has rank O(N). A remarkable consequence of these results is that certain multipartite transformations, impossible even probabilistically, can become possible when performed in multiple copy bunches or when assisted by some catalyzing state. This effect is impossible for bipartite pure states., Comment: PhysRevLett.105.200501

We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain operator space as the quantum generalisation of the adjacency matrix, in terms of which the plain, quantum and entanglement-assisted capacity can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovasz' famous theta function, as the norm-completion (or stabilisation) of a "naive" generalisation of theta. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite programme, whose dual we write down explicitly, and that it is multiplicative with respect to the natural (strong) graph product. We explore various other properties of the new quantity, which reduces to Lovasz' original theta in the classical case, give several applications, and propose to study the operator spaces associated to channels as "non-commutative graphs", using the language of Hilbert modules., Comment: 24 pages: v2 has added discussion and more details in section 7.

Measurement based quantum computation (MBQC), which requires only single particle measurements on a universal resource state to achieve the full power of quantum computing, has been recognized as one of the most promising models for the physical realization of quantum computers. Despite considerable progress in the last decade, it remains a great challenge to search for new universal resource states with naturally occurring Hamiltonians, and to better understand the entanglement structure of these kinds of states. Here we show that most of the resource states currently known can be reduced to the cluster state, the first known universal resource state, via adaptive local measurements at a constant cost. This new quantum state reduction scheme provides simpler proofs of universality of resource states and opens up plenty of space to the search of new resource states, including an example based on the one-parameter deformation of the AKLT state studied in [Commun. Math. Phys. 144, 443 (1992)] by M. Fannes et al. about twenty years ago., Comment: 5 pages

We construct new families of multi-error-correcting quantum codes for the amplitude damping channel. Our key observation is that, with proper encoding, two uses of the amplitude damping channel simulate a quantum erasure channel. This allows us to use concatenated codes with quantum erasure-correcting codes as outer codes for correcting multiple amplitude damping errors. Our new codes are degenerate stabilizer codes and have parameters which are better than the amplitude damping codes obtained by any previously known construction., Comment: 5 pages. Submitted to ISIT 2010

A bipartite state which is secretly chosen from a finite set of known entangled pure states cannot be immediately useful in standard quantum information processing tasks. To effectively make use of the entanglement contained in this unknown state, we introduce a new way to locally manipulate the original quantum system: either identify the state successfully or distill some pure entanglement. Remarkably, if many copies are available, we show that any finite set of entangled pure states, whatever orthogonal or not, can be locally distinguished in this way, which further implies that pure entanglement can be deterministically extracted from unknown pure entanglement. These results make it clear why a large class of entangled bipartite quantum operations including unitary operations and measurements that are globally distinguishable can also be locally distinguishable: they can generate pure entanglement consistently., Comment: 7 pages. Comments are welcome

For a multipartite quantum system of the dimension $d_1\otimes d_2\otimes... d_n$, $d_1\ge d_2\ge...\ge d_n$, is there an entangled state {\em maximum} in the sense that all other states in the system can be obtained from the state through local quantum operations and classical communications (LOCC)? When $d_1\ge\Pi_{i=2}^n d_i$, such state exists. We show that this condition is also necessary. Our proof, somewhat surprisingly, uses results from algebraic complexity theory., Comment: 10 pages, no figure. We know the answer is quite simple, but the proof is somewhat involved. Comments are welcome

Tensor rank refers to the number of product states needed to express a given multipartite quantum state. Its non-additivity as an entanglement measure has recently been observed. In this note, we estimate the tensor rank of multiple copies of the tripartite state $\ket{W}=\tfrac{1}{\sqrt{3}}(\ket{100}+\ket{010}+\ket{001})$. Both an upper bound and a lower bound of this rank are derived. In particular, it is proven that the tensor rank of $\ket{W}^{\otimes 2}$ is seven, thus resolving a previously open problem. Some implications of this result are discussed in terms of transformation rates between $\ket{W}^{\otimes n}$ and multiple copies of the state $\ket{GHZ}=\tfrac{1}{\sqrt{2}}(\ket{000}+\ket{111})$., Comment: Comments: 3 pages (Revtex 4). Minor corrections to Theorem 1. Presentation refined. Main results unchanged. Comments are welcome

We consider the problem of deciding if a given three-party entangled pure state can be converted, with a non-zero success probability, into a given two-party pure state through local quantum operations and classical communication. We show that this question is equivalent to the well-known computational problem of deciding if a multivariate polynomial is identically zero. Efficient randomized algorithms developed to study the latter can thus be applied to the question of tripartite to bipartite entanglement transformations.

We provide a feasible necessary and sufficient condition for when an unknown quantum operation (quantum device) secretely selected from a set of known quantum operations can be identified perfectly within a finite number of queries, and thus complete the characterization of the perfect distinguishability of quantum operations. We further design an optimal protocol which can achieve the perfect discrimination between two quantum operations by a minimal number of queries. Interestingly, employing the techniques from the theory of $q$-numerical range we find that an optimal perfect discrimination between two isometries is always achievable without using auxiliary systems or entanglement., Comment: 6.25 pages (Revtex 4), a preliminary version. Comments are welcome

A $2\otimes 2$ unitary operation is called a perfect entangler if it can generate a maximally entangled state from some unentangled input. We study the following question: How many runs of a given two-qubit entangling unitary operation is required to simulate some perfect entangler with one-qubit unitary operations as free resources? We completely solve this problem by presenting an analytical formula for the optimal number of runs of the entangling operation. Our result reveals an entanglement strength of two-qubit unitary operations., Comment: 4 pages, Comments are welcomed;v2 : more discussions with previous related works, main results unchanged, submitted to PRA

We study various super-activation effects in the following zero-error communication scenario: One sender wants to send classical or quantum information through a noisy quantum channel to one receiver with zero probability of error. First we show that there are quantum channels of which a single use is not able to transmit classical information perfectly yet two uses can. This is achieved by employing entangled input states between different uses of the given channel and thus cannot happen for classical channels. Second we exhibit a class of quantum channel with vanishing zero-error classical capacity such that when a noiseless qubit channel or one ebit shared entanglement are available, it can be used to transmit $\log_2 d$ noiseless qubits, where 2d is the dimension of input state space. Third we further construct quantum channels with vanishing zero-error classical capacity when assisted with classical feedback can be used to transmit both classical and quantum information perfectly. These striking findings not only indicate both the zero-error quantum and classical capacities of quantum channels satisfy a strong super-additivity beyond any classical channels, but also highlight the activation power of auxiliary physical resources in zero-error communication., Comment: 11 pages, 2 eps figures. Results in Sec. IV partially overlap with an indepdent work arXiv:0906.2547. See the "Noted Added" para. in Sec. VIII for details