Consider an arbitrary boolean function

$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as:

$$f(x_1, x_2 ... x_n) $$ where each $x_i$ is a boolean variable

We note here that the function in question can be evaluated in constant time (is given by a constant time oracle).

The task is to determine whether this function is constant on all inputs or not.

We can consider the set of integers $Z$ modulo $2^n$ and look at their binary representation: noting that each digit in this binary representation corresponds to a value for one of the functional variables thus we write out $f$ as

$$f((Q \mod 2)_2, \frac{(Q \mod 4)_2}{2_2}, \frac{(Q \mod 8)_2}{4_2} ... \frac{(Q \mod 2^n)_2}{2^{n-1}_2})) $$

Where $n_2$ means convert n to binary and division is integer division

We note that if this function is periodic with period = 1, then it must be constant. Can a Quantum Fourier Transform be employed to calculate the period of this function or merely test that the period is not equal to 1?

  • 5
    $\begingroup$ The Quantum Fourier transform can't distinguish between a constant function and a function which is constant except for a few isolated points. It can determine whether a function is nearly constant, but that can be done classically using random sampling. $\endgroup$ Dec 25, 2013 at 5:29
  • 5
    $\begingroup$ Agreed. In fact an efficient algorithm for this problem provably cannot exist; this follows from the optimality of Grover search. (More specifically, given $f:\{0,1\}^n \rightarrow \{0,1\}$, a quantum computer requires $\Omega(2^{n/2})$ queries to $f$ to determine if there exists an $x$ such that $f(x)=1$.) $\endgroup$ Dec 25, 2013 at 15:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.