#### Publications

Chen, J., Guo, C., Ji, Z., Poon, Y.T., Yu, N., Zeng, B. & Zhou, J. 2017, 'Joint product numerical range and geometry of reduced density matrices', *Science China: Physics, Mechanics and Astronomy*, vol. 60, no. 2.View/Download from: Publisher's site

#### View description

© 2016, Science China Press and Springer-Verlag Berlin Heidelberg. The reduced density matrices of a many-body quantum system form a convex set, whose three-dimensional projection is convex in R 3 . The boundary of 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 of the Hamiltonian interaction terms. We focus on the case where the interaction terms have certain structures, such that a ruled surface emerges naturally when taking a convex hull of . We show that, a ruled surface on sitting in 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 , with two boundary pieces of symmetry breaking origin separated by two gapless lines.

Chen, J.Y., Ji, Z., Liu, Z.X., Qi, X., Yu, N., Zeng, B. & Zhou, D. 2017, 'Physical origins of ruled surfaces on the reduced density matrices geometry', *Science China: Physics, Mechanics and Astronomy*, vol. 60, no. 2.View/Download from: Publisher's site

#### View description

© 2016, Science China Press and Springer-Verlag Berlin Heidelberg. 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.

Haah, J., Harrow, A.W., Ji, Z., Wu, X. & Yu, N. 2017, 'Sample-Optimal Tomography of Quantum States', *IEEE Transactions on Information Theory*, vol. 63, no. 9, pp. 5628-5641.View/Download from: UTS OPUS or Publisher's site

#### View description

© 1963-2012 IEEE. 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 to estimate \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.

Xin, T., Lu, D., Klassen, J., Yu, N., Ji, Z., Chen, J., Ma, X., Long, G., Zeng, B. & Laflamme, R. 2017, 'Quantum State Tomography via Reduced Density Matrices.', *Physical review letters*, vol. 118, no. 2, p. 020401.View/Download from: Publisher's site

#### View description

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 demonstrate the advantages and possible pitfalls of quantum state tomography with local measurements.

Yu, N., Duan, R. & Xu, Q. 2017, 'Bounds on the Distance Between a Unital Quantum Channel and the Convex Hull of Unitary Channels', *IEEE Transactions on Information Theory*, vol. 63, no. 2, pp. 1299-1310.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2016 IEEE. 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.

Chen, J., Ji, Z., Yu, N. & Zeng, B. 2016, 'Detecting consistency of overlapping quantum marginals by separability', *Physical Review A*, vol. 93, no. 3.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2016 American Physical Society. 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 nontrivial 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.

Chen, J.Y., Ji, Z., Yu, N. & Zeng, B. 2016, 'Entanglement depth for symmetric states', *Physical Review A*, vol. 94, no. 4.View/Download from: Publisher's site

#### View description

© 2016 American Physical Society. Entanglement depth characterizes the minimal number of particles in a system that are mutually entangled. For symmetric states, 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. We show that this dichotomy property for entangled symmetric states is even stable under nonsymmetric 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 on the order of the system size (i.e., several thousands of atoms).

Leung, D. & Yu, N. 2016, 'Maximum privacy without coherence, zero-error', *Journal of Mathematical Physics*, vol. 57, no. 9.View/Download from: UTS OPUS or Publisher's site

#### View description

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 Leung et al. [Phys. Rev. Lett. 113, 030512 (2014)], 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.

Lu, D., Xin, T., Yu, N., Ji, Z., Chen, J., Long, G., Baugh, J., Peng, X., Zeng, B. & Laflamme, R. 2016, 'Tomography is Necessary for Universal Entanglement Detection with Single-Copy Observables.', *Physical review letters*, vol. 116, no. 23, p. 230501.View/Download from: UTS OPUS or Publisher's site

#### View description

