Considering Deutsch–Jozsa algorithm

problem statement, of not being able to recognize "constant functions" from "balanced functions" on single call conventionally is clear to me...

Now quantum part, slightly modifies the "problem" function, from being a function (due to how quantum circuits work on gate based quantum computer)...

 |0>×N // N Input qbits, initialized to state 0 - so far good
 |1>  // single output qbit, initialized to state 1 - well, why not...

Now let's toy with some sample oracles

 Or1) always return 0, do not touch input qbits
 Or2) always return 1, do not touch input qbits
 Or3) balanced // just XOR some qbits together, via CNOT gate on those qbits with result one 

Now the explanation/algorithm goes via

 0) - the function must be given as quantum oracle - i.e. built from the gates
 1) H gate on inputs and output
 2) pass qbits, now in H rotation, into oracle - thus exactly one invocation
 3) make H gate on inputs and outputs once again (is self inverse, so we are back in original rotation)
 4) Inspect INPUT qbits instead of output, and make decision

Like, wait a moment.... how does this differ from me modifying the original task into: instead of

bool F(bool[] inputs) // considered pass as value

I make it

void F(ref QBit result, ref QBit[] inputs)  // considered pass as value

and I require you to give me the function as definition via gates

where QBit would have "state" for normal perspective as well as state in H rotated perspective

and I define gates, in a way that they are reacting on both, inputs and outputs, i.e. CNOT would be in normal perspective, as expected (modifies target, reads control)

Control × Target => Control Target
 |00> to |00>
 |01> to |01>
 |10> to |11>
 |11> to |10>

whereas in H perspective, from point of action-reaction would also influence the other qbit

 |++> to |++>
 |+-> to |-->
 |-+> to |-+>
 |--> to |+->

or in other words.... apart from computing what to make result into, in H rotation I make it "mark" which qbits were used to actual decision making.... since function can only be constant or balanced, there are 3 cases

 Case1) is constant - so no qbit is touched in decision making
 Case2) something is used for decision making - thus (apart from Case3) must be a balanced
 Case3) decision making makes a tautology, so always decides the same - hence some XOR like marking - so reversed decision cancels out

as, now, I can also make the "quantum claimed superiority" by single call to the "oracle" function, by completely ignoring its output, rather using reference to the inputs as a probe to the function

So the question: why is this not considered "probing the oracle" in classical computing, or if make the comaprison somehow fairer, would be "Deutsch-Jozsa" algorithm still bringing any benefit over classical way (i.e. allowing probing on classical / disallowing probing on quantum)?


1 Answer 1


If you are given the combination of quantum gates that are used to implement the oracle, the problem is easier, even for classical algorithms.

But when we have an oracle, we don't get to see the quantum gates. We just have a black-box API. The quantum algorithm doesn't see the gates. Neither does the classical algorithm. The quantum algorithm can still distinguish even without seeing the gates. The classical algorithm can't.

So that's how it differs from your thought experiment.

  • $\begingroup$ ....The quantum algorithm doesn't see the gates... that is the part, I don't necessarily agree with.... as it observes side-effect of inputs, once "hidden gates" were applied, where I am not sure whether all gates have side effect on the input in H rotation, and compare that to classical one, which sort of has ability to observe "which input bit was used to make a decision"..... as if decision was made, it is not constant thus must be balanced $\endgroup$
    – chmirko
    Dec 28, 2023 at 5:47
  • $\begingroup$ @chmirko, I don't think this is a matter of opinion where people are invited to agree or disagree. It is part of the mathematical definition of an oracle algorithm that the algorithm only sees inputs and outputs, but does not get to see the configuration of gates. Perhaps you don't find results about oracle algorithms terribly relevant to real-world computation. That would be understandable. $\endgroup$
    – D.W.
    Dec 28, 2023 at 19:16

Your Answer

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

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