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
Thank you Simon again:D
Thanks a lot, it works.
What an amazing trick
...(continued)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
You can check on the arXiv for the email address of the person who submitted the work.
...(continued)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
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
...(continued)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)Hello,
Thanks for the interesting paper.
I'm more curious about the section about the model for AIMC (ReRAM) and digital MACs.
In the paper, the value for each parameter is collected from several papers (as in Table IV). But I think the value will change if a different paper is chosen. Can
...(continued)Hello,
>[...] “in this universe, the extent of diverse
and complex things is increasing over time.” There are
undoubtedly many people who have already come to this
idea.And one of them is also (or maybe even foremost) Julian Barbour. I would love to see some day how your general definition
Fascinating work! Would be interesting to see comparisons or discussions around how this works fits in with thermodynamic capacity of quantum channels a la Faist, Berta, Brandao.
https://arxiv.org/abs/1807.05610
...(continued)Hey Jahan, thanks for the pointer, we’ll plan to add that one to our citation list. As you say, this one, like another one preceding it we cite ( https://arxiv.org/pdf/0910.4074.pdf ) point out that you can have 10% interface error if the bulk error is substantially below threshold (0 to 0.1% errors
...(continued)You might want to compare to https://arxiv.org/abs/1509.07796, which analyzes a very similar setup but does not appear in your citations.
It's worth noting that this earlier paper used a fairly convoluted scheme to do error correction across the modules, which I never really understand the motiva
This appears to be a major development for quantum rate-distortion theory.
...(continued)Hi all,
It has been kindly pointed out to us that the proof of Lemma 5.13 has an error in it, and one cannot lower bound the code distance of a merged code in all generality -- we would require extra conditions to do so.
We will amend this in a future version (along with the header formatting!
Just spotted this video abstract - what a great idea! Excellent way to communicate the essence of your work.
Braneshop, and
the US National Science Foundation.
SciRate