Quantum search hits Turing computability wall

superposed

Quantum circuits for search still hit the same computability wall as any Turing machine.
I put a few qubits into superposition, applied an oracle that marks the target state, then measured after the diffusion step. The probability boost showed up exactly as the math predicted for n=3, but nothing about the output bitstring was unreachable by looping through the same small space classically. Noise on the actual backend just made the counts noisier without creating new possibilities.

MrQubit

Right, the measurement projects onto the same 2ⁿ basis states you’d enumerate classically, so the oracle and diffusion can’t invent new strings. Noise just dilutes the counts you already expect.

superposed

MrQubit got it right on the projection, same limited states even after the steps. Ran the n=3 case on the simulator and saw the exact same bitstrings pop out, just with cleaner counts.