3
$\begingroup$

I am currently attempting to solve a problem from Nielsen-Chuang, and I can't seem to figure out how I would do this;

I'm trying to implement Grover's algorithm to solve the problem of differentiating between the two functions with 99% probability in O(1),

$$ f_0:\{0,1\}^n → \{-1,1\} \; s.t. \; \hat{f}(00...0)=\sqrt{2/3}\\ f_1:\{0,1\}^n → \{-1,1\} \; s.t. \; \hat{f}(11...1)=\sqrt{2/3} $$

Does anyone know how I would do this?

$\endgroup$
3
  • $\begingroup$ what is $\hat f$ here? $\endgroup$ – glS Mar 16 at 16:00
  • $\begingroup$ @glS $\hat{f}$ is a function such that $\hat{f}=<f | \chi_x>$ where $\chi_x$ is a Fourier basis or Boolean function $\endgroup$ – lambda Mar 16 at 17:30
  • $\begingroup$ @MarkS thanks for the response, how would I resolve it using the Deutsch-Josza? I'm still getting to grips with quantum query algorithms so any help would be appreciated $\endgroup$ – lambda Mar 16 at 19:31
1
$\begingroup$

I hunted around for this for a little bit and couldn't find it in my copy of N&C, but nonetheless I think that the setup is more akin to the Deutsch-Jozsa algorithm than to Grover's algorithm.

TL/DR, much as the Deutsch-Jozsa algorithm uses the Hadamard transform to distinguish a constant function from a balanced function with the promise that the function is constant or balanced, a quantum Fourier transform can distinguish an almost-constant function from a high frequency function with the promise that the function is almost-constant or is high-frequency. Repeating a small number of times amplifies the success probability.


For example, the Deutsch-Jozsa algorithm uses the Hadamard transform to distinguish a constant function from a balanced function. Similarly as described in the question it appears that we have oracle access to a Boolean function $f$:

$$f:\{0,1\}^n \mapsto \{0,1\}$$

with a promise on the coefficients of the Fourier transform, that either:

$$\hat{f}(00...0)=\sqrt{2/3},$$

e.g. $f$ is nearly constant on its codomain, or

$$\hat{f}(11...1)=\sqrt{2/3},$$

e.g. $f$ has a high frequency. There is no promise on other Fourier coefficients. Our task is to determine whether $f$ is constant or is high frequency.

Similar to the Deutsch-Jozsa where we prepare a uniform superposition on the input register, evaluate the oracle function, perform a Hadamard transform on the first register, and measure the first register, here we can prepare a uniform superposition on our input register, evaluate the oracle function, perform a quantum Fourier transform on the first register, and measure the first register.

If our oracle is nearly constant, we measure the first register as $\vert 00\cdots0\rangle$ with probability $(\sqrt{2/3})^2=2/3$. If our oracle is high-frequency, we measure the first register as $\vert 11\cdots 1\rangle$ with probability $(\sqrt{2/3})^2=2/3$. Either way with probability $1/3$ we might get junk by measuring some other string (say $\vert101001\cdots0\rangle$) corresponding to another Fourier coefficient.

Nonetheless we can repeat the procedure, say, $4$ times, and quickly get a high probability, $\gt 99\%$, of faithfully determining whether $f$ is constant or high-frequency, simply based on taking the majority and relying on Chernoff's bound.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.