#### Can supervise: YES

#### Publications

Broadbent, A, Ji, Z, Song, F & Watrous, J 2020, 'Zero-knowledge proof systems for qma', *SIAM Journal on Computing*, vol. 49, no. 2, pp. 245-283.View/Download from: Publisher's site

#### View description

© 2020 Society for Industrial and Applied Mathematics. Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.

Chen, J, Ji, Z, Kribs, DW, Zeng, B & Zhang, F 2019, 'Minimum entangling power is close to its maximum', *Journal of Physics A: Mathematical and Theoretical*, vol. 52, no. 21.View/Download from: Publisher's site

#### View description

© 2019 IOP Publishing Ltd. Given a quantum gate U acting on a bipartite quantum system, its maximum (average, minimum) entangling power is the maximum (average, minimum) entanglement generation with respect to certain entanglement measures when the inputs are restricted to be product states. In this paper, we mainly focus on the 'weakest' one, i.e. the minimum entangling power, among all these entangling powers. We show that, by choosing the entropy of entanglement or Schmidt rank as entanglement measure, even the 'weakest' entangling power is generically very close to the maximum possible value of the entanglement measure. In other words, maximum, average and minimum entangling powers are generically close. We then study minimum entangling power with respect to other Lipschitiz-continuous (for the Hilbert space distance) entanglement measures and generalize our results to multipartite quantum systems.

Ji, Z 2019, 'Classical veriﬁcation of quantum proofs', *Theory of Computing*, vol. 15, no. 5, pp. 1-42.View/Download from: Publisher's site

#### View description

© 2019 Zhengfeng Ji. We present a classical interactive protocol that checks the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the nonlocal value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our result makes a connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of nonlocal games and Bell inequalities on the other.

Ji, Z 2019, 'The complexity-theoretic Bell inequality', *National Science Review*, vol. 6, no. 1, pp. 21-21.View/Download from: Publisher's site

Lu, S, Huang, S, Li, K, Li, J, Chen, J, Lu, D, Ji, Z, Shen, Y, Zhou, D & Zeng, B 2018, 'Separability-entanglement classifier via machine learning', *PHYSICAL REVIEW A*, vol. 98, no. 1.View/Download from: Publisher's site

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.

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-Y, Ji, Z, Liu, Z-X, Shen, Y & Zeng, B 2016, 'Geometry of reduced density matrices for symmetry-protected topological phases', *PHYSICAL REVIEW A*, vol. 93, no. 1.View/Download from: Publisher's site

Ji, Z & Xia, M 2016, 'The limits of computation', *Kexue Tongbao/Chinese Science Bulletin*, vol. 61, no. 4-5, pp. 404-408.View/Download from: Publisher's site

#### View description

© 2016, Science Press. All right reserved. The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.

Ma, X, Jackson, T, Zhou, H, Chen, J, Lu, D, Mazurek, MD, Fisher, KAG, Peng, X, Kribs, D, Resch, KJ, Ji, Z, Zeng, B & Laflamme, R 2016, 'Pure-state tomography with the expectation value of Pauli operators', *PHYSICAL REVIEW A*, vol. 93, no. 3.View/Download from: Publisher's site

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.

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.

Chen, J, Ji, Z, Kribs, D, Lütkenhaus, N & Zeng, B 2014, 'Symmetric extension of two-qubit states', *Physical Review A - Atomic, Molecular, and Optical Physics*, vol. 90, no. 3, pp. 032318-1-032318-10.View/Download from: Publisher's site

#### View description

© 2014 American Physical Society. A bipartite state ρAB is symmetric extendible if there exists a tripartite state ρABB' whose AB and AB' marginal states are both identical to ρAB. Symmetric extendibility of bipartite states is of vital importance in quantum information because of its central role in separability tests, one-way distillation of Einstein-Podolsky-Rosen pairs, one-way distillation of secure keys, quantum marginal problems, and antidegradable quantum channels. We establish a simple analytic characterization for symmetric extendibility of any two-qubit quantum state ρAB; specifically, tr(ρB2)≥tr(ρAB2)-4detρAB. As a special case we solve the bosonic three-representability problem for the two-body reduced density matrix.

