Concentration Bounds from Parallel Repetition Theorems

quantum information;parallel repetition;nonlocal games;interactive proofs;concentration bounds

Hornby, Tayloradvisor:Watrous, John ; affiliation1:Faculty of Mathematics ; Watrous, John ;

University of Waterloo

关键词: Master Thesis;    interactive proofs;    nonlocal games;    quantum information;    concentration bounds;    parallel repetition;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13638/1/Hornby_Taylor.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.