# Time Complexity of Deustch Algorithm

The Deustch algorithm use an oracle, the quantum gate $$U_f$$ The first question is can we count the complexity of $$U_f$$ as one if it is used once. I mean since one computation of $$U_f$$ can't be equivalent to one evaluation of f.

Another question is, since $$U_f$$ depends on f, does that mean we need to implement the $$U_f$$ for each f, so why the time for creating $$U_f$$ doesn't count? For example. I give you a f, then you need to create the $$U_f$$ before excuting deustch algorithm, the time to create $$U_f$$ seems to make the algorithm not universal, is it universal? And when you are creating the $$U_f$$, doesn't that mean you have to evaluate f for $$2^{n-1}$$?If so, why not the time used here doesn't count for a part of Deustch algorithm. So that would make this algorithm no-use in practice.

When I say universal, I mean we have to specify a specific circuit for a specific problem. Universal computer don't do that, they simply use different programs to solve different problem based on the same circuits, the same as our classical computer did.

There is always some puzzle with the Oracle.

These are natural questions that I address at some length in a lesson on Quantum query algorithms that's part of a short course on quantum algorithms. (See also the video for the lesson on YouTube.)

Summarizing what is explained therein, Deutsch's algorithm is an example of an algorithm in the quantum query model of computation. This model is like Petri dish for developing algorithmic ideas, and is not meant to be a practical model that describes the sorts of computational problems we encounter in real life. Rather, it's a simple model that allows us to explore the potential of quantum computers without a lot of technical details getting in the way. With it we can isolate important ideas behind quantum computing and how it works.

When we design and analyze query algorithms, we don't worry at all about how oracle gates are implemented. It's assumed that the gate $$U_f$$ is given to us, and the difficulty of building it isn't our concern. You can think of these gates as themselves being the input — and it's not our job to create the input, we're just trying to solve a particular problem given the input. In general, for functions with many input bits, it could be extremely difficult to implement oracle gates for those functions.

To be clear, this isn't to say that the issue of how oracle gates can be implemented isn't important, but rather, that it isn't considered to be part of the complexity of a query algorithm. This is consistent with the idea that this isn't really about practical computing or actually building circuits per se, it's about working within a theoretical framework that tells us interesting things about computation.

• Thank you for your answer, I would go through the video later, but I still want to figure out how to create an oracle, if an oracle can't be created, then the model is no-use, right? so what gives researchers confidence to develop their model before making sure how to implement oracle? I could just ignore the Oracle and try to develop my algorithms, but after hard-work and the algorithm looks very perfect and then one-day I found it is impossible to create the oracle used in that algorithm, that would be a huge blow to me. Apr 3 at 15:08
• If you have an implementation of the oracle as an ordinary Boolean circuit then you can convert it to a quantum circuit implementation. The number of quantum gates needed will be linear in the size of the Boolean circuit. This is explained in the last section of the lesson following the one I mentioned: learning.quantum.ibm.com/course/… . Apr 3 at 15:39
• Every function has a Boolean circuit so this is always possible, but there's no such thing as a free lunch — most functions require exponentially large Boolean circuits and this will result in an exponential-size quantum gate implementation of the oracle. Apr 3 at 15:39
• thank you for your answer. yes, recently I found I am more clear about the Oracle, since after some calculation I found that the Oracle is just a simple unitary matrix(with all entries 1 or 0) by the definition. So it can be realized definitly. But this word really confused me at first since it makes me to think that it can't be realized in real life. Apr 6 at 3:05

I'll post my answer to this question to help other beginners. @John Watrous 's answer is instructive and after some self-study, I'v found the answer to this question.

Firstly, The Oracle $$U_f$$ can be realized, after some calculation you can find it is just a simple unitary matrix(with entries 1 or 0), what we only care about is the circuit complexity of this unitary matrix but this is anoter story.

Secondly, the Oracle should be treated as an input of the algorithm, the algorithm just assume that we have made the Oracle $$U_f$$ before evaluation, And it can also be treated as a library.

Thirdly, yes, we need to create the Oracle before doing anything, but the point is: you only need to create it once and you can use it any number of times after creating it, I think this is the benefit of the algorithm.

Besides, quantum algorithm is far from universal now.