Recent comments from SciRate

Lim Youngrong Nov 16 2022 20:32 UTC

Thank you for your question. Because the error of our scheme is larger than what we need in the hardness conjecture of that paper, our result does not contradict the conjecture.
Please refer to AA's original boson sampling paper, where a similar thing happened for the permanent and Gurvits's algorit

...(continued)
Zhenghao Li Nov 15 2022 18:16 UTC

Hi, amazing work! I was wondering if your results would affect the structure of proof in [https://www.science.org/doi/epdf/10.1126/sciadv.abi7894][1], which is based on the conjecture that |Haf|^2 is #P-hard to approximate to within *additive* error (Conjecture 2 in the paper)? Thanks!

[1]: h

...(continued)
Lorenzo Leone Nov 11 2022 06:13 UTC

Amazing work! Look forward to reading it in more detail!

Patryk Lipka-Bartosik Nov 03 2022 07:53 UTC

Thanks for the nice question. In this framework, in the simplest case, we have two systems (the main system and the heat bath) coupled by an energy-conserving interaction. Therefore, any change in the energy of the system
is equivalent to the same (with a minus sign) change on the bath (therefore

...(continued)
MariusK Nov 02 2022 12:47 UTC

I really like your axiomatic formalization!

One suggestion, though:
I would rename "efficiency" to "faithfulness".

Seok Hyung Lie Nov 02 2022 05:45 UTC

Thanks for the reply. I have a small question content-wise. Is there no distinction between work and heat in this framework? It seems like all the energy influx into a system is counted as 'heat', but I think somehow work can be exchanged too between systems with different temperatures through a ene

...(continued)
Patryk Lipka-Bartosik Nov 01 2022 19:39 UTC

Thanks for the comment. You are right. The second statement about heat flows should be just as you wrote, i.e: "heat will flow from the environment". The right statement is captured by Eq. (5).

Thanks for mentioning the typos. We plan to update the arXiv version soon; We'll get rid of them :)

Aram Harrow Nov 01 2022 18:06 UTC

Classic work establishing, among other things, equivalence between establishing high entanglement fidelity and low diamond-norm error. However, the arxiv version has an incorrect proof of this fact (Thm 1 in section V.A); see the IEEE IT version for the correct proof.

Seok Hyung Lie Nov 01 2022 07:21 UTC

Nice work. I am still reading the paper but I think "Heat will always flow towards the environment " and "the environment will always absorb
heat" on the first page mean the same thing. It seems like the second sentence should say that the heat will flow from the environment as it is hotter than $\r

...(continued)
Elizabeth Crosson Oct 28 2022 14:28 UTC

The proof that the stoquastic local Hamiltonian problem is in AM also applies to stoquastic Hamiltonians that are sparse, but non-local. On [page 5][1]:

"Moreover, we will prove that evaluation of the largest eigenvalue of any n-qubit non-negative matrix whose matrix elements are efficiently co

...(continued)
Chinmay Nirkhe Oct 28 2022 11:17 UTC

I see. We are no experts in the technicalities here so we will correct the section here accordingly. I believe MA is correct since the Hamiltonian corresponding to a graph is frustration-free. But we will need to clarify this.

All we were trying to say (and the gist this holds) that the algorithm

...(continued)
Yupan Liu Oct 28 2022 04:19 UTC

Thanks for this interesting result, but I am confused about the discussion regarding stochastic Hamiltonians (on Page 7):
> The problem of calculating the ground energy of stoquastic local Hamiltonians was shown to be contained in MA by Bravyi, Divincenzo, Oliveira, and Terhal [BDOT08].

As far as

...(continued)
Yoshifumi Nakata Oct 28 2022 00:08 UTC

We updated our paper. In the new version (ver. 2), we removed an unnecessary assumption, which rarely holds in general as pointed out, and further improved Theorem 1. We mentioned the comparison of the performance of our decoder with previous ones as an interesting future problem.

Seok Hyung Lie Oct 25 2022 17:58 UTC

Nice work on superchannels. However, I have a simple question about the motivation of studying QSCs. Superchannels are naturally characterized by the requirement that they should map bipartite quantum channels to bipartite quantum channels even if they act on one party of the channel. On the other

...(continued)
MariusK Oct 25 2022 16:11 UTC

It might be worth saying more about the implementability of your encoding $R_f$.
Your Figure 1 (b) seems to suggest that one needs over 50 orders of magnitude of precision.
You mention that this leads to numerical instabilities.
However, I am more worried about experimental implementations in act

...(continued)
Wojciech Kryszak Oct 21 2022 20:37 UTC

It seems to be a nice clash between you and Nicolas - a lot to think about, thank you (both)!

> Wouldn’t we be more free if we can determine our next decisions
> based on how we are now, rather than letting them at the mercy of
> randomness?

My nearest next decision is just almost now so I

...(continued)
MJKastoryano Oct 19 2022 10:28 UTC

Thanks for the clarifications, and for the nice paper!

Chris (Jielun) Chen Oct 18 2022 15:02 UTC

Hi, thanks a lot for the reply! Our paper’s results mainly differ from them as follows:

- In the two papers you mentioned, the authors consider the *exact* tensor contraction of the *approximate* QFT (AQFT) on product inputs and outputs. Specifically, they are simulating $\langle x| C |y\rangle$,

...(continued)
MJKastoryano Oct 18 2022 10:34 UTC

How do your results relate to, [arXiv:quant-ph/0611156] and [Phys. Rev. A 76,
042321 (2007)]? On the surface, the conclusions look quite similar.

Johannes Bausch Oct 18 2022 09:13 UTC

Interesting paper! One point: I wouldn't say that current quantum NNs don't have inductive biases; my paper on QRNNs (https://arxiv.org/abs/2006.14619) has a circuit designed to mimick latent state read and write operations; as well as many circuits used in the context of many-body Hamiltonians feat

...(continued)
Yoshifumi Nakata Oct 15 2022 09:45 UTC

Thanks for letting us know a relevant paper. We have not compared our bound with yours. We will have a closer look and write you back.

Jon Tyson Oct 15 2022 09:01 UTC

Have you compared your new bound to those of equation (153) of https://arxiv.org/abs/0907.3386? Note that this is NOT the Petz map, and furthermore the gamma quantities do not involve anything at all similar to a petz map.

Yoshifumi Nakata Oct 15 2022 08:39 UTC

Thank you for pointing it out. You are right, the basis $F_{\diamond}$ satisfying our condition rarely exists unless $E$ and $F$ are already MUBs.

We will update the paper soon, but we would like to mention here that our main message is still valid: $\Delta_q$ is bounded by $\Delta_{cl, E}$, $\De

...(continued)
Jon Tyson Oct 15 2022 07:43 UTC

To put this another way, choosing the computational basis to be the $F$-basis , equation 12 and the one directly above it say that the vectors in $F_\Diamond$ are formed by rescaling each coordinate of each $E$ -vector (by a positive real number multiple) to have magnitude $d^{1/2}$.

However the

...(continued)
Jon Tyson Oct 14 2022 15:11 UTC

Unfortunately, there a bug in equation (12), which overdetermines the phases of the coordinates of the mutually unbiased basis F_diamond in the F-basis.

Since generally there is no MUB satisfying all these phase conditions, the decoder of Theorem 1 does not exist for most bases E and F in dimension

...(continued)
Pasi Lähteenmäki Oct 14 2022 10:05 UTC

Contrary to the author, I certainly don't know that I or anyone else has free will. I just know that I exist as I keep experiencing things. I can't even imagine how free will would work. One would first have to define free will in a coherent manner to have a meaningful discussion about it. What exac

...(continued)
Blake Stacey Oct 13 2022 13:24 UTC

The basic suggestion of "maybe we can combine economics with gauge theory" is at least as old as a 1994 essay by Lane Hughston, better known to physicists for his work on [density-matrix decompositions](https://en.wikipedia.org/wiki/Schr%C3%B6dinger%E2%80%93HJW_theorem):

L. P. Hughston (1994), "S

...(continued)
Hakop Pashayan Oct 12 2022 12:28 UTC

Hi Robert

I fully agree :). Indeed high weigh Paulis are an "expensive" observable for classical shadows in general as they have exponential sample complexity in all three depth regimes. Nevertheless, the sample complexity can be orders of magnitude different depending on the choice of depth used

...(continued)
Jalan Ziyad Oct 11 2022 22:10 UTC

Hi there is an error on Figure 1. Your logical Z doesn't commute with one of the stabilizers.

Hsin-Yuan Huang Oct 11 2022 14:58 UTC

Hi Hakop,

Thank you for the prompt reply! That makes the advancement much clearer!

To summarize, for the computational task (1), the efficiency in your work refers to the fact that one can compute the estimated value of any linear combination of $\mathrm{poly}(n)$ general Paulis from classical sha

...(continued)
Hakop Pashayan Oct 11 2022 13:15 UTC

Hi Robert

Thanks for your comment. There are two kinds of efficiency that are important here. The first of these is relevant to both your shadow scheme and ours. This is the sample complexity associated with producing accurate estimates. As you correctly point out, for high weight Paulis the shad

...(continued)
Hsin-Yuan Huang Oct 10 2022 16:10 UTC

Thank you all for the nice work!

Should there be a constraint that the poly(n) Paulis must all be few-body (similar to random Pauli measurements) in the abstract? Prior works proved that we could not efficiently estimate many general Paulis using single-copy measurements.

Best regards,

Robert (Hs

...(continued)
Weilei Zeng Oct 09 2022 06:47 UTC

Nice work! Can you give a short explanation for the name _Quark_ ?

Chinmay Nirkhe Oct 08 2022 18:18 UTC

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.pdf

Apologie

...(continued)
Marcos Crichigno Sep 29 2022 20:57 UTC

Thank you for your prompt reply, Seth! Once again, congratulations on your paper to both!

Seth Lloyd Sep 29 2022 16:27 UTC

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)
Marcos Crichigno Sep 29 2022 09:09 UTC

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)
Chris Cade Sep 28 2022 18:07 UTC

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)
Ryan Babbush Sep 28 2022 15:17 UTC

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)
Ismail Yunus Akhalwaya Sep 28 2022 07:10 UTC

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)
Marcos Crichigno Sep 27 2022 19:21 UTC

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)
Chris Cade Sep 27 2022 13:39 UTC

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)
Ryan Babbush Sep 24 2022 14:29 UTC

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)
Marcos Crichigno Sep 23 2022 23:41 UTC

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)
Ismail Yunus Akhalwaya Sep 23 2022 17:43 UTC

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)
Earl Campbell Sep 21 2022 21:55 UTC

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)
Ryan Babbush Sep 21 2022 21:01 UTC

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)
Travis Scholten Sep 21 2022 15:10 UTC

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

...(continued)
Aram Harrow Sep 21 2022 14:32 UTC

Is this problem known to be DQC1-complete? That would be one way to address Ryan's concern.

Ryan Babbush Sep 21 2022 03:24 UTC

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)