At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, ...
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction -- between quantum one-way functions and quantum hard-predicates -- is quantitatively more efficient than the known classical version. Roughly speaking, if the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/epsilon^2) in the classical case but only by a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the probability of predicting the hard-predicate. Moreover, we prove via a lower bound that, in a black-box framework, the classical version of the reduction cannot have overhead less than order n/epsilon^2. We also show that, using this reduction, a quantum bit commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation. This complements a recent result by Dumais, Mayers and Salvail, where the bit commitment scheme is perfectly concealing and computationally binding. We also show how to perform qubit commitment by a similar approach.
We present a quadratic Goldreich–Levin algorithm that is nearly optimal in the following ways. Given a bounded function f:F2n→R and any ε>0, the algorithm outputs a quadratic polynomial q:F2n→F2 whose correlation with (−1)q is within an additive ε of the maximum achievable correlation with any quadratic phase function. It runs in Oε(n3) time and makes Oε(n2logn) queries to f, matching the information-theoretic lower bound up to a logarithmic factor. The design of our algorithm draws on ideas from recent advances in quantum learning theory and departs from previous approaches based on algorithmic proofs of the inverse theorem for the Gowers uniformity norms.
Our problem is to evaluate a multi-valued Boolean function F through oracle calls. If F is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle f(a,x):{0,1}n×{0,1}n→{0,1} and a fixed (but hidden) value a0, we wish to obtain the value of a0 by querying the oracle f(a0,x). Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as f(a,x)=1 iff x=a and the IP-oracle defined as f(a,x)=a⋅xmod2. It is also well-known that the query complexity is Θ(N) (N=2n) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter K as the maximum number of 1's in a single column of Tf where Tf is the N×N truth-table of the oracle f(a,x). Our main result shows that the (quantum) query complexity is heavily governed by this parameter K: (i) The query complexity is Ω(N/K). (ii) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is O(N/K). (iii) The tight complexity, Θ(KN+logK), is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when K is small and this merit becomes larger when K is large, e.g., logK v.s. constant when K=cN.