01440nas a2200121 4500008004100000245010100041210006900142260001500211520101600226100002401242700001601266856003601282 2016 eng d00aPerformance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree0 aPerformance of QAOA on Typical Instances of Constraint Satisfact c2016/01/083 aWe consider constraint satisfaction problems of bounded degree, with a good notion of "typicality", e.g. the negation of the variables in each constraint is taken independently at random. Using the quantum approximate optimization algorithm (QAOA), we show that μ+Ω(1/D−−√) fraction of the constraints can be satisfied for typical instances, with the assignment efficiently produced by QAOA. We do so by showing that the averaged fraction of constraints being satisfied is μ+Ω(1/D−−√), with small variance. Here μ is the fraction that would be satisfied by a uniformly random assignment, and D is the number of constraints that each variable can appear. CSPs with typicality include Max-kXOR and Max-kSAT. We point out how it can be applied to determine the typical ground-state energy of some local Hamiltonians. We also give a similar result for instances with "no overlapping constraints", using the quantum algorithm. We sketch how the classical algorithm might achieve some partial result.1 aLin, Cedric, Yen-Yu1 aZhu, Yechao uhttp://arxiv.org/abs/1601.01744