Penghui Yao

We consider the problem of deciding whether an $n$-qubit unitary (or $n$-bit Boolean function) is $\varepsilon_1$-close to some $k$-junta or $\varepsilon_2$-far from every $k$-junta, where $k$-junta unitaries act non-trivially on at most $k$ qubits and as the identity on the rest, and $k$-junta Boolean functions depend on at most $k$ variables. For constant numbers $\varepsilon_1,\varepsilon_2$ such that $0 < \varepsilon_1 < \varepsilon_2 < 1$, we show the following. 1. A non-adaptive $O(k\log k)$-query tolerant $(\varepsilon_1,\varepsilon_2)$-tester for $k$-junta unitaries when $2\sqrt{2}\varepsilon_1 < \varepsilon_2$. 2. A non-adaptive tolerant $(\varepsilon_1,\varepsilon_2)$-tester for Boolean functions with $O(k \log k)$ quantum queries when $4\varepsilon_1 < \varepsilon_2$. 3. A $2^{\widetilde{O}(k)}$-query tolerant $(\varepsilon_1,\varepsilon_2)$-tester for $k$-junta unitaries for any $\varepsilon_1,\varepsilon_2$. The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+25]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap. Besides, we adapt the first two quantum algorithms to be implemented using only single-qubit operations, thereby enhancing experimental feasibility, with a slightly more stringent requirement for the parameter gap.

We prove the decidability results for a sub-class of local state transformation problems, a fundamental problem in quantum information theory and quantum communication complexity. A local state transformation is specified by two bipartite quantum states $\rho^{AB}$ and $\sigma^{AB}$. Two non-communicating parties, Alice and Bob are provided with unbounded copies of the source state $\rho^{AB}$. The goal is to determine whether they can generate the target state that is arbitrarily close to the target state $\sigma^{AB}$ without communication. Ghazi, Kamath, and Sudan initiated the study of the decidability of the classical counterpart, non-interactive simulation of joint distributions, by introducing a machinery built on the theory of analysis on Boolean functions. With such a machinery, the decidability of non-interactive simulation of joint distributions was fully resolved by subsequent works. However, the decidability of local state transformations remains largely open. Qin and Yao resolved the case where the source state $\rho^{AB}$ is a noisy maximally entangled state. In this work, we show that whenever the source state $\rho^{AB}$ is classical, then local state transformations are decidable. Specifically, given $\delta>0$, the algorithm either outputs local operations that transform the source state to a state that is $\delta$-close to the target state or asserts that such local operations do not exist.

Motivated by the limitations of near-term quantum devices, we study nonlocal games in the highnoise regime, where the two players may share arbitrarily many copies of a noisy entangled state. In this regime, existing rigidity theorems are unable to certify any nontrivial quantum structure. We first characterize the maximal quantum winning probabilities of the CHSH game[CHSH69], the Magic Square game[Mer90a], and their 2-out-of-𝑛 variants [CRSV18] as explicit functions of the noise rate. These characterizations enable the construction of device-independent protocols for estimating the underlying noise level. Building on these results, we prove noise-robust rigidity theorems showing that these games ceritify one, two, and n pairs of anticommuting Pauli observables, respectively. To our knowledge, these are the first rigidity results of Pauli measurements that remain sound in the highnoise regime, which has applications in Measurement-Device-Independent (MDI) cryptography and studying the computational power of Multi-prover Interactive Proof System with entanglement and a vanishing completeness-soundness gap (MIP∗0). Our proofs rely on Sum-of-Squares decompositions and Pauli analysis techniques originating from quantum proof systems and quantum learning theory, respectively.

Shallow quantum circuits have attracted increasing attention in recent years, due to the fact that current noisy quantum hardware can only perform faithful quantum computation for a short amount of time. The constant-depth quantum circuits $\mathsf{QAC}^0$, a quantum counterpart of $\mathsf{AC}^0$ circuits, are the polynomial-size and constant-depth quantum circuits composed of only single-qubit unitaries and polynomial-size generalized Toffoli gates. The computational power of $\mathsf{QAC}^0$ has been extensively investigated in recent years. In this paper, we are concerned with $\mathsf{QLC}^0$ circuits, which are linear-size $\mathsf{QAC}^0$ circuits, a quantum counterpart of $\mathsf{LC}^0$. * We show that depth-$d$ $\mathsf{QAC}^0$ circuits working on $n$ input qubits and $a$ ancilla qubits have approximate degree at most $\tilde{O}((n+a)^{1-2^{-d}})$, improving the $\tilde{O}((n+a)^{1-3^{-d}})$ degree upper bound of previous works. Consequently, this directly implies that to compute the parity function, $\mathsf{QAC}^0$ circuits need at least $\tilde{O}(n^{1+2^{-d}})$ circuit size. * We present the first agnostic learning algorithm for $\mathsf{QLC}^0$ channels using subexponential running time and queries. Moreover, we also establish exponential lower bounds on the query complexity of learning $\mathsf{QAC}^0$ channels under both the spectral norm distance of the Choi matrix and the diamond norm distance. * We present a tolerant testing algorithm which determines whether an unknown quantum channel is a $\mathsf{QLC}^0$ channel. This tolerant testing algorithm is based on our agnostic learning algorithm. Our approach leverages low-degree approximations of $\mathsf{QAC}^0$ circuits and Pauli analysis as key technical tools. Collectively, these results advance our understanding of agnostic learning for shallow quantum circuits.

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family (PRU). Their proof developed a new path recording technique. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.