Post #4134470

2026-07-27 09:03 UTC

@FishFace@ioc.exchange It is worth noting that if the size of the search space is limited to the size of an array in memory then its logarithm is bounded by the size of a register and so should be regarded as constant-bounded. But Grover’s algorithm in practice converges so quickly that it hardly matters. The usual analyses are practically worst case instances. I actually had three of the item in the array, which is supposed to be bad for Grover’s algorithm, but it took only two iterations, not 804.

Replies (1)

@FishFace@ioc.exchange 2026-07-27 10:14

@chemoelectric@masto.ai I must say I was more interested in the recursion theory subject. The last time we discussed one of your code projects it turned out not to be a faithful simulation of what you said it was. Let's have a look... Ah, I see. > According to quantum theory, our tampering with the computation should have shattered the coherence Coherence is a property of the hardware, not the algorithm. Quantum theory has nothing to say about algorithms; it has something to say about the outcome of certain experiments (and those characteristics then allow certain algorithms to work). Because you are running on a normal computer, if you want to see quantum effects like coherence, you have to simulate them yourself, but you haven't done so. > The usual analyses are practically worst case instances. I actually had three of the item in the array, which is supposed to be bad for Grover’s algorithm, but it took only two iterations, not 804. You only need 2 iterations to find the target because you are not simulating the effects quantum theory predicts your algorithm has on real quantum hardware. This is not a surprise. The real Grover's algorithm operates on its state with a quantum operation. Such operations are mathematically represented by unitary operators, but your operations are *not* unitary (they don't preserve norms). So you have not simulated Grover's algorithm and have therefore not replicated its behaviour. Do you find that surprising? > Grover’s algorithm is actually extremely fast. Lightning fast. But you haven't implemented it. What you have implemented is something which takes two whole iterations, in a classical computer, to find a target *when you have declared that a scan of the entire search space is free*. Can you think of a way of improving from two iterations to one iteration? I can. --- A general note: You could use this approach to find a problem in the theory, but to do so you must faithfully reproduce what the quantum physicists say are the mathematical assumptions - by failing to model coherence (and its destruction by non-unitary operators) you have not done this. You CANNOT use this approach to disprove the experimental claims though - in a mirror situation, you would have to faithfully reproduce what the quantum physicists say are the experimental conditions. By running on a classical computer, you have not done this. This is directly parallel to your computer simulations of Bell tests, which modelled neither the experimental (obviously) nor mathematical (more subtly) assumptions of quantum physics. Hope this helps. P.S. you may have missed (or maybe have just not yet got round to) a reply from me on a subject I am more interested and more qualified in, here: https://ioc.exchange/@FishFace/116943508398344382

Open ##4134469