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?

  • $\begingroup$ I am a beginner and I have been reading about Deutsch and I want to know whether I can link two functions, so from my reading Deutsch oracle lets us know if the function is Constant or Balanced, and from searching online there are circuits for when you want to implement a constant or balanced functions, but how to implement a circuit that lets me know whether two functions are constant or balanced? $\endgroup$
    – n22
    Apr 1, 2022 at 23:28

1 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: Parallel DJ circuits

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!

  • $\begingroup$ What if I have two constant Deutsch circuits in parallel, how would I link them together to give me 1 if both are constant? $\endgroup$
    – n22
    Apr 2, 2022 at 20:07
  • $\begingroup$ @n22 I've added the circuit to my answer, please have a look. $\endgroup$ Apr 3, 2022 at 14:18

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.