Nice work! Can you give a short explanation for the name _Quark_ ?
...(continued)We are withdrawing this note from the arXiv -- the withdrawal will update on arXiv at the next update.
The withdrawal is due to an uncorrectable error in the proof.
A detailed explanation of the error is hosted on my website at
https://nirkhe.github.io/simple_nlts_retraction.pdfApologie
Thank you for your prompt reply, Seth! Once again, congratulations on your paper to both!
...(continued)First of all, congratulations on your (very recent!) excellent preprint on the QMA1-hardness of clique homology. Quite a few papers on quantum homology have appeared on the arXiv in the last week: we are still analyzing the overlaps, connected components, and voids in this `homological hundredth mo
...(continued)Dear Alexander and Seth,
Congratulations on your paper! Your comments on when exponential quantum advantage is possible are very interesting!
You may not be aware of this but I should point out that the result reported in your **Theorem 1** (*#P-hardness of exact Betti numbers of clique-dense com
...(continued)Hi Ryan, I'll try to keep my reply short ;) (Also happy to take the discussion offline if it looks likely to continue indefinitely).
What you write is correct indeed. The hard-core fermion model on a graph considered in their paper is precisely the independence complex for that graph: i.e. the '
...(continued)Thanks Ismail. I think the new version of your abstract that you've recently uploaded is much improved. I agree that the relaxation of the problem you describe in your most recent post is likely to admit a substantial quantum speedup for many data sets. I agree it's cool. But, as you mention, the ma
...(continued)Hi everyone, I'm tickled pink by the fascinating discussions here, thank you!
Just to let everyone know, we have uploaded a new version to arxiv incorporating the above suggestions (with acknowledgements). We're still happy to make further changes as they crop up.
One further thought combining
...(continued)Hi all,
Related to your question, Chris, I agree that it is not sufficient to just have “beta_k” growing exponentially but it should grow exactly like 2^n/poly(n), which indeed is fine-tuned. On the other hand, as you know well, one should keep in mind that the LGZ algorithm does not estimate the *
...(continued)Hi all,
Nice that you are having this discussion! I agree with the sentiment of Ryan's comments, in that it feels unlikely that a real-world dataset will happen to be one for which we can obtain an exponential ('proved' or otherwise) advantage over classical algorithms.
On that note: you both
...(continued)Thank you for your thoughtful reply. I think we’re basically in agreement about the facts of the matter. While these terms are a bit ambiguous, the requirement that data have exponentially many holes still seems pathological enough that I would hesitate to call it “arbitrary” and “non-handcrafted” w
...(continued)To clarify, the nice work by Gyurik-Cade-Dunjko that you mention does not claim to show DQC1-hardness of estimating normalized "Betti" numbers. What they establish, improving on work by Brandao, is DQC1-hardness of determining the low-lying spectrum of a general Hamiltonian, which has nothing to do
...(continued)Dear Ryan, Aram, and Travis
Thank you very much for this discussion and for sharing your precious time and insights. This is what we love about arxiv/scirate in that it allows us to improve our pre-print before publication.
Thank you for doing a great job of getting to the heart of what seem
...(continued)Thanks for your question. We did indeed so some experiments as you suggest, but decided to keep the message simple and omit them.
For a quantum memory experiment, we found you could roughly half the buffer region with no significant impact on the logical fidelity, but improving the decoding
...(continued)As I mentioned in my comment, the DQC1 results from Dunjko and others pertain to estimating the normalized Betti number - a quantity that exponentially concentrates to zero unless the Betti number is exponentially large. Having exponentially large Betti number is a very unusual property that we shou
...(continued)There is this work from Dunjko et al: https://arxiv.org/abs/2005.02607
From the abstract:
"In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by th
Is this problem known to be DQC1-complete? That would be one way to address Ryan's concern.
...(continued)The abstract of this paper suggests that the quantum topological data analysis algorithm provides a “provable exponential speedup on arbitrary classical (non-handcrafted) data”. This is a strong claim, especially in light of arguments, see e.g. [arXiv:1906.07673][1], that super-polynomial speedup is
...(continued)Did you experiment with varying the sizes of $n_{com}$ and $n_{buf}$? Intuitively, larger $n_{buf}$ means decreased error rate but increased overhead... and large $n_{com}$ decreases both but increases latency. Would be nice to see empirically the benefits or drawbacks of values other than d, especi
...(continued)A special case of your formula for the probability distribution $p(x | n, m, k, l)$ was obtained by Montanaro in [arXiv:0903.5466][1]. Namely, when $n = k$ and $m = l$ we have $p(x | k, l, k, l) = \mathrm{Pr}[x|l]$, where $\mathrm{Pr}[x|l]$ is given in Montanaro's Lemma 4. It denotes the probability
Equation (25) appears to be incorrect to me, you are writing the second order Trotter formula as $U_2(dt) = \left[ U_1 (dt/2) U_1(dt/2)^T\right]^m$, but since $dt = t/m$ then this would correspond to a Trotter formula for $U_2(t)$ not $U_2(dt)$?
...(continued)Hey, thanks for your question.
So in our work, we find that for the ansatze we consider, the onset of barren plateaus is related to the width of the causal cone of an observable.
The width itself expands via entangling gates like CNOTs in the circuit architecture.In the qMPS ansatz, the ent
...(continued)Hi, congratulations to your work. From your work, you state that the barren plateau is absent for qMERA and qTTN, but exists for qMPS. From previous works, entanglement can induce barren plateau, and I assume the ensemble of states generated by qMPS has smaller entanglement than the other two and a
Thanks! Indeed, there is a typo in the direction of the majorization symbol of Definition 1 in Appendix C.
Outstanding work. Small typo?: It seems like the direction of majorization symbol in Definition 1 of Appendix C is reversed.
This paper refers to the version of RQM that existed before the introduction of "cross-perspective links" in [arXiv:2203.13342](http://arxiv.org/abs/2203.13342), a change that amounts to saying, "Well, we didn't want all those 'relative facts' anyway."
...(continued)Hi, Anthony! Thank you for pointing out the Oded Goldreich survey. I think it's really neat! I haven't read it yet before since the original paper [30] was written so well that I never needed to look anywhere else. I believe you are referring to the comment on page 3, where he indeed considers somet
Hi Pavel,
You're right that ref [30] doesn't use double covers, although the overview from Oded Goldreich that came out a few weeks later did
https://eccc.weizmann.ac.il/report/2021/175/
Of course, we'll be happy to give you proper credit when we update the manuscript.
Best,
Anthony & Gilles
...(continued)Congratulations! A very nice result with much shorter proofs than ever before! It is great that with all these recent simplifications each next paper rapidly approaches the high standards of simplicity and elegancy set by Sipser and Spielman in 1996. However, with all due respect, I believe, you inc
Note that Eqs. 7 through 14 in the arXiv version of this paper are not correct. The correct expressions appear in the published version in Physical Review Letters. It's pretty straightforward to fix these equations if you are following the paper by hand, but be warned!
This is an outstanding paper in quantum Shannon theory. Congratulations to the author.
Thanks for pointing this out! The PDF should be working now. Sorry about the initial error.
The arXiv vanity version seems to work (to some extent): https://www.arxiv-vanity.com/papers/2207.14438/
Looks like arXiv is not able to produce the PDF file for this paper.
It seems that our future AI overlords will have us all speaking Pirahã, then. :)
Very nice paper. You may be interested in this great paper by Montina:
https://arxiv.org/abs/1107.4647
that looks into the d>2 case that you mention in your discussion section. It seems this qubit case is quite exceptional and difficult to generalize.
Thanks Mark! I'm also looking forward to read your paper in detail.
Thanks a lot for your comment and for pointing out your paper. We'll definitely add a citation to your work in a revision of our paper. We're reading your paper now and will email you if we have any questions about it.
...(continued)Congratulations for the nice result! I did not expect that estimation of multivariate trances (also known as Bargmann invariants) can be performed so easily. Still, I wanted to point out that in this earlier work https://scirate.com/arxiv/2109.10006 with Ernesto Galvao and Dan Brod we managed to co
...(continued)Hi William, Thanks for pointing out the error. Indeed, it should be
..., then $|{H_{ji}}|^2 = \sum_{kk'}h_kh_{k'}p_{kk'}^i(j)$ with $p_{kk'}^i(j)=\mathrm{Re}\langle i|U^\dagger P_k U\Pi_jU^\dagger P_{k'} U|i \rangle$ satisfying $\sum_j |p_{kk'}^i(j)|\le 1$.
The key point here is that by regar
I've been reading your paper with interest but I think that the claim (top left of page 4) that $p^i_{kk'}(j) \geq 0$ and $\sum_j p^i_{kk'}(j) =1$ is incorrect.
I'd also be curious to know how you expect your algorithm to perform in the presence of sampling noise.
...(continued)I think there is a mistake in the proof, which causes Theorem 2 to be incorrect. There should be an additional $2^n$ factor ($n$ is the number of qubits) in the number of experiments stated in Theorem 2. If Theorem 2 is true, then given any exponentially deep classical boolean circuits on $n$ bits,
...(continued)Thanks for pointing out this nice paper. Our main results relate to single copy measurements, not multi-copy measurements (e.g. Hillary's paper with noiseless circuits but also https://arxiv.org/abs/quant-ph/0111082, which we do cite). We have also entanglement conditions in terms of only the first
Thank you for your reply, and I appreciate your revision in the next version.
Go right ahead! I'm glad you like it :D
Thanks Shu for the clarification. We will revise that description in the next version of our work.
I think they're supposed to be arm-wrestling, not making a deal. :)
This is beautiful, thank you, hahaha! A deal with the devil it is :D
Also... do you mind if I use this in a talk some day?
Braneshop, and
the US National Science Foundation.
SciRate