How to create a quantum circuit checking whether two functions $f$ or $g$ are of the same type?

Question

I want to create a quantum circuit that checks whether two functions f and g are of the same type, i.e., constant or balanced, or not. In other words, the output of the circuit should output 1 if both f and g are constants, and 0 otherwise. I know how to implement a balanced circuit and a constant one but how do I address the situation above?

Answer 1

Assuming that you have two oracles that implements respectively $f$ and $g$, it is quite simple to perform the algorithm you're looking for, using only a single call to both $\mathcal{O}_f$ and $\mathcal{O}_g$.

With a single call to $\mathcal{O}_f$, you can get a single bit telling you whether $f$ is balanced or constant. In parallel, you can run the same circuit using $\mathcal{O}_g$. You would thus get another bit telling you whether $g$ is balanced or constant. You finally have to compare these two bits to decide whether they were of the same type. All in all, the complexity is almost the same as the original Deutsch algorithm, since you only run it in parallel and add a single operation after it.

The associated circuit is the following one:

It is to be noted that the classical control check whether the measured states are $\left|0^n\right\rangle$. Thus, when we measure the fourth register, its state is:

• $|0\rangle$ if the two previous measurements yielded the same result;
• $|1\rangle$ otherwise.

This of course assume that both $f$ and $g$ are either balanced or constant, and that you can use as many qubits as you want. Don't hesitate to tell me whether you would like too know about a solution using the same number of qubits as in Deutsch's algorithm!