I know that the oracle $U_f$ has to be either constant or balanced. But what if $f$ is an AND function? I know in that case it is neither.
So my question is what happens if $U_f$ is neither constant nor balanced?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ You can just work it out? $\endgroup$– Norbert SchuchApr 5, 2022 at 22:50
-
$\begingroup$ sorry but what do you mean? $\endgroup$– n22Apr 5, 2022 at 23:12
-
$\begingroup$ It should be very easy to work out what happens when you e.g. plug in the AND function. $\endgroup$– Norbert SchuchApr 5, 2022 at 23:24
-
1$\begingroup$ I think @NorbertSchuch means to merely apply Hadamard gates to the output when the promise is broken, and calculate the corresponding probabilities. You use the example of an AND oracle, as opposed to a constant or balanced function. See this question and answer from a sister site. This paper on broken promises seems relevant. $\endgroup$– Mark SpinelliApr 5, 2022 at 23:25
-
1$\begingroup$ @Mark Thanks for digging out that answer of mine. Had completely forgotten about it! $\endgroup$– Norbert SchuchApr 5, 2022 at 23:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
I like to think of the Deutsch-Jozsa problem as akin to asking for the squared "DC component" of the output oracle, where for convenience $1$ gets mapped to $-1$ and $0$ gets mapped to $+1$.
Considering only two qubit gates for now, we have the "constant" all $-1$ oracle (TRUE) or the all $+1$ oracle (FALSE), and the "balanced" identity oracle and the XOR/XNOR oracles. The squared DC component of the constant functions, after normalization, is $1$, and hence you can measure $|1\rangle$ with probability $1$, while the squared DC component of the balanced functions, after normalization, is $0$, and hence you measure $|0\rangle$ with probability $1$.
The AND oracle, on the other hand, acting on two qubits, has an output of $-1$ for precisely $\frac{1}{4}$'th of the time, and has an output of $+1$ for the remaining $\frac{3}{4}$'th of the time. You can sum the outputs to get the DC component, and do as Norbert S. recommends to calculate the corresponding probabilities. You'll find that, with two qubit input gates and your oracle being the AND gate, you get the output of $|0\rangle$ with 50% probability and the output of $|1\rangle$ with 50% probability. So you don't learn much of anything in this case. Same with the NAND gate (and OR and NOR and NIMPLIES).
It's a bit more interesting for larger inputs. For example the AND gate, acting on a large number of qubits, is very close to being $0$ for almost all inputs, and hence is close to constant and the Deutsch-Jozsa algorithm has a high probability of measuring $|1\rangle$. Similarly the OR gate, acting on a large number of qubits, is very close to being $1$ for almost all inputs, and hence is also close to constant and the Deutsch-Jozsa algorithm likewise has a high probability of measuring $|1\rangle$.
answered Apr 5, 2022 at 23:58
-
$\begingroup$ regarding the last part of your answer, if it is close to constant for example, can we consider it constant? $\endgroup$– n22Apr 6, 2022 at 0:28
-
$\begingroup$ Uhm.... no. A constant function is the same for all inputs. The AND gate with $n$ bits fanned in is not constant, even though it would be $0$ for all but one of the $2^n$ inputs. $\endgroup$ Apr 6, 2022 at 1:06