# Nengkun Yu

**Chancellor's Postdoctoral Research Fellow,**A/DRsch Centre for Quantum Software and Information

**Core Member,**Centre for Quantum Software and Information

Ba CompSci, PhD of Phil

## Conferences

Haah, J., Harrow, A.W., Ji, Z., Wu, X. & Yu, N. 2016, 'Sample-optimal tomography of quantum states',

View/Download from: UTS OPUS or Publisher's site

*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

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',

View/Download from: UTS OPUS or Publisher's site

*Lecture Notes in Computer Science*, the 38th Int. Symp. on Mathematical Foundations of Computer Science (MFCS'13), Springer, IST Austria, pp. 385-396.View/Download from: UTS OPUS or Publisher's site

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',

View/Download from: UTS OPUS or Publisher's site

*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

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',

View/Download from: UTS OPUS or Publisher's site

*Lecture Notes in Computer Science*, the 24th International Conference on Concurrency Theory (CONCUR'13), Springer, University of Buenos Aires, Argentina, pp. 334-348.View/Download from: UTS OPUS or Publisher's site

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.

Qiao, Y., Sun, X. & Yu, N. 2013, 'Determinantal Complexities and Field Extensions',

View/Download from: UTS OPUS or Publisher's site

*LNCS - Algorithms and Computation - Proceedings of the 24th International Symposium, ISAAC 2013*, ISAAC, Springer, Hong Kong, pp. 119-129.View/Download from: UTS OPUS or Publisher's site

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.

## Journal articles

Yu, N. 2016, 'Separability of a mixture of Dicke states',

View/Download from: Publisher's site

*Physical Review A - Atomic, Molecular, and Optical Physics*, vol. 94, no. 6.View/Download from: Publisher's site

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

Leung, D. & Yu, N. 2016, 'Maximum privacy without coherence, zero-error',

View/Download from: UTS OPUS or Publisher's site

*Journal of Mathematical Physics*, vol. 57, no. 9.View/Download from: UTS OPUS or Publisher's site

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.

Chen, J., Ji, Z., Yu, N. & Zeng, B. 2016, 'Detecting consistency of overlapping quantum marginals by separability',

View/Download from: UTS OPUS or Publisher's site

*Physical Review A - Atomic, Molecular, and Optical Physics*, vol. 93, no. 3.View/Download from: UTS OPUS or Publisher's site

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

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

Chen, J.-.Y., Ji, Z., Yu, N. & Zeng, B. 2016, 'Entanglement depth for symmetric states',

View/Download from: Publisher's site

*Physical Review A*, vol. 94, no. 4.View/Download from: Publisher's site

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',

View/Download from: Publisher's site

*Science China: Physics, Mechanics and Astronomy*, vol. 59, no. 10.View/Download from: Publisher's site

© 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. & Ying, M. 2015, 'Optimal simulation of Deutsch gates and the Fredkin gate',

View/Download from: Publisher's site

*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',

View/Download from: Publisher's site

*Acta Informatica*, vol. 51, pp. 1-24.View/Download from: Publisher's site

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.

Yu, N., Duan, R. & Ying, M. 2014, 'Distinguishability of Quantum States by Positive Operator-Valued Measures with Positive Partial Transpose',

View/Download from: UTS OPUS or Publisher's site

*IEEE Transactions on Information Theory*, vol. 60, no. 4, pp. 2069-2079.View/Download from: UTS OPUS or Publisher's site

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',

View/Download from: UTS OPUS or Publisher's site

*Physical Review Letters*, vol. 112, no. 16.View/Download from: UTS OPUS or Publisher's site

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',

View/Download from: UTS OPUS or Publisher's site

*Journal of Computer and System Sciences*, vol. 79, no. 7, pp. 1181-1198.View/Download from: UTS OPUS or Publisher's site

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

Yu, N. 2013, 'Multipartite W-type State Is Determined By Its Single-particle Reduced Density Matrices Among All W-type States',

View/Download from: UTS OPUS or Publisher's site

*Physical Review A*, vol. 87, no. 5, pp. 1-3.View/Download from: UTS OPUS or Publisher's site

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.

Ying, M., Yu, N., Feng, Y. & Duan, R. 2013, 'Verification of quantum programs',

View/Download from: UTS OPUS or Publisher's site

*Science Of Computer Programming*, vol. 78, no. 9, pp. 1679-1700.View/Download from: UTS OPUS or Publisher's site

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',

View/Download from: UTS OPUS or Publisher's site

*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',

View/Download from: UTS OPUS or Publisher's site

*Chinese Science Bulletin*, vol. 57, no. 16, pp. 1903-1909.View/Download from: UTS OPUS or Publisher's site

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. & Ying, M. 2012, 'Reachability and Termination Analysis of Concurrent Quantum Programs',

View/Download from: UTS OPUS or Publisher's site

*Lecture Notes in Computer Science*, vol. 7454, pp. 69-83.View/Download from: UTS OPUS or Publisher's site

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.

Yu, N., Duan, R. & Ying, M. 2012, 'Four Locally Indistinguishable Ququad-Ququad Orthogonal Maximally Entangled States',

View/Download from: Publisher's site

*PHYSICAL REVIEW LETTERS*, vol. 109, no. 2.View/Download from: Publisher's site

Yu, N., Duan, R. & Ying, M. 2011, 'Any 2 Circle Times N Subspace Is Locally Distinguishable',

View/Download from: UTS OPUS or Publisher's site

*Physical Review A*, vol. 84, no. 1, pp. 1-3.View/Download from: UTS OPUS or Publisher's site

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)',

View/Download from: UTS OPUS

*Physical Review A*, vol. 81, no. 1, pp. 1-3.View/Download from: UTS OPUS

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

Haah, J., Harrow, A.W., Ji, Z., Wu, X. & Yu, N., 'Sample-optimal tomography of quantum states'.

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