by Daniel Colomer
10th August 2020 >_
It’s been along time I wanted to talk to you guys about the deutsch algorithm and wanted to do so also following the computational branches model. Just to try out whether it extends to explain such things too.
So this is the one with the constant vs. balanced function right? and actuall I think the biggest challenge is to explain it without tha math and without looking inside the box really. Because we shouldn’t care about the box. The whole point of the algorithm is that if you do a hadamard sandwich then you can distinguish between the two types of function in just one pass.
Now we do need to assume the result of the function is computed in the out register right? The wikipedia page about it will be the base for what I’m trying to say here
Ok, so we got 2 registers one representing the input of the function in superposition, another one initialized in the state - and then we assume we use that to compute the function’s result which is just either a 0 or a 1. But I’m not so sure how to think about this in terms of the black box. The black box should can be thought of as a set of wiring such that by means of using controllers gates (you can’t do it otherwise if you are using separate registers for the input and the output) is basically implementing the function.
We know the function is either constant or balanced. If it’s constant it might as well not have any gate in it :) or basically even if it has some wiring in it it will be such that if we shoot a superposition of inputs in there we will only create computational branches which are all equivalent and thus basically having no entanglement at all. The top wire should still measure 0’s all the time after the last H gate.
Things probably change if we got a balanced function. If we’ve got a wiring implementing a balanced function inside the box and we shoot a superposition of inputs, we’ll basically create different computational branches which can be grouped into two kinds: The ones with a 1 and the ones with a 0 in the output. The trick here is that we’ve initialized the output qubit with the - state and so the wiring wont probably spit 0’s or 1’s but rather will spit the same - state or a physical equivalent (-0 +1 state). Because the computational branches must all play along with the same rules and 0 states have by definition a phase of 0 degrees we need to apply a correction to thos branches that are left in the (-0 +1 state). This correction will affect the input register effectivly kicking in some negative phases to some fot he wires up there. This means that after applying the last H layer, the input register will never be all 0’s again! and so we’ve found a way to distinguish between balanced and constant functions.
I like this explanation because it feels a bit higher level at least a bit more foused at the register level rather than the wiring. It’s using entanglement and computational branches as core concepts and we really do not care about the internals of the box!
I like the fact that the constant case can also be explained in a neat way. I mean let me give it another try. If it’s a constant function either there’s no wiring (trivial case), or there’s some wiring that turns the - state into a (-0 +1 state) for all possible inputs and that is in all possible computational branches created by the black box. In this case no correctio needs to be applied anywhere. The input register stays unchanged. I mean this case has got one single computational branch with a the + state being it’s sort of “identifier”. Even if you wanna be picky and apply a correction to get the -0 + 1 state into a proper 0 - 1 state all you’ll do to the branch ID is turn into a - 0 - 1 which is equivalent to a 0 + 1 and therefore a 0 after applying the latest H layer.
Uff writting this stuff can seem overcomplicated but once you run it through your head becomes super intuitive. I’m starting to like a lot to think this way!tags: