2020/08/17 by Abel Molina, Molina, Abel
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2008.07445
openalex publication_date 2020/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note, we show that O(log (1/ε)) rounds of parallel repetition with a threshold suffice to reduce completeness and soundness error to ε for single-prover quantum interactive proof systems. This improves on a previous O(log (1/ε) log log (1/ε)) bound from Hornby (2018), while also simplifying its proof. A key element in our proof is a concentration bound from Impagliazzo and Kabanets (2010).