• ### Characterization of multipartite entanglement in terms of local transformations(1401.2627)

Aug. 31, 2018 quant-ph
The degree of the generators of invariant polynomial rings of is a long standing open problem since the very initial study of the invariant theory in the 19th century. Motivated by its significant role in characterizing multipartite entanglement, we study the invariant polynomial rings of local unitary group---the tensor product of unitary group, and local general linear group---the tensor product of general linear group. For these two groups, we prove polynomial upper bounds on the degree of the generators of invariant polynomial rings. On the other hand, systematic methods are provided to to construct all homogenous polynomials that are invariant under these two groups for any fixed degree. Thus, our results can be regarded as a complete characterization of the invariant polynomial rings. As an interesting application, we show that multipartite entanglement is additive in the sense that two multipartite states are local unitary equivalent if and only if $r$-copies of them are LU equivalent for some $r$.
• ### Quantum Coupling and Strassen Theorem(1803.10393)

March 28, 2018 quant-ph, cs.LO
We introduce a quantum generalisation of the notion of coupling in probability theory. Several interesting examples and basic properties of quantum couplings are presented. In particular, we prove a quantum extension of Strassen theorem for probabilistic couplings, a fundamental theorem in probability theory that can be used to bound the probability of an event in a distribution by the probability of an event in another distribution coupled with the first.
• ### A New Class of Criteria for Tripartite Marginal Problem(1803.02673)

March 1, 2018 quant-ph
The question of whether given density operators for subsystems of a multipartite quantum system are compatible to one common total density operator is known as the quantum marginal problem. In this paper, we focus on its tripartite version that of determining whether there exists tripartite quantum state with bipartite reduced density matrices equal to the given bipartite states. We first study the bipartite marginal problem and find out there is a "duality" relation: The distance between the marginal states is at most the fidelity between the probability distributions generated by measuring the bipartite state with measurements onto the symmetric (anti-symmetric) space and antisymmetric (symmetric) space; the fidelity between the marginal states is at least the distance between the probability distributions by measuring the bipartite state with measurements onto the symmetric (anti-symmetric) space and antisymmetric (symmetric) space. Then we generalize it into the tripartite version, and build a new class of necessary criteria for the tripartite marginal problem.
• ### Entanglement Verification, with or without tomography(1802.02648)

Feb. 7, 2018 quant-ph
Multipartite entanglement has been widely regarded as key resources in distributed quantum computing, for instance, multi-party cryptography, measurement based quantum computing, quantum algorithms. It also plays a fundamental role in quantum phase transitions, even responsible for transport efficiency in biological systems. Certifying multipartite entanglement is generally a fundamental task. Since an $N$ qubit state is parameterized by $4^N-1$ real numbers, one is interested to design a measurement setup that reveals multipartite entanglement with as little effort as possible, at least without fully revealing the whole information of the state, the so called "tomography", which requires exponential energy. In this paper, we study this problem of certifying entanglement without tomography in the constrain that only single copy measurements can be applied. This task is formulate as a membership problem related to a dividing quantum state space, therefore, related to the geometric structure of state space. We show that universal entanglement detection among all states can never be accomplished without full state tomography. Moreover, we show that almost all multipartite correlation, include genuine entanglement detection, entanglement depth verification, requires full state tomography. However, universal entanglement detection among pure states can be much more efficient, even we only allow local measurements. Almost optimal local measurement scheme for detecting pure states entanglement is provided.
• ### Chernoff Bound for Quantum Operations is Faithful(1705.01642)

May 3, 2017 quant-ph
We consider the problem of testing two quantum hypotheses of quantum operations in the setting of many uses where an arbitrary prior distribution is given. The concept of the Chernoff bound for quantum operations is investigated to track the minimal average probability of error of discriminating two quantum operations asymptotically. We show that the Chernoff bound is faithful in the sense that it is finite if and only if the two quantum operations can not be distinguished perfectly. More precisely, upper bounds of the Chernoff bound for quantum operations are provided. We then generalize these results to multiple Chernoff bound for quantum operations.
• ### Sample-optimal tomography of quantum states(1508.01797)

Jan. 24, 2017 quant-ph, cs.IT, math.IT
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 $\epsilon$ in trace distance required $O(dr^2/\epsilon^2)$ copies for a $d$-dimensional density matrix of rank $r$. Here, we give a theoretical measurement scheme (POVM) that requires $O (dr/ \delta ) \ln (d/\delta)$ copies of $\rho$ to error $\delta$ in infidelity, and a matching lower bound up to logarithmic factors. This implies $O( (dr / \epsilon^2) \ln (d/\epsilon) )$ copies suffice to achieve error $\epsilon$ in trace distance. We also prove that for independent (product) measurements, $\Omega(dr^2/\delta^2) / \ln(1/\delta)$ copies are necessary in order to achieve error $\delta$ in infidelity. For fixed $d$, our measurement can be implemented on a quantum computer in time polynomial in $n$.
• ### Exponential Separation of Quantum Communication and Classical Information(1611.08946)