Chen, J, Dawkins, H, Ji, Z, Johnston, N, Kribs, D, Shultz, F & Zeng, B 2013, 'Uniqueness of quantum states compatible with given measurement results', *PHYSICAL REVIEW A*, vol. 88, no. 1.View/Download from: Publisher's site

Chen, J, Ji, Z, Klyachko, A, Kribs, DW & Zeng, B 2012, 'Rank reduction for the local consistency problem', *JOURNAL OF MATHEMATICAL PHYSICS*, vol. 53, no. 2.View/Download from: Publisher's site

Chen, J, Ji, Z, Kribs, D, Wei, Z & Zeng, B 2012, 'Ground-state spaces of frustration-free Hamiltonians', *JOURNAL OF MATHEMATICAL PHYSICS*, vol. 53, no. 10.View/Download from: Publisher's site

Chen, J, Ji, Z, Ruskai, MB, Zeng, B & Zhou, D-L 2012, 'Comment on some results of Erdahl and the convex structure of reduced density matrices', *JOURNAL OF MATHEMATICAL PHYSICS*, vol. 53, no. 7.View/Download from: Publisher's site

Chen, J, Ji, Z, Wei, Z & Zeng, B 2012, 'Correlations in excited states of local Hamiltonians', *PHYSICAL REVIEW A*, vol. 85, no. 4.View/Download from: Publisher's site

Chen, J, Ji, Z, Zeng, B & Zhou, DL 2012, 'From ground states to local Hamiltonians', *PHYSICAL REVIEW A*, vol. 86, no. 2.View/Download from: Publisher's site

Jain, R, Ji, Z, Upadhyay, S & Watrous, J 2011, 'QIP = PSPACE', *JOURNAL OF THE ACM*, vol. 58, no. 6.View/Download from: Publisher's site

Ji, Z, Wei, Z & Zeng, B 2011, 'Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubits', *PHYSICAL REVIEW A*, vol. 84, no. 4.View/Download from: Publisher's site

Ocko, SA, Chen, X, Zeng, B, Yoshida, B, Ji, Z, Ruskai, MB & Chuang, IL 2011, 'Quantum Codes Give Counterexamples to the Unique Preimage Conjecture of the N-Representability Problem', *PHYSICAL REVIEW LETTERS*, vol. 106, no. 11.View/Download from: Publisher's site

Chen, J, Chen, X, Duan, R, Ji, Z & Zeng, B 2011, 'No-go Theorem For One-way Quantum Computing On Naturally Occurring Two-level Systems', *Physical Review A*, vol. 83, no. 5, pp. 0-0.View/Download from: Publisher's site

#### View description

The ground states of some many-body quantum systems can serve as resource states for the one-way quantum computing model, achieving the full power of quantum computation. Such resource states are found, for example, in spin- 5 2 and spin- 3 2 systems. It is, of course, desirable to have a natural resource state in a spin- 1 2 , that is, qubit system. Here, we give a negative answer to this question for frustration-free systems with two-body interactions. In fact, it is shown to be impossible for any genuinely entangled qubit state to be a nondegenerate ground state of any two-body frustration-free Hamiltonian. What is more, we also prove that every spin- 1 2 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states. In other words, there cannot be any interesting entanglement features in the ground state of such a qubit Hamiltonian.

Grassl, M, Ji, Z, Wei, Z & Zeng, B 2010, 'Quantum-capacity-approaching codes for the detected-jump channel', *PHYSICAL REVIEW A*, vol. 82, no. 6.View/Download from: Publisher's site

Jain, R, Ji, Z, Upadhyay, S & Watrous, J 2010, 'QIP = PSPACE', *Communications of the ACM*, vol. 53, no. 12, pp. 102-109.View/Download from: Publisher's site

#### View description

The interactive proof system model of computation has been studied extensively in computational complexity theory and theoretical cryptography for more than 25 years, and has driven the development of interesting new techniques and insights in those fields. This work considers the quantum interactive proof system model, which is the classical model's natural quantum computational analog. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable with an ordinary classical computer using at most a polynomial amount of memory (or QIP = PSPACE in complexity-theoretic terminology). One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems. © 2010 ACM.

