...(continued)Looks super interesting! It seems to me that this paper makes progress on the question that we raised here:
https://quantum-journal.org/papers/q-2021-03-23-419/pdf/
In particular, these objects are one particular type of resource in the resource theory of local operations and shared randomness (th
...(continued)In terms of applications, there are certainly very large systems (~$10^{30}$) that can be modeled using the classical harmonic approximation and within Newtonian dynamics, and we expect that problems like that could benefit from our results. Keep in mind that many different types of things (not just
...(continued)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 in
...(continued)@quantumfugazi, your argument appears self-consistent. However, my understanding of this paper is that the problem statement (Section II) is *not* intended to be bounded by any $N_{\mathrm{max}}$, nor to incorporate the effects of relativity. To put it more bluntly, I assert that this is *not* act
...(continued)I mentioned the physics problem first because, theoretically, one does not have to shrink the mass-spring setup (i.e. the Spring computer) at all. So in that case, if the physics problem is within the Newtonian limit, the mass-spring setup will also operate in the Newtonian limit.
Now when it co
...(continued)One thing your analog (aka Spring) algorithm fails to consider is effects of noise in your measurement apparatus. The quantum algorithm provided in the preprint gives an $\epsilon$ close state to the actual output state, which can then provide measurements that satisfy arbitrary error margins that a
...(continued)Thanks Robin, will try to give you a quick rebuttal soon. I want to emphasize that I have been right all along: My Spring algorithm solves the coupled classical-oscillator problem in $O(T)$, independent of $n$.
As you pointed out, there might be some extreme cases where its runtime suddenly depe
...(continued)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 st
...(continued)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 wh
...(continued)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
...(continued)@quantumfugazi: The effects of relativity are relevant not to the *problem*, but to the practical question of how rapidly a given computer can solve that problem. The problem that we're trying to solve is a well-defined math problem, and it does indeed describe a Newtonian (not relativistic) physi
...(continued)@Robin, Thank you for your kind comment. I will read Scott's paper and look at the quantum gate details. However, since the goal is to solve Newton's equation, the assumption of the physics problem size ($N=2^n$, also $x$, $\dot{x}$, $a$) is not in the limit that requires Einstein's relativities.
...(continued)@Ryan Thanks for the comment. In my first argument, I am focusing my analysis on time complexity, in which I also talk about speedup in terms of $n$ (like Grover's quadratic speedup).
I only wrote about "resource" (or space complexity) in my second argument after Aram pointed out that the initial
...(continued)Jack: Thanks for your response. We should do the comparisons in time complexity, which I believe is (correct me if I am wrong):
$O(T)$ for Spring (and Analog) vs $O(nTd)$ for Quantum vs $O(\text{exp}(n))$) for Classical.
I mentioned the couplers since Aram kindly reminded us that the initial set
...(continued)@quantumfugazi: First of all, thank you (and kudos) for engaging professionally. Like Will Kirby, I initially interpreted your comment as a troll, but I really appreciate that your followup comments indicate sincere engagement in a good faith effort to determine the truth. I'll respond in kind.
...(continued)@quantumfugazi, I have trouble following some aspects of your argument but let me just clarify the following. Our algorithm can simulate $2^n$ classical oscillators using a total number of quantum hardware elements, operations and resources (e.g., qubits, space, energy, time, gates, hardware coupler
...(continued)I think you're comparing apples to oranges, to a certain extent. Sure, you number of possible couplers of *arbitrary size* between qubits in some register will scale exponentially, but it is far too pessimistic to assume we will need to utilize anywhere close to all of these choices. More fundamenta
...(continued).... (continued)
Now let me take on the space complexity, which is not even important. Yes, I need $2^n$ springs. And yes, the quantum algorithm initiaites (at $t=0$) with $n$ qubits. However, we should also count couplers (similar to springs) later on, and gates (which are made of couplers). If t
...(continued)Sorry for being impolite in my comment. Aram you wrote that this would take $2^n$
classical springs vs $O(n)$
qubits, and Ryan agrees. However, this is the initial resource requirement at $t=0$ (not even Space complexity!)...I will come back to this point later.Let us focus on the time compl
...(continued)UPDATE: from the comments below it looks like quantumfugazi is now making a good-faith effort to engage with the paper as well as other commenters. So I retract my claim that they are probably a troll. ORIGINAL: Although I know I'm probably responding to a troll (quantumfugazi joined scirate for the
Thanks Aram, that is correct.
Fantastic title, at the very least.
I haven't read the paper but presumably this would take $2^n$ classical springs vs $O(n)$ qubits. Also, couldn't you phrase your comment more politely?
I am sorry but I can simulate these coupled classical oscillators using coupled springs (Mapping Newton to Newton). Should I call it Spring supremacy?
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.
...(continued)@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 tar
...(continued)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" bitstrin
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
...(continued)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
...(continued)@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
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.
...(continued)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
...(continued)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 out
...(continued)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
...(continued)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
...(continued)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
...(continued)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 a
...(continued)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
...(continued)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 t
...(continued)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 de
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.
...(continued)Hi everyone!
This discussion is very interesting! I would like to add a few points that I also discussed per email with Nengkun, Tzu-Chieh and Cambyse:1. I believe we also do not need to know the structure of the circuit if you want a trace distance bound and can afford a polynomial number of
...(continued)Hi Robert,
Thank you very much for explaining your method.
Using the random Clifford measurements shadow and pure state classical shadow is a great idea. This method reduces the sample complexity, as you explained.However, we restrict ourselves to local measurements, i.e., Pauli measurement
...(continued)Hi Nengkun and Tzu-Chieh,
Right! The approaches taken by the two papers are quite different. Cambyse Rouzé and Daniel Stilck França reduce the problem of learning states of low circuit complexity to learning low-temperature thermal states, while your new work reduces to learning ground states. The
...(continued)Hi Robert,
Thank you very much for providing your insightful comments.
Thank you for mentioning the nice paper by Cambyse Rouzé and Daniel Stilck França.
With our immature understanding of this paper, their method works under the assumption of a known interaction graph. Moreover, they left t
...(continued)I think there is a simple algorithm using shadow tomography to resolve an open question mentioned in the paper on efficient tomography of quantum states with polynomial circuit complexity. In particular, one can prove the following claim.
Given a quantum state $\lvert \psi\rangle$ generated by a qu
Hi Tim, thanks for the response! Good to know Im not missing anything. I’ll shoot you an email if I notice anything else when I get back to working through this paper. And I’m always happy to be acknowledged in acknowledgements!
...(continued)This is possibly a naive question, but how would you calculate $\partial_{\theta_i}\left\langle\Psi_{\mathrm{ref}} \vert \hat{A}_i (\theta_i) \Psi^{(m-1)}\right\rangle$ on a physical device? It doesn't seem like representing the gradient as the expectation value of a commutator as in Grimsley *et a
...(continued)Thanks for the comments Jahan! And sorry for the slow response. You’re correct, we could replace the entire paragraph on the lower left of page 19 (which you’re quoting above) with your much more concise statement. We’ll update that when we next update the paper and, if it’s ok with you, thank you i
Braneshop, and
the US National Science Foundation.
SciRate