Entanglement, one of the central mysteries of quantum mechanics, plays an essential role in numerous tasks of quantum information science. A natural question of both theoretical and experimental importance is whether universal entanglement detection can be accomplished without full state tomography. In this Letter, we prove a no-go theorem that rules out this possibility for nonadaptive schemes that employ single-copy measurements only. We also examine a previously implemented experiment [H. Park et al., Phys. Rev. Lett. 105, 230404 (2010)], which claimed to detect entanglement of two-qubit states via adaptive single-copy measurements without full state tomography. In contrast, our simulation and experiment both support the opposite conclusion that the protocol, indeed, leads to full state tomography, which supplements our no-go theorem. These results reveal a fundamental limit of single-copy measurements in entanglement detection and provide a general framework of the detection of other interesting properties of quantum states, such as the positivity of partial transpose and the k-symmetric extendibility.

Wang, H.Y., Zheng, W.Q., Yu, N.K., Li, K.R., Lu, D.W., Xin, T., Li, C., Ji, Z.F., Kribs, D., Zeng, B., Peng, X.H. & Du, J.F. 2016, 'Quantum state and process tomography via adaptive measurements', *Science China: Physics, Mechanics and Astronomy*, vol. 59, no. 10.View/Download from: Publisher's site

#### View description

© 2016, Science China Press and Springer-Verlag Berlin Heidelberg.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 d2+d1 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 (/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.

Yu, N. 2016, 'Separability of a mixture of Dicke states', *Physical Review A*, vol. 94, no. 6.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2016 American Physical Society. The structural relation between multipartite entanglement and symmetry is one of the central mysteries of quantum mechanics. In this paper, we study the separability of quantum states in the bosonic system. We show that a mixture of multiqubit Dicke states is separable if and only if its partial transpose is positive semidefinite, which confirms the hypothesis of Wolfe and Yelin [E. Wolfe and S. F. Yelin, Phys. Rev. Lett. 112, 140402 (2014)PRLTAO0031-900710.1103/PhysRevLett.112.140402]. We generalize this result to a class of bosonic states in the d - d system; and for general d, we determine its separability is NP-hard although verifiable conditions for separability are easily derived when d=3,4.

Bandyopadhyay, S., Cosentino, A., Johnston, N., Russo, V., Watrous, J. & Yu, N. 2015, 'Limitations on separable measurements by convex optimization', *IEEE Transactions on Information Theory*, vol. 61, no. 6, pp. 3593-3604.View/Download from: UTS OPUS or Publisher's site

#### View description

© 1963-2012 IEEE. 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 o f 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.

Chen, J., Ji, Z., Li, C.K., Poon, Y.T., Shen, Y., Yu, N., Zeng, B. & Zhou, D. 2015, 'Discontinuity of maximum entropy inference and quantum phase transitions', *New Journal of Physics*, vol. 17, no. 8, pp. 1-19.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2015 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. 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 me asurements 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.

Chen, T., Yu, N. & Han, T. 2015, 'Continuous-time orbit problems are decidable in polynomial-time', *Information Processing Letters*, vol. 115, no. 1, pp. 11-14.View/Download from: UTS OPUS or Publisher's site

#### View description

We place the continuous-time orbit problem in P, sharpening the decidability result shown by Hainry [7]. © 2014 Published by Elsevier B.V.

Cui, S.X., Yu, N. & Zeng, B. 2015, 'Generalized graph states based on Hadamard matrices', *Journal of Mathematical Physics*, vol. 56, no. 7.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2015 AIP Publishing LLC. 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.

Yu, N. & Ying, M. 2015, 'Optimal simulation of Deutsch gates and the Fredkin gate', *PHYSICAL REVIEW A*, vol. 91, no. 3.View/Download from: Publisher's site

Zhao, Y.Y., Yu, N.K., Kurzyński, P., Xiang, G.Y., Li, C.F. & Guo, G.C. 2015, 'Experimental realization of generalized qubit measurements based on quantum walks', *Physical Review A - Atomic, Molecular, and Optical Physics*, vol. 91, no. 4.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2015 American Physical Society. We report an experimental implementation of a single-qubit generalized measurement scenario, the positive-operator valued measure (POVM), based on a quantum walk model. The qubit is encoded in a single-photon polarization. The photon performs a quantum walk on an array of optical elements, where the polarization-dependent translation is performed via birefringent beam displacers and a change of the polarization is implemented with the help of wave plates. We implement: (i) trine POVM, i.e., the POVM elements uniformly distributed on an equatorial plane of the Bloch sphere; (ii) symmetric-informationally-complete (SIC) POVM; and (iii) unambiguous discrimination of two nonorthogonal qubit states.

Li, Y., Yu, N. & Ying, M. 2014, 'Termination of nondeterministic quantum programs', *Acta Informatica*, vol. 51, pp. 1-24.View/Download from: Publisher's site

#### View description

We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.

Ying, M., Li, Y., Yu, N. & Feng, Y. 2014, 'Model-Checking Linear-Time Properties of Quantum Systems', *ACM TRANSACTIONS ON COMPUTATIONAL LOGIC*, vol. 15, no. 3.View/Download from: UTS OPUS or Publisher's site

Yu, N., Duan, R. & Ying, M. 2014, 'Distinguishability of Quantum States by Positive Operator-Valued Measures with Positive Partial Transpose', *IEEE Transactions on Information Theory*, vol. 60, no. 4, pp. 2069-2079.View/Download from: UTS OPUS or Publisher's site

#### View description

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})$.

