Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument ⋆

Abstract. We use a quantum computational argument to prove, for any integer k ≥ 2, a complexity upper bound for nonadaptive k-query classical locally random reductions (LRRs) that allow bounded-errors. Extending and improving a recent result of Pavan and Vinodchandran [PV], we prove that if a set L has a nonadaptive 2-query classical LRR to functions g and h, where both g and h can output O(log n) bits, such that the reduction succeeds with probability at least 1/2 + 1/poly(n), then L ∈ PP NP /poly. Previous complexity upper bound for nonadaptive 2-query classical LRRs was known only for much restricted LRRs: LRRs in which the target functions can only take values in {0, 1, 2} and the error probability is zero [PV]. For k> 2, we prove that if a set L has a nonadaptive k-query classical LRR to boolean functions g1, g2,..., gk such that the reduction succeeds with probability at least 2/3 and the distribution on (k/2+ √ k)-element subsets of queries depends only on the input length, then L ∈ PP NP /poly. Previously, for no constant k> 2, complexity upper bound for nonadaptive k-query classical LRRs was known even for LRRs that do not make errors. Our proofs follow a two stage argument: (1) simulate a nonadaptive kquery classical LRR by a 1-query quantum weak LRR, and (2) upper bound the complexity of this quantum weak LRR. To carry out the two stages, we formally define nonadaptive quantum weak LRRs, and prove that if a set L has a 1-query quantum weak LRR to a function g, where g can output polynomial number of bits, such that the reduction succeeds with probability at least 1/2 + 1/poly(n), then L ∈ PP NP /poly