Chen, L, Chitambar, E, Duan, R, Ji, Z & Winter, A 2010, 'Tensor rank and stochastic entanglement catalysis for multipartite pure states.', *Physical review letters*, vol. 105, no. 20, p. 200501.View/Download from: Publisher's site

#### View description

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

Chen, L, Chitambar, EA, Duan, R, Ji, Z & Winter, A 2010, 'Tensor Rank And Stochastic Entanglement Catalysis For Multipartite Pure States', *Physical Review Letters*, vol. 105, no. 20, pp. 1-4.View/Download from: Publisher's site

#### View description

The tensor rank (also known as generalized Schmidt rank) of multipartite pure states plays an important role in the study of entanglement classifications and transformations. We employ powerful tools from the theory of homogeneous polynomials to investig

Chen, X, Duan, R, Ji, Z & Zeng, B 2010, 'Quantum State Reduction For Universal Measurement Based Computation', *Physical Review Letters*, vol. 105, no. 2, pp. 1-4.View/Download from: Publisher's site

#### View description

Measurement based quantum computation, which requires only single particle measurements on a universal resource state to achieve the full power of quantum computing, has been recognized as one of the most promising models for the physical realization of

Ji, Z, Chen, J, Wei, Z & Ying, M 2010, 'The LU-LC conjecture is false', *Quantum Information and Computation*, vol. 10, no. 1, pp. 97-108.

#### View description

The LU-LC conjecture is an important open problem concerning the structure of entanglement of states described in the stabilizer formalism. It states that two local unitary equivalent stabilizer states are also local Clifford equivalent. If this conjecture were true, the local equivalence of stabilizer states would be extremely easy to characterize. Unfortunately, however, based on the recent progress made by Gross and Van den Nest, we find that the conjecture is false.

Ying, M, Feng, Y, Duan, R & Ji, Z 2009, 'An Algebra Of Quantum Processes', *Acm Transactions On Computational Logic*, vol. 10, no. 3, pp. 1-36.View/Download from: Publisher's site

#### View description

We introduce an algebra qCCS of pure quantum processes in which communications by moving quantum states physically are allowed and computations are modeled by super-operators, but no classical data is explicitly involved. An operational semantics of qCCS is presented in terms of (nonprobabilistic) labeled transition systems. Strong bisimulation between processes modeled in qCCS is defined, and its fundamental algebraic properties are established, including uniqueness of the solutions of recursive equations. To model sequential computation in qCCS, a reduction relation between processes is defined. By combining reduction relation and strong bisimulation we introduce the notion of strong reduction-bisimulation, which is a device for observing interaction of computation and communication in quantum systems. Finally, a notion of strong approximate bisimulation (equivalently, strong bisimulation distance) and its reduction counterpart are introduced. It is proved that both approximate bisimilarity and approximate reduction-bisimilarity are preserved by various constructors of quantum processes. This provides us with a formal tool for observing robustness of quantum processes against inaccuracy in the implementation of its elementary gates.

Chitambar, EA, Duan, R & Shi, Y 2008, 'Tripartite Entanglement Transformations And Tensor Rank', *Physical Review Letters*, vol. 101, no. 14, pp. 1-4.View/Download from: Publisher's site

#### View description

A basic question regarding quantum entangled states is whether one can be probabilistically converted to another through local operations and classical communication exclusively. While the answer for bipartite systems is known, we show that for tripartit

Chen, JF, Duan, R, Ji, Z, Ying, M & Yu, JX 2008, 'Existence Of Universal Entangler', *Journal of Mathematical Physics*, vol. 49, no. 1, pp. 1-7.View/Download from: Publisher's site

#### View description

A gate is called an entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for gener

Ji, Z, Wang, G, Duan, R, Feng, Y & Ying, M 2008, 'Parameter Estimation of Quantum Channels', *IEEE Transactions On Information Theory*, vol. 54, no. 11, pp. 5172-5185.View/Download from: Publisher's site

#### View description

The efficiency of parameter estimation of quantum channels is studied in this paper. We introduce the concept of programmable parameters to the theory of estimation. It is found that programmable parameters obey the standard quantum limit strictly; hence, no speedup is possible in its estimation. We also construct a class of nonunitary quantum channels whose parameter can be estimated in a way that the standard quantum limit is broken. The study of estimation of general quantum channels also enables an investigation of the effect of noises on quantum estimation.

