miles7

Not at all clear from the paper whether you need a quantum computer to do these calculations or whether the same circuits could be simulated classically.

(I.e. from what I can see the paper never mentions the amount of entanglement or complexity in the quantum state, or that they used state-of-the-art simulation techniques like tensor networks to check.)

If someone knows of a blog post, supplemental material, etc. that reports this I'd be curious to know.

I encourage people to read the article for themselves and reach their own conclusions.

To clarify a bit more, for us the purpose of opening the oracle and simulating it, whether or not we were the first ones to do it (e.g. we weren't, see Chamon paper above) was to say that

"There are many cases where it's already known one doesn't need Grover's algorithm, such as if a problem already has a polynomial-time solution. We have now identified a new set of cases where one doesn't need Grover's, which is where the oracle can be simulated only once by a tensor network (or log(N) times in a "closed" simulation".

So the point of that part of the article is to further delineate when Grover's algorithm is actually needed or not needed. It only applies to real-life problems where one must actually know the circuit.

Your comment is helpful to us to see what are some common misunderstandings about what we are saying in our paper versus not saying. It could be some problems with our writing. For example, we state all of the things you said above explicitly in the paper and wrestle with them in quite a few places. Also there is a whole second half of the paper that addresses precisely the question of "what if we have an instance that we can't classically simulate? i.e. scales as 2^n?". Your comments don't address that part of the paper.

The first half of the paper, about opening up the oracle is written by definition for people who don't know it, as is the case in any article. Personally knowing about something but which is not published is not a valid or helpful criticism of a published work (or preprint). On the other hand we could not find any publications talking about opening the oracle in the context of attempting to simulate it nor discussing entanglement barriers in the oracle (other than giving unhelpfully general worst-case bounds). The one exception is the following paper by Chamon and Mucciolo https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.10.... If you know of some publications you could point us to, we'd be happy to incorporate them into a later draft of the article and cite them.

As one of the authors, I'm ok with reasonable disagreements (e.g. see D. Bacon's below) about whether our overall conclusions are justified. But I feel it important to point out that your comment above is just a pure misrepresentation of the procedure in our paper.

