<p>The <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=589" rel="nofollow">Kushilevitz-Mansour</a> algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, <a href="http://epubs.siam.org/doi/abs/10.1137/0222080" rel="nofollow">Kushilevitz-Mansour</a> only talked about Fourier transforms over $\mathbb{Z}_2$, but generalization to FTs over general finite Abelian groups (see e.g. <a href="http://people.csail.mit.edu/akavia/AkaviaPhDThesis.pdf" rel="nofollow">Akavia's thesis</a>) are known.</p>

<p>As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster <a href="http://martinschwarz.files.wordpress.com/2012/01/qip2010-simulatinghth.pdf" rel="nofollow">here</a>, and the pre-print <a href="http://arxiv.org/abs/1310.6749" rel="nofollow">here</a>). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.</p>

CC BY-SA 3.0
2013-04-29T21:38:10.503Z
Thanks, Martin! I suppose it is not known how hard it is to sample from the Fouriet transform even of AC^0 functions, right? (In the case of depth-2 a conjecture of Mansour asserts that it is polynomial (with randomization).
Gil Kalai
CC BY-SA 3.0
2013-04-29T07:40:20.627Z
2013-11-01T22:44:26.947Z
2013-11-01T22:44:26.947Z
Martin Schwarz
<p>One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.</p>

<p>Here and below when I talk about sampling the Fourier transform I mean choosing x according to $|\hat f(x)|^2$. (Normalized if necessary and approximately).</p>

<p>Can we describe the complexity class, that we can call P-FOURIER SAMPLING, of approximate sampling Boolean functions of P? Are there problems which are complete for this class?</p>

<p>Given a class X of Boolean functions what can be said about the the computational complexity, that we can refer to as SAMPLING-X of approximating sampling the Fourier transform of functions in X. (I suppose that if X is BQP then X-SAMPLING is still within the power of quantum computers.)</p>

<p>What are the examples of X where SAMPLING-X is in P? Are there interesting examples where SAMPLING-X is NP-hard? </p>

<p>There are several variants of this problem that can also be interesting. 
On the Fourier side, rather than approximate-sample we can talk about a decision problem enabled (probabilistically) by approximate sampling. On the primal side, we can start with a class X of probability distributions and ask what is the relation between the ability to approximately sample a distribution D in X and approximately sample the (normalized) Fourier transform.    </p>

<p>In short, what is known about this question. </p>

<p><strong>Update:</strong> Martin Schwarz pointed out that if all the Fourier coefficients themselves are concentrated only on a polynomial number of entries then it is possible in BPP to approximate these large coefficients (and thus also to approximately sample.) This goes back to Goldreich-Levin, and Kushilevitz-Mansour. Are there interesting classes of functions where there is a probabilistic polynomial algorithm for approximately sampling the Fourier side, where the Fourier coefficients are spread over more than polynomially many coefficients?   </p>

<p><strong>Added Later:</strong> Let me mention a few concrete problems.</p>

<p>1) How hard is it to approximately sample the Fourier transform of Boolean functions in P.</p>

<p>a) One question that Scott Aaronson mentioned in a comment below is to show that this is not in BPP. Or something weaker along the lines that if this task is in BPP some collapse is happening.  (Scot Conjectures that this is the case.)</p>

<p>b) Another question is to show that this task is hard with respect to some quantum-based complexity class. E.g, to show that if you can perform this task you can solve decision problems in BPP assisted with log-depth quantum computers, or something like that.</p>

<p>2) What are classes of Boolean functions such that approximately sampling their Fourler transform is in P. What we know is that this is the case when the Fourier coefficients are concentrated on polynomial many coefficients, but this seems very restricted.</p>

<p>3) Is there some complexity class X high up in the PH that an X-machine can approximately sample the Fourier transform of every function that an X-machine can compute. </p>

<p>4) I was especially interested in the problem of sampling the Fourier transform of the crossing event for percolation on an n by n hexagonal grid.  </p>

CC BY-SA 3.0
2013-05-03T18:49:33.707Z
Gil, in case this is of interest to you: before Alex Arkhipov and I started working on BosonSampling, the "original" thing I wanted to prove was that the approximate Fourier sampling problem -- i.e., *exactly* the problem you describe -- is not in BPP unless the polynomial hierarchy collapses.  Unfortunately, I wasn't able to prove that or even get good evidence for it, which motivated us to switch attention to bosons and the "robustly #P-complete" permanent.  However, I'd now like to reiterate my conjecture that approximate Fourier sampling is hard, assuming only that PH is infinite. :-)
Scott Aaronson
CC BY-SA 3.0
2013-05-04T20:00:42.917Z
Thanks, Scott, thhis is very interesting. I will mention your conjecture along with a few others in the next edit of the question.
Gil Kalai
CC BY-SA 3.0
2013-05-05T16:47:43.067Z
BTW, Scott, isn't the argument via permanents that shows that BOSONSAMPLING in BPP implies collapse of the PH works also for Fourier sampling?
Gil Kalai
CC BY-SA 3.0
2013-05-06T15:02:41.523Z
Gil: Yes, for *exact* sampling algorithms, exactly the same argument goes through.  But for approximate sampling algorithms, I'm not certain: one would need to believe that approximate computation of Fourier coefficients should be #P-complete on average, just as Arkhipov and I conjectured that approximating the permanent of an i.i.d. Gaussian matrix should be #P-complete on average.
Scott Aaronson
<cc.complexity-theory><quantum-computing><pr.probability><randomized-algorithms><sample-complexity>
The complexity of sampling (approximately) the Fourier transform of a Boolean function
Gil Kalai
# The complexity of sampling (approximately) the Fourier transform of a Boolean function