Feng, Y, Duan, R, Ji, Z & Ying, M 2007, 'Probabilistic bisimulations for quantum processes', *Information and Computation*.View/Download from: Publisher's site

Duan, R, Feng, Y, Ji, Z & Ying, M 2007, 'Distinguishing Arbitrary Multipartite Basis Unambiguously Using Local Operations And Classical Communication', *Physical Review Letters*, vol. 98, no. 23, pp. 1-4.

#### View description

We show that an arbitrary basis of a multipartite quantum state space consisting of K distant parties such that the kth party has local dimension d(k) always contains at least N=Sigma(K)(k=1)(d(k)-1)+1 members that are unambiguously distinguishable using

Duan, R, Feng, Y, Ji, Z & Ying, M 2007, 'Distinguishing arbitrary multipartite basis unambiguously using local operations and classical communication (vol 98, art no 230602, 2007)', *PHYSICAL REVIEW LETTERS*, vol. 99, no. 1.View/Download from: Publisher's site

Feng, Y, Duan, R, Ji, Z & Ying, M 2007, 'Probabilistic Bisimulations For Quantum Processes', *Information And Computation*, vol. 205, no. 11, pp. 1608-1639.View/Download from: Publisher's site

#### View description

Modeling and reasoning about concurrent quantum systems is very important for both distributed quantum computing and quantum protocol verification. As a consequence, a general framework formally describing communication and concurrency in complex quantum

Feng, Y, Duan, R, Ji, Z & Ying, M 2007, 'Proof Rules For The Correctness Of Quantum Programs', *Theoretical Computer Science*, vol. 386, no. 1-2, pp. 151-166.View/Download from: Publisher's site

#### View description

We apply the notion of quantum predicate proposed by D'Hondt and Panangaden to analyze a simple language fragment which may describe the quantum part of a future quantum computer in Knill's architecture. The notion of weakest liberal precondition semanti

Feng, Y, Duan, R & Ji, Z 2006, 'Optimal Dense Coding With Arbitrary Pure Entangled States', *Physical Review A*, vol. 74, no. 1, pp. 1-5.

#### View description

We examine dense coding with an arbitrary pure entangled state sharing between the sender and the receiver. Upper bounds on the average success probability in approximate dense coding and on the probability of conclusive results in unambiguous dense codi

Duan, R, Ji, Z, Feng, Y & Ying, M 2006, 'Some Issues In Quantum Information Theory', *Journal Of Computer Science And Technology*, vol. 21, no. 5, pp. 776-789.View/Download from: Publisher's site

#### View description

Quantum information theory is a new interdisciplinary research field related to quantum mechanics, computer science, information theory, and applied mathematics. It provides completely new paradigms to do information processing tasks by employing the pri

Ji, Z, Feng, Y, Duan, R & Ying, M 2006, 'Boundary Effect Of Deterministic Dense Coding', *Physical Review A*, vol. 73, no. 3, pp. 1-3.

#### View description

We present a rigorous proof of an interesting boundary effect of deterministic dense coding first observed by S. Mozes, J. Oppenheim, and B. Reznik [Phys. Rev. A 71, 012311 (2005)]. Namely, it is shown that d(2)-1 cannot be the maximal alphabet size of a

Ji, Z, Feng, Y, Duan, R & Ying, M 2006, 'Identification And Distance Measures Of Measurement Apparatus', *Physical Review Letters*, vol. 96, no. 20, pp. 1-4.

#### View description

We propose simple schemes that can perfectly identify projective measurement apparatuses secretly chosen from a finite set. Entanglement is used in these schemes both to make possible the perfect identification and to improve the efficiency significantly

Wei, Z & Ying, M 2006, 'Majorization In Quantum Adiabatic Algorithms', *Physical Review A*, vol. 74, no. 4, pp. 1-7.

#### View description

The majorization theory has been applied to analyze the mathematical structure of quantum algorithms. An empirical conclusion by numerical simulations obtained in the previous literature indicates that step-by-step majorization seems to appear universall

Feng, Y, Duan, R & Ji, Z 2005, 'Condition And Capability Of Quantum State Separation', *Physical Review A*, vol. 72, no. 1, pp. 1-6.

