Recent comments from SciRate

@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)

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

...(continued)

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.

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

...(continued)

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!

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

...(continued)

Thank you Simon again:D

Thanks a lot, it works.

What an amazing trick

Although now that I'm thinking about it a little more, I don't understand why all this is necessary. In this proposition, you're assuming $\mathbb{S}=\mathbb{S}_d$ and trying to prove the twirl has no unit-modulus eigenchannels other than the depolarizing and identity channels. Why can't you just sa

...(continued)

You can check on the arXiv for the email address of the person who submitted the work.

I'm having a little trouble understanding the last three sentences of the first column on page 19.

> Thus, because $\mathbb{S} = \mathbb{S}_{d}$ by assumption, the space of all superoperators preserved under conjugation by all elements of ${R}^{-1}\mathbb{G} $ contains $\mathbb{S}_d$, since we se

...(continued)

Dear author and editors,

I am researching quantum unitary decomposition and find this work very interesting.

Please let me know if I can have the author's email address to further discuss this work.

Here is my Email (yize.sun@campus.lmu.de) if you need it.

BR,
Yize Sun

Thanks for the clarification!

Regarding the open problem on "MA containment of guidable stoqastic LH" in Section 1.3, I do not have a quick answer yet since I need to take a close look at Def 7 in your work. However, the corresponding paragraph in Section 1.3 is not totally precise:

i) Thres

...(continued)

Dear Yupan Liu,

Thank you for pointing out your interesting work, with which we were not familiar. We will add this as a reference in a future update of our work.

However, we believe that our classically evaluatable states (and hence our notion of classical evaluability) are conceptually dif

...(continued)

Thanks for this interesting result and extending the efficient query access in terms of quantum circuits!

However, I would like to emphasize that showing MA containment of a subclass of QMA using both query access (a.k.a, "classically evaluatable") and sample access, as well as so-called "dequanti

...(continued)

The main claim of the paper, that by setting A=2/pi ((w, x) + b) the probability of measuring the state 1 resembles the output of a neural network with cos^2 actication function, is a tautology. By that same logic you can set A=sqrt(arccos({whatever you want})) and claim the single qubit is computin

...(continued)

Hi, thanks for the great result!!
But I have a small question about the implementation of random Clifford unitaries.
Your paper said random Clifford unitaries (with $\epsilon$-error) can be achieved by single-qubit random Cliffords in the first section and random neighboring 2-qubit Clifford unitar

...(continued)