(Asked by: username_0 on 2013-04-28)

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.

Here and below when I talk about sampling the Fourier transform I mean choosing x according to $|\hat f(x)|^2$. (Normalized if necessary and approximately).

Can we describe the complexity class, that we can call P-FOURIER SAMPLING, of approximate sampling Boolean functions of P? Are there problems which are complete for this class?

Given a class X of Boolean functions what can be said about the the computational complexity, that we can refer to as SAMPLING-X of approximating sampling the Fourier transform of functions in X. (I suppose that if X is BQP then X-SAMPLING is still within the power of quantum computers.)

What are the examples of X where SAMPLING-X is in P? Are there interesting examples where SAMPLING-X is NP-hard?

There are several variants of this problem that can also be interesting.
On the Fourier side, rather than approximate-sample we can talk about a decision problem enabled (probabilistically) by approximate sampling. On the primal side, we can start with a class X of probability distributions and ask what is the relation between the ability to approximately sample a distribution D in X and approximately sample the (normalized) Fourier transform.

In short, what is known about this question.

**Update:** username_2 pointed out that if all the Fourier coefficients themselves are concentrated only on a polynomial number of entries then it is possible in BPP to approximate these large coefficients (and thus also to approximately sample.) This goes back to Goldreich-Levin, and Kushilevitz-Mansour. Are there interesting classes of functions where there is a probabilistic polynomial algorithm for approximately sampling the Fourier side, where the Fourier coefficients are spread over more than polynomially many coefficients?

**Added Later:** Let me mention a few concrete problems.

1) How hard is it to approximately sample the Fourier transform of Boolean functions in P.

a) One question that username_1 mentioned in a comment below is to show that this is not in BPP. Or something weaker along the lines that if this task is in BPP some collapse is happening. (Scot Conjectures that this is the case.)

b) Another question is to show that this task is hard with respect to some quantum-based complexity class. E.g, to show that if you can perform this task you can solve decision problems in BPP assisted with log-depth quantum computers, or something like that.

2) What are classes of Boolean functions such that approximately sampling their Fourler transform is in P. What we know is that this is the case when the Fourier coefficients are concentrated on polynomial many coefficients, but this seems very restricted.

3) Is there some complexity class X high up in the PH that an X-machine can approximately sample the Fourier transform of every function that an X-machine can compute.

4) I was especially interested in the problem of sampling the Fourier transform of the crossing event for percolation on an n by n hexagonal grid.

**Tags:** cc.complexity-theory, quantum-computing, pr.probability, randomized-algorithms, sample-complexity

> **Comments:**
> **username_1**: Gil, in case this is of interest to you: before Alex Arkhipov and I started working on BosonSampling, the "original" thing I wanted to prove was that the approximate Fourier sampling problem -- i.e., *exactly* the problem you describe -- is not in BPP unless the polynomial hierarchy collapses.  Unfortunately, I wasn't able to prove that or even get good evidence for it, which motivated us to switch attention to bosons and the "robustly #P-complete" permanent.  However, I'd now like to reiterate my conjecture that approximate Fourier sampling is hard, assuming only that PH is infinite. :-)  
> **username_0**: Thanks, Scott, thhis is very interesting. I will mention your conjecture along with a few others in the next edit of the question.  
> **username_0**: BTW, Scott, isn't the argument via permanents that shows that BOSONSAMPLING in BPP implies collapse of the PH works also for Fourier sampling?  
> **username_1**: Gil: Yes, for *exact* sampling algorithms, exactly the same argument goes through.  But for approximate sampling algorithms, I'm not certain: one would need to believe that approximate computation of Fourier coefficients should be #P-complete on average, just as Arkhipov and I conjectured that approximating the permanent of an i.i.d. Gaussian matrix should be #P-complete on average.  

---

## 1 answers

### Answer by username_2 on 2013-04-29. Score: 10

The [Kushilevitz-Mansour](http://www.contrib.andrew.cmu.edu/~ryanod/?p=589) algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, [Kushilevitz-Mansour](http://epubs.siam.org/doi/abs/10.1137/0222080) only talked about Fourier transforms over $\mathbb{Z}\_2$, but generalization to FTs over general finite Abelian groups (see e.g. [Akavia's thesis](http://people.csail.mit.edu/akavia/AkaviaPhDThesis.pdf)) are known.

As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster [here](http://martinschwarz.files.wordpress.com/2012/01/qip2010-simulatinghth.pdf), and the pre-print [here](http://arxiv.org/abs/1310.6749)). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.

> **Comments:**
> **username_0**: Thanks, Martin! I suppose it is not known how hard it is to sample from the Fouriet transform even of AC^0 functions, right? (In the case of depth-2 a conjecture of Mansour asserts that it is polynomial (with randomization).  

---

