These days, I often need to remind myself that, as an undergrad, grad student, postdoc, or professor, I’ve now been doing quantum computing research for a quarter-century—i.e., well over half of the subject’s existence. As a direct result, when I feel completely jaded about a new development in QC, it might actually be exciting. When I feel moderately excited, it might actually be the most exciting thing for years.<\/p>\n\n\n\n
With that in mind:<\/p>\n\n\n\n
(1) Last week National Public Radio’s Marketplace interviewed<\/a> me, John Martinis, and others about the current state of quantum computing. While the piece wasn’t entirely hype-free, I’m pleased to report that my own views were represented accurately! To wit:<\/p>\n\n\n\n \u201cThere is a tsunami of hype about what quantum computers are going to revolutionize,\u201d said Scott Aaronson, a professor of computer science at the University of Texas at Austin. \u201cQuantum computing has turned into a word that venture capitalists or people seeking government funding will sprinkle on anything because it sounds good.\u201d<\/p> Aaronson warned we can\u2019t be certain that these computers will in fact revolutionize machine learning and finance and optimization problems. \u00a0\u201cWe can\u2019t prove that there\u2019s not a quantum algorithm that solves all these problems super fast, but we can\u2019t even prove there\u2019s not an algorithm for a conventional computer that does it,\u201d he said. [In the recorded version, they replaced this by a simpler but also accurate thought: namely, that we can’t prove one way or the other whether there’s a useful quantum advantage for these tasks.]<\/p> <\/span><\/p><\/blockquote>\n\n\n\n (2) I don’t like to use this blog to toot my own research horn, but on Thursday my postdoc Jason Pollack and I released a paper, entitled Discrete Bulk Reconstruction<\/a>. And to be honest, I’m pretty damned excited about it. It represents about 8 months of Jason—a cosmologist and string theorist who studied under Sean Carroll—helping me understand AdS\/CFT<\/a> in the language of the undergraduate CS curriculum, like min-cuts on undirected graphs, so that we could then look for polynomial-time algorithms to implement the holographic mapping from boundary quantum states to the spatial geometry in the bulk. We drew heavily on previous work in the same direction, especially the already-seminal 2015 holographic entropy cone<\/a> paper by Ning Bao et al. But I’d like to think that, among other things, our work represents a new frontier in just how accessible AdS\/CFT itself can be made to CS and discrete math types. Anyway, here’s the abstract if you’re interested:<\/p>\n\n\n\n According to the AdS\/CFT correspondence<\/i>, the geometries of certain spacetimes are fully determined by quantum states that live on their boundaries — indeed, by the von Neumann entropies of portions of those boundary states. This work investigates to what extent the geometries can be reconstructed from the entropies in polynomial time<\/i>. Bouland, Fefferman, and Vazirani (2019) argued that the AdS\/CFT map can be exponentially complex if one wants to reconstruct regions such as the interiors of black holes. Our main result provides a sort of converse: we show that, in the special case of a single 1D boundary, if the input data consists of a list of entropies of contiguous<\/i> boundary regions, and if the entropies satisfy a single inequality called Strong Subadditivity, then we can construct a graph model for the bulk in linear time. Moreover, the bulk graph is planar, it has O(N2<\/sup>) vertices (the information-theoretic minimum), and it’s “universal,” with only the edge weights depending on the specific entropies in question. From a combinatorial perspective, our problem boils down to an “inverse” of the famous min-cut problem: rather than being given a graph and asked to find a min-cut, here we’re given the values of min-cuts separating various sets of vertices, and need to find a weighted undirected graph consistent with those values. Our solution to this problem relies on the notion of a “bulkless” graph, which might be of independent interest for AdS\/CFT. We also make initial progress on the case of multiple 1D boundaries — where the boundaries could be connected via wormholes — including an upper bound of O(N4<\/sup>) vertices whenever a planar bulk graph exists (thus putting the problem into the complexity class NP).<\/p><\/blockquote>\n\n\n\n (3) Anand Natarajan and Chinmay Nirkhe posted a preprint entitled A classical oracle separation between QMA and QCMA<\/a>, which makes progress on a problem that’s been raised on this blog all the way back to its inception. A bit of context: QMA<\/a>, Quantum Merlin-Arthur, captures what can be proven using a quantum state with poly(n) qubits as the proof, and a polynomial-time quantum algorithm as the verifier. QCMA, or Quantum Classical Merlin-Arthur, is the same as QMA except that now the proof has to be classical. A fundamental problem of quantum complexity theory, first raised by Aharonov and Naveh<\/a> in 2002, is whether QMA=QCMA. In 2007, Greg Kuperberg and I<\/a> introduced the concept of quantum oracle separation—that is, a unitary that can be applied in a black-box manner—in order to show that there’s a quantum oracle relative to which QCMA\u2260QMA. In 2015, Fefferman and Kimmel<\/a> improved this, to show that there’s a “randomized in-place” oracle relative to which QCMA\u2260QMA. Natarajan and Nirkhe now remove the “in-place” part, meaning the only thing still “wrong” with their oracle is that it’s randomized. Derandomizing their construction would finally settle this 20-year-old open problem (except, of course, for the minor detail of whether QMA=QCMA in the “real,” unrelativized world!).<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n
\n\n\n\n