## Biography

I received the BS and PhD from the Department of Computer Science and Technology, Tsinghua University, Beijing, China in the years of 2008 and 2013, respectively. I am currently a Senior Lecturer of the Centre for Quantum Software and Information (QSI), Faculty of Engineering and Information Technology (FEIT), University of Technology Sydney (UTS).

#### Can supervise: YES

#### Research Interests

Distributed quantum computing

Quantum network

Quantum logic

Quantum algorithms

#### Publications

Qiao, Y, Sun, X & Yu, N 2020, 'Local Equivalence of Multipartite Entanglement', *IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS*, vol. 38, no. 3, pp. 568-574.View/Download from: Publisher's site

Zhou, L, Ying, S, Yu, N & Ying, M 2020, 'Strassen's theorem for quantum couplings', *THEORETICAL COMPUTER SCIENCE*, vol. 802, pp. 67-76.View/Download from: Publisher's site

Zhou, L, Ying, S, Yu, N & Ying, M 2020, 'Strassen's theorem for quantum couplings', *Theoretical Computer Science*, vol. 802, pp. 67-76.View/Download from: Publisher's site

#### View description

© 2019 Elsevier B.V. Strassen's theorem for probabilistic couplings is 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. It has been widely applied in computer science for analysis of random algorithms, machine learning and verification of security and privacy protocols. We extend the coupling techniques in probability theory to quantum systems. A quantum generalisation of the notion of lifting, a coupling under certain constraints, is introduced. Several interesting examples and basic properties of quantum couplings and liftings are presented. Finally, a quantum extension of Strassen's theorem is established.

Chen, JY, Ji, Z, Liu, ZX, Qi, X, Yu, N, Zeng, B & Zhou, D 2017, 'Physical origins of ruled surfaces on the reduced density matrices geometry', *Science in China Series G: 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, AW, 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: 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, pp. 020401-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.

Chen, J, Guo, C, Ji, Z, Poon, YT, 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 R3. 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.

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: 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: Publisher's site

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

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.View/Download from: Publisher's site

Wang, HY, Zheng, WQ, Yu, NK, Li, KR, Lu, DW, Xin, T, Li, C, Ji, ZF, Kribs, D, Zeng, B, Peng, XH & Du, JF 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+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 (π/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.

Leung, D & Yu, N 2016, 'Maximum privacy without coherence, zero-error', *Journal of Mathematical Physics*, vol. 57, no. 9.View/Download from: 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.

Yu, N 2016, 'Separability of a mixture of Dicke states', *PHYSICAL REVIEW A*, vol. 94, no. 6.View/Download from: Publisher's site

Chen, J, Ji, Z, Li, CK, Poon, YT, 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: 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.

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: Publisher's site

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: Publisher's site

Cui, SX, Yu, N & Zeng, B 2015, 'Generalized graph states based on Hadamard matrices', *JOURNAL OF MATHEMATICAL PHYSICS*, vol. 56, no. 7.View/Download from: Publisher's site

Zhao, Y-Y, Yu, N-K, Kurzynski, P, Xiang, G-Y, Li, C-F & Guo, G-C 2015, 'Experimental realization of generalized qubit measurements based on quantum walks', *PHYSICAL REVIEW A*, vol. 91, no. 4.View/Download from: Publisher's site

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

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: 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: 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: 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.

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: 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.

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: 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: 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, 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: 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: 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, pp. 020506-020506.View/Download from: Publisher's site

#### View description

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⊗d orthogonal maximally entangled states for some positive integer d. We further show that a 2⊗2 maximally entangled state can be used to locally distinguish this set of states without being consumed, thus demonstrate a novel phenomenon of entanglement discrimination catalysis. Based on this set of states, we construct a new set K consisting of four locally indistinguishable states such that K(⊗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.

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: 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, Duan, R & Ying, M 2010, 'Optimal Simulation Of A Perfect Entangler', *Physical Review A*, vol. 81, no. 3, pp. 1-4.View/Download from: 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

Yu, N, Chitambar, EA, 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 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

Barthe, G, Hsu, J, Ying, M, Yu, N & Zhou, L 2020, 'Relational proofs for quantum programs', *Proceedings of the ACM on Programming Languages*, Association for Computing Machinery (ACM), pp. 1-29.View/Download from: Publisher's site

Zhou, L, Yu, N & Ying, M 2019, 'An Applied Quantum Hoare Logic', *PROCEEDINGS OF THE 40TH ACM SIGPLAN CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION (PLDI '19)*, 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) part of ACM's Federated Computing Research Conference (FCRC), ASSOC COMPUTING MACHINERY, Phoenix, AZ, pp. 1149-1162.View/Download from: Publisher's site

Leung, D, Touchette, D, Nayak, A, Yao, P, Shayeghi, A & Yu, N 2018, 'Capacity approaching coding for low noise interactive quantum communication', *Proceedings of the Annual ACM Symposium on Theory of Computing*, Symposium on the Theory of Computing, ACM, Los Angeles, CA, USA, pp. 926-939.View/Download from: Publisher's site

#### View description

© 2018 Copyright held by the owner/author(s). We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2−Θ(nϵ) and uses a qudit channel n 1 + Θ times, of which an fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O log log ϵ1 in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for low .

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*, Annual ACM SIGACT Symposium on Theory of Computing, ACM, Montreal, Canada, 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/2O(b)bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.

Cui, SX, 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: 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, AW, 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: 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.

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: 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.

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: 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.

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: 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: 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: 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.