Yu, N., Guo, C. & Duan, R. 2014, 'Obtaining a W state from a Greenberger-Horne-Zeilinger state via stochastic local operations and classical communication with a rate approaching unity', *Physical Review Letters*, vol. 112, no. 16.View/Download from: UTS OPUS or Publisher's site

#### View description

We introduce a notion of the entanglement transformation rate to characterize the asymptotic comparability of two multipartite pure entangled states under stochastic local operations and classical communication (SLOCC). For two well known SLOCC inequivalent three-qubit states |GHZ=(1/2)(|000+|111) and |W=(1/3)(|100+|010+|001), we show that the entanglement transformation rate from |GHZ to |W is exactly 1. That means that we can obtain one copy of the W state from one copy of the Greenberg-Horne-Zeilinger (GHZ) state by SLOCC, asymptotically. We then apply similar techniques to obtain a lower bound on the entanglement transformation rates from an N-partite GHZ state to a class of Dicke states, and prove the tightness of this bound for some special cases which naturally generalize the |W state. A new lower bound on the tensor rank of the matrix permanent is also obtained by evaluating the tensor rank of Dicke states. © 2014 American Physical Society.

Feng, Y., Yu, N. & Ying, M. 2013, 'Model Checking Quantum Markov Chains', *Journal of Computer and System Sciences*, vol. 79, no. 7, pp. 1181-1198.View/Download from: UTS OPUS or Publisher's site

#### View description

Although security of quantum cryptography is provable based on principles of quantum mechanics, it can be compromised by flaws in the design of quantum protocols. So, it is indispensable to develop techniques for verifying and debugging quantum cryptogra

Ying, M., Yu, N., Feng, Y. & Duan, R. 2013, 'Verification of quantum programs', *Science Of Computer Programming*, vol. 78, no. 9, pp. 1679-1700.View/Download from: UTS OPUS or Publisher's site

#### View description

This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold. Sharir, Pnueli and Hart [M. Sharir, A. Pnueli, S. Hart, Verification of probabilistic programs, SIAM Journal of Computing 13 (1984) 292314] 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 to 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 SharirPnueliHart method can be elegantly generalized to quantum programs by exploiting the SchrödingerHeisenberg duality between quantum states and observables. In particular, a completeness theorem for the SharirPnueliHart verification method of quantum programs is established.

Yu, N. 2013, 'Multipartite W-type State Is Determined By Its Single-particle Reduced Density Matrices Among All W-type States', *Physical Review A*, vol. 87, no. 5, pp. 1-3.View/Download from: UTS OPUS or Publisher's site

#### View description

It is known that the n-qubit W-type state is determined by its bipartite reduced density matrices. In this paper, we show that the multipartite W-type state is uniquely determined by its reduced density matrices among W-type states in the sense of local unitary equivalence.

Yu, N., Duan, R. & Ying, M. 2013, 'Five two-qubit gates are necessary for implementing the Toffoli gate', *PHYSICAL REVIEW A*, vol. 88, no. 1.View/Download from: UTS OPUS or Publisher's site

Ying, M., Feng, Y., Duan, R., Li, Y. & Yu, N. 2012, 'Quantum Programming: From Theories To Implementations', *Chinese Science Bulletin*, vol. 57, no. 16, pp. 1903-1909.View/Download from: UTS OPUS or Publisher's site

