0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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$
    – Peter Shor
    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$
    – Adam Bouland
    Dec 25, 2013 at 15:27

0

Reset to default

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.