I am working on a circuit for a Grover problem and during that I am trying to minimize the used QuBits.

The problem is shown in the attached image. In this case the circuit is more or less efficient but with a growing number of input bits (the x register) the ccx grows more complex (cccx, ccccx, ...) and inefficient but more importantly more qubits in y register are needed (one more for each comparison).

My primary goal is to reduce the used y-QuBits. Can someone think of such a circuit or is it already optimal (I really dont think so).

enter image description here


1 Answer 1


Instead of saving the information of a single comparison into a y qubit, you can use a controlled adder. Instead of $n$ y qubits you would only need $\log_2 n$.

  • $\begingroup$ Thanks for your answer. Could you clarify what you mean by a controleld adder? A link to a paper or further information would be great. $\endgroup$
    – Idefixus
    May 3, 2020 at 13:09
  • 1
    $\begingroup$ @Idefixus maybe this : arxiv.org/pdf/quant-ph/0206028 but there are plenty of adders online. Pick one and perform every operation of the adder implementation as a controlled operation so that you only increment when you state is a solution $\endgroup$
    – draks ...
    May 3, 2020 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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