Nov. 28, 2016 quant-ph, cs.IT, math.IT, cs.CC
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
• ### Joint product numerical range and geometry of reduced density matrices(1606.07422)

June 23, 2016 quant-ph
The reduced density matrices of a many-body quantum system form a convex set, whose three-dimensional projection $\Theta$ is convex in $\mathbb{R}^3$. The boundary $\partial\Theta$ of $\Theta$ may exhibit nontrivial geometry, in particular ruled surfaces. Two physical mechanisms are known for the origins of ruled surfaces: symmetry breaking and gapless. In this work, we study the emergence of ruled surfaces for systems with local Hamiltonians in infinite spatial dimension, where the reduced density matrices are known to be separable as a consequence of the quantum de Finetti's theorem. This allows us to identify the reduced density matrix geometry with joint product numerical range $\Pi$ of the Hamiltonian interaction terms. We focus on the case where the interaction terms have certain structures, such that ruled surface emerge naturally when taking a convex hull of $\Pi$. We show that, a ruled surface on $\partial\Theta$ sitting in $\Pi$ has a gapless origin, otherwise it has a symmetry breaking origin. As an example, we demonstrate that a famous ruled surface, known as the oloid, is a possible shape of $\Theta$, with two boundary pieces of symmetry breaking origin separated by two gapless lines.
• ### Physical origins of ruled surfaces on the reduced density matrices geometry(1605.06357)

May 20, 2016 quant-ph
The reduced density matrices (RDMs) of many-body quantum states form a convex set. The boundary of low dimensional projections of this convex set may exhibit nontrivial geometry such as ruled surfaces. In this paper, we study the physical origins of these ruled surfaces for bosonic systems. The emergence of ruled surfaces was recently proposed as signatures of symmetry-breaking phase. We show that, apart from being signatures of symmetry-breaking, ruled surfaces can also be the consequence of gapless quantum systems by demonstrating an explicit example in terms of a two-mode Ising model. Our analysis was largely simplified by the quantum de Finetti's theorem---in the limit of large system size, these RDMs are the convex set of all the symmetric separable states. To distinguish ruled surfaces originated from gapless systems from those caused by symmetry-breaking, we propose to use the finite size scaling method for the corresponding geometry. This method is then applied to the two-mode XY model, successfully identifying a ruled surface as the consequence of gapless systems.
• ### Quantum State and Process Tomography via Adaptive Measurements(1604.06277)

April 21, 2016 quant-ph
We investigate quantum state tomography (QST) for pure states and quantum process tomography (QPT) for unitary channels via $adaptive$ measurements. For a quantum system with a $d$-dimensional Hilbert space, we first propose an adaptive protocol where only $2d-1$ measurement outcomes are used to accomplish the QST for $all$ pure states. This idea is then extended to study QPT for unitary channels, where an adaptive unitary process tomography (AUPT) protocol of $d^2+d-1$ measurement outcomes is constructed for any unitary channel. We experimentally implement the AUPT protocol in a 2-qubit nuclear magnetic resonance system. We examine the performance of the AUPT protocol when applied to Hadamard gate, $T$ gate ($\pi/8$ phase gate), and controlled-NOT gate, respectively, as these gates form the universal gate set for quantum information processing purpose. As a comparison, standard QPT is also implemented for each gate. Our experimental results show that the AUPT protocol that reconstructing unitary channels via adaptive measurements significantly reduce the number of experiments required by standard QPT without considerable loss of fidelity.
• ### Dichotomy of entanglement depth for symmetric states(1603.03245)

April 15, 2016 quant-ph, cond-mat.quant-gas
Entanglement depth characterizes the minimal number of particles in a system that are mutually entangled. For symmetric states, we show that there is a dichotomy for entanglement depth: an $N$-particle symmetric state is either fully separable, or fully entangled---the entanglement depth is either $1$ or $N$. This property is even stable under non-symmetric noise. We propose an experimentally accessible method to detect entanglement depth in atomic ensembles based on a bound on the particle number population of Dicke states, and demonstrate that the entanglement depth of some Dicke states, for example the twin Fock state, is very stable even under a large arbitrary noise. Our observation can be applied to atomic Bose-Einstein condensates to infer that these systems can be highly entangled with the entanglement depth that is of the order of the system size (i.e. several thousands of atoms).
• ### Quantum state tomography via reduced density matrices(1604.02046)

