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?
Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this communityI 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?
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$.