Publications (77)
Tomography is necessary for universal entanglement detection with single-copy observables
Dawei Lu, Tao Xin, Nengkun Yu +7
Entanglement, one of the central mysteries of quantum mechanics, plays an essential role in numerous applications of quantum information theory. A natural question of both theoreti…
Optimal Simulation of a Perfect Entangler
Nengkun Yu, Runyao Duan, Mingsheng Ying
A 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…
Quantum Information-Flow Security: Noninterference and Access Control
Mingsheng Ying, Yuang Feng, Nengkun Yu
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 i…
When is the Chernoff Exponent for Quantum Operations finite?
Nengkun Yu, Li Zhou
We consider the problem of testing two hypotheses of quantum operations in a setting of many uses where an arbitrary prior probability distribution is given. The Chernoff exponent…
Learning marginals suffices!
Nengkun Yu, Tzu-Chieh Wei
Beyond computer science, quantum complexity theory can potentially revolutionize multiple branches of physics, ranging from quantum many-body systems to quantum field theory. In th…
Physical origins of ruled surfaces on the reduced density matrices geometry
Ji-Yao Chen, Zhengfeng Ji, Zheng-Xin Liu +4
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 su…
Approximation does not help in quantum unitary time-reversal
Kean Chen, Nengkun Yu, Zhicheng Zhang
Access to the time-reverse of an unknown quantum unitary process is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unita…
Checking Continuous Stochastic Logic against Quantum Continuous-Time Markov Chains
Ming Xu, Jingyi Mei, Ji Guan +2
Verifying quantum systems has attracted a lot of interest in the last decades.In this paper, we study the quantitative model-checking of quantum continuous-time Markov chains (quan…
LOCC protocols with bounded width per round optimize convex functions
Debbie Leung, Andreas Winter, Nengkun Yu
We start with the task of discriminating finitely many multipartite quantum states using LOCC protocols, with the goal to optimize the probability of correctly identifying the stat…
Manjushri: A Tool for Equivalence Checking of Quantum Circuits
Xuan Du Trinh, Meghana Sistla, Nengkun Yu +1
Verifying whether two quantum circuits are equivalent is a central challenge in the compilation and optimization of quantum programs. We introduce \textsc{Manjushri}, a new automat…
Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets
Debbie Leung, Ashwin Nayak, Ala Shayeghi +3
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 commun…
Non-Additivity of Minimum Output p- Entropy
Nengkun Yu, Mingsheng Ying
Hastings disproved additivity conjecture for minimum output entropy by using random unitary channels. In this note, we employ his approach to show that minimum output Rényi en…
Sample optimal Quantum identity testing via Pauli Measurements
Nengkun Yu
In this paper, we show that is the sample complexity of testing whether two -qubit quantum states and are identical or …
Separability of Bosonic Systems
Nengkun Yu
In this paper, we study the separability of quantum states in bosonic system. Our main tool here is the "separability witnesses", and a connection between "separability witnesses"…
Quantum channel tomography and estimation by local test
Kean Chen, Nengkun Yu, Zhicheng Zhang
We study the estimation of an unknown quantum channel with input dimension , output dimension and Kraus rank at most . We establish a connection between…
Characterization of multipartite entanglement in terms of local transformations
Youming Qiao, Xiaoming Sun, Nengkun Yu
The degree of the generators of invariant polynomial rings of is a long standing open problem since the very initial study of the invariant theory in the 19th century. Motivated by…
Accelerating Voting by Quantum Computation
Ao Liu, Qishen Han, Lirong Xia +1
Studying the computational complexity and designing fast algorithms for determining winners under voting rules are classical and fundamental questions in computational social choic…
Protocols for Packet Quantum Network Intercommunication
Nengkun Yu, Ching-Yi Lai, Li Zhou
A quantum network, which involves multiple parties pinging each other with quantum messages, could revolutionize communication, computing and basic sciences. The future internet wi…
Quantum State and Process Tomography via Adaptive Measurements
Hengyan Wang, Wenqiang Zheng, Nengkun Yu +9
We investigate quantum state tomography (QST) for pure states and quantum process tomography (QPT) for unitary channels via measurements. For a quantum system with a …
Termination of Nondeterministic Quantum Programs
Yangjia Li, Nengkun Yu, Mingsheng Ying
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 represente…
Quantum Coupling and Strassen Theorem
Li Zhou, Shenggang Ying, Nengkun Yu +1
We introduce a quantum generalisation of the notion of coupling in probability theory. Several interesting examples and basic properties of quantum couplings are presented. In part…
What if you have only one copy? Low-depth quantum circuits have no advantage in decision problems!
Nengkun Yu
The conventional approach to understanding the characteristics of an unknown quantum state involves having numerous identical independent copies of the system in that state. Howeve…
Orbit Problem Revisited
Taolue Chen, Xiaoming Sun, Nengkun Yu
In this letter, we revisit the {\em orbit problem}, which was studied in \cite{HAR69,SHA79,KL86}. In \cite{KL86}, Kannan and Lipton proved that this problem is decidable in polynom…
Model Checking Quantum Continuous-Time Markov Chains
Ming Xu, Jingyi Mei, Ji Guan +1
Verifying quantum systems has attracted a lot of interests in the last decades. In this paper, we initialised the model checking of quantum continuous-time Markov chain (QCTMC). As…
Quantum Closeness Testing: A Streaming Algorithm and Applications
Nengkun Yu
One of the main subjects of this paper is to study quantum property testing with local measurement. In particular, we establish a novel norm connection between quantum pro…
Four Locally Indistinguishable Ququad-Ququad Orthogonal Maximally Entangled States
Nengkun Yu, Runyao Duan, Mingsheng Ying
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 communicat…
Quantum Capacities for Entanglement Networks
Shawn X Cui, Zhengfeng Ji, Nengkun Yu +1
We discuss quantum capacities for two types of entanglement networks: for the quantum repeater network with free classical communication, and for the te…
The QQUIC Transport Protocol: Quantum assisted UDP Internet Connections
Peng Yan, Nengkun Yu
Quantum key distribution, initialized in 1984, is a commercialized secure communication method which enables two parties to produce shared random secret key by the nature of quantu…
Entanglement Certification by Measuring Nonlocality
Xuan Du Trinh, Zhengyu Wu, Junlin Bai +3
Reliable verification of entanglement is a central requirement for quantum networks. This paper presents a practical verification approach based on violations of the Clauser-Horne-…
Scalable Equivalence Checking and Verification of Shallow Quantum Circuits
Nengkun Yu, Xuan Du Trinh, Thomas Reps
This paper concerns the problem of checking if two shallow (i.e., constant-depth) quantum circuits perform equivalent computations. Equivalence checking is a fundamental correctnes…
A Quantum Interpretation of Bunched Logic for Quantum Separation Logic
Li Zhou, Gilles Barthe, Justin Hsu +2
We propose a model of the substructural logic of Bunched Implications (BI) that is suitable for reasoning about quantum states. In our model, the separating conjunction of BI descr…
Pauli measurements are not optimal for single-copy tomography
Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1
Quantum state tomography is a fundamental problem in quantum computing. Given copies of an unknown -qubit state , the goal is to learn t…
Maximum privacy without coherence, zero-error
Debbie Leung, Nengkun Yu
We study the possible difference between the quantum and the private capacities of a quantum channel in the zero-error setting. For a family of channels introduced by arXiv:1312.49…
Discontinuity of Maximum Entropy Inference and Quantum Phase Transitions
Jianxin Chen, Zhengfeng Ji, Chi-Kwong Li +5
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 te…
Optimal lower bound for quantum channel tomography in away-from-boundary regime
Kean Chen, Zhicheng Zhang, Nengkun Yu
Consider quantum channels with input dimension , output dimension and Kraus rank at most . Any such channel must satisfy the constraint , and the parame…
Model checking quantum Markov chains
Yuan Feng, Nengkun Yu, Mingsheng Ying
Although the security of quantum cryptography is provable based on the principles of quantum mechanics, it can be compromised by the flaws in the design of quantum protocols and th…
Model-Checking Linear-Time Properties of Quantum Systems
Mingsheng Ying, Yangjia Li, Nengkun Yu +1
We define a formal framework for reasoning about linear-time properties of quantum systems in which quantum automata are employed in the modeling of systems and certain closed subs…
Discrimination of quantum states under locality constraints in the many-copy setting
Hao-Chung Cheng, Andreas Winter, Nengkun Yu
We study quantum hypothesis testing between orthogonal states under restricted local measurements in the many-copy scenario. For testing arbitrary multipartite entangled pure state…
Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1
We provide the first non-trivial lower bounds for single-qubit tomography algorithms and show that at least copies are required…
Sample efficient tomography via Pauli Measurements
Nengkun Yu
Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli mea…
SAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum Circuits
Nengkun Yu, Jens Palsberg, Thomas Reps
Reasoning about quantum programs remains a fundamental challenge, regardless of the programming model or computational paradigm. Despite extensive research, existing verification t…
Sample-optimal tomography of quantum states
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji +2
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 esti…
Quantum Earth mover's distance, No-go Quantum Kantorovich-Rubinstein theorem, and Quantum Marginal Problem
Nengkun Yu, Li Zhou, Shenggang Ying +1
The earth mover's distance is a measure of the distance between two probabilistic measures. It plays a fundamental role in mathematics and computer science. The Kantorovich-Rubinst…
A Probabilistic Logic for Verifying Continuous-time Markov Chains
Ji Guan, Nengkun Yu
A continuous-time Markov chain (CTMC) execution is a continuous class of probability distributions over states. This paper proposes a probabilistic linear-time temporal logic, name…
Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate
Nengkun Yu, Runyao Duan, Mingsheng Ying
In this paper, we settle the long-standing open problem of the minimum cost of two-qubit gates for simulating a Toffoli gate. More precisely, we show that five two-qubit gates are…
The Tensor Rank of the Tripartite State }
Nengkun Yu, Eric Chitambar, Cheng Guo +1
Tensor rank refers to the number of product states needed to express a given multipartite quantum state. Its non-additivity as an entanglement measure has recently been observed. I…
Sample optimal tomography of quantum Markov chains
Li Gao, Nengkun Yu
A state on a tripartite quantum system forms a Markov chain, i.e., quantum conditional independence, if it can be re…
Dichotomy of entanglement depth for symmetric states
Ji-Yao Chen, Zhengfeng Ji, Nengkun Yu +1
Entanglement depth characterizes the minimal number of particles in a system that are mutually entangled. For symmetric states, we show that there is a dichotomy for entanglement d…
Adaptivity is not helpful for Pauli channel learning
Xuan Du Trinh, Nengkun Yu
We prove that adaptive strategies offer no advantage over non-adaptive ones for learning and testing Pauli channels using entangled inputs. This key observation allows us to charac…
Entanglement Verification, with or without tomography
Nengkun Yu
Multipartite entanglement has been widely regarded as key resources in distributed quantum computing, for instance, multi-party cryptography, measurement based quantum computing, q…
Detecting Consistency of Overlapping Quantum Marginals by Separability
Jianxin Chen, Zhengfeng Ji, Nengkun Yu +1
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…
Optimal simulation of three-qubit gates
Nengkun Yu, Mingsheng Ying
In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit…
Experimental Cryptographic Verification for Near-Term Quantum Cloud Computing
Xi Chen, Bin Cheng, Zhaokai Li +4
Recently, there are more and more organizations offering quantum-cloud services, where any client can access a quantum computer remotely through the internet. In the near future, t…
Multi-partite type state is determined by its single particle reduced density matrices
Nengkun Yu
In this short note, we show that multi-partite -type state is up to local unitaries uniquely determined by its reduced density matrices.
Quantum Max-Flow Min-Cut theorem
Nengkun Yu
The max-flow min-cut theorem is a cornerstone result in combinatorial optimization. Calegari et al. (arXiv:0802.3208) initialized the study of quantum max-flow min-cut conjecture,…
Bounds on the distance between a unital quantum channel and the convex hull of unitary channels, with applications to the asymptotic quantum Birkhoff conjecture
Nengkun Yu, Runyao Duan, Quanhua Xu
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…
Joint product numerical range and geometry of reduced density matrices
Jianxin Chen, Cheng Guo, Zhengfeng Ji +4
The reduced density matrices of a many-body quantum system form a convex set, whose three-dimensional projection is convex in . The boundary of …
Relational Proofs for Quantum Programs
Gilles Barthe, Justin Hsu, Mingsheng Ying +2
Relational verification of quantum programs has many potential applications in quantum and post-quantum security and other domains. We propose a relational program logic for quantu…
Entirety of Quantum Uncertainty and Its Experimental Verification
Jie Xie, Songtao Huang, Li Zhou +5
As a foundation of modern physics, uncertainty relations describe an ultimate limit for the measurement uncertainty of incompatible observables. Traditionally, uncertain relations…
Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition
Kean Chen, Filippo Girardi, Aadil Oufkir +2
How many black-box queries to a quantum channel are needed to learn its full classical description? This question lies at the heart of quantum channel tomography (also known as qua…
Distinguishability of Quantum States by Positive Operator-Valued Measures with Positive Partial Transpose
Nengkun Yu, Runyao Duan, Mingsheng Ying
We study the distinguishability of bipartite quantum states by Positive Operator-Valued Measures with positive partial transpose (PPT POVMs). The contributions of this paper includ…
Towards Efficient Verification of Computation in Quantum Devices
Keren Li, Peng Yan, Hanru Jiang +1
Designing quantum processors is a complex task that demands advanced verification methods to ensure their correct functionality. However, traditional methods of comprehensively ver…
Limitations on separable measurements by convex optimization
Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston +3
We prove limitations on LOCC and separable measurements in bipartite state discrimination problems using techniques from convex optimization. Specific results that we prove include…
Quantum Temporal Logic
Nengkun Yu
In this paper, we introduce a model of quantum concurrent program, which can be used to model the behaviour of reactive quantum systems and to design quantum compilers. We investig…
Formalizing CHSH Rigidity in Lean 4
Tianrun Zhao, Nengkun Yu
Violation of the Clauser-Horne-Shimony-Holt (CHSH) inequality certifies genuine quantum correlations. In this work, we formalize in Lean 4 the rigidity theorem -- any strategy achi…
Proq: Projection-based Runtime Assertions for Debugging on a Quantum Computer
Gushu Li, Li Zhou, Nengkun Yu +3
In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (…
Experimental quantification of coherence of a tunable quantum detector
Huichao Xu, Feixiang Xu, Thomas Theurer +5
Quantum coherence is a fundamental resource that quantum technologies exploit to achieve performance beyond that of classical devices. A necessary prerequisite to achieve this adva…
Reachability and Termination Analysis of Concurrent Quantum Programs
Nengkun Yu, Mingsheng Ying
We introduce a Markov chain model of concurrent quantum programs. This model is a quantum generalization of Hart, Sharir and Pnueli's probabilistic concurrent programs. Some charac…
Generalized Graph States Based on Hadamard Matrices
Shawn X Cui, Nengkun Yu, Bei Zeng
Graph states are widely used in quantum information theory, including entanglement theory, quantum error correction, and one-way quantum computing. Graph states have a nice structu…
Obtain -state from three-qubit -state on rate 1
Nengkun Yu, Cheng Guo, Runyao Duan
In this paper, we study the entanglement transformation rate between multipartite states under stochastic local operations and classical communication (SLOCC). Firstly, we show tha…
Verification of Quantum Programs
Mingsheng Ying, Nengkun Yu, Yuan Feng +1
This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold: 1. Sharir, Pnueli and Hart [SIAM J. Comput. 13(1984)292-314] prese…
Exponential Separation of Quantum Communication and Classical Information
Anurag Anshu, Dave Touchette, Penghui Yao +1
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the oth…
Defining Quantum Control Flow
Mingsheng Ying, Nengkun Yu, Yuan Feng
A remarkable difference between quantum and classical programs is that the control flow of the former can be either classical or quantum. One of the key issues in the theory of qua…
Reachability Probabilities of Quantum Markov Chains
Shenggang Ying, Yuan Feng, Nengkun Yu +1
This paper studies three kinds of long-term behaviours, namely reachability, repeated reachability and persistence, of quantum Markov chains (qMCs). As a stepping-stone, we introdu…
Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs
Mingsheng Ying, Nengkun Yu, Yuan Feng
We extract a novel quantum programming paradigm - superposition of programs - from the design idea of a popular class of quantum algorithms, namely quantum walk-based algorithms. T…
Any subspace is locally distinguishable
Nengkun Yu, Runyao Duan, Mingsheng Ying
A subspace of a multipartite Hilbert space is called \textit{locally indistinguishable} if any orthogonal basis of this subspace cannot be perfectly distinguished by local operatio…
Quantum state tomography via reduced density matrices
Tao Xin, Dawei Lu, Joel Klassen +7
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 (U…