Recent comments from SciRate

I think indeed the main issue is the dependence on the confidence level. In Corollary 3 of our paper, as you mentioned, in order to achieve $1-\delta$ confidence level we only need a $\log(\delta^{-1})$ overhead, so the dependence is very weak. In the textbook version of QPE there is a linear $\delt

...(continued)

Actually, indeed textbook PE https://arxiv.org/pdf/quant-ph/9708016.pdf does not reach Heisenberg scaling as the total simulation times T scales as T \sim 2^m where m is the number of bits in phase and I think m has to partially scale as like log(1/\delta)=log(1/\epsilon^2) where 1-\delta is confide

...(continued)

I agree that MSE is the right quantity (only equal to variance if estimator is unbiased) and I agree with your choice of delta. So in Corollary 3, M has a dependence like \log(\epsilon^{-2}||H||) and you are saying that this only leads to a polylog(\epsilon^-1) factor in the total evolution time so

...(continued)

The reason we can do this in our paper, but not in the setting of 0709.2996, is that they did not assume the error to be bounded. However in most Hamiltonians we care about it is straightforward to obtain a bound on $\|H\|$ that is polynomial in the number of qubits, so we think this is a reasonable

...(continued)

Hello Professor Terhal, thank you for this very nice question! First as you correctly pointed out, we assume we start with a quantum state that only has a non-trivial overlap with the ground state, instead of the exact ground state. With this assumption a lot of phase estimation methods, such as the

...(continued)

Hi authors, interesting results! How does your work relate to Heisenberg-limited scaling in Theorem V.1 in https://arxiv.org/pdf/1502.02677.pdf in which one bounds the variance of the estimator. You write that your error is epsilon (which you get with high probability in Corollary 3), but this is no

...(continued)

Thanks for the question! Yes, we assume perfect free-fermion states. Also, we only require measurements in the standard basis, and we assume that they are performed without errors.

Thank you for sharing your paper on Fermion Sampling! Yes, based on your results, it appears that we wouldn't be abl

...(continued)

Very nice paper!

Does the result assume perfect free fermion states or some imperfection is allowed (say in trace distance)?

I also wanted to remark on two of the open problems stated in the end of the paper.

1) Learning pdfs corresponding to superpositions of free states.
I think that it is u

...(continued)

Is this a monotonic (aka non-increasing with respect to quantum channels) distance measure?

An important original contribution of this paper is that the author has identified conditions under which the relative entropy of Gaussian states is finite. The conditions depend only on the mean vectors and covariance matrices of the states being evaluated.

@Marcel Hinsche. Thank you for your question. I agree that polynomial extrapolation is notoriously ill-conditioned and suffers from the shortcoming you refer to. Our techniques might get you close to O(2^-n/poly(n)) for constant depth circuits but not close enough. Moreover, one loses the anti-conce

...(continued)

Dear authors, if I understand correctly worst-case to average-case reductions via polynomial interpolation cannot possibly extend into the regime of additive errors of size $O(2^{-n}/poly(n))$ that would be needed to close the gap in the hardness of sampling argument for random circuit sampling. Thi

...(continued)

Robert: I believe in the 2002 paper there is a single additional system that is used to go from qubits to rebits, so locality is not preserved in the translation from qubit systems to rebit systems.

How does this fit with
https://arxiv.org/abs/quant-ph/0210187
?

If I understand correctly, the authors have made a grand achievement in experimental quantum foundations. Congratulations!

My understanding is as follows:
They construct something like a
tripartite Bell inequality [0], whose maximal violation is achieved with only 4 qubits. Any experimental

...(continued)

Today an updated version of the paper has been uploaded to arXiv. We have added new quantum algorithms along with complexity-theoretic evidence for the classical intractability of the underlying problems, we have identified families of instances (i.e., graphs) with a quantum speedup, and we have imp

...(continued)

Problem solved.

Since today, an updated version of the paper is available on the arXiv. Besides having fixed the grammar mistake in the title, we have been able to extend our argumentation to show that the classes are already distinct for $n \geq 2$ qubits ($n\geq 3$ in v1) and agree for $n=1$.

There seems to be an issue with the arXiv tex engine.
No idea why the system accepted our submission in the first place,
when everything seemed OK, but cannot compile it now.

However, it _does_ produce perfectly good Postscript, which you
can then convert to pdf or any other format.

I just realized arXiv does not favor frequent version updates... My update frequency is limited to once per month. See my personal website for the most recent version (which contains some typo fixes and font change etc compared to the previous versions) and sorry for the possible bothering.

Since

...(continued)

