Hacker News new | ask | show | jobs
by miles7 1175 days ago
To clarify a bit more, for us the purpose of opening the oracle and simulating it, whether or not we were the first ones to do it (e.g. we weren't, see Chamon paper above) was to say that

"There are many cases where it's already known one doesn't need Grover's algorithm, such as if a problem already has a polynomial-time solution. We have now identified a new set of cases where one doesn't need Grover's, which is where the oracle can be simulated only once by a tensor network (or log(N) times in a "closed" simulation".

So the point of that part of the article is to further delineate when Grover's algorithm is actually needed or not needed. It only applies to real-life problems where one must actually know the circuit.