In a future draft we will bring out this point more clearly, but we do not unroll the post-oracle state into a vector of size 2^n and just look at the winners. We use a well-established sampling technique from the matrix product state literature (reference: https://arxiv.org/abs/1201.3974, also cited in the paper) which runs deterministically and always scales as log(N) = n. (This part is independent of the oracle used.)

Overall our approach scales as log(N) for cases where the oracle can be simulated in polynomial time. We give such a case explicitly in the paper. Of course for many oracles, applying the oracle will scale exponentially which we say, but we show that there exist quite a few instances (we could show many more) where the actual time is minutes or hours to sizes of qubits (e.g. 40 qubits) that would require a million iterations of Grover's algorithm if it were run on a physical quantum computer.

I have a dumb question that keeps nagging me, and wonder if someone here has a good answer. What does Web3 necessarily have to do with the web? Couldn't an iOS app which uses blockchain technology as a decentralized database be just as good an example of what Web3 is trying to achieve? Or a technically oriented command line app for finance using a blockchain which does not involve a web browser?

Are Web3 people just using "web" as a stand-in for the internet?

My favorite is the quantum computing researcher Toby Cubitt.

An easy to read (minimal theorems) but authoritative and modern introduction to tensors can be found in the book “An Introduction to Tensors and Group Theory for Physicists” by Jevanjee (https://www.springer.com/gp/book/9783319147932).

He takes the more geometrical perspective as a tensor as a multi-linear function of vectors, from which all other statements about tensors (eg how the components transform) follows straightforwardly. Lots of other great material in this book and best of all there are loads of examples.

Last paragraph of the article for some reason: “The CDC also said the report is “insufficient” to draw conclusions about the effectiveness of the authorized vaccines against Covid, including the delta variant, during this outbreak.”

Often one is not really interested in solving Ax=b for all possible b but just one particular b. In that case one can iteratively solve for x by algorithms like conjugate gradient which only require multiplying A times the current best guess for x, which can be very fast and avoids numerical instability issues in many cases.

To your first question, probably not any time soon. The main quantum algorithm for breaking (certain types of) cryptography is Shor’s algorithm, and will probably need error-corrected quantum computers with at least hundreds of logical qubits to beat classical methods. That translates into thousands of physical qubits of very high quality with exquisite control over them and interconnectivity.

If my answer makes it sound like the prospect of quantum computers is overhyped that’s because it most definitely is.

A somewhat smaller version of this quantum simulator from Harvard has been studied a lot in the past and given high enough quality results on various benchmark tests that the community is convinced the author’s claims about it are legit.

Conformally symmetric critical systems are often, though not always, studied by modeling them by conformal field theories, which do involve an action obeying a conformal symmetry. A good reference about conformal field theories is any book or paper by John Cardy who is exceptionally clear. Here is a good one where he shows an action of a CFT at the beginning of section 3.0.1: https://arxiv.org/abs/0807.3472

For some reason the Wikipedia page on CFT’s says they are quantum which can be true but is certainly not necessarily the case, and a huge amount of the beautiful mathematics of CFTs was worked out for purely classical systems (classical statistical mechanics). The whole subject is a triumph of the 20th century and deserves to be better known.

I’m pretty sure Noether’s theorem does apply to CFTs and is used quite heavily to analyze them. See for example these notes: https://www.google.com/amp/s/tracingcurves.wordpress.com/201...

Seems notable that they are using the Sinopharm and Covishield vaccines which have been found to be less effective than vaccines like Pfizer or Moderna. Also that 63% of people with new cases had either not been vaccinated or had received only one dose.

What’s your opinion on Julia?

It really blows my mind to think of the things experimental physicists have accomplished and continue to accomplish. One example is molecular beam expitaxy (MBE) technology that lets researchers deposit layers of a material that are literally one atom thick. Another example is the work by the LIGO project to push mirror technology to limits that are hard to believe: https://www.quantamagazine.org/to-make-the-perfect-mirror-ph...

I think for most people defund sounds like “take away all funding for” which would be tantamount to abolishing.

Another important consideration is library development. As someone developing a large library, when we were previously developing in C++ we would encounter large barriers where some design goal we had either couldn't be done in the language in a practical sense or would require hours of tweaking things like template constraints to work correctly. Our users also had such a hard time extending our library's features they usually gave up and just waited for us to add features for them.

Now that we're developing in Julia we can realize our designs as we envisioned them with very little code. Features like multiple dispatch have been a lifesaver for us. And we are getting performance that is quite close to C++. Now we're looking forward to using features like composable multithreading.

One could wonder "why not use python?" but for performance reasons one ends up with the 'two-language problem' which we wanted to avoid.

What about students from countries whose time zone is 12 hours different? They can watch lecture recordings, sure, but miss out on asking live questions or participating in discussion groups with other students unless they stay up through the night.

Agree, though for many Americans it doesn’t take too much energy since they don’t pay any attention to what’s going on in other countries.

Here's a brief statement by Anderson that he wrote for the website www.edge.org. Apparently his main issue was that string theory isn't experimentally driven:

""" Philip W. Anderson Physicist and Nobel laureate, Princeton

Is string theory a futile exercise as physics, as I believe it to be? It is an interesting mathematical specialty and has produced and will produce mathematics useful in other contexts, but it seems no more vital as mathematics than other areas of very abstract or specialized math, and doesn't on that basis justify the incredible amount of effort expended on it.

My belief is based on the fact that string theory is the first science in hundreds of years to be pursued in pre-Baconian fashion, without any adequate experimental guidance. It proposes that Nature is the way we would like it to be rather than the way we see it to be; and it is improbable that Nature thinks the same way we do.

The sad thing is that, as several young would-be theorists have explained to me, it is so highly developed that it is a full-time job just to keep up with it. That means that other avenues are not being explored by the bright, imaginative young people, and that alternative career paths are blocked. """

(source: https://www.nytimes.com/2005/01/04/science/god-or-not-physic...)

One thing I didn't see mentioned about creating software is that the tools and the systems often have serious problems to begin with, even before you start writing a program.

Some well known examples are:

- major programming languages such as C don't do enough to help with memory safety issues

- lack of explicit types in python function arguments can lead to surprising bugs which recur again and again

- operating systems and platforms, such as different web browsers, adhere to widely different conventions about how dependencies on other libraries and code is managed

Forgot to mention, but here is a recent theoretical result (prediction of generalization performance giving size of training set) based on tensor networks: https://itensor.org/miles/GenerativeMPS.pdf

Agreed. There is still a lot of work left to do!

There is a lot of evidence for what Paul says once you dig into a specific field. Taking two fields I know well: in physics, there was decades of work on fundamental questions on systems in equilibrium, while many obviously important open questions in out-of-equilibrium systems went neglected until the last 10 years or so when there's been a huge upsurge. These questions were known to be open 20 and 30 years ago, but just weren't as fashionable as a topic. Anyone senior enough in those earlier decades knew there were tons of open questions but also that relatively few people were working on them for whatever reason.

In machine learning, there are currently a lot of people working with neural networks, but relatively fewer people exploring alternative model architectures. So much so that issues specific to neural networks sometimes get framed as fundamental to machine learning itself. I'm personally exploring an alternative class of models called tensor networks with many possibilities for research directions and lots of open questions but only a handful of people work on them. One reason for working on a popular idea is that it's nice to work on a topic where you have many colleagues and know in advance that your model is likely to give good results on challenging datasets.

I agree it's an important question. But one thing often left out of the possible answers is to go forward with using cheap labor overseas while also providing a very strong safety net and job retraining options to those who lose their jobs as a result. If this was done, then those workers might be able to benefit from the cheaper prices of products too while still having money in their pocket. Instead they've just been abandoned.

Obviously this is oversimplifying things, but I'm just saying that on the one hand it's important for disruption to happen (Uber making it harder for taxis) for the sake of progress, but for the sake of justice and the social fabric we should protect those most affected by the disruption.

Regarding Lukin’s experiment - which is very interesting and high quality - in most instances it can be simulated by existing classical methods (matrix product states / DMRG being a key example). This does not detract from the importance of realizing the same system experimentally at all. But it does prevent it from realizing a gap between classical and quantum computing.

Does getting the job done include being able to improve the product later?

I agree they do, but in my experience they also make them do aptitude tests like whiteboard coding or asking trick math questions. These tests overlook the actual (rare) skills the candidate has in favor of skills more often known only to certain types of engineers and CS majors.

Too many religious people that I know think that scientists have it out for them and/or are conspiring against them. Enough articles like this and it will prove their point for them (the statement equating being irreligious with acting like an adult), even though I don't think it's true of scientists as a whole.

Summary: Lauren Hayward Sierens from the Perimeter Institute gives a pedagogical lecture to a group of high school teachers, walking through the very basics of feed-forward neural networks. A great talk for anyone just getting started with the subject.