Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an "oracle" (external quantum subroutine) which must be specified for a given application and whose internal structure is not part of the formal scaling of the quantum speedup guaranteed by the algorithm. Grover's algorithm also requires exponentially many steps to succeed, raising the question of its implementation on near-term, non-error-corrected hardware and indeed even on error-corrected quantum computers. In this work, we construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of call to the oracle - an exponentially smaller number than Grover's algorithm - and demonstrate this algorithm explicitly for boolean satisfiability problems (3-SAT). Our finding implies that there is no a priori theoretical quantum speedup associated with Grover's algorithm. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle. We argue that the unfavorable scaling of the success probability of Grover's algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions on both hardware quality and availability.
Submitted 20 Mar 2023 to Quantum Physics [quant-ph] Published 21 Mar 2023
I believe the basis of this claim is that the theoretical quantum speed-up isn't generic: it would need to be proven on a problem-by-problem basis by assessing the simulability of the oracle. The practical issues become relevant in the cases when a theoretical quantum speed-up does exist.
Adam, it has always been clear that applying Grover to structured databases doesn't "generically" guarantee a quadratic speedup, let alone quantum advantage, because you can often classically search such databases in time less than 2^n (e.g., this is the case for 3-SAT). But these results seem to be sold as something stronger than that.
While I don't necessarily disagree that the results might be a little oversold, the innovation here is that they are not allowing the classical algorithm access to any additional structure beyond what is already available to GA.
@Adam: As Grover’s algorithm is conceptualized in the context of an unstructured algorithm, the issue of what additional structure is known about the oracle (or the oracle unitary) is everything. Consider the two-qubit Grover, once you know the explicit quantum circuits/unitary, the entire algorithm is just one bitflip per qubit! Put differently, searching a four-element database goes from taking at least three queries to a classical oracle to just one bit flip.
In their paper, they start with a unitary with the tensor network structure exposed from the outset. This, while easy to simulate, is not the representation that the quantum implementation would start with. In fact, a programmable quantum computer today will take a quantum circuit description (like qasm) as input and, as I detailed in my comment below, in this context finding the marked entry is much easier than what the paper proposes. I concede that, as of now we don't know how to get a practical advantage out of black box type of oracular quantum algorithms (Grover, BV, DJ included). However, I am not convinced that this paper rules it out.
@Bibek, thanks for your thoughtful engagement with the paper. Just to clarify, while we do indeed show a tensor network in Section III for the oracle (Eq. (13)) where the target bitstring(s) w can simply be read off (i.e. are exposed from the outset), later in Section IV we use oracles where the targets cannot be read off at all. In that section the oracle only exposes the structure of the SAT clauses defining the problem, and computing the target (marked) bitstrings is non-trivial.
I find the following phrase from the abstract quite misleading:
> "we construct a quantum inspired algorithm, executable on a classical
> computer, that performs Grover's task in a linear number of call to
> the oracle - an exponentially smaller number than Grover's algorithm"
The way you define a "call" to the oracle is highly nontrivial, as it corresponds to a classical simulation of the quantum oracle. This might (and often will) take exponential time, even if there is a polynomial quantum circuit for the quantum oracle. So comparing this to the oracle complexity of Grover's algorithm seems unfair.
Thanks - we will think about clarifying that sentence in the abstract, but we had to be brief there in the limited space. We do unpack the details and implications of what it really means to "call" the oracle classically quite thoroughly in the main text in many places. We also say that we believe there must be oracle circuits which are exponentially hard to implement classically. On the other hand, for oracle circuits which are shallow enough it's pretty much a "black box" to apply such oracle to an MPS and only takes seconds even for hundreds of qubits.
Your point is important in another direction, which is that the oracle is also not a single "call" for a real quantum device either, and that e.g. if the oracle is deep or otherwise challenging to implement, then to perform Grover's algorithm one would have to implement that same challenging circuit 2^(n/2) times (e.g. if Google used all of their Sycamore qubits it would be 2^(54/2) = 134,217,728 iterations of that deep oracle circuit, so the gate count would be that number times the number of oracle gates).
Hi Miles, If I understand correctly, the 2^{n/2} iterations is the theoretical optimum for maximizing the success probability on a noiseless quantum device. Is it necessary to call the oracle that many times on a noisy device? It is clear that the experimentally optimal number of oracles calls will be much lower due to decoherence. Couldn’t we call the oracle until a clear winner emerges among the database entries, i.e., the correct answer is the mode of the experimentally observed distribution?
Bibek: A subtle point about the 2^(n/2) time is that isn't just the one that maximizes the success probability, it is also (within a constant factor) the one that minimizes the time to solution. The exact number that maximizes the success probability is f(n) = (pi/4)*2^(n/2). If you instead run for only C*f(n) many steps, then your success probability is sin^2(C*(pi/2)). With a bit of math you can see that the optimal C is 0.74, and you get a 1.13x speedup on average.
But if C is very small, say, 10^-5, then you're getting a 10^-10 success probability. This corresponds to a scenario where your noise limits you to a coherence time of C*f(n) with exponential falloff afterwards. You suffer a quadratic 'penalty' for not running for the full time.
If you run many times for a shorter time, taking the mode is not necessary: just, as each sample comes in, check it with your oracle. That's pretty fast and easy. :) The critical issue is more that you just can't expect to ever hit the correct answer, not even once.
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.
It is well understood that applying Grover's algorithm to 3-SAT in the standard way would not give a quadratic speedup over the best classical algorithm for 3-SAT in the worst case (and especially not on average). But there are problems for which Grover is expected to give a quadratic speedup over any classical algorithm in the worst case. For example, the problem "Circuit SAT" starts by me handing you a specification of a poly-size classical circuit with AND/OR/NOT gates, so it's all explicit. Then you need to solve SAT on this circuit. Classically we strongly believe it will take time 2^n (this is even the basis of many conjectures in complexity theory, like the exponential time hypothesis), and quantumly we know it can be done with 2^{n/2}*poly(n) quantum gates using Grover and the explicitly given classical circuit. So while I think there are some very nice insights in this paper, the statement in the title "Grover's Algorithm Offers No Quantum Advantage" seems untrue in a general theoretical sense. Of course, this is putting aside issues with the overheads of error-correction for quadratic speedups (a well understood practical matter that is resolved by going to large problem sizes that wouldn't be available to the first fault-tolerant quantum computers). What am I missing?
Thanks, Ryan, for the constructive points which definitely help to sharpen the discussion.
One of our main points is that for any Grover-type problem too hard to solve classically, if such a problem eventually gets solved with a quantum algorithm, the algorithm used to solve it will not be Grover’s.
A key point, we think, is that scaling and asymptotics plays no role per se in determining quantum advantage for a given (fixed) size of problem, even though scaling might inform estimates before one of the two platforms is able to tackle some target problem. Quantum advantage, as we've defined it, is only about the resources needed to solve specific, concrete, and finite instance of a problem. And even if the resources needed on the classical side sit on a curve going like 2^n, if that curve remains below the quantum curve going as 2^(n/2) then I believe we'd both agree there is no quantum advantage for that problem at that n.
Then we can consider three ranges of n (number of logical qubits):
1. n <= 40: all Grover's problems can be solved by full state classical simulators in reasonable times. (n=40 is on the low side of estimates for this.)
2. n <= 60: all Grover's problems can be solved by a combination of "closed-mode" tensor network simulation plus slicing parallelism (noting that closed-mode halves the effective circuit depth)
3. n > 60: the resources needed to run Grover's algorithm for any problem rapidly become astronomical, even under very generous assumptions.
So Grover's does not offer a viable path to obtaining quantum advantage on concrete problems. We're not saying other quantum algorithms couldn't solve these problems.
To support the claim of n >= 60 being already out of reach for Grover's, I did some estimates of number of iterations needed and times needed to reach a probability of success of p=0.01. These estimates assume that each quantum gate takes 200 microseconds to apply, and assumes only 2n gates inside the oracle and 2n gates inside the diffuser for a total of 4n gates per iteration. (I.e. the estimates are being extremely generous to the quantum computer, as classically hard problems would need something like n^2 gates in the oracle, there's no inclusion of the significant extra error correction resources needed for larger n as argued in the paper, etc.) I get the following numbers of iterations and running times (running times include repeating the experiment 100 times to account for p=0.01):
n iterations time
40 52,516 1 day
50 1,680,530 39 days
60 53,776,974 1493 days
These timings in fact show that even n=50 is pretty optimistic for Grover's. Unless the engineering is rather incredible, the n=50 estimate might be closer to one year.
On the other hand, in our classical approaches in the paper, we barely scratched the surface of the classical simulation toolbox. If we used even the techniques in our arxiv:2207.05612 paper where we roughly tied the Google quantum sumpremacy results, if we used GPUs, and combined this with the fact that Grover oracles have a special structure in the computational basis that makes them amenable to "slicing" the inputs and getting a corresponding reduction in entanglement (and being able to perfectly parallelize over the slices), we would get significant gains and be able to tackle much more highly entangled instances.
We are planning to make some edits to the paper to be more explicit about various points above and perhaps tweak the numbers in Fig. 1 (e.g. n=80 there is probably too generous to Grover's and might leave the perception that classical has to reach that to compete). We didn't originally put in timings for Grover's because of other works that did this already, and we didn't elaborate much about slicing and other classical techniques because we didn't want to overcomplicate the paper. But I'm thinking it could benefit from some more discussion of these things.
Thanks Miles. So we agree there are some problems that scale as $O(2^n)$ on a classical computer and $O(2^{n/2})$ on a quantum computer but that the ratio of constant factors between the quantum and classical scaling might be high enough that $n$ would need to so large that the point of crossover into quantum advantage could be practically prohibitive. However, this point is already well appreciated by the quantum computing community. For example, it essentially the argument we make in Ref. [58] of your work, and we were mostly rehashing arguments that had been made many times before.
But I might also point out that those "practical" arguments are not very charitable to the long term future of quantum computing. The surface code might have high constant factors, but we can certainly hope to eventually (perhaps many decades later and with the help of a surface code quantum computer) make topological quantum computers (or something else) with logical gate times well below hundreds of microseconds. After all, superconducting qubits have physical gate times of tens of nanoseconds. Even if this doesn't happen, I think the title is still a bit strong because a theoretical quantum advantage exists for some problems, regardless of practical challenges to reaching it.
I do appreciate some of your findings here about the use of tensor networks to simulate Grover oracles. My feeling is that the work is getting so much pushback because the framing implied by the abstract and title seem to suggest that your conclusions run counter to the standard understanding our community has about about the relationship between Grover and quantum advantage. The finding that tensor networks can sometimes simulate certain Grover oracles efficiently is novel, interesting, and valuable but certainly does not change our fundamental understanding of this relationship.
You make estimates for the ration $N_C$ of physical to logical qubits, and argue that it grows quadratically. What does that mean for the run time, measured in elementary gates on physical qubits?
If one assumed that one had a perfect transversal gate set, perhaps the circuit depth might not change dramatically. But I don't like to measure run time in circuit depth, because it is not a fair comparison to classical computers. For classical computers, one usually has a fixed and small number of parallel threads (e.g. the number of CPU cores, or the number of tapes of a Turing machine).
So I would be interested in the runtime assuming that there is an upper limit on the number of parallel physical quantum gates one can implement.
Your paper has generated a lot of interest. So firstly, congratulations. After reading the article, I felt that the claims were more ambitious than the evidence you provided. I have some questions, and I am posting them here for everyone to see. Please feel free to respond here or via email.
- Firstly, I was concerned by the claim regarding the efficient classical simulation of Grover's algorithm. Let me quote the following excerpt from one of Scott Aaronson's [lectures](https://www.scottaaronson.com/qclec/18.pdf). While he is talking about Simon's algorithm, I think it very much applies to Grover's algorithm as well.
> The difficulty in claiming that we're getting a quantum speedup this
> way is that, once we pin down the details of how we're computing
> $f$-so, for example, the actual matrix $A$-we then need to compare
> against classical algorithms that know those details as well. And as
> soon as we reveal the innards of the black box, the odds of an
> efficient classical solution become much higher! So for example, if we
> knew the matrix $A$, then we could solve Simon's problem in classical
> polynomial time just by calculating $A$ 's nullspace. More generally,
> it's not clear whether anyone to this day has found a straightforward
> "application" of Simon's algorithm, in the sense of a class of
> efficiently computable functions $f$ that satisfy the Simon promise,
> and for which any classical algorithm plausibly needs exponential time
> to solve Simon's problem, even if the algorithm is given the code for
> $f$.
I understood your paper as an instance of how knowing the structure of the unitary that implements the call to the oracle allows you to simulate the oracle classically and efficiently. While such a demonstration is interesting, it is hard to see if it justifies claiming that Grover's algorithm has no quantum advantage. For instance, the quantum oracle can be written as $$ U_w = X^{1-w_1} \otimes X^{1-w_2} \cdots \otimes X^{1-w_n} \cdot C_{n-1}Z \cdot X^{1-w_1} \otimes X^{1-w_2} \cdots \otimes X^{1-w_n} $$ and once we know how $C_{n-1}Z$ is natively implemented on a quantum computer, finding $w$ from a quantum circuit representation is trivial and can be done in no time by simply looking at the gate representation. Put differently, whether Grover's oracle can be efficiently simulated depends on the representation of the oracle. The representation I provided above makes the problem trivial; the MPO representation you have chosen can take an hour or two on a desktop/supercomputer. So are you claiming that an efficient simulation for a well-chosen representation is enough to claim a lack of quantum advantage? I should add that your answer to this question probably also extends to Bernstein-Vazirani, Deustch-Josza, Hidden Shift, and Simon's algorithm, all of which also have Clifford gate-based representations, i.e., they are easily simulatable.
- Secondly, on page 12, you claim that "in order to apply GA on just 5 qubits, one needs $\epsilon ≤ 5.10^{−4}$ which is much better than any existing hardware." In https://arxiv.org/pdf/2211.04543.pdf, which you were kind enough to cite, we did demonstrate a 5-qubit Grover and identified the marked entry. We also did implement the oracle unitary, and I think it wasn't the case of a "contrived example where one uses Eq. (3) instead of Eq. (2), i.e., one explicitly uses information about the solution w instead of performing the classical logic of computing f (b)." We only called the oracle enough times to get the marked entry and not to the theoretically optimum number of calls. Can you clarify why our implementation (and similar ones like Nature communications 8, 1 (2017)) are invalid even though the marked entry was identified? Is it because we did not implement the theoretically optimal number of queries even though that is never experimentally optimal? I think this is an important question because your arguments about the gate error scaling exponentially with the number of qubits are related to this.
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.
Your work is very interesting. But I think there is a subtle difference between the output of your QiGA and Grover’s algorithm. Please correct me if I misunderstood.
In Grover’s algorithm, one can obtain the exact bitstring $b$ satisfying $f(b)=1$. However, the final output of QiGA is just an MPS representation of the final state of the Grover’s algorithm.
From the MPS representation, if one want to obtain $b$ satisfying $f(b)=1$, it seems that in general, one has to transfer from MPS representation to the vector representation. This process, to my understanding, takes time $O(N)$ in general.
I am also curious about your numerical results in Table I & II, which shows the “execution times to compute the post-oracle state”. If one want the bistring $b$ satisfying $f(b)=1$ (as also available in Grover’s algorithm) instead, will the execution time have large differences?
The paper claims: "The form of |Ψw⟩ as a sum of product states in Eq. (15) immediately presents a classical strategy to extract the solution states {|wi⟩} in a single step: one simply sub- tracts the state |s⟩. Subtracting a product state such as |s⟩ from an MPS is a straightforward operation with a cost scaling as nχ3 ∝ log N . For example, in the case of n = 100 qubits and χ = 50 the subtraction takes about 0.2 seconds." - So it seems they claim you can extract the set of solutions in logarithmic time. Do you disagree? I do not see any reference that they provide for this assertion. I am also not sure the complexity of extracting a single solution from the set of solutions.
Indeed, just after the oracle step of QiGA, i.e. applying the oracle circuit to the |s> product state, indeed we have an MPS of the post-oracle state. Then we subtract |s> from that to get another MPS. This MPS is a superposition of all of the "target" bitstrings b that satisfy f(b)=1.
Now to your question: one does not have to transfer an MPS into the vector representation to extract these target bitstrings. The reason is that MPS generically admit a very efficient sampling algorithm (https://arxiv.org/abs/1201.3974) that scales as log(N) (We mention this in the paper at the end of point 3, page 6, but we think we will highlight it more strongly in the future.) In this context the full scaling to sample one bitstring would be log(N)*S^2 where S is the number of solutions or target bitstrings B (more generally S would be the bond dimension, chi, of an MPS one is sampling). In practice, for S < 100 and n < 100, the time to collect one sample this way is very fast, under one second per sample.
Regarding your other question, those execution times are the times to compute the state before we subtract |s> from it, but the subtraction of |s> and sampling of representative (usually 5000) target bitstrings is so fast in general (just a handful of seconds) we did not think to include it in the timings. Happy to discuss more.
A lot of comments have already been made but I'll just leave a link to Scott Aaronson's blogpost about the preprint (in case someone missed it): https://scottaaronson.blog/?p=7143
If practicalities are discussed, isn't there an important issue of space complexity? My understanding is that for hard problems both Grover's and QiGA would have exponential time complexity, but the former will have polynomial space complexity while the latter's will be exponential.
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.
Braneshop, and
the US National Science Foundation.
SciRate
I believe the basis of this claim is that the theoretical quantum speed-up isn't generic: it would need to be proven on a problem-by-problem basis by assessing the simulability of the oracle. The practical issues become relevant in the cases when a theoretical quantum speed-up does exist.
Adam, it has always been clear that applying Grover to structured databases doesn't "generically" guarantee a quadratic speedup, let alone quantum advantage, because you can often classically search such databases in time less than 2^n (e.g., this is the case for 3-SAT). But these results seem to be sold as something stronger than that.
Edited Mar 22 2023 03:26 UTC by Ryan Babbush
While I don't necessarily disagree that the results might be a little oversold, the innovation here is that they are not allowing the classical algorithm access to any additional structure beyond what is already available to GA.
@Adam: As Grover’s algorithm is conceptualized in the context of an unstructured algorithm, the issue of what additional structure is known about the oracle (or the oracle unitary) is everything. Consider the two-qubit Grover, once you know the explicit quantum circuits/unitary, the entire algorithm is just one bitflip per qubit! Put differently, searching a four-element database goes from taking at least three queries to a classical oracle to just one bit flip.
In their paper, they start with a unitary with the tensor network structure exposed from the outset. This, while easy to simulate, is not the representation that the quantum implementation would start with. In fact, a programmable quantum computer today will take a quantum circuit description (like qasm) as input and, as I detailed in my comment below, in this context finding the marked entry is much easier than what the paper proposes. I concede that, as of now we don't know how to get a practical advantage out of black box type of oracular quantum algorithms (Grover, BV, DJ included). However, I am not convinced that this paper rules it out.
@Bibek, thanks for your thoughtful engagement with the paper. Just to clarify, while we do indeed show a tensor network in Section III for the oracle (Eq. (13)) where the target bitstring(s) w can simply be read off (i.e. are exposed from the outset), later in Section IV we use oracles where the targets cannot be read off at all. In that section the oracle only exposes the structure of the SAT clauses defining the problem, and computing the target (marked) bitstrings is non-trivial.
I find the following phrase from the abstract quite misleading:
> "we construct a quantum inspired algorithm, executable on a classical
> computer, that performs Grover's task in a linear number of call to
> the oracle - an exponentially smaller number than Grover's algorithm"
The way you define a "call" to the oracle is highly nontrivial, as it corresponds to a classical simulation of the quantum oracle. This might (and often will) take exponential time, even if there is a polynomial quantum circuit for the quantum oracle. So comparing this to the oracle complexity of Grover's algorithm seems unfair.
Thanks - we will think about clarifying that sentence in the abstract, but we had to be brief there in the limited space. We do unpack the details and implications of what it really means to "call" the oracle classically quite thoroughly in the main text in many places. We also say that we believe there must be oracle circuits which are exponentially hard to implement classically. On the other hand, for oracle circuits which are shallow enough it's pretty much a "black box" to apply such oracle to an MPS and only takes seconds even for hundreds of qubits.
Your point is important in another direction, which is that the oracle is also not a single "call" for a real quantum device either, and that e.g. if the oracle is deep or otherwise challenging to implement, then to perform Grover's algorithm one would have to implement that same challenging circuit 2^(n/2) times (e.g. if Google used all of their Sycamore qubits it would be 2^(54/2) = 134,217,728 iterations of that deep oracle circuit, so the gate count would be that number times the number of oracle gates).
Hi Miles, If I understand correctly, the 2^{n/2} iterations is the theoretical optimum for maximizing the success probability on a noiseless quantum device. Is it necessary to call the oracle that many times on a noisy device? It is clear that the experimentally optimal number of oracles calls will be much lower due to decoherence. Couldn’t we call the oracle until a clear winner emerges among the database entries, i.e., the correct answer is the mode of the experimentally observed distribution?
Edited Mar 21 2023 19:58 UTC by Bibek Pokharel
Bibek: A subtle point about the 2^(n/2) time is that isn't just the one that maximizes the success probability, it is also (within a constant factor) the one that minimizes the time to solution. The exact number that maximizes the success probability is f(n) = (pi/4)*2^(n/2). If you instead run for only C*f(n) many steps, then your success probability is sin^2(C*(pi/2)). With a bit of math you can see that the optimal C is 0.74, and you get a 1.13x speedup on average.
But if C is very small, say, 10^-5, then you're getting a 10^-10 success probability. This corresponds to a scenario where your noise limits you to a coherence time of C*f(n) with exponential falloff afterwards. You suffer a quadratic 'penalty' for not running for the full time.
If you run many times for a shorter time, taking the mode is not necessary: just, as each sample comes in, check it with your oracle. That's pretty fast and easy. :) The critical issue is more that you just can't expect to ever hit the correct answer, not even once.
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.
It is well understood that applying Grover's algorithm to 3-SAT in the standard way would not give a quadratic speedup over the best classical algorithm for 3-SAT in the worst case (and especially not on average). But there are problems for which Grover is expected to give a quadratic speedup over any classical algorithm in the worst case. For example, the problem "Circuit SAT" starts by me handing you a specification of a poly-size classical circuit with AND/OR/NOT gates, so it's all explicit. Then you need to solve SAT on this circuit. Classically we strongly believe it will take time 2^n (this is even the basis of many conjectures in complexity theory, like the exponential time hypothesis), and quantumly we know it can be done with 2^{n/2}*poly(n) quantum gates using Grover and the explicitly given classical circuit. So while I think there are some very nice insights in this paper, the statement in the title "Grover's Algorithm Offers No Quantum Advantage" seems untrue in a general theoretical sense. Of course, this is putting aside issues with the overheads of error-correction for quadratic speedups (a well understood practical matter that is resolved by going to large problem sizes that wouldn't be available to the first fault-tolerant quantum computers). What am I missing?
Edited Mar 21 2023 23:42 UTC by Ryan Babbush
Thanks, Ryan, for the constructive points which definitely help to sharpen the discussion.
One of our main points is that for any Grover-type problem too hard to solve classically, if such a problem eventually gets solved with a quantum algorithm, the algorithm used to solve it will not be Grover’s.
A key point, we think, is that scaling and asymptotics plays no role per se in determining quantum advantage for a given (fixed) size of problem, even though scaling might inform estimates before one of the two platforms is able to tackle some target problem. Quantum advantage, as we've defined it, is only about the resources needed to solve specific, concrete, and finite instance of a problem. And even if the resources needed on the classical side sit on a curve going like 2^n, if that curve remains below the quantum curve going as 2^(n/2) then I believe we'd both agree there is no quantum advantage for that problem at that n.
Then we can consider three ranges of n (number of logical qubits):
1. n <= 40: all Grover's problems can be solved by full state classical simulators in reasonable times. (n=40 is on the low side of estimates for this.)
2. n <= 60: all Grover's problems can be solved by a combination of "closed-mode" tensor network simulation plus slicing parallelism (noting that closed-mode halves the effective circuit depth)
3. n > 60: the resources needed to run Grover's algorithm for any problem rapidly become astronomical, even under very generous assumptions.
So Grover's does not offer a viable path to obtaining quantum advantage on concrete problems. We're not saying other quantum algorithms couldn't solve these problems.
To support the claim of n >= 60 being already out of reach for Grover's, I did some estimates of number of iterations needed and times needed to reach a probability of success of p=0.01. These estimates assume that each quantum gate takes 200 microseconds to apply, and assumes only 2n gates inside the oracle and 2n gates inside the diffuser for a total of 4n gates per iteration. (I.e. the estimates are being extremely generous to the quantum computer, as classically hard problems would need something like n^2 gates in the oracle, there's no inclusion of the significant extra error correction resources needed for larger n as argued in the paper, etc.) I get the following numbers of iterations and running times (running times include repeating the experiment 100 times to account for p=0.01):
n iterations time
40 52,516 1 day
50 1,680,530 39 days
60 53,776,974 1493 days
These timings in fact show that even n=50 is pretty optimistic for Grover's. Unless the engineering is rather incredible, the n=50 estimate might be closer to one year.
On the other hand, in our classical approaches in the paper, we barely scratched the surface of the classical simulation toolbox. If we used even the techniques in our arxiv:2207.05612 paper where we roughly tied the Google quantum sumpremacy results, if we used GPUs, and combined this with the fact that Grover oracles have a special structure in the computational basis that makes them amenable to "slicing" the inputs and getting a corresponding reduction in entanglement (and being able to perfectly parallelize over the slices), we would get significant gains and be able to tackle much more highly entangled instances.
We are planning to make some edits to the paper to be more explicit about various points above and perhaps tweak the numbers in Fig. 1 (e.g. n=80 there is probably too generous to Grover's and might leave the perception that classical has to reach that to compete). We didn't originally put in timings for Grover's because of other works that did this already, and we didn't elaborate much about slicing and other classical techniques because we didn't want to overcomplicate the paper. But I'm thinking it could benefit from some more discussion of these things.
Thanks Miles. So we agree there are some problems that scale as $O(2^n)$ on a classical computer and $O(2^{n/2})$ on a quantum computer but that the ratio of constant factors between the quantum and classical scaling might be high enough that $n$ would need to so large that the point of crossover into quantum advantage could be practically prohibitive. However, this point is already well appreciated by the quantum computing community. For example, it essentially the argument we make in Ref. [58] of your work, and we were mostly rehashing arguments that had been made many times before.
But I might also point out that those "practical" arguments are not very charitable to the long term future of quantum computing. The surface code might have high constant factors, but we can certainly hope to eventually (perhaps many decades later and with the help of a surface code quantum computer) make topological quantum computers (or something else) with logical gate times well below hundreds of microseconds. After all, superconducting qubits have physical gate times of tens of nanoseconds. Even if this doesn't happen, I think the title is still a bit strong because a theoretical quantum advantage exists for some problems, regardless of practical challenges to reaching it.
I do appreciate some of your findings here about the use of tensor networks to simulate Grover oracles. My feeling is that the work is getting so much pushback because the framing implied by the abstract and title seem to suggest that your conclusions run counter to the standard understanding our community has about about the relationship between Grover and quantum advantage. The finding that tensor networks can sometimes simulate certain Grover oracles efficiently is novel, interesting, and valuable but certainly does not change our fundamental understanding of this relationship.
Edited Mar 28 2023 19:06 UTC by Ryan Babbush
Cool work!
You make estimates for the ration $N_C$ of physical to logical qubits, and argue that it grows quadratically. What does that mean for the run time, measured in elementary gates on physical qubits?
If one assumed that one had a perfect transversal gate set, perhaps the circuit depth might not change dramatically. But I don't like to measure run time in circuit depth, because it is not a fair comparison to classical computers. For classical computers, one usually has a fixed and small number of parallel threads (e.g. the number of CPU cores, or the number of tapes of a Turing machine).
So I would be interested in the runtime assuming that there is an upper limit on the number of parallel physical quantum gates one can implement.
Hi Miles and Xavier,
Your paper has generated a lot of interest. So firstly, congratulations. After reading the article, I felt that the claims were more ambitious than the evidence you provided. I have some questions, and I am posting them here for everyone to see. Please feel free to respond here or via email.
- Firstly, I was concerned by the claim regarding the efficient classical simulation of Grover's algorithm. Let me quote the following excerpt from one of Scott Aaronson's [lectures](https://www.scottaaronson.com/qclec/18.pdf). While he is talking about Simon's algorithm, I think it very much applies to Grover's algorithm as well.
> The difficulty in claiming that we're getting a quantum speedup this
> way is that, once we pin down the details of how we're computing
> $f$-so, for example, the actual matrix $A$-we then need to compare
> against classical algorithms that know those details as well. And as
> soon as we reveal the innards of the black box, the odds of an
> efficient classical solution become much higher! So for example, if we
> knew the matrix $A$, then we could solve Simon's problem in classical
> polynomial time just by calculating $A$ 's nullspace. More generally,
> it's not clear whether anyone to this day has found a straightforward
> "application" of Simon's algorithm, in the sense of a class of
> efficiently computable functions $f$ that satisfy the Simon promise,
> and for which any classical algorithm plausibly needs exponential time
> to solve Simon's problem, even if the algorithm is given the code for
> $f$.
I understood your paper as an instance of how knowing the structure of the unitary that implements the call to the oracle allows you to simulate the oracle classically and efficiently. While such a demonstration is interesting, it is hard to see if it justifies claiming that Grover's algorithm has no quantum advantage. For instance, the quantum oracle can be written as $$ U_w = X^{1-w_1} \otimes X^{1-w_2} \cdots \otimes X^{1-w_n} \cdot C_{n-1}Z \cdot X^{1-w_1} \otimes X^{1-w_2} \cdots \otimes X^{1-w_n} $$ and once we know how $C_{n-1}Z$ is natively implemented on a quantum computer, finding $w$ from a quantum circuit representation is trivial and can be done in no time by simply looking at the gate representation. Put differently, whether Grover's oracle can be efficiently simulated depends on the representation of the oracle. The representation I provided above makes the problem trivial; the MPO representation you have chosen can take an hour or two on a desktop/supercomputer. So are you claiming that an efficient simulation for a well-chosen representation is enough to claim a lack of quantum advantage? I should add that your answer to this question probably also extends to Bernstein-Vazirani, Deustch-Josza, Hidden Shift, and Simon's algorithm, all of which also have Clifford gate-based representations, i.e., they are easily simulatable.
- Secondly, on page 12, you claim that "in order to apply GA on just 5 qubits, one needs $\epsilon ≤ 5.10^{−4}$ which is much better than any existing hardware." In https://arxiv.org/pdf/2211.04543.pdf, which you were kind enough to cite, we did demonstrate a 5-qubit Grover and identified the marked entry. We also did implement the oracle unitary, and I think it wasn't the case of a "contrived example where one uses Eq. (3) instead of Eq. (2), i.e., one explicitly uses information about the solution w instead of performing the classical logic of computing f (b)." We only called the oracle enough times to get the marked entry and not to the theoretically optimum number of calls. Can you clarify why our implementation (and similar ones like Nature communications 8, 1 (2017)) are invalid even though the marked entry was identified? Is it because we did not implement the theoretically optimal number of queries even though that is never experimentally optimal? I think this is an important question because your arguments about the gate error scaling exponentially with the number of qubits are related to this.
Edited Mar 22 2023 18:18 UTC by Bibek Pokharel
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
Hi Miles and Xavier,
Your work is very interesting. But I think there is a subtle difference between the output of your QiGA and Grover’s algorithm. Please correct me if I misunderstood.
In Grover’s algorithm, one can obtain the exact bitstring $b$ satisfying $f(b)=1$. However, the final output of QiGA is just an MPS representation of the final state of the Grover’s algorithm.
From the MPS representation, if one want to obtain $b$ satisfying $f(b)=1$, it seems that in general, one has to transfer from MPS representation to the vector representation. This process, to my understanding, takes time $O(N)$ in general.
I am also curious about your numerical results in Table I & II, which shows the “execution times to compute the post-oracle state”. If one want the bistring $b$ satisfying $f(b)=1$ (as also available in Grover’s algorithm) instead, will the execution time have large differences?
The paper claims: "The form of |Ψw⟩ as a sum of product states in Eq. (15) immediately presents a classical strategy to extract the solution states {|wi⟩} in a single step: one simply sub- tracts the state |s⟩. Subtracting a product state such as |s⟩ from an MPS is a straightforward operation with a cost scaling as nχ3 ∝ log N . For example, in the case of n = 100 qubits and χ = 50 the subtraction takes about 0.2 seconds." - So it seems they claim you can extract the set of solutions in logarithmic time. Do you disagree? I do not see any reference that they provide for this assertion. I am also not sure the complexity of extracting a single solution from the set of solutions.
Thanks for the question, Xiao-Ming.
Indeed, just after the oracle step of QiGA, i.e. applying the oracle circuit to the |s> product state, indeed we have an MPS of the post-oracle state. Then we subtract |s> from that to get another MPS. This MPS is a superposition of all of the "target" bitstrings b that satisfy f(b)=1.
Now to your question: one does not have to transfer an MPS into the vector representation to extract these target bitstrings. The reason is that MPS generically admit a very efficient sampling algorithm (https://arxiv.org/abs/1201.3974) that scales as log(N) (We mention this in the paper at the end of point 3, page 6, but we think we will highlight it more strongly in the future.) In this context the full scaling to sample one bitstring would be log(N)*S^2 where S is the number of solutions or target bitstrings B (more generally S would be the bond dimension, chi, of an MPS one is sampling). In practice, for S < 100 and n < 100, the time to collect one sample this way is very fast, under one second per sample.
Regarding your other question, those execution times are the times to compute the state before we subtract |s> from it, but the subtraction of |s> and sampling of representative (usually 5000) target bitstrings is so fast in general (just a handful of seconds) we did not think to include it in the timings. Happy to discuss more.
A lot of comments have already been made but I'll just leave a link to Scott Aaronson's blogpost about the preprint (in case someone missed it): https://scottaaronson.blog/?p=7143
If practicalities are discussed, isn't there an important issue of space complexity? My understanding is that for hard problems both Grover's and QiGA would have exponential time complexity, but the former will have polynomial space complexity while the latter's will be exponential.
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.