Paper 2023/1783

An efficient quantum parallel repetition theorem and applications

John Bostanci, Columbia University
Luowen Qian, Boston University
Nicholas Spooner, University of Warwick, New York University
Henry Yuen, Columbia University

We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled to an equivalent $3$-message argument system, mirroring the transformation for quantum proof systems [KW00, KKMV07]. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan [Yan22]), EFI pairs (answering a question of Brakerski, Canetti, and Qian [BCQ23]), public-key quantum money schemes (answering a question of Aaronson and Christiano [AC13]), and quantum zero-knowledge argument systems. We also derive an XOR lemma [Yao82] for quantum predicates as a corollary.

Note: Full version.

Available format(s)
Publication info
Published elsewhere. Major revision. STOC 2024
post-quantumaverage-case complexitydirect productpuzzle
Contact author(s)
chb2154 @ columbia edu
luowenq @ bu edu
nickspoon0 @ gmail com
hyuen @ cs columbia edu
2024-04-16: revised
2023-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {John Bostanci and Luowen Qian and Nicholas Spooner and Henry Yuen},
      title = {An efficient quantum parallel repetition theorem and applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1783},
      year = {2023},
      doi = {10.1145/3618260.3649603},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.