玉置 卓

It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to ``fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> circuits. Similar results should hold for other sub-universal models.

A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics. The parallel repetition theorem states that for any two-prover one-round game with value smaller than 1, k-fold parallel repetition reduces the value of the game exponentially in k. The theorem was originally proved by Raz (SICOMP 1998) and later simplified and improved by Holenstein (Theory of Computing 2009) and Rao (SICOMP 2011). All the known proofs are based on information theoretic arguments. Very recently, Dinur and Steurer (STOC 2014) obtained a new proof of the parallel repetition theorem based on a matrix analysis argument. In this paper, we describe a special case of Dinur and Steurer's proof. We also describe an application of the parallel repetition theorem to inapproximability results of two-prover one-round games. Our presentation is almost self-contained in the sense that we only assume the PCP theorem. To do so, we also present proofs for the necessary results related to algebraic graph theory and hardness of approximation.