Take a classical algorithm and compile it into quantum gates. For example, let's take the addition of two n-bit numbers. Obviously there is an efficient classical algorithm to determine the most likely bit string to arise as an output, because there is only one bit string that will arise and it is the solution to a primary school maths problem.
Now, prior to every gate, insert an rotation around the Hadamard axis by some angle $\theta$ on all qubits. For $\theta \neq 0$ the final state will now be a superposition of multiple but strings. For sufficiently small $\theta$, the correct output of the classical algorithm will still be most likely, but what is the second most likely bit string?
I am wondering about the computational complexity of this problem. I would imagine that for large $\theta$, such as $\theta=\pi$ when the circuit is composed of the universal gate set of Hadamards and Toffolis and the output won't resemble the original problem at all, the problem will be classically intractable. But how about the point at which the correct output of the classical algorithm still occurs 50% of the time? Here we remain close enough to the classical algorithm to still easily retrieve its output (at least if we repeat a few times), but the quantum gates also have a very significant effect on the output. Does classical tractability fail at the same point at which we can no longer reliably retrieve the classical result, or do these things happen at different values of $\theta$?
