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.
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.
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.
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?
> 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?
Until Tim decides to wave his hand and shut it down. Same thing with a hosted website. But developers could distribute the web app as html and then users run it locally. It connects to the blockchain and submits transactions.
> Or a technically oriented command line app for finance using a blockchain which does not involve a web browser?
Interacting with smart contracts does not require a web browser.
Cryptocurrency has no value beyond what someone is currently willing to pay you for it and blockchain networks are expensive always-on distributed systems which require payment in other currencies. That requires a constant stream of new buyers, and the combination of limited usefulness and mounting bad reputation was starting to cut into it.
“web3” is the rebranding campaign which the large holders came up with to try to drive demand.
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.
(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.