3
$\begingroup$

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$)?

Improve this question
$\endgroup$
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – СССР
    Mar 4 '20 at 15:41
  • $\begingroup$ 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. $\endgroup$
    – Davit Khachatryan
    Mar 4 '20 at 16:55
  • $\begingroup$ One can question the usefulness of this algorithm, but, how I understand, it is not useful and that is the reason that I called the problem that it solves a "funny" game)). The goal of the algo is to show an advantage of the quantum computer over the classical computer and not worry about the practicality of it. $\endgroup$
    – Davit Khachatryan
    Mar 4 '20 at 16:56
  • 2
    $\begingroup$ @СССР 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. $\endgroup$
    – lacker
    Mar 4 '20 at 21:29

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.