Minglong Qin

In many quantum information tasks, we encounter scenarios where information about two incompatible observables must be retrieved. A natural approach is to perform consecutive measurements, raising a key question: How does the information gained from the first measurement compare to that from both? The consecutive measurement theorem (CMT) provides a general relation between these quantities and has found applications in quantum cryptography. However, its previous formulations are often either too loose or too brittle to yield meaningful bounds. In this work, we first establish a tight CMT and apply it to achieve the best upper bounds on the quantum value of certain nonlocal games and their parallel repetitions to date. We then develop a robust CMT and explore a novel application of CMT to obtain a tighter no-go theorem for quantum oblivious transfer in some regime. These contributions strengthen the theoretical tools for analyzing quantum advantage and have concrete implications for nonlocal games and quantum cryptographic protocols.

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.

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.

In many cryptographic tasks, we encounter situations where we would like to retrieve some information about two incompatible observables. A natural strategy to tackle this problem involves consecutive measurements of two observables, raising the critical question: How does the information gained from the first measurement relate to that obtained through both consecutive measurements? A loose relation between these two quantities has been established by the consecutive measurement theorem and is found useful in quantum proofs of knowledge and nonlocal games. In this work, we establish a tight consecutive measurement theorem, and apply our theorem to improve the best-known bounds on the quantum value of CHSH_q(p) games and their parallel repetition. Moreover, we explore a novel application of the consecutive measurement theorem to find tighter trade-off relations for quantum oblivious transfer in most regimes. This advancement enhances the analytical toolkit to study quantum advantage and has direct implications for quantum cryptographic protocols.