0
$\begingroup$

so I'm self-studying quantum computing and have a question about the proposed classical solution to the Deustch-Jozsa problem.

So given your function $f: \{0,1\}^n \rightarrow \{0,1\}$ say you were to define a linear map $F: \mathbb C(\{0,1\}^n) \cong \mathbb C^{2n} \rightarrow \mathbb C$ by sending $x \mapsto (-1)^{f(x)}$. Now the oracle you use for the classical solution is an oracle for $F$ which is derived from your oracle for $f$. It only takes 1 call to this oracle to determine if $f$ is balanced or constant, using a similar argument to the quantum case.

My question is why isn't this a valid classical solution? To me, when you implement a quantum oracle for $f$ you're basically doing the same thing I am doing here when constructing $F$ - i.e. you put all the 'magic' into this new oracle and hide it using the black box, and then claim the number of calls to this new oracle only needs to be one. Which is true basically by design of the oracle. But that seems like cheating to me and I can't see why the example I gave is any different to the quantum solution and so I don't see why the quantum case gives a speed up.

Edit: Changed the definition of $F$ from $x \mapsto (-1)^{f(x)} x$.

Edit 2: From discussions in the comments I think I can clarify my issue more coherently and without reference to Deutsch-Jozsa. I think it comes down to, from a complexity perspective, why it's valid to compare a classical solution to a quantum solution with them both using different oracles. To me this comparison isn't useful because we have to use different oracles and since it cannot be made in the real world the idea that one is faster than the other has no meaning.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ I am having trouble understanding what your proposed classical solution is. Could you explain it? Anyways, if it helps, in the algorithm, the oracle itself only evaluates $|x\rangle|0\rangle \mapsto |x\rangle|f(x)\rangle$. It is not the oracle, but rather the superposition used in the algorithm that allows us to evaluate the oracle for all bitstrings. $\endgroup$
    – tpws
    Apr 5 at 16:52
  • $\begingroup$ Sorry , I made a with the definition of $F$ - it should send $x \mapsto (-1)^{f(x)}$. Then with the oracle for $F$ you can use it to evaluate $F(\sum_{x=0}^{2^n-1} x)$ which is 0 when $f$ is balanced and non-zero otherwise. As for your second sentence I'm not really sure what it means, sorry. To me it appears that by assuming the existence of a quantum oracle for $f$ which is then used in the quantum algorithm you are giving the quantum algoruthma ccess to a more powerful oracle so it's no wonder that it can solved with less calls to the oracle. $\endgroup$
    – Proliferate309
    Apr 6 at 11:39
  • $\begingroup$ The quantum algorithm uses the oracle to evaluate on $\sum |x \rangle (|0 \rangle - |1 \rangle)$ which is essentially what my oracle $F$ is being used for. $\endgroup$
    – Proliferate309
    Apr 6 at 11:43
  • $\begingroup$ @Proliferate309 if I'm not mistaken, $f$ and $F$ are defined on the same inputs. Thus, $F\left(\sum_xx\right)$ is not even well-defined. Furthermore, even if it was, note that you would get $(-1)^{f\left(\sum_xx\right)}$ instead of $(-1)^{\sum_xf(x)}$, which would allow you to use the same argument as in the quantum case. Or did I miss something? $\endgroup$
    – Tristan Nemoz
    Apr 6 at 12:45
  • 1
    $\begingroup$ The problem with your $F$ is that it still needs to call $f$ 2^n times when performing classical computation. Technically, it is not even an oracle, it is a program that calls oracle $f$ many times. $\endgroup$
    – MonteNero
    Apr 6 at 18:21

1 Answer 1

Reset to default
2
$\begingroup$

As discussed in the comments, your main mistake is applying $F$ to $\sum_{x=0}^{2^n-1} x$ in the classical case. Unlike the quantum case, there's no superposition of classical bitstrings, and such an operation is impossible.

On a deeper level, you are misunderstanding the role of oracles. To start with, the input to the algorithm is not the oracle, but the description of the function $f$. As you correctly noticed, the input for the classical and quantum cases must be equal in order for the comparison to be meaningful, and it is.

Now how exactly $f$ is provided and how do you build the oracles from that is usually omitted from the textbooks, as it's not particularly interesting or relevant. You can assume that $f$ is provided as a description of the classical gates that implement it in the circuit model. This makes building the oracle trivial in both the classical and the quantum cases.

Furthermore, the purpose of the oracle model is to ask what is the complexity of solving the problem by only applying the function to some inputs, without looking at the details of $f$. Once you do look at the details of $f$ then it often becomes much easier to solve the problem. For instance, if $f$ is a constant function it's usually very easy to recognize that from the circuit description, and there is no pointing in applying it to any input, you just use some routine to detect that and be done with it.

What is the point of using oracles then, you might ask. First of all, because it allows us to prove theorems. In computer science it's usually extremely hard to to prove anything about a quantum-versus-classical advantage, except via using oracles. Secondly, you often don't know how to do anything better than just applying the function to all inputs, like when you're doing unstructured search. The oracle model will then capture precisely the complexity of your algorithm.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer - I have a few comments. "there's no superposition of classical bitstrings, and such an operation is impossible" I think this misunderstanding is likely to come from my background as mathematician but I don't really understand why not? By simply defining $F$ as a function over a vector space we can take linear sums so why is it not possible to evaluate $F$ on this sum? $\endgroup$
    – Proliferate309
    Apr 11 at 7:23
  • $\begingroup$ "To start with, the input to the algorithm is not the oracle, but the description of the function f . As you correctly noticed, the input for the classical and quantum cases must be equal in order for the comparison to be meaningful, and it is." I don't see how the input's are the same? One of them works on classical bits whilst the other works on qubits. "You can assume that f is provided as a description of the classical gates that implement it in the circuit model." If that's the case then how do we even get a quantum oracle? $\endgroup$
    – Proliferate309
    Apr 11 at 7:28
  • $\begingroup$ You can define $F$ to act over a vector space, but that won't help you make a classical computer evaluate a superposition of bitstrings, that's physically impossible. $\endgroup$
    – Mateus Araújo
    Apr 11 at 9:05
  • $\begingroup$ The input is just the function. For example, $f(00) = 0, f(01) = 1, f(10) = 0, f(11) = 1$. That's it, same input for both cases. If you get it instead as a description of classical gates that implement the function (which is much more convenient), it is straightforward to translate that into a quantum circuit implementing the function. It's an automated and efficient procedure. $\endgroup$
    – Mateus Araújo
    Apr 11 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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