#### View description

This paper surveys the new field of programming methodology and techniques for future quantum computers, including design of sequential and concurrent quantum programming languages, their semantics and implementations. Several verification methods for qu

Yu, N., Duan, R. & Ying, M. 2012, 'Four Locally Indistinguishable Ququad-Ququad Orthogonal Maximally Entangled States', *PHYSICAL REVIEW LETTERS*, vol. 109, no. 2.View/Download from: UTS OPUS or Publisher's site

Yu, N., Duan, R. & Ying, M. 2011, 'Any 2 Circle Times N Subspace Is Locally Distinguishable', *Physical Review A*, vol. 84, no. 1, pp. 1-3.View/Download from: UTS OPUS or Publisher's site

#### View description

A subspace of a multipartite Hilbert space is said to be locally indistinguishable if any orthonormal basis of this subspace cannot be perfectly distinguished by local operations and classical communication. Previously it was shown that any m . n bipartite system with 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 in negative by showing that any 2 . n bipartite subspace contains a basis that is locally distinguishable. As an interesting application, we show that any quantum channel with two Kraus operators has optimal environment-assisted classical capacity.

Yu, N., Chitambar, E.A., Guo, C. & Duan, R. 2010, 'Tensor Rank Of The Tripartite State Vertical Bar W >(Circle Times N)', *Physical Review A*, vol. 81, no. 1, pp. 1-3.View/Download from: UTS OPUS

#### View description

Tensor rank refers to the number of product states needed to express a given multipartite quantum state. Its nonadditivity as an entanglement measure has recently been observed. In this Brief Report, we estimate the tensor rank of multiple copies of the

Yu, N., Duan, R. & Ying, M. 2010, 'Optimal Simulation Of A Perfect Entangler', *Physical Review A*, vol. 81, no. 3, pp. 1-4.View/Download from: UTS OPUS or Publisher's site

#### View description

A2 circle times 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 are required to

Anshu, A., Touchette, D., Yao, P. & Yu, N. 2017, 'Exponential separation of quantum communication and classical information', *Proceedings of the Annual ACM Symposium on Theory of Computing*, pp. 277-288.View/Download from: Publisher's site

#### View description

© 2017 ACM. 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. Motivated by the celebrated results of Ganor, Kol and Raz [FOCS 14, pp. 557-566, STOC 15, pp. 977-986] , and by Rao and Sinha [ECCC TR15-057], we use the Symmetric k-ary Pointer Jumping function, 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/2 O(b) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.

Cui, S.X., Ji, Z., Yu, N. & Zeng, B. 2016, 'Quantum Capacities for Entanglement Networks', *Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT)*, IEEE International Symposium on Information Theory, IEEE, Barcelona, Spain, pp. 1685-1689.View/Download from: UTS OPUS or Publisher's site

#### View description

We discuss quantum capacities for two types of entanglement networks: Q for the quantum repeater network with free classical communication, and R for the tensor network as the rank of the linear operation represented by the tensor network. We find that Q always equals R in the regularized case for the same network graph. However, the relationships between the corresponding one-shot capacities Q1 and R1 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 R1 is a natural upper bound of Q1. We analyze the possible gap between R1 and Q1 for certain networks, and compare them with the one-shot classical capacity of the corresponding classical network.

Haah, J., Harrow, A.W., Ji, Z., Wu, X. & Yu, N. 2016, 'Sample-optimal tomography of quantum states', *STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing*, ACM symposium on Theory of Computing, ACM, Cambridge, MA, USA, pp. 913-925.View/Download from: UTS OPUS or Publisher's site

#### View description

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(dr2/2) 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 / 2) 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/2)/ 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 (r2d/) 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.

Feng, Y., Yu, N. & Ying, M. 2013, 'Reachability Analysis of Recursive Quantum Markov Chains', *Lecture Notes in Computer Science*, International Symposium on Mathematical Foundations of Computer Science, Springer, IST Austria, pp. 385-396.View/Download from: UTS OPUS or Publisher's site

#### View description

