Nengkun Yu

STOC Conference 2025 Conference Paper

Pauli Measurements Are Not Optimal for Single-Copy Tomography

• Jayadev Acharya
• Abhilash Dharmavarapu
• Yuhan Liu 0007
• Nengkun Yu

I&C Journal 2024 Journal Article

Quantum temporal logic and reachability problems of matrix semigroups

• Nengkun Yu

We study the reachability problems of a quantum finite automaton. More precisely, we introduce quantum temporal logic (QTL) that specifies the time-dependent behavior of quantum finite automaton by presenting the time dependence of events temporal operators ◊ (eventually) and □ (always) and employing the projections on subspaces as atomic propositions. The satisfiability of QTL formulae corresponds to various reachability problems of matrix semigroups. We prove that the satisfiability problems for □ ∨ i m p i, ◊ □ ∨ i m p i and □ ◊ ∨ i m p i with atomic propositions p i are decidable. This result solves the open problem of Li and Ying 2014. Notably, the decidability of □ ◊ p can be interpreted as a generalization of Skolem-Mahler-Lech's celebrated theorem based on additive number theory. This paper's last part shows how the quantum finite automaton can model the general concurrent quantum programs, which may involve an arbitrary classical control flow.

UAI Conference 2023 Conference Paper

Accelerating Voting by Quantum Computation

• Ao Liu 0001
• Qishen Han
• Lirong Xia
• Nengkun Yu

Studying the computational complexity and designing fast algorithms for determining winners under voting rules are classical and fundamental questions in computational social choice. In this paper, we accelerate voting by leveraging quantum computation: we propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. We show that our algorithm can be quadratically faster than any classical algorithm (based on sampling with replacement) under a wide range of common voting rules, including positional scoring rules, Copeland, and single transferable voting (STV). Precisely, our quantum-accelerated voting algorithm outputs the correct winner with high probability in $\Theta\left(\frac{n}{\text{MOV}}\right)$ time, where $n$ is the number of votes and $\text{MOV}$ is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires $\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.

TCS Journal 2020 Journal Article

Strassen's theorem for quantum couplings

• Li Zhou
• Shenggang Ying
• Nengkun Yu
• Mingsheng Ying

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.

STOC Conference 2018 Conference Paper

Capacity approaching coding for low noise interactive quantum communication

• Debbie W. Leung
• Ashwin Nayak 0001
• Ala Shayeghi
• Dave Touchette
• Penghui Yao
• Nengkun Yu

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 (√є loglog1/є) 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 є.

STOC Conference 2017 Conference Paper

Exponential separation of quantum communication and classical information

• Anurag Anshu
• Dave Touchette
• Penghui Yao
• Nengkun Yu

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.

STOC Conference 2016 Conference Paper

Sample-optimal tomography of quantum states

• Jeongwan Haah
• Aram W. Harrow
• Zhengfeng Ji
• Xiaodi Wu 0001
• Nengkun Yu

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 ( dr 2 /є 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 Ω( r 2 d /δ) 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 .

MFCS Conference 2013 Conference Paper

Reachability Analysis of Recursive Quantum Markov Chains

• Yuan Feng 0001
• Nengkun Yu
• Mingsheng Ying

Abstract 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 Yannakakis’s 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.