Recent comments from SciRate

Hi all,

I agree with Seok-Hyung that the Type II fusion scheme given in Figure 3 is actually measuring $X_1 Z_2$ and $Z_1 X_2$, and that failure leads to measurement of $X$ on one qubit and $Z$ on the other. This is problematic for the boosted fusion protocol presented here, because a $Z$ measur

...(continued)

Very nice result, though I feel the way the statement of the main result in the abstract should be more precise. It seems the result applies to $f$ which has integer points as the extreme points of its solution set, or, better said, any $f: \mathbb{R}^n \rightarrow \mathbb{R} $ whose set of minimize

...(continued)

Thank you, Craig. We intend to explore deeper circuits (hopefully in the ballpark of what you've suggested) in the future. Pushing the circuits to the brink of failure at the chosen error rate would, no doubt, be a useful experiment.

Also, our goal here was to establish the value of the DS-ZNE idea

...(continued)

This paper should really consider circuit depths beyond 20 or 30. Table I should include depths 100, 1000, 10000, 100000 and 1000000. Push it until it breaks.

For scale, note that you want ~100 non-Clifford gates for the circuit to not be classically simulable. This is why you'd at least want to

...(continued)

Hi,

First, congratulations on the publication of your paper! Your paper seems to be very appealing to researchers studying MBQC and photonic quantum computing like me.

I have one question regarding your work. In page 6, it is written that a type-II fusion failure leads to $Z$ measurements on both

...(continued)

"Another interesting feature is the intermediate connectivity between qubits, which
can be made variable by shuttling atoms during the computation" Is any neutral atom computing vendor seriously considering this _during computation_?

Came to the discussion quite late, but I think @quantumfugazi is pointing out that the Spring Algorithm solves the problem with $\exp(n)$ springs and $O(T)$ circuit depth.

Note that we already know that every BQP problem (indeed, every PSPACE problem) can be solved using classical polynomial cir

...(continued)

Ah, I think I understood. Thanks for your kind answer!

Since you have analyzed the shadow norm and inversion of observables as a function of low depth d, I don't think I've experienced some difficulty reading this paper due to the above question :)

Best regards,

Guedong Park

Hi, thank you for the comment, and sorry for the late reply, we missed it!

The main result in the paper you mention is formulated in terms of the Haar measure on the unitary group, but since the uniform distribution on the Clifford group forms a 3 design, the t-th moment operator for t≤3 for this m

...(continued)

Dear Aram and Francois,

thanks for your answers!

Yes, I was wondering particularly about the dequantizations for sparse matrices in Gharibian and Le Gall (STOC 2022). Your information about the degree of polynomials solved my paradox. :)

Aram is absolutely right.

I would just like to add that one exception is the recent dequantization framework by Gharibian and Le Gall (STOC 2022), for which I give a robust dequantization in Section 6.3. This framework does work for sparse matrices. It dequantizes the Quantum Singular Value Tran

...(continued)

Dequantization requires low-rank matrices. That's why the canonical example is inner-product estimation, i.e. rank-1 matrices. The BQP-completeness results require high-rank matrices.

Great work!

I have a question about the case of sparse matrices:
Isn't this the case that the original HHL algorithm considers?
You cite a reference that says this is BQP-hard, so how is it possible that this can be dequantized?
What am I missing?

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

...(continued)

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.

@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

...(continued)

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

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

...(continued)

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.

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)