April 7, 2016 quant-ph
Quantum state tomography via local measurements is an efficient tool for characterizing quantum states. However it requires that the original global state be uniquely determined (UD) by its local reduced density matrices (RDMs). In this work we demonstrate for the first time a class of states that are UD by their RDMs under the assumption that the global state is pure, but fail to be UD in the absence of that assumption. This discovery allows us to classify quantum states according to their UD properties, with the requirement that each class be treated distinctly in the practice of simplifying quantum state tomography. Additionally we experimentally test the feasibility and stability of performing quantum state tomography via the measurement of local RDMs for each class. These theoretical and experimental results advance the project of performing efficient and accurate quantum state tomography in practice.
• ### Quantum Capacities for Entanglement Networks(1602.00401)

Feb. 1, 2016 quant-ph, cs.IT, math.IT
We discuss quantum capacities for two types of entanglement networks: $\mathcal{Q}$ for the quantum repeater network with free classical communication, and $\mathcal{R}$ for the tensor network as the rank of the linear operation represented by the tensor network. We find that $\mathcal{Q}$ always equals $\mathcal{R}$ in the regularized case for the samenetwork graph. However, the relationships between the corresponding one-shot capacities $\mathcal{Q}_1$ and $\mathcal{R}_1$ are more complicated, and the min-cut upper bound is in general not achievable. We show that the tensor network can be viewed as a stochastic protocol with the quantum repeater network, such that $\mathcal{R}_1$ is a natural upper bound of $\mathcal{Q}_1$. We analyze the possible gap between $\mathcal{R}_1$ and $\mathcal{Q}_1$ for certain networks, and compare them with the one-shot classical capacity of the corresponding classical network.
• ### Tomography is necessary for universal entanglement detection with single-copy observables(1511.00581)

Nov. 2, 2015 quant-ph
Entanglement, one of the central mysteries of quantum mechanics, plays an essential role in numerous applications of quantum information theory. A natural question of both theoretical and experimental importance is whether universal entanglement detection is possible without full state tomography. In this work, we prove a no-go theorem that rules out this possibility for any non-adaptive schemes that employ single-copy measurements only. We also examine in detail a previously implemented experiment, which claimed to detect entanglement of two-qubit states via adaptive single-copy measurements without full state tomography. By performing the experiment and analyzing the data, we demonstrate that the information gathered is indeed sufficient to reconstruct the state. These results reveal a fundamental limit for single-copy measurements in entanglement detection, and provides a general framework to study the detection of other interesting properties of quantum states, such as the positivity of partial transpose and the $k$-symmetric extendibility.
• ### Detecting Consistency of Overlapping Quantum Marginals by Separability(1509.06591)

Sept. 23, 2015 quant-ph
The quantum marginal problem asks whether a set of given density matrices are consistent, i.e., whether they can be the reduced density matrices of a global quantum state. Not many non-trivial analytic necessary (or sufficient) conditions are known for the problem in general. We propose a method to detect consistency of overlapping quantum marginals by considering the separability of some derived states. Our method works well for the $k$-symmetric extension problem in general, and for the general overlapping marginal problems in some cases. Our work is, in some sense, the converse to the well-known $k$-symmetric extension criterion for separability.
• ### Maximum privacy without coherence, zero-error(1509.01300)

Sept. 3, 2015 quant-ph
We study the possible difference between the quantum and the private capacities of a quantum channel in the zero-error setting. For a family of channels introduced by arXiv:1312.4989, we demonstrate an extreme difference: the zero-error quantum capacity is zero, whereas the zero-error private capacity is maximum given the quantum output dimension.
• ### Discontinuity of Maximum Entropy Inference and Quantum Phase Transitions(1406.5046)

April 14, 2015 quant-ph, cond-mat.str-el
In this paper, we discuss the connection between two genuinely quantum phenomena --- the discontinuity of quantum maximum entropy inference and quantum phase transitions at zero temperature. It is shown that the discontinuity of the maximum entropy inference of local observable measurements signals the non-local type of transitions, where local density matrices of the ground state change smoothly at the transition point. We then propose to use the quantum conditional mutual information of the ground state as an indicator to detect the discontinuity and the non-local type of quantum phase transitions in the thermodynamic limit.
• ### Generalized Graph States Based on Hadamard Matrices(1502.07195)