#### View description

The linearity of quantum operations puts many fundamental constraints on the information processing tasks we can achieve on a quantum system whose state is not exactly known, just as we observe in quantum cloning and quantum discrimination. In this paper

Duan, R, Feng, Y, Ji, Z & Ying, M 2005, 'Efficiency Of Deterministic Entanglement Transformation', *Physical Review A*, vol. 71, no. 2, pp. 1-7.

#### View description

We prove that sufficiently many copies of a bipartite entangled pure state can always be transformed into some copies of another one with certainty by local quantum operations and classical communication. The efficiency of such a transformation is charac

Ji, Z, Cao, H & Ying, M 2005, 'Optimal Conclusive Discrimination Of Two States Can Be Achieved Locally', *Physical Review A*, vol. 71, no. 3, pp. 1-5.

#### View description

This paper constructs a local operation and classical communication protocol that achieves the global optimality of conclusive discrimination of any two pure states with arbitrary a priori probability. This can be interpreted that there is no

Ji, Z, Feng, Y & Ying, M 2005, 'Local Cloning Of Two Product States', *Physical Review A*, vol. 72, no. 3, pp. 1-5.

#### View description

Local quantum operations and classical communication (LOCC) put considerable constraints on many quantum information processing tasks such as cloning and discrimination. Surprisingly, however, discrimination of any two pure states survives such constrain

Duan, R, Ji, Z, Feng, Y & Ying, M 2004, 'Quantum Operation Quantum Fourier Transform And Semi-Definite Programming', *Physics Letters A*, vol. 323, no. 1-2, pp. 48-56.View/Download from: Publisher's site

#### View description

We analyze a class of quantum operations based on a geometrical representation of d-level quantum system (or qudit for short). A sufficient and necessary condition of complete positivity, expressed in terms of the quantum Fourier transform, is found for

Ji, Z, Duan, R & Ying, M 2004, 'Comparability Of Multipartite Entanglement', *Physics Letters A*, vol. 330, no. 6, pp. 418-423.View/Download from: Publisher's site

#### View description

We prove, in a multipartite setting, that it is always feasible to exactly transform a genuinely m-partite entangled pure state with sufficient many copies to any other m-partite state via local quantum operation and classical communication. This result

Feng, Y, Duan, R & Ji, Z, 'Condition and capability of quantum state separation', *Physical Review A*, vol. 72, no. 1.View/Download from: Publisher's site

Feng, Y, Duan, R & Ji, Z, 'Optimal dense coding with arbitrary pure entangled states', *Physical Review A*, vol. 74, no. 1.View/Download from: Publisher's site

Ying, M, Duan, R, Feng, Y & Ji, Z 2010, 'Predicate Transformer Semantics of Quantum Programs' in Gay, S & Mackie, I (eds), *Semantic Techniques in Quantum Computation*, Cambridge University Press, Cambridge, pp. 311-360.

#### View description

This chapter presents a systematic exposition of predicate transformer semantics for quantum programs. It is divided into two parts: The first part reviews the state transformer (forward) semantics of quantum programs according to Selingerâs suggestion of representing quantum programs by superoperators and elucidates DâHondt-Panangadenâs theory of quantum weakest preconditions in detail. In the second part, we develop a quite complete predicate transformer semantics of quantum programs based on Birkhoffâvon Neumann quantum logic by considering only quantum predicates expressed by projection operators. In particular, the universal coujunctivity and termination law of quantum programs are proved, and Hoareâs induction rule is established in the quantum setting.

Fitzsimons, J, Ji, Z, Vidick, T & Yuen, H 2019, 'Quantum proof systems for iterated exponential time, and beyond', *STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*, Annual ACM SIGACT Symposium on Theory of Computing, ACM, Phoenix, AZ, USA, pp. 473-480.View/Download from: Publisher's site

#### View description

© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. We show that any language solvable in nondeterministic time exp(exp(· · · exp(n))), where the number of iterated exponentials is an arbitrary function R(n), can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1 − exp(−C exp(· · · exp(n))), where the number of iterated exponentials is R(n) − 1 and C > 0 is a universal constant. The result was previously known for R = 1 and R = 2; we obtain it for any time-constructible function R. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result on the uncomputability of the entangled value of multiprover games (Forum of Mathematics, Pi 2019). Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP∗ contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations.

