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