# What happens with the oracle $U_f$ if you have different blackbox execution times for different inputs?

What will happen if the 'blackbox' function $$f$$ in Deutsch's algorithm is designed in such a way that it takes millions of years to deliver result if input is $$x = 1$$ and few seconds if the input is $$x = 0$$?

How long would it take the oracle $$U_f$$ to calculate $$f$$ for all inputs? My understanding is that $$U_f$$ has such quantum properties, that given a state $$|\psi \rangle$$ as a superposition of two qubits it will apply $$U_f$$ (and thus apply internally $$f$$) to each base state of $$|\psi \rangle$$ simultaneously.

In the scenario I've described $$f$$ will, however, take different execution times for different inputs. Will then there be a delay until all base states are evaluated by $$U_f$$ (or more precisely by $$f$$)?

One implements $$U_f$$ with one circuit that acts on qubit(s) in the superposition state. This means that no matter what is the input (basis state in the superposition), we act on the qubits with the same circuit and it takes the same execution time (the same number of gates in the circuit) for all possible inputs. So, how I understand, the scenario of different times of execution depending on the inputs is not possible. We always apply the same set of gates that implement the $$U_f$$.
• I don't quite get it then, one would then have to know the working mechanism of $f$ in order to build a $U_f$ circuit, meaning that $f$ won't be just a "blackbox" connected to $U_f$ circuit but become internal part of quantum gate $U_f$. If we know the working mechanism of $f$, then it defies the purpose of the algorithm.
• In the textbook of Nielsen and Chuang, they introduce two parties Alice and Bob that live in different cities and they are playing a "funny" game. Alice sends qubits to Bob. Bob acts on the qubits with his decided $U_f$ circuit and sends back to Alice the qubits. Alice with only one measurement understands what property (balanced or constant) Bob's function has. For Alice, the $U_f$ is a blackbox function, but for Bob, it is not. Or in other "game", $U-f$ may be given to Alice, but it can be such a big/difficult to understand circuit that she considers it as a blackbox. Mar 4 '20 at 16:55
• @СССР You do have to know the working mechanism of $f$ to build a circuit for $U_f$. The point of describing it as a "black box" is that Deutsch's algorithm doesn't depend on the inner workings of $U_f$, not that you can calculate $f$ or apply $U_f$ without knowing how $f$ is implemented. Mar 4 '20 at 21:29