Hi Vladimir, it's an interesting point, though not one ultimately affecting quantum advantage (see below). I would say that, yes, for classical simulations in the hardest cases where tensor network approaches start failing in their compression (i.e. growth of entanglement) and the classical costs start crossing over as a function of circuit depth into exponentially growing resources, then yes both the computational and memory resources will start to grow exponentially. Theoretically the number of qubits (memory resources) of a quantum computer would still grow polynomially, though as we argue in the paper it's a worse polynomial than one might have thought due to the doubly-exponential compounding of errors in Grover's.
But regarding any implications of the above for quantum advantage I'd refer you to my answer above to Ryan Babbush, where I emphasize than what we mean by quantum advantage cannot be fundamentally decided by scaling. Scaling can play a role in terms of extrapolating time estimates, but ultimately it is the estimates themselves (including prefactors) that must be compared.
Hi Bibek,
Your question is an interesting one as Alex Meiburg's answer showed. His answer is more insightful than what I would have said about the optimal number of iterations, so I'll refer to his answer.
From our point of view in the paper, we were just consdering two cases. One is the case where the oracle can be simulated, where we showed one then only needs a single iteration (we think this is non-obvious, because one might have previously thought exponential time was needed to extract the marked states classically). The other is the case where one can't simulate the oracle (say if n=80 and one has a hard instance of some problem), in which case the resources needed to run Grover's is astronomical even assuming perfect error correction and so on.
So for that second case, doing a more optimized number of iterations would not help much, because the 2^(n/2) scaling is so strong that if n=80 is assumed to be within reach, then n=90 will again be out of reach and so on.
Braneshop, and
the US National Science Foundation.
SciRate
Hi Bibek,
Thanks for your helpful comments & sorry for the very slow reply. Let me reply to your two questions or points in reverse order.
(1) first of all, we think very highly of your experimental demonstration of Grover's and it's an important milestone in demonstrating how it can be done and the amount of sophistication needed in carrying it out. We definitely do not think your implementation is "invalid" or that anything about your experiment is faulty. (We also believe that our statements about necessary error levels are fairly consistent with your results when one accounts for the probability of success we use as the metric versus yours, and the error mitigation techniques you used.) Basically, our paper is about two things: (a) conceptual aspects of Grover's algorithm (e.g. what is the right classical algorithm to compare to a quantum implementation of Grover's) and (b) whether it's feasible to scale up quantum Grover's to large enough problems to beat classical (which would have to be n > 40-50 qubits at a bare minimum, and most likely n > 80 even for the hardest problems). So the 5-qubit regime of Grover's is very interesting experimentally, but not yet in the large-qubit regime we focus on. For the n=5 qubit regime, our main statement would be that n < 40-50 and most likely n < 80 would definitely be classically solvable no matter the problem or oracle used, even for the very hardest types of problems.
(2) About the first part of your comment, I strongly agree that as you said "...whether Grover's oracle can be efficiently simulated depends on the representation of the oracle..." if by representation you mean the specific problem one wants to solve and its representation as a quantum circuit. Then yes, an efficient simulation of the oracle circut (just once, not a full simulation of the entirety of Grover's algorithm) is enough to show a lack of quantum advantage for that specific problem as we argue and show. So the conceptual (first) part of our paper is mainly saying that it's really highly problem dependent whether there even could be a possibility of advantage for a given, specific problem, and that it has to be decided problem-by-problem, including looking at details of the oracle circuit for that problem (its depth, entanglement it generates, number of T-gates, etc.). The first half shows more things than this, but it is one of the main conceptual conclusions.
This case-by-case aspect of Grover's possible advantage is in fact well-known to some, but certainly not to all (I would argue even most). One can take the huge amount of convoluted discussion about our paper as some evidence of this! Though also certain aspects of our writing and presentation that may have been confusing, which we are revising for clarity (without changing any statements or conclusions from the first version). The conceptual problems with the oracle model have been remarked very little if at all in a clear way in any published paper we know of, though sometimes it has been remarked in unpublished lecture notes as you helpfully pointed out above, and even there in reference to other algorithms such as Simon's. We plan to cite those notes and would be happy to cite any other notes or papers that make similar statements to ours about the case-by-case aspect of determining possible quantum advantage for Grover's.
Happy to discuss more – thanks,
Miles