4
$\begingroup$

I'm trying to understand how the Deutsch–Jozsa algorithm works with the following circuit:

Circuit in Quirk

enter image description here

Since we have the top 2 wires measuring $|0\rangle$ with 100% probability, it means $U_f$ is constant. And that's what I'm having trouble understanding...what exactly is constant?

If I isolate $U_f$ I get this: Oracle function

enter image description here

I understand the concept of balanced and constant functions, and that an n-bit binary string will have $2^n$ mappings, which gives $2^n$ possible functions. So how can I see that $f$ is constant in the isolated circuit above?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

The circuit you gave implements an oracle for a function $f(x) = 0$, which is constant.

enter image description here

You can observe that there are no gates leading from the top two wires (inputs $|x\rangle$) to the bottom wire (output $|y\rangle$). Since the oracle is supposed to transform $|x\rangle|y\rangle$ into $|x\rangle|y \oplus f(x)\rangle$, and $|y\rangle$ always remains unaffected, you can see that $f(x) = 0$.

$\endgroup$
3
  • $\begingroup$ Wow, you are fantastic, thanks. I'm new to quantum programming, so I'll need to meditate on this. Is there a way to "extract" the oracle function to a classical form? Like a matrix or something. $\endgroup$
    – Fernando
    Mar 23, 2019 at 4:06
  • $\begingroup$ You can reverse-engineer the matrix of the unitary representing the oracle by applying the circuit (stripped of the H before and after oracle application) to all basis vectors in turn and writing down the amplitudes of the results. For example, for your oracle you'll start with your "isolated" Uf to get the oracle effect on 00; then you'll flip the state of the first qubit to get the oracle effect on 10, and so on. (By the way, your circuit swaps the two inputs to the oracle, so strictly speaking it's not an implementation of an oracle - oracles are supposed to leave their inputs unchanged.) $\endgroup$ Mar 23, 2019 at 4:36
  • $\begingroup$ Ok, I'll read more and try some stuff on my own. If case of trouble, I can post a more specific question. Спасибо )) $\endgroup$
    – Fernando
    Mar 23, 2019 at 8:15

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.

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