How to implement a controlled-U gate?

Also this Monday in Paraty, in a talk aptly titled “Impossibility of controlling a black box quantum gate”, Mateus Araújo talked about alternative ways of framing what seems to be the same question, and the different answers that follow. The first question Mateus considers is: given a single qubit unitary U, how can we apply the gate controlled-U (CTR-U)?

Answer: As we can see in Nielsen and Chuang (and following an old paper by Barenco et al.), there is a decomposition of CTR-U in terms of four single qubit unitaries and two CNOT gates. Alternatively, Kitaev in quant-ph/9522026 gives an alternative construction.
These two constructions require us knowing U in advance, so the relevant decomposition can be worked out.

Let us now reformulate the question: what if U is a black-box unitary – can we implement CTR-U then?

Now we have two conflicting answers, which shows that perhaps this reformulation is an ill-defined question.

Answer A: Zhou et al., in arxiv:1006.2670, give a simple prescription. If U is given as a unitary that acts on the polarization of a photon, put it in one arm of a Mach-Zehnder interferometer. The first beam splitter creates a superposition of the (path degree of freedom) control, and we have implemented a CTR-U.

Answer B: it’s impossible. In the circuit model, Mateus gave a simple proof (that this blog post is too brief to include!) that given a black-box unitary, it is impossible to construct a CTR-U gate. This seems to be a folklore result in quantum information, as it is mentioned en passant in a footnote in Kitaev’s paper.

Using this new result, Mateus gave yet another proof of the no-cloning theorem.

Mateus’ results show an apparent discrepancy in the hypotheses behind the circuit model on one hand, and physically relevant physical implementations of unitaries on the other. This conflict deserves to be better studied. Mateus points out that algorithms which rely on controlled unitaries may profit from a better understanding of this problem, for example the DQC1 model of one pure qubit controlling mixed qubits, and Kitaev’s phase estimation algorithm.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s