We introduce the notion of recursive quantum Markov chain (RQMC) for analysing recursive quantum programs with procedure calls. RQMCs are natural extension of Etessami and Yannakakiss recursive Markov chains where the probabilities along transitions are replaced by completely positive and trace-nonincreasing super-operators on a state Hilbert space of a quantum system. We study the reachability problem for RQMCs and establish a reduction from it to computing the least solution of a system of polynomial equations in the semiring of super-operators. It is shown that for an important subclass of RQMCs, namely linear RQMCs, the reachability problem can be solved in polynomial time. For general case, technique of Newtonian program analysis recently developed by Esparza, Kiefer and Luttenberger is employed to approximate reachability super-operators. A polynomial time algorithm that computes the support subspaces of the reachability super-operators in general case is also proposed.

Qiao, Y., Sun, X. & Yu, N. 2013, 'Determinantal Complexities and Field Extensions', *LNCS - Algorithms and Computation - Proceedings of the 24th International Symposium, ISAAC 2013*, International Symposium on Algorithms and Computation, Springer, Hong Kong, pp. 119-129.View/Download from: UTS OPUS or Publisher's site

#### View description

Let F be a field of characteristic ??2. The determinantal complexity of a polynomial P?F[x1,,xn] is defined as the smallest size of a matrix M whose entries are linear polynomials of x i s over F, such that P=det(M) as polynomials in F[x1,,xn]. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem. Let K be an extension field of F; then P can be viewed as a polynomial over K. We are interested in the comparison between the determinantal complexity of P over K (denoted as dcK(P)), and that of P over F (denoted as dcF(P)). It is clear that dcK(P)=dcF(P), and the question is whether strict inequality can happen. In this note we consider polynomials defined over Q.

Ying, M., Feng, Y. & Yu, N. 2013, 'Quantum information-flow security - noninterference and access control', *Proceedings of the 2013 IEEE 26th Computer Security Foundations Symposium*, IEEE Computer Security Foundations Symposium, IEEE Computer Society, Tulane University, New Orleans, Louisiana, USA, pp. 130-144.View/Download from: UTS OPUS or Publisher's site

#### View description

Quantum cryptography has been extensively studied in the last twenty years, but information-flow security of quantum computing and communication systems has been almost untouched in the previous research. Due to the essential difference between classical and quantum systems, formal methods developed for classical systems, including probabilistic systems, cannot be directly applied to quantum systems. This paper defines an automata model in which we can rigorously reason about information-flow security of quantum systems. The model is a quantum generalisation of Goguen and Meseguer's noninterference. The unwinding proof technique for quantum noninterference is developed, and a certain compositionality of security for quantum systems is established. The proposed formalism is then used to prove security of access control in quantum systems.

Ying, S., Feng, Y., Yu, N. & Ying, M. 2013, 'Reachability probabilities of quantum Markov chains', *Lecture Notes in Computer Science*, International Conference on Concurrency Theory, Springer, University of Buenos Aires, Argentina, pp. 334-348.View/Download from: UTS OPUS or Publisher's site

#### View description

This paper studies three kinds of long-term behaviour, namely reachability, repeated reachability and persistence, of quantum Markov chains (qMCs). As a stepping-stone, we introduce the notion of bottom strongly connected component (BSCC) of a qMC and develop an algorithm for finding BSCC decompositions of the state space of a qMC. As the major contribution, several (classical) algorithms for computing the reachability, repeated reachability and persistence probabilities of a qMC are presented, and their complexities are analysed.

Yu, N. & Ying, M. 2012, 'Reachability and Termination Analysis of Concurrent Quantum Programs', *Lecture Notes in Computer Science*, International Conference on Concurrency Theory, Sringer-Verlag, Newcastle upon Tyne, UK, pp. 69-83.View/Download from: UTS OPUS or Publisher's site

#### View description

We introduce a Markov chain model of concurrent quantum programs. This model is a quantum generalization of Hart, Sharir and Pnuelis probabilistic concurrent programs. Some characterizations of the reachable space, uniformly repeatedly reachable space and termination of a concurrent quantum program are derived by the analysis of their mathematical structures. Based on these characterizations, algorithms for computing the reachable space and uniformly repeatedly reachable space and for deciding the termination are given.