The projector-controlled not gate $\text{C$_\Pi$NOT}$ is defined as

$$\text{C$_\Pi$NOT} \, \colon= \Pi \otimes X + (\mathbb{I}-\Pi)\otimes\mathbb{I}\,, \tag{1}$$ in András Gilyén et. al. (2018)[arXiv:1806.01838].

Can this gate be implemented efficiently, namely, polynomial size to qubits included by the circuit?

Particularly, how about the case that $\Pi$ is a projector onto $r$-dimensional subspace spanned by computational bases? I.e., $$\Pi = \sum_{i=1}^r |i\rangle\langle i|\,,\tag{2}$$where $\{|i\rangle\}_i$ are computational bases.

Maybe, I think that this problem is reduced to whether a measurement $\{\Pi, \mathbb{I}-\Pi\}$ is efficiently implementable in a coherent manner using multi-Toffoli gates and ancilla qubits.


1 Answer 1


I suspect that depends on $\Pi$. There will be easily categorised cases where you can.

For example: $\Pi$ projects onto a subset of basis states for which there exists an efficient classical calculation that recognises membership of the subset).

There will be other $\Pi$ for which it's impossible, e.g. (I suspect) a rank 1 projector onto a (family of) quantum states that cannot be efficiently prepared on a quantum computer.

  • $\begingroup$ How about in the case that $\Pi$ is a projector onto a $r$-dimensional subspace spanned by computational bases? I.e., $\Pi = \sum_{i=1}^r |i\rangle\langle i|$, where $\{| i\rangle\}_i$ is computational bases. I think that if we use $r$ multi-controlled Toffoli gate (which has $\mathcal{O}(n)$ circuit complexity), we can trivially implement this C$_\Pi$NOT gate in $\mathcal{O}(rn)$. However, if $r$ is exponential, it is inefficient. Then, I don't find that more efficiently implementable... $\endgroup$
    – Takimoto.R
    Nov 28, 2023 at 11:08
  • $\begingroup$ Sorry, $n$ denotes the number of qubits $\endgroup$
    – Takimoto.R
    Nov 28, 2023 at 11:24
  • $\begingroup$ this is the same calculation as introducing an ancilla and evaluating $i\leq r$. There's an efficient classical algorithm for that. $\endgroup$
    – DaftWullie
    Nov 28, 2023 at 12:03
  • $\begingroup$ Is it correct to understand it as efficiently implementable (using ancillae maintaining superposition) since there exists an efficient classical algorithm that judges whether i≤r or not, right? If it's not inconvenient, could you please provide me with references? $\endgroup$
    – Takimoto.R
    Nov 29, 2023 at 2:44
  • $\begingroup$ I've got no idea about a reference (not my strong point!), but it's a very simple procedure: compute a 0/1 value onto an ancilla. Do a controlled-not off that ancilla. Then invert the computation that set the value of the ancilla. Any efficient classical algorithm (such as $i\leq r$) can be done in this way. $\endgroup$
    – DaftWullie
    Nov 29, 2023 at 7:46

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.