Paperz
Soon, all anyone will want to talk about is quarantines, food shortages, N95 masks, the suspension of universities and of scientific conferences. (As many others have pointed out, this last might actually be a boon to scientific productivity—as it was for a young Isaac Newton when Cambridge was closed for the bubonic plague, so Newton went home and invented calculus and mechanics.)
Anyway, before that all happens, I figured I’d get in a last post about quantum information and complexity theory progress.
Hsin-Yuan Huang, Richard Kueng, and John Preskill have a nice preprint entitled Predicting Many Properties of a Quantum System from Very Few Measurements. In it they take shadow tomography, which I proposed a couple years ago, and try to bring it closer to practicality on near-term devices, by restricting to the special case of non-adaptive, one-shot measurements, on separate copies of the state ρ that you’re trying to learn about. They show that this is possible using a number of copies that depends logarithmically on the number of properties you’re trying to learn (the optimal dependence), not at all on the Hilbert space dimension, and linearly on a new “shadow norm” quantity that they introduce.
Rahul Ilango, Bruno Loff, and Igor Oliveira announced the pretty spectacular-sounding result that the Minimum Circuit Size Problem (MCSP) is NP-complete for multi-output functions—that is, for Boolean functions f with not only many input bits but many outputs. Given the 2n-sized truth table of a Boolean function f:{0,1}n→{0,1}, the original MCSP simply asks for the size of the smallest Boolean circuit that computes f. This problem was studied in the USSR as early as the 1950s; whether it’s NP-complete has stood for decades as one of the big open problems of complexity theory. We’ve known that if you could quickly solve MCSP then you could also invert any one-way function, but we’ve also known technical barriers to going beyond that to a flat-out NP-hardness result, at least via known routes. Before seeing this paper, I’d never thought about whether MCSP for many-output functions might somehow be easier to classify, but apparently it is!
Hamoon Mousavi, Seyed Nezhadi, and Henry Yuen have now taken the MIP*=RE breakthrough even a tiny step further, by showing that “zero-gap MIP*” (that is, quantum multi-prover interactive proofs with an arbitrarily small gap between the completeness and soundness probabilities) takes you even beyond the halting problem (i.e., beyond Recursively Enumerable or RE), and up to the second level of the arithmetical hierarchy (i.e., to the halting problem for Turing machines with oracles for the original halting problem). This answers a question that someone asked in the comments section of this blog.
Several people asked me for comment on the paper What limits the simulation of quantum computers?, by Yiqing Zhou, Miles Stoudenmire, and Xavier Waintal. In particular, does this paper refute or weaken Google’s quantum supremacy claim, as the paper does not claim to do (but, rather coyly, also does not claim not to do)? Short answer: No, it doesn’t, or not now anyway.
Longer, more technical answer: The quoted simulation times, just a few minutes for quantum circuits with 54 qubits and depth 20, assume Controlled-Z gates rather than iSWAP-like gates. Using tensor network methods, the classical simulation cost with the former is roughly the square root of the simulation cost with the latter (~2k versus ~4k for some parameter k related to the depth). As it happens, Google switched its hardware from Controlled-Z to iSWAP-like gates a couple years ago precisely because they realized this—I had a conversation about it with Sergio Boixo at the time. Once this issue is accounted for, the quoted simulation times in the new paper seem to be roughly in line with what was previously reported by, e.g., Johnnie Gray and Google itself.
Oh yeah, I enjoyed Quantum Homeopathy Works. Cool result, and the title is actually a pretty accurate description of the contents.
To end with a community announcement: as many of you might know, the American Physical Society’s March Meeting, which was planned for this week in Denver, was abruptly cancelled due to the coronavirus (leaving thousands of physicists out their flights and hotel rooms—many had even already arrived there). However, my colleague Michael Biercuk kindly alerted me to a “virtual March Meeting” that’s been set up online, with recorded talks and live webinars. Even after the pandemic passes, is this a model that we should increasingly move to? I wouldn’t have thought so ten or fifteen years ago, but today every schlep across the continent brings me a step closer to shouting “yes”…
Follow
Comment #1 March 3rd, 2020 at 2:38 pm
Az to paperz, you could add “An algebraic approach to Koopman classical mechanics”, Annals of Physics, a few weeks ago, https://authors.elsevier.com/a/1aZC%7EopqoQN9
Dunno, Scott, whether this might be just enough to move you on from “Peter Morgan #41: In years of your commenting here, so far you have not written a single comment that I’ve understood in the slightest.” [Do you remember saying that? Google does. Unsurprisingly, I do, though I’ll try not to tax you with it often, insofar as I recognize that I am a little out of the box. What I’m really uncertain of is whether I’m crazy enough.]
If you want a quick-with-not-much-nuance 1000 word pop-level version of part of the paper, you could try https://thequantumdaily.com/2020/02/16/unifying-classical-physics-and-quantum-physics/ (11002 page impressions as of just now, so it’s almost at the point where someone like you will have to tell everyone what parts of it are nonsense), or you could enjoy Yale News’s provocatively OTT 100 words on this here: https://news.yale.edu/2020/03/02/insights-outcomes-thermodynamics-and-algebra-everything (the fourth item, “Algebra to the rescue”, if anybody needs rescuing.)
Comment #2 March 3rd, 2020 at 5:50 pm
Peter #1: Could you explain the double slit experiment or CNOT gate using your formalism?
Comment #3 March 3rd, 2020 at 6:50 pm
So who did you vote for today, Scott? Biden?
Comment #4 March 3rd, 2020 at 7:30 pm
Michael #3: Yeah, in the end, I “deciden for Biden”—though among the remaining top four, the only one who I didn’t seriously consider was Sanders.
Comment #5 March 3rd, 2020 at 11:10 pm
> I “deciden for Biden”
Guessing it was one of those strategic decisions “Who is likely to beat Trump” that backfired in 2016. Can’t imagine Biden being in any way an exciting candidate, and his role in discounting Anita Hill and confirming Clarence Thomas is not likely to gain him sympathy among progressive voters. Looks like the DNC is shooting itself in the foot once again.
Also “quantum homeopathy” is a very cool name. Though to be truly homeopathic, one needs an inverse-log dependence, because 10 times more dilution means twice as strong or something 🙂
It would be neat if the main outcome of this pandemic would be greater acceptance of telecommuting and better teleconferencing tools! Something Greta would approve of.
Comment #6 March 4th, 2020 at 7:58 am
Simplicio, a comment here is not the place to take apart lots of specific cases, however section 7.2 of AlgKoopman (that is, “An algebraic approach to Koopman classical mechanics”) gives something of an account of how we might think about an experiment that violates a Bell inequality. I’m currently working on a third piece expanding on that for The Quantum Daily, though it’s possible they’ll decide it goes too far from AlgKoopman, in which case I’ll perhaps post it to my blog.
AlgKoopman is building on Lorentz invariant isomorphisms between a specific random field and quantized electromagnetism that are constructed in a Physica Scripta paper, “Classical states, quantum field measurement”, https://arxiv.org/abs/1709.06711 (DOI there). As such this is different from quantization, which obviously is not an isomorphism, and it’s different from deBB because of the Lorentz invariance. There is a lot of nuance about what exactly this gives us, but it does give us something of a different perspective on QFT/QM and their relationships with random fields/CM. I take it that the editors and referees at Physica Scripta and at Annals of Physics —and the principals at The Quantum Daily— had and have reservations about details, as I certainly do, but I also take it they at least a little think that this might be a significantly new perspective, with whether it is in fact significant TBD.
I emphasize that I think QM/QFT comes out of this almost completely intact. Nobody will be abandoning QM/QFT. If different perspectives don’t drive you crazy, however, perhaps they make you strong, and if people start to find a perspective useful, first mover advantage comes into play.
If you want to respond, I suggest you find me somewhere else unless Scott decides to comment. He long ago discovered that I do go away if nobody encourages me, so he must have been specially frustrated with me that time (to be clear, however, I can’t remember Scott ever killing my comments in moderation). FQXi has a stub of a post about AlgKoopman, or find me on Facebook, peter.w.morgan.98, which I from time to time use as a whiteboard.
Comment #7 March 4th, 2020 at 9:36 am
Shmi #5:
Guessing it was one of those strategic decisions “Who is likely to beat Trump” that backfired in 2016. Can’t imagine Biden being in any way an exciting candidate…
Biden might not be an exciting candidate, he might even be senile and gaffe-prone, but he strikes me as basically a decent human being and not a cynical opportunist. I think he’d be willing to avail himself of the copious expert advice available to a president. And most importantly, the evidence of the Ukraine scandal suggests that Trump himself—who’s brilliant at demagoguery if at little else—regarded Biden as his most serious threat. And that’s more than enough to make me happy with my vote, and with how well Biden did yesterday, including in my newish home state of Texas.
Comment #8 March 4th, 2020 at 2:19 pm
nice article on MIP*=RE (at least for ppl like me!)
https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
Comment #9 March 5th, 2020 at 3:27 pm
I had been hoping for a charismatic candidate to emerge. The problem is that Sanders is the only one with a hint of charisma, although perhaps “bizarro-world” charisma.
Comment #10 March 5th, 2020 at 4:04 pm
Raoul Ohio #9: A funny thing about that is that, if you knew (say) Pete Buttigieg in real life, he might strike you as the most charismatic person you’d ever met. For godsakes, that might even be true for Tom Steyer or Amy Klobuchar. I base this on my experiences being struck by the charisma of “mere” CEOs, university presidents, and politicians of orders of magnitude less fame. Where the candidates fall short is only in comparing them to the superhuman charisma levels of an Obama or a Bill Clinton, or (of course) the evil charisma of Trump.
Comment #11 March 6th, 2020 at 7:20 am
Hi Scott
With regard to tomography, (I think) we show in https://arxiv.org/abs/1910.10543 that there is also no dependence on the number of properties you’re trying to learn (as well as no dependence on the Hilbert space dimension and just a linear dependence on a seminorm of the observables – seminorm and not norm as there are no errors in measuring the identity). Yes, the choice made for the definition of the snapshots (or shadows) is unfavourable for non-local observables, but that is a different matter…
Comment #12 March 9th, 2020 at 4:15 am
Scott,
I browsed both What limits the simulation of quantum computers? (12 pages) and On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking (7 pages). Even if I would invest more time and read those papers more carefully, I would not be able to fully understand them, without also studying some of the references in addition to the papers themselves. (I do know some background, like efficient classical simulation of stabilizer circuits, or how the Schmidt decomposition can be used for approximation.)
Therefore I have a slightly different question to you about that paper: Would that paper be a good starting point for me to dig deeper into approximate classical simulation of quantum circuits? Or are there better starting points which don’t appear among the references in that paper?