This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions:- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances).- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies.- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.
【 预 览 】
附件列表
Files
Size
Format
View
Concentration Bounds from Parallel Repetition Theorems