Ji, Z, Qiao, Y, Yun, A & Song, F 2019, 'General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography', *TCC 2019: Theory of Cryptography*, International Conference on Theory of Cryptography, Springer, Nuremberg, pp. 251-281.View/Download from: Publisher's site

#### View description

Starting from the one-way group action framework of Brassard and Yung (Crypto'90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm).

We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny–Grochow–Sergeichuk Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, hardness results, as well as quantum algorithms.

We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group G acting on a set S, we assume that it is hard to distinguish two distributions of (s, t) either uniformly chosen from S×S , or where s is randomly chosen from S and t is the result of applying a random group action of g∈G on s. This subsumes the classical Decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support instantiating this assumption by the general linear group action on tensors.

Finally, we construct several cryptographic primitives such as digital signatures and pseudorandom functions. We give quantum security proofs based on the one-way group action assumption and the pseudorandom group action assumption.

Ji, Z, Liu, YK & Song, F 2018, 'Pseudorandom quantum states', *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, Annual International Cryptology Conference, Santa Barbara, CA, USA, pp. 126-152.View/Download from: Publisher's site

#### View description

© International Association for Cryptologic Research 2018. We propose the concept of pseudorandom quantum states, which appear random to any quantum polynomial-time adversary. It offers a computational approximation to perfectly random quantum states analogous in spirit to cryptographic pseudorandom generators, as opposed to statistical notions of quantum pseudorandomness that have been studied previously, such as quantum t-designs analogous to t-wise independent distributions. Under the assumption that quantum-secure one-way functions exist, we present efficient constructions of pseudorandom states, showing that our definition is achievable. We then prove several basic properties of pseudorandom states, which show the utility of our definition. First, we show a cryptographic no-cloning theorem: no efficient quantum algorithm can create additional copies of a pseudorandom state, when given polynomially-many copies as input. Second, as expected for random quantum states, we show that pseudorandom quantum states are highly entangled on average. Finally, as a main application, we prove that any family of pseudorandom states naturally gives rise to a private-key quantum money scheme.

Ji, Z 2017, 'Compression of quantum multi-prover interactive proofs', *Proceedings of the Annual ACM Symposium on Theory of Computing*, 49th Annual ACM SIGACT Symposium on Theory of Computing, AM, Montreal, Canada, pp. 289-302.View/Download from: Publisher's site

#### View description

© 2017 ACM. We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, it follows that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP∗, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.

Broadbent, A, Ji, Z, Song, F & Watrous, J 2016, 'Zero-knowledge proof systems for QMA (Extended Abstract)', *2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS)*, 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New Brunswick, NJ, pp. 31-40.View/Download from: Publisher's site

Ji, Z 2016, 'Classical verification of quantum proofs', *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. 885-898.View/Download from: Publisher's site

#### View description

We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.

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.

Beigi, S, Chen, J, Grassl, M, Ji, Z, Wang, Q & Zeng, B 2013, 'Symmetries of codeword stabilized quantum codes', *Leibniz International Proceedings in Informatics, LIPIcs*, pp. 192-206.View/Download from: Publisher's site

#### View description

© Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang, and Bei Zeng;. Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.e., Q = (S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q = (S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G, C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.

Jain, R, Ji, Z, Upadhyay, S & Watrous, J 2010, 'QIP = PSPACE', *Proceedings of the Annual ACM Symposium on Theory of Computing*, pp. 573-581.View/Download from: Publisher's site

#### View description

We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows. © 2010 ACM.

Duan, R, Grassl, M, Ji, Z & Zeng, B 2010, 'Multi-error-correcting amplitude damping codes', *IEEE International Symposium on Information Theory - Proceedings*, International Symposium on Information Theory, IEEE, Austin, USA, pp. 2672-2676.View/Download from: Publisher's site

#### View description

We construct new families of multi-error-correcting quantum codes for the amplitude damping channel. Our key observation is that, with proper encoding, two uses of the amplitude damping channel simulate a quantum erasure channel. This allows us to use co