Feb. 25, 2015 quant-ph, math-ph, math.MP
Graph states are widely used in quantum information theory, including entanglement theory, quantum error correction, and one-way quantum computing. Graph states have a nice structure related to a certain graph, which is given by either a stabilizer group or an encoding circuit, both can be directly given by the graph. To generalize graph states, whose stabilizer groups are abelian subgroups of the Pauli group, one approach taken is to study non-abelian stabilizers. In this work, we propose to generalize graph states based on the encoding circuit, which is completely determined by the graph and a Hadamard matrix. We study the entanglement structures of these generalized graph states, and show that they are all maximally mixed locally. We also explore the relationship between the equivalence of Hadamard matrices and local equivalence of the corresponding generalized graph states. This leads to a natural generalization of the Pauli $(X,Z)$ pairs, which characterizes the local symmetries of these generalized graph states. Our approach is also naturally generalized to construct graph quantum codes which are beyond stabilizer codes.
• ### Separability of Bosonic Systems(1501.02957)

Jan. 13, 2015 quant-ph
In this paper, we study the separability of quantum states in bosonic system. Our main tool here is the "separability witnesses", and a connection between "separability witnesses" and a new kind of positivity of matrices--- "Power Positive Matrices" is drawn. Such connection is employed to demonstrate that multi-qubit quantum states with Dicke states being its eigenvectors is separable if and only if two related Hankel matrices are positive semidefinite. By employing this criterion, we are able to show that such state is separable if and only if it's partial transpose is non-negative, which confirms the conjecture in [Wolfe, Yelin, Phys. Rev. Lett. (2014)]. Then, we present a class of bosonic states in $d\otimes d$ system such that for general $d$, determine its separability is NP-hard although verifiable conditions for separability is easily derived in case $d=3,4$.
• ### Limitations on separable measurements by convex optimization(1408.6981)

Aug. 29, 2014 quant-ph
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.
• ### Obtain $W$-state from three-qubit $GHZ$-state on rate 1(1309.4833)

April 21, 2014 quant-ph
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.
• ### Distinguishability of Quantum States by Positive Operator-Valued Measures with Positive Partial Transpose(1209.4222)

April 1, 2014 quant-ph
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})$.
• ### Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs(1402.5172)

Feb. 20, 2014 quant-ph, cs.LO, cs.PL
We extract a novel quantum programming paradigm - superposition of programs - from the design idea of a popular class of quantum algorithms, namely quantum walk-based algorithms. The generality of this paradigm is guaranteed by the universality of quantum walks as a computational model. A new quantum programming language QGCL is then proposed to support the paradigm of superposition of programs. This language can be seen as a quantum extension of Dijkstra's GCL (Guarded Command Language). Surprisingly, alternation in GCL splits into two different notions in the quantum setting: classical alternation (of quantum programs) and quantum alternation, with the latter being introduced in QGCL for the first time. Quantum alternation is the key program construct for realizing the paradigm of superposition of programs. The denotational semantics of QGCL are defined by introducing a new mathematical tool called the guarded composition of operator-valued functions. Then the weakest precondition semantics of QGCL can straightforwardly derived. Another very useful program construct in realizing the quantum programming paradigm of superposition of programs, called quantum choice, can be easily defined in terms of quantum alternation. The relation between quantum choices and probabilistic choices is clarified through defining the notion of local variables. We derive a family of algebraic laws for QGCL programs that can be used in program verification, transformations and compilation. The expressive power of QGCL is illustrated by several examples where various variants and generalizations of quantum walks are conveniently expressed using quantum alternation and quantum choice. We believe that quantum programming with quantum alternation and choice will play an important role in further exploiting the power of quantum computing.
• ### Model checking quantum Markov chains(1205.2187)

Nov. 14, 2013 quant-ph, cs.LO
Although the security of quantum cryptography is provable based on the principles of quantum mechanics, it can be compromised by the flaws in the design of quantum protocols and the noise in their physical implementations. So, it is indispensable to develop techniques of verifying and debugging quantum cryptographic systems. Model-checking has proved to be effective in the verification of classical cryptographic protocols, but an essential difficulty arises when it is applied to quantum systems: the state space of a quantum system is always a continuum even when its dimension is finite. To overcome this difficulty, we introduce a novel notion of quantum Markov chain, specially suited to model quantum cryptographic protocols, in which quantum effects are entirely encoded into super-operators labelling transitions, leaving the location information (nodes) being classical. Then we define a quantum extension of probabilistic computation tree logic (PCTL) and develop a model-checking algorithm for quantum Markov chains.
• ### Orbit Problem Revisited(1302.0566)

Sept. 19, 2013 cs.CC
In this letter, we revisit the {\em orbit problem}, which was studied in \cite{HAR69,SHA79,KL86}. In \cite{KL86}, Kannan and Lipton proved that this problem is decidable in polynomial time. In this paper, we study the {\em approximate orbit problem}, and show that this problem is decidable except for one case.