1
$\begingroup$

Let us assume that we have a classical function $f:\{0\,;\,1\}^n\to\{0\,;\,1\}^m$ which is efficiently computable. Then, its oracle is defined with $\mathbf{U}_f\,|x\rangle\,|y\rangle=|x\rangle\,|y\oplus f(x)\rangle$. I quite often read that if $f$ is efficiently computable, then so is $\mathbf{U}_f$. Why is it the case? Where is the computational cost of evaluating $f$ taken into account?

Since $\mathbf{U}_f$ is a permutation matrix, one can implement it with at most $2^{n+m}$ SWAP gates, but this is not very efficient. What am I missing?

Another related question is: given a permutation matrix, how can one find the appropriate CNOT/SWAP gates succession to implement it? Even if an efficient solution exists, how does one find it?

Improve this question
$\endgroup$
1
$\begingroup$

There are several different issues all bundled together here.

First is the concept of classical universality: whatever gate set you choose to specify your classical algorithm in terms of, there's a polynomial conversion to any other gate set. This includes a gate set that comprises reversible classical gates (such as Toffoli). For this, you just need to find a constructive conversion between the two gate sets. So, you can efficiently implement the reversible computation. It also means that you can efficiently implement it on a quantum computer, just by using the quantum computer's version of Toffoli as compared to the classical version (the only difference being that the quantum version accepts superpositions as inputs).

However, the terminology that you're using is one of oracles. The oracle model is different. There, each use of the oracle counts as "1", and you don't count any other gates. You're accepting that the cost of implementing the oracle is (relatively) high to the extent that it's the dominant source, and so the only relevant question is how many times you use the oracle. Part of the point here being that somebody could come up with a different gate sequence for the oracle that takes a different running time, but that doesn't affect the oracle-based analysis.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The only thing I don't understand is the link between the fact that I have access to a gate set that includes the Toffoli gate and the fact that the computation can be performed efficiently. Is there some kind of result that states this? $\endgroup$
    – Tristan Nemoz
    Apr 28 '20 at 11:36
  • 1
    $\begingroup$ You have said that the function you want to implement can be implemented efficiently. That's your starting point. That means that for some gate set, you have written out the circuit and found how its size scales (and that it's a polynomial in the number of bits of input). What I'm saying is that this means you can do the same for any (classically) universal gate set. Toffoli is one such set. $\endgroup$
    – DaftWullie
    Apr 28 '20 at 12:51
  • $\begingroup$ Okay, I got it! Thank you! $\endgroup$
    – Tristan Nemoz
    Apr 28 '20 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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