Honghao Fu

In the recent breakthrough result (Mastel and Slofstra, STOC24), the authors show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE. We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we analyze the four central compression techniques underlying the MIP*=RE proof (Ji et al., arXiv:2001.04383) --- question reduction, oracularization, answer reduction, and parallel repetition --- and show that they all preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol. Furthermore, we complete the study of the conversion between constraint-constraint and constraint-variable binary constraint system (BCS) nonlocal games, which provide a quantum information characterization of MIP* protocols. While Paddock (arXiv:2203.02525) established that any near perfect strategy for a constraint-variable game can be mapped to a constraint-constraint version, we prove the converse, fully establishing their equivalence.

Abstract When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is quantum? This question is central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations --- that is, correlations for which the number of measurements and number of measurement outcomes are fixed --- such that solving the quantum membership problem for this family is computationally impossible. Intuitively, our result means that the undecidability that arises in understanding Bell experiments is innate, and is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.

With the growing availability of experimental loophole-free Bell tests, it has become possible to implement a new class of device-independent random number generators whose output can be certified to be uniformly random without requiring a detailed model of the quantum devices used. However, all previous experiments require many input bits in order to certify a small number of output bits, and it is an outstanding challenge to develop a system that generates more randomness than is used. Here, we devise a device-independent spot-checking protocol which uses only uniform bits as input. Implemented with a photonic loophole-free Bell test, we can produce 24% more certified output bits (1,181,264,237 bits) than consumed input bits (953,301,640 bits), which is 5 orders of magnitude more efficient than our previous work [Phys. Rev. Lett. 124, 010505 (2020)]. The experiment ran for 91.0 hours, creating randomness at an average rate of 3,606 bits/second with a soundness error bounded by 5.7e-7 in the presence of classical side information. Our system will allow for greater trust in public sources of randomness, such as randomness beacons, and the protocol may one day enable high-quality sources of private randomness as the device footprint shrinks.

Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. Here we develop a broadly applicable framework, quantum probability estimation, for yielding efficient quantum-proof protocols. The framework is general and encompasses methods from previous works [Miller and Shi, SIAM Journal on Computing 46, 1304 (2017); Arnon-Friedman et al., Nature Communications 9, 459 (2018)]. Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution. Moreover, we demonstrate device-independent quantum randomness generation from a loophole-free Bell test with quantum probability estimation, obtaining multiple blocks of 512 random bits with an average experiment time of less than 5 minutes per block and with certified error bounded by $2^{-64}\approx 5.42\times 10^{-20}$.

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.