(Updates: improved talk in https://www.youtube.com/watch?v=ri8uOOreEJU after a little bit of practicing. Resources in http://cs-people.bu.edu/jyz16 )

Maybe tone down the "epidemiology" bit in the abstract or substantiate it somewhere in the paper? You don't want some popular science journalist to draw the wrong conclusions.

It is my first time to see that a paper in quantum finance is using the JHEP style latex preprint.

Thanks for Angelo for reporting this on github - https://github.com/scirate/scirate/issues/396 - it's the font! Great discovery.

Wow what an awesome random bug tantan
(confirmed in Safari 14.0 on macOS 10.15.7)

Scirate question - why does `tantan` render as tantan (a smiley face in my browser)?

Thanks for the comment! Indeed, part of our motivation for writing this perspective was to provoke the community into describing ways of implementing quadratic speedup algorithms that might defy this analysis. But if I understand your suggestion correctly I do not think it would work. Usually the "c

...(continued)

Great perspective. One wonders if some kind of hybridization is possible, where at each step the classical logic primitive is computed on a classical computer based on information obtained via partial measurement and the result fed into the quantum algorithm. E.g. for optimization, the value of the

...(continued)

Dear all who are interested in this paper:
This paper has gone through significant rewrites in this half a year and recently and hopefully is more understandable than previous versions. The most suggested talk so far can be found in https://www.youtube.com/watch?v=PqGwYDeBvQU&feature=youtu.be which

...(continued)

A tutorial on Tensorflow Quantum [https://www.tensorflow.org/quantum/tutorials/quantum_data][1] provides an implementation of the numerical experiments.

It shows how classical and quantum ML models can both easily achieve near-zero training error but the quantum model can generalize better on eng

...(continued)

The referenced paper is https://scirate.com/arxiv/2004.01469

This is a strong and interesting result for the resource theory of thermodynamics and the resource theory of asymmetric distinguishability. I send my congrats to the authors.

Yes, it certainly *seems* like the operational argument (at the end of section IV.A) would apply to Bohmian mechanics.

In this paper, there is an operational argument in support of the assumption which is labeled P3 (that the two-time probability is a linear function of the quantum state). One might have supposed that this argument would apply equally-well to Bohmian mechanics; however, (as noted in the paper), a

...(continued)

A nice perspective by one of the authors: [https://mycqstate.wordpress.com/2020/09/29/it-happens-to-everyonebut-its-not-fun/](https://mycqstate.wordpress.com/2020/09/29/it-happens-to-everyonebut-its-not-fun/)

Or, shamelessly advertising myself here, "Recurrent Quantum Neural Networks", http://arxiv.org/abs/2006.14619 (2020)

At the bottom of p. 2 the authors comment "However, the problem of learning sequential data, to our best knowledge, has not been investigated in the quantum domain."

However, with the ubiquity of modern search engines, it would not have taken too much effort to find that in fact there have been s

...(continued)

Thanks!

They actually work by copying and pasting, but the embedded URLs leads to the wrong places.

Interesting result. Just as a feedback, the two google links on Page 4 are not available.

Ah yes! Thanks for the explanation.

Glad you like it! I must admit, we also thought it was N^{5/8} for a while. But, I think N^{3/5} is indeed what follows from balancing. Though, if we miss something, please let us know so we can get that extra 0.025 power in the exponent.

Ignoring polylogs, one has distances N^{1/2} and N^{3/4

...(continued)

Amazing! Unless I'm missing something, the distance should even be $N^{5/8}$ instead of $N^{3/5}$, unless the balancing trick (or the final weight reduction) causes the expected distance to decrease.

Yes, please do post it here if you find something interesting -- you're also welcome to just send me an email! Also, thanks for pointing to its role as a biodiversity measure -- I never would have found that (in fact, they use the entire family of Rényi entropies).

Thanks for the reply!

The first time I encountered a quantity of the form $\sum_i p(i)^2$ was in the context of Rényi entropy, and then as a [biodiversity measure](https://www.maths.ed.ac.uk/~tl/mdiss.pdf), so it defintely does appear under many names! I'll look around for earlier references conn

...(continued)

Hi Blake, thanks for the comment. In fact, the connection between $l_2$-norm of coherence and participation ratio was already used in a previous paper by a subset of the authors: https://arxiv.org/abs/1906.09242; see Appendix C (where it is implicitly used). But for some reason, we had forgotten to

...(continued)

In Eq. (5), the authors state that given a pure state and a basis, the second moment of the probabilities for that state measured in that basis is equal to 1 minus the [$l_2$-norm of coherence](https://arxiv.org/abs/1311.0275), and they say that "To the best of our knowledge", they make that connect

...(continued)

Victory asked if my theory does not contradict the (excellent) paper "Quantum advantage with noisy shallow circuits in 3D" by Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel (BGKT).

This is a good question.

The crucial point is that my theory excludes the ability of NISQ s

...(continued)

I like the title of this paper! It is very cyberpunkian!

Thanks for the very detailed comments, this was extremely helpful.

I posted a revision based on your suggestions. Let me remark that this introduction is meant for non-physicists that may not be comfortable with the more traditional approach.