### Ten updates

Wednesday, November 7th, 2018If you like quantum, complexity, etc., then please read to the end! I’ve gotten a bunch of emails lately of the form “why haven’t you ever blogged about such-and-such?,” when it turned out that I damn well *did* blog about it; it was just somewhere down in a multi-item post.

**1.** Like many of you, I watched the US midterm election results with (mostly…) disappointment and dismay. I think that history will judge us harshly for not totally and unequivocally rebuking everything Trump stands for and every politician associated with him. But that’s not what I wanted to blog about today.

**2.** There was a breakthrough in communication complexity by Arkadev Chattopadhyay, Nikhil Mande, and Suhail Sherif: the first exponential separation between randomized communication complexity and log approximate rank for a total Boolean function *f*. This falsifies the longstanding conjecture that these measures are polynomially related (though it doesn’t resolve the original log rank conjecture). For those of you keeping score at home, the *quantum* communication complexity of *f* is sandwiched in between randomized CC and log approximate rank. So, at least one of the following must now be true: *either* randomized CC is exponentially separated from quantum CC, or else quantum CC is exponentially separated from log approximate rank. My money’s on the latter.

**3.** Ewin Tang, who achieved fame with a quantum-inspired classical algorithm for recommendation systems (which I blogged about in July), is now back with quantum-inspired classical algorithms for principal component analysis and supervised clustering. Well, with the *announcements* of such algorithms; details of the analysis are to come later.

**4.** A bunch of people asked me about the paper by Sergey Bravyi, David Gosset, and Robert Koenig, Quantum advantage with shallow circuits. tl;dr: it’s great! And it was deservedly a highlight of the QIP conference back in January! That’s why it confused me when everyone started asking about it a couple weeks ago. The resolution is that the paper was just recently published in *Science* magazine, which led to popular coverage like this, which in turn led to people asking me whether this result unconditionally proves P≠BQP (that is, quantum computers can solve more problems in polynomial time than classical computers), and if not why not. The answer is no: the paper proves *an* unconditional separation, but one that’s a long long way from P≠BQP, or anything else that would entail solving the central open problems of complexity theory like P vs. PSPACE. Basically, it shows there are problems solvable in *constant* time with a quantum computer that aren’t solvable in *constant* time classically, for suitable meanings of “problem” (namely, a relation problem) and “in constant time” (namely, NC^{0} circuits, in which each output bit depends on only a constant number of input bits). I understand that a stronger separation has since been achieved, between quantum NC^{0} and classical AC^{0}, in work that’s not yet on the arXiv. The problems in question, however, are all easy to solve in P, or even in classical logarithmic time, given a polynomial number of parallel processors.

**5.** A bunch of people also asked me about the paper by Xun Gao and Luming Duan, Efficient classical simulation of noisy quantum computation. This paper tries to formalize something that many of us have suspected/feared for years, namely that *random* quantum circuits (the whole thing is specific to random circuits) can tolerate only a tiny amount of noise and decoherence before they become efficiently simulable classically. If true, this has obvious implications for the sampling-based quantum supremacy experiments that Google and others are planning for the next few years: namely, that all the engineering effort they’ve already been investing anyway to push down the noise rate, will actually be necessary! However, correspondence with the authors revealed that there’s a significant gap in the analysis as it currently stands: namely, the current proof applies only to *closed* quantum systems, which would (for example) rule out all the techniques that people eventually hope to use to achieve quantum fault-tolerance—all of which are based on constantly measuring subsets of the qubits, doing essentially error-free classical computation on the measurement outcomes, throwing away noisy qubits, and pumping in fresh qubits. Xun and Duan say that they’re currently working on an extension to open systems; in my personal view, such an extension seems essential for this interesting result to have the informal interpretation that the authors want.

**6.** My friend Bram Cohen asked me to announce that his company, Chia, has launched a competition for best implementation of its Verifiable Delay Functions (VDFs), with real money rewards. You can find the details at this Github page.

**7.** The second Q2B (“Quantum 2 Business”) conference, organized by QC Ware Corp., will be held this coming December 10-12, at the Computer History Museum in Mountain View. There will be two keynote addresses, one by John Preskill and the other by me. I hope I’ll get a chance to meet some of you there!

**8.** Longtime colleague and friend-of-the-blog Ashwin Nayak asked me to announce that the 2019 Conference on Computational Complexity, to be held July 18-20 in exciting New Brunswick, NJ, is now accepting submissions. I hope to be there!

**9.** OK, what the hell: the 21st annual, and nearly impossible to capitalize correctly, SQuInT (Southwest Quantum Information and Technology) workshop will be held February 2019 in Albuquerque, NM. UT Austin is now a node of the SQuInT network, and I’ll hopefully be attending along with a posse of students and postdocs. The deadline for abstract submission is coming up soon: Monday November 12!

**10.** I went to morning Shabbat services in Austin this past weekend, exactly one week after the tragedy in Pittsburgh. There was massively increased security, with armed guards interrogating us, Israeli-style, about why we had no membership sticker on our car, whether we knew the name of the rabbi, etc. Attendance was maybe a factor of three higher than usual. About thirty priests, ministers, and Christian seminary students, and one Muslim, came up to the bima to say a prayer of solidarity with Jews. The mayor of Austin, Steve Adler, was also on hand to give a speech. Then the rabbi read a letter to the synagogue by Sen. Ted Cruz denouncing antisemitism (well, parts of it; he said the letter was really long). There were murmurs of disapproval from the crowd when Cruz’s name was mentioned, but then everyone quieted down and listened. The thing is, the US and large parts of the world are now so far outside the norms of liberal democracy, in territory so terrifyingly uncharted since the end of World War II, that *shooting up synagogues is bad* is actually something that it’s better than not for powerful people to affirm explicitly. Anyway, while I’m neither a believer nor much of a synagogue-goer, I found the show of unity moving.