Connect with us


Interaction + Entanglement = Efficient Proofs of Halting



A couple weeks ago my co-authors Zhengfeng Ji (UTS Sydney), Heny Yuen (University of Toronto) and Anand Natarajan and John Wright (both at Caltech’s IQIM, with John soon moving to UT Austin) & I posted a manuscript on the arXiv preprint server entitled


The magic of the single-letter formula quickly made its effect, and our posting received some attention on the blogosphere (see links below). Within computer science, complexity theory is at an advantage in its ability to capture powerful statements in few letters: who has not head of P, NP, and, for readers of this blog, BQP and QMA? (In contrast, I am under no illusion that my vague attempt at a more descriptive title has, by the time you reach this line, all but vanished from the reader’s memory.)

Even accounting for this popularity however, it is a safe bet that fewer of our readers have heard of MIP* or RE. Yet we are promised that the above-stated equality has great consequences for physics (“Tsirelson’s problem” in the study of nonlocality) and mathematics (“Connes’ embedding problem” in the theory of von Neumann algebras). How so — how can complexity-theoretic alphabet soup have any consequence for, on the one hand, physical reality, and on the other, abstract mathematics?

The goal of this post and the next one is to help the interested reader grasp the significance of interactive proofs (that lie between the symbols MIP*) and undecidability (that lies behind RE) for quantum mechanics.

The bulk of the present post is an almost identical copy of a post I wrote for my personal blog. To avoid accusations of self-plagiarism, I will substantiate it with a little picture and a story, see below. The post gives a very personal take on the research that led to the aforementioned result. In the next post, my co-author Henry Yuen has offered to give a more scientific introduction to the result and its significance.

Before proceeding, it is important to make it clear that the research described in this post and the next has not been refereed or thoroughly vetted by the community. This process will take place over the coming months, and we should wait until it is completed before placing too much weight on the results. As an author, I am proud of my work; yet I am aware that there is due process to be made before the claims can be officialised. As such, these posts only represent my opinion (and Henry’s) and not necessarily that of the wider scientific community.

For more popular introductions to our result, see the blog posts of Scott Aaronson, Dick Lipton, and Gil Kalai and reporting by Davide Castelvecchi for Nature and Emily Conover for Science.

Now for the personal post…and the promised picture. IMG_8074Isn’t it beautiful? The design is courtesy of Tony Metger and Alexandru Gheorghiu, the first a visiting student and the second a postdoctoral scholar at Caltech’s IQIM. While Tony and Andru came up with the idea, the execution is courtesy of the bakery store employee, who graciously implemented the custom design (apparently writing equations on top of cakes is not  common enough to be part of the standard offerings, so they had to go for the custom option). Although it is unclear if the executioner grasped the full depth of the signs they were copying, note how perfect the execution: not a single letter is out of place! Thanks to Tony, Andru, and the anonymous chef for the tasty souvenir.

Now for the story. In an earlier post on my personal research blog, I had reported on the beautiful recent result by Natarajan and Wright showing the astounding power of multi-prover interactive proofs with quantum provers sharing entanglement: in letters, text{NEEXP} subseteq text{MIP}^star. In the remainder of this post I will describe our follow-up work with Ji, Natarajan, Wright, and Yuen. In this post I will tell the story from a personal point of view, with all the caveats that this implies: the “hard science” will be limited (but there could be a hint as to how “science”, to use a big word, “progresses”, to use an ill-defined one; see also the upcoming post by Henry Yuen for more), the story is far too long, and it might be mostly of interest to me only. It’s a one-sided story, but that has to be. (In particular below I may at times attribute credit in the form “X had this idea”. This is my recollection only, and it is likely to be inaccurate. Certainly I am ignoring a lot of important threads.) I wrote this because I enjoyed recollecting some of the best moments in the story just as much as some the hardest; it is fun to look back and find meanings in ideas that initially appeared disconnected. Think of it as an example of how different lines of work can come together in unexpected ways; a case for open-ended research. It’s also an antidote against despair that I am preparing for myself: whenever I feel I’ve been stuck on a project for far too long, I’ll come back to this post and ask myself if it’s been 14 years yet — if not, then press on.

It likely comes as a surprise to me only that I am no longer fresh out of the cradle. My academic life started in earnest some 14 years ago, when in the Spring of 2006 I completed my Masters thesis in Computer Science under the supervision of Julia Kempe, at Orsay in France. I had met Julia the previous term: her class on quantum computing was, by far, the best-taught and most exciting course in the Masters program I was attending, and she had gotten me instantly hooked. Julia agreed to supervise my thesis, and suggested that I look into some interesting recent result by Stephanie Wehner that linked the study of entanglement and nonlocality in quantum mechanics to complexity-theoretic questions about interactive proof systems (specifically, this was Stephanie’s paper showing that text{XOR-MIP}^star subseteq text{QIP}(2)).

At the time the topic was very new. It had been initiated the previous year with a beautiful paper by Cleve et al. (that I have recommended to many a student since!) It was a perfect fit for me: the mathematical aspects of complexity theory and quantum computing connected to my undergraduate background, while the relative concreteness of quantum mechanics (it is a physical theory after all) spoke to my desire for real-world connection (not “impact” or even “application” — just “connection”). Once I got myself up to speed in the area (which consisted of three papers: the two I already mentioned, together with a paper by Kobayashi and Matsumoto where they studied interactive proofs with quantum messages), Julia suggested looking into the “entangled-prover” class text{MIP}^star introduced in the aforementioned paper by Cleve et al. Nothing was known about this class! Nothing besides the trivial inclusion of single-prover interactive proofs, IP, and the containment in…ALL, the trivial class that contains all languages.

Yet the characterization MIP=NEXP of its classical counterpart by Babai et al. in the 1990s had led to one of the most productive lines of work in complexity of the past few decades, through the PCP theorem and its use from hardness of approximation to efficient cryptographic schemes. Surely, studying text{MIP}^star had to be a productive direction? In spite of its well-established connection to classical complexity theory, via the formalism of interactive proofs, this was a real gamble. The study of entanglement from the complexity-theoretic perspective was entirely new, and bound to be fraught with difficulty; very few results were available and the existing lines of works, from the foundations of non-locality to more recent endeavors in device-independent cryptography, provided little other starting point than strong evidence that even the simplest examples came with many unanswered questions. But my mentor was fearless, and far from a novice in terms of defraying new areas, having done pioneering work in areas ranging from quantum random walks to Hamiltonian complexity through adiabatic computation. Surely this would lead to something?

It certainly did. More sleepless nights than papers, clearly, but then the opposite would only indicate dullness. Julia’s question led to far more unexpected consequences than I, or I believe she, could have imagined at the time. I am writing this post to celebrate, in a personal way, the latest step in 15 years of research by dozens of researchers: today my co-authors and I uploaded to the quant-ph arXiv what we consider a complete characterization of the power of entangled-prover interactive proof systems by proving the equality text{MIP}^star = text{RE}, the class of all recursively enumerable languages (a complete problem for RE is the halting problem). Without going too much into the result itself (if you’re interested, look for an upcoming post here that goes into the proof a bit more), and since this is a more personal post, I will continue on with some personal thoughts about the path that got us there.

When Julia & I started working on the question, our main source of inspiration were the results by Cleve et al. showing that the non-local correlations of entanglement had interesting consequences when seen through the lens of interactive proof systems in complexity theory. Since the EPR paper, a lot of work in understanding entanglement had already been accomplished in the Physics community, most notably by Mermin, Peres, Bell, and more recently the works in device-independent quantum cryptography by Acin, Pironio, Scarani and many others, stimulated by Ekert’s proposal for quantum key distribution and Mayers and Yao’s idea for “device-independent cryptography”. By then we certainly knew that “spooky action-at-a-distance” did not entail any faster-than-light communication, and indeed was not really “action-at-a-distance” in the first place but merely “correlation-at-a-distance”. What Cleve et al. recognized is that these “spooky correlations-at-a-distance” were sufficiently special so as to not only give numerically different values in “Bell inequalities”, the tool invented by Bell to evidence non-locality in quantum mechanics, but also have some potentially profound consequences in complexity theory.

In particular, examples such as the “Magic Square game” demonstrated that enough correlation could be gained from entanglement so as to defeat basic proof systems whose soundness relied only on the absence of communication between the provers, an assumption that until then had been wrongly equated with the assumption that any computation performed by the provers could be modeled entirely locally. I think that the fallacy of this implicit assumption came as a surprise to complexity theorists, who may still not have entirely internalized it. Yet the perfect quantum strategy for the Magic Square game provides a very concrete “counter-example” to the soundness of the “clause-vs-variable” game for 3SAT. Indeed this game, a reformulation by Aravind and Cleve-Mermin of a Bell Inequality discovered by Mermin and Peres in 1990, can be easily re-framed as a 3SAT system of equations that is not satisfiable, and yet is such that the associated two-player clause-vs-variable game has a perfect quantum strategy. It is this observation, made in the paper by Cleve et al., that gave the first strong hint that the use of entanglement in interactive proof systems could make many classical results in the area go awry.

By importing the study of non-locality into complexity theory Cleve et al. immediately brought it into the realm of asymptotic analysis. Complexity theorists don’t study fixed objects, they study families of objects that tend to have a uniform underlying structure and whose interesting properties manifest themselves “in the limit”. As a result of this new perspective focus shifted from the study of single games or correlations to infinite families thereof. Some of the early successes of this translation include the “unbounded violations” that arose from translating asymptotic separations in communication complexity to the language of Bell inequalities and correlations (e.g. this paper). These early successes attracted the attention of some physicists working in foundations as well as some mathematical physicists, leading to a productive exploration that combined tools from quantum information, functional analysis and complexity theory.

The initial observations made by Cleve et al. had pointed to text{MIP}^star as a possibly interesting complexity class to study. Rather amazingly, nothing was known about it! They had shown that under strong restrictions on the verifier’s predicate (it should be an XOR of two answer bits), a collapse took place: by the work of Hastad, XOR-MIP equals NEXP, but text{MIP}^star is included in EXP. This seemed very fortuitous (the inclusion is proved via a connection with semidefinite programming that seems tied to the structure of XOR-MIP protocols): could entanglement induce a collapse of the entire, unrestricted class? We thought (at this point mostly Julia thought, because I had no clue) that this ought not to be the case, and so we set ourselves to show that the equality text{MIP}^star=text{NEXP}, that would directly parallel Babai et al.’s characterization MIP=NEXP, holds. We tried to show this by introducing techniques to “immunize” games against entanglement: modify an interactive proof system so that its structure makes it “resistant” to the kind of “nonlocal powers” that can be used to defeat the clause-vs-variable game (witness the Magic Square). This was partially successful, and led to one of the papers I am most proud of — I am proud of it because I think it introduced elementary techniques (such as the use of the Cauchy-Schwarz inequality — inside joke — more seriously, basic things such as “prover-switching”, “commutation tests”, etc.) that are now routine manipulations in the area. The paper was a hard sell! It’s good to remember the first rejections we received. They were not unjustified: the main point of criticism was that we were only able to establish a hardness result for exponentially small completeness-soundness gap. A result for such a small gap in the classical setting follows directly from a very elementary analysis based on the Cook-Levin theorem. So then why did we have to write so many pages (and so many applications of Cauchy-Schwarz!) to arrive at basically the same result (with a ^star)?

Eventually we got lucky and the paper was accepted to a conference. But the real problem, of establishing any non-trivial lower bound on the class text{MIP}^star with constant (or, in the absence of any parallel repetition theorem, inverse-polynomial) completeness-soundness gap, remained. By that time I had transitioned from a Masters student in France to a graduate student in Berkeley, and the problem (pre-)occupied me during some of the most difficult years of my Ph.D. I fully remember spending my first year entirely thinking about this (oh and sure, that systems class I had to pass to satisfy the Berkeley requirements), and then my second year — yet, getting nowhere. (I checked the arXiv to make sure I’m not making this up: two full years, no posts.) I am forever grateful to my fellow student Anindya De for having taken me out of the cycle of torture by knocking on my door with one of the most interesting questions I have studied, that led me into quantum cryptography and quickly resulted in an enjoyable paper. It was good to feel productive again! (Though the paper had fun reactions as well: after putting it on the arXiv we quickly heard from experts in the area that we had solved an irrelevant problem, and that we better learn about information theory — which we did, eventually leading to another paper, etc.) The project had distracted me and I set interactive proofs aside; clearly, I was stuck.

About a year later I visited IQC in Waterloo. I don’t remember in what context the visit took place. What I do remember is a meeting in the office of Tsuyoshi Ito, at the time a postdoctoral scholar at IQC. Tsuyoshi asked me to explain our result with Julia. He then asked a very pointed question: the bedrock for the classical analysis of interactive proof systems is the “linearity test” of Blum-Luby-Rubinfeld (BLR). Is there any sense in which we could devise a quantum version of that test?

What a question! This was great. At first it seemed fruitless: in what sense could one argue that quantum provers apply a “linear function”? Sure, quantum mechanics is linear, but that is besides the point. The linearity is a property of the prover’s answers as a function of their question. So what to make of the quantum state, the inherent randomness, etc.?

It took us a few months to figure it out. Once we got there however, the answer was relatively simple — the prover should be making a question-independent measurement that returns a linear function that it applies to its question in order to obtain the answer returned to the verifier — and it opened the path to our subsequent paper showing that the inclusion of NEXP in text{MIP}^star indeed holds. Tsuyoshi’s question about linearity testing had allowed us to make the connection with PCP techniques; from there to MIP=NEXP there was only one step to make, which is to analyze multi-linearity testing. That step was suggested by my Ph.D. advisor, Umesh Vazirani, who was well aware of the many pathways towards the classical PCP theorem, since the theorem had been obtained in great part by his former student Sanjeev Arora. It took a lot of technical work, yet conceptually a single question from my co-author had sufficed to take me out of a 3-year slumber.

This was in 2012, and I thought we were done. For some reason the converse inclusion, of text{MIP}^star in NEXP, seemed to resist our efforts, but surely it couldn’t resist much longer. Navascues et al. had introduced a hierarchy of semidefinite programs that seemed to give the right answer (technically they could only show convergence to a relaxation, the commuting value, but that seemed like a technicality; in particular, the values coincide when restricted to finite-dimensional strategies, which is all we computer scientists cared about). There were no convergence bounds on the hierarchy, yet at the same time commutative SDP hierarchies were being used to obtain very strong results in combinatorial optimization, and it seemed like it would only be a matter of time before someone came up with an analysis of the quantum case. (I had been trying to solve a related “dimension reduction problem” with Oded Regev for years, and we were making no progress; yet it seemed someone ought to!)

In Spring 2014 during an open questions session at a workshop at the Simons Institute in Berkeley Dorit Aharonov suggested that I ask the question of the possible inclusion of QMA-EXP, the exponential-sized-proofs analogue of QMA, in text{MIP}^star. A stronger result than the inclusion of NEXP (under assumptions), wouldn’t it be a more natural “fully quantum” analogue of MIP=NEXP? Dorit’s suggestion was motivated by research on the “quantum PCP theorem”, that aims to establish similar hardness results in the realm of the local Hamiltonian problem; see e.g. this post for the connection. I had no idea how to approach the question — I also didn’t really believe the answer could be positive — but what can you do, if Dorit asks you something… So I reluctantly went to the board and asked the question. Joe Fitzsimons was in the audience, and he immediately picked it up! Joe had the fantastic ideas of using quantum error-correction, or more specifically secret-sharing, to distribute a quantum proof among the provers. His enthusiasm overcame my skepticism, and we eventually showed the desired inclusion. Maybe text{MIP}^star was bigger than text{NEXP} after all.

Our result, however, had a similar deficiency as the one with Julia, in that the completeness-soundness gap was exponentially small. Obtaining a result with a constant gap took 3 years of couple more years of work and the fantastic energy and insights of a Ph.D. student at MIT, Anand Natarajan. Anand is the first person I know of to have had the courage to dive into the most technical aspects of the analysis of the aforementioned results, while also bringing in the insights of a “true quantum information theorist” that were supported by Anand’s background in Physics and upbringing in the group of Aram Harrow at MIT. (In contrast I think of myself more as a “raw” mathematician; I don’t really understand quantum states other than as positive-semidefinite matrices…not that I understand math either of course; I suppose I’m some kind of a half-baked mish-mash.) Anand had many ideas but one of the most beautiful ones led to what he poetically called the “Pauli braiding test”, a “truly quantum” analogue of the BLR linearity test that amounts to doing two linearity tests in conjugate bases and piecing the results together into a robust test for {n}-qubit entanglement (I wrote about our work on this here).

At approximately the same time, Zhengfeng Ji had another wonderful idea that was in some sense orthogonal to our work. (My interpretation of) Zhengfeng’s idea is that one can see an interactive proof system as a computation (verifier-prover-verifier) and use Kitaev’s circuit-to-Hamiltonian construction to transform the entire computation into a “quantum CSP” (in the same sense that the local Hamiltonian problem is a quantum analogue of classical constraint satisfaction problems (CSP)) that could then itself be verified by a quantum multi-prover interactive proof system…with exponential gains in efficiency! Zhengfeng’s result implied an exponential improvement in complexity compared to the result by Julia and myself, showing inclusion of NEEXP, instead of NEXP, in text{MIP}^star. However, Zhengfeng’s technique suffered from the same exponentially small completeness-soundness gap as we had, so that the best lower bound on text{MIP}^star per se remained NEXP.

Both works led to follow-ups. With Natarajan we promoted the Pauli braiding test into a “quantum low-degree test” that allowed us to show the inclusion of QMA-EXP into text{MIP}^star, with constant gap, thereby finally answering the question posed by Aharonov 4 years after it was asked. (I should also say that by then all results on text{MIP}^star started relying on a sequence of parallel repetition results shown by Bavarian, Yuen, and others; I am skipping this part.) In parallel, with Ji, Fitzsimons, and Yuen we showed that Ji’s compression technique could be “iterated” an arbitrary number of times. In fact, by going back to “first principles” and representing verifiers uniformly as Turing machines we realized that the compression technique could be used iteratively to (up to small caveats) give a new proof of the fact (first shown by Slofstra using an embedding theorem for finitely presented group) that the zero-gap version of text{MIP}^star contains the halting problem. In particular, the entangled value is uncomputable! This was not the first time that uncomputability crops in to a natural problem in quantum computing (e.g. the spectral gap paper), yet it still surprises when it shows up. Uncomputable! How can anything be uncomputable!

As we were wrapping up our paper Henry Yuen realized that our “iterated compression of interactive proof systems” was likely optimal, in the following sense. Even a mild improvement of the technique, in the form of a slower closing of the completeness-soundness gap through compression, would yield a much stronger result: undecidability of the constant-gap class text{MIP}^star. It was already known by work of Navascues et al., Fritz, and others, that such a result would have, if not surprising, certainly consequences that seemed like they would be taking us out of our depth. In particular, undecidability of any language in text{MIP}^star would imply a negative resolution to a series of equivalent conjectures in functional analysis, from Tsirelson’s problem to Connes’ Embedding Conjecture through Kirchberg’s QWEP conjecture. While we liked our result, I don’t think that we believed it could resolve any conjecture(s) in functional analysis.

So we moved on. At least I moved on, I did some cryptography for a change. But Anand Natarajan and his co-author John Wright did not stop there. They had the last major insight in this story, which underlies their recent STOC best paper described in the previous post. Briefly, they were able to combine the two lines of work, by Natarajan & myself on low-degree testing and by Ji et al. on compression, to obtain a compression that is specially tailored to the existing text{MIP}^star protocol for NEXP and compresses that protocol without reducing its completeness-soundness gap. This then let them show Ji’s result that text{MIP}^star contains NEEXP, but this time with constant gap! The result received well-deserved attention. In particular, it is the first in this line of works to not suffer from any caveats (such as a closing gap, or randomized reductions, or some kind of “unfair” tweak on the model that one could attribute the gain in power to), and it implies an unconditional separation between MIP and text{MIP}^star.

As they were putting the last touches on their result, suddenly something happened, which is that a path towards a much bigger result opened up. What Natarajan & Wright had achieved is a one-step gapless compression. In our iterated compression paper we had observed that iterated gapless compression would lead to text{MIP}^star=text{RE}, implying negative answers to the aforementioned conjectures. So then?

I suppose it took some more work, but in some way all the ideas had been laid out in the previous 15 years of work in the complexity of quantum interactive proof systems; we just had to put it together. And so a decade after the characterization QIP = PSPACE of single-prover quantum interactive proof systems, we have arrived at a characterization of quantum multiprover interactive proof systems, text{MIP}^star = text{RE}. With one author in common between the two papers: congratulations Zhengfeng!

Even though we just posted a paper, in a sense there is much more left to do. I am hopeful that our complexity-theoretic result will attract enough interest from the mathematicians’ community, and especially operator algebraists, for whom CEP is a central problem, that some of them will be willing to devote time to understanding the result. I also recognize that much effort is needed on our own side to make it accessible in the first place! I don’t doubt that eventually complexity theory will not be needed to obtain the purely mathematical consequences; yet I am hopeful that some of the ideas may eventually find their way into the construction of interesting mathematical objects (such as, who knows, a non-hyperlinear group).

That was a good Masters project…thanks Julia!



How a Space Engineer Made Her Own Rotary Cell Phone



Justine Haupt never expected that a project she’d been working on for the past three years would suddenly cause her website to crash. But when Haupt published photos and schematics for her handheld rotary cell phone yesterday, that’s exactly what happened.

Haupt, who works as an astronomy instrumentation engineer at Brookhaven National Laboratory in New York, detailed how she took the rotary mechanism from an old Trimline telephone, paired it with a microcontroller and an Adafruit Fona 3G cell transceiver, put it all into a 3D-printed casing, and built something that could replace her daily flip phone.

Correct: A flip phone. Haupt is firmly anti-smartphone, she told WIRED in an interview, and for a long time she’s used an LG flip phone for her basic mobile needs. But even that felt like too much, so Haupt’s goal with the rotary cell was two-pronged: She wanted to strip a mobile phone down to its absolute essentials, while giving her an even more legitimate excuse for not text messaging her friends. “The point isn't to be anachronistic,” Haupt wrote on her website. “It's to show that it's possible to have a perfectly usable phone that goes as far from having a touchscreen as I can imagine, and which in some ways may actually be more functional.”

In our interview, which has been edited for clarity and length, Haupt talks about tech products as novelties, the similarities between cellphone trends and ChapStick, and why she’s excited about our tech’s rapid release cycles, despite some obvious downsides to it.

Lauren Goode: Let’s talk about your background first. Can you tell me a little bit more about what you do at Brookhaven?

Justine Haupt: I’ve worked on mostly instrumentation development for cosmology and astronomy projects. For example, I've been working on a large ground-based survey telescope for dark energy and dark matter for the past 10 years; that's winding down. I’m working on a radio telescope now and and some other projects, including a possible NASA mission and a quantum information experiment, which is not astronomy-related but it's interesting so I've been getting more involved with that. So it’s, you know, basically building experimental hardware for those kinds of things.

LG: How much of your free time do you spend on your own experimental hardware?

The custom board Haupt created for her phone.

Illustration: Justine Haupt 

JH: It’s pretty hard actually, though I do make time for it. I'm also trying to start a company, so I reduced my time at Brookhaven to 80 percent so that I’d have an extra day a week to work on that. I'm pretty strict with myself about not taking too much work home with me.

LG: What kind of company are you trying to start?

JH: You know, it’s a shame because I was so surprised when this [rotary phone] went viral, I didn’t intend to do anything that would make that happen, I just put the thing up on my own website which I didn’t think anybody ever read, and then this happened. I would have made sure the website for my new company was up. My first product is basically a kind of two-channel brushless motor controller for domestic robots. And my next project will hopefully be an actual full-size domestic robot because robots are, you know—they’re awesome.

LG: You talk a little bit about this on your website, but why did you decide to make this rotary phone? What problem were you looking to solve?

JH: It’s funny, I usually love [having] problems to solve … But this wasn’t intended to be a product or an invention or anything like that. I just thought for a long time that rotary dials are so cool, they don’t have a use in modern society, and I’d love to make myself some device that uses it for data entry. And then I thought, Well, it might as well be a phone. And if I'm gonna do this, it should be something that I could really use. It wouldn't just be a novelty. It would be something I could actually fit in my pocket, that I'd want to use as my primary cell phone.

That would probably be a tough sell for most people who live with their smartphones. But I'm anti-smartphone, despite working in technology development. All of my friends know that I have a flip phone, or have had a flip phone until now, and that I don't text. I don't. I just don't like being that connected. I don't want to have to respond to people at any point of the day. So this is kind of a way of downgrading my flip phone even more. And then if people say, "You don't text? Why don't you text?" I could just hold up the phone and say, this is why!


And also, you know, smartphones are one thing—you have this finicky annoying touchscreen interface, it drives me crazy, it really does. But then even my flip phone does things that I don’t ask it to do, unexpectedly, because some weird button got pushed. I wanted physical keys or buttons I could push for every function and not having to guess whether or not it was actually going to do what I told it to do. You know, when you hold down the power button–is it turning on right now? Is it turning off? I have a switch. It’s a toggle switch, it’s either on or it’s off. That’s it. I just wanted to control the technology. I think people have gone too far acquiescing to the standards of dealing with smartphones.

LG: What kind of flip phone have you been using?

JH: Oh, OK … Do I have it with me? This is so new, it’s only my third day of using my rotary phone over my primary phone, but I’ve been keeping my flip phone in my pocketbook. It is an LG branded flip phone, it’s on a T-Mobile pay-as-you-go-plan, but I don’t even know the model number.

LG: It sounds like what you’re describing is a kind of yearning for a tactile experience.

JH: Exactly. There’s something to be said for tactile interface, actual switches and buttons. Even simple things, like, a little FM radio that has a dial so you can listen to stations, even that’s been replaced by electronic keys that only let you increment left and right. I guess it’s fine, but it does come with its tradeoffs, and no one seems to care and I care.

LG: What would you say was the biggest challenge in building this? You were not only working with the rotary dial but also the 3D-printed enclosure and the micro controller and the cell transceiver and—was it a Raspberry Pi?

JH: Actually it was an Arduino custom board. First, I’ll say that this has been a back-burner project for a long time. I first had the idea years ago. Now if you Google rotary cell phones, a few other people have done it, but none I don’t think could be used as your primary phone. Adafruit has some stuff that makes this easier—for example, a cell phone radio development board, which I started with. I got it working in a very basic way on my workbench, without it being enclosed in the cell phone casing, and proved it wasn’t too crazy.

Testing the circuits on breadboards.

Photograph: Justine Haupt 


But the hardest part was moving from that, which was minimally usable, to something that was truly compact and light enough and sleek enough so I could slip it into my pocket and really use it. And know that it would be reliable and have long enough battery life. That took awhile, I think about three years, and only in the past couple months did I pick it up again. It’s still a work in progress.

LG: What’s interesting is that you still have an e-paper display [on the phone] so that you can see messages and missed calls. Which is funny because, when you think about it, with the old rotary phones, you couldn’t see any of that. It just rang and rang, and if you missed it, you missed it.

JH: Right. The main point I think is that I didn’t do it just to be a throwback novelty thing, to reproduce a rotary phone for the modern era. I wanted it to be a usable, functional phone, and you can’t really do that without having some kind of display now, especially because of robocalls. You know, you want to be sure it’s a number you’re really interested in before you pick it up.

LG: It seems like an important point to make, because there is a lot of nostalgic tech out now. Motorola’s just resurrected the Razr. Of course, it has this new flexible polymer display, but it’s a clamshell phone that flips open and closed. Nintendo has resurrected the original NES in a new form. There was even an app for iPhone recently that mimicked the click wheel experience on an old iPod. What do you think all of this says about the way we’re looking back to tech from 10, 20, 30 years ago, right as we’re being inundated with new tech?

JH: I was just thinking about this the other day. You’re right about this resurgence of older-feeling technology. Even cameras, you know, mirrorless single-lens cameras are being stylized in this '70s and '80s film SLR style of camera, more bulky and boxy with more buttons. And in some ways it’s perceived as a kind of hipster mentality. I do like it, even though I don’t identify as a hipster. And then things like the Motorola Razr, which I just found out about today … I think the point of these throwbacks is that novelty wins. People love novelty so much that they’re willing to overlook functionality.

Take, for example, a really simple thing: ChapStick. It’s been around forever. My parents used it. It’s not a technological thing. And then all of a sudden these egg-shaped ones appear, and everybody starts using them. If you think about it, an egg-shaped applicator is a lot less precise and annoying to use than the little pencil one. But gosh darn it, it looks like an egg, it’s colorful, people want it! And it wins. Given enough time, people circle around again and then the older stick-shaped ones become the novelty and then you go back to that. But none of it is really based in logic or how usable the thing is. It’s just trends. And you certainly see that with phones. I mean, maybe people are finally ready to explore a form factor for phones other than what Apple invented with the iPhone. And maybe with other things too. I don’t know if we ever stabilize, or if we keep oscillating between different styles.

LG: What do you think about the fact that production cycles for some of these new products are compressed, and not only that, but purchasing cycles are compressed? When I think back to the rotary phone, the family PC, the VCR … people had those for years.


JH: I’m sorry that we always have this bias that your childhood, your nostalgia, is the deepest one. But also, being in technology and developing technology, I wonder how it might affect one’s ability to understand technology. When I grew up, I could easily take things apart. They were hard to understand, but at least there was something to take apart and you could see mechanisms and understand that there was circuitry inside. And now technology is increasingly like magic, so you really can’t disassemble things. So I do wonder how the next generation of engineers, how they’ll bridge the gap between being interested in something and being able to actualize it.

On the other hand, I’m so excited that release timelines are so compressed and how fast the future is coming. Just in the past ten years I’m seeing things I never thought I’d see and I’m recalibrating myself to expect even greater things. For example, things like gene editing and what biohackers are doing. And space exploration, which is a passion of mine. And all of that. So on the other hand I’m just so excited. I think we live in an amazing time.

Read more:

Continue Reading


Trump Proposes a Cut in Research Spending, but a Boost for AI



President Trump Monday proposed cutting federal research spending—except in key areas including artificial intelligence and quantum technologies.

Trump’s budget for the fiscal year beginning October 1 proposes spending $142.2 billion in research and development, 9 percent less than in the current year. The White House says its proposal is 6 percent more than it requested last year.

The budget request is something of a gambler’s approach to funding American innovation, betting big in select areas. “I find it disappointing and concerning that funding for basic research is down,” says Martijn Rasser, a senior fellow at the Center for a New American Security, a policy think tank in Washington, DC. “We just don’t know where the next breakthroughs will come from.”

The budget goes all-in on AI and quantum, proposing to double funding across the departments including the National Science Foundation, the National Institutes of Health, the Department of Energy, Darpa, and the DoD’s Joint AI Center.

At the same time, the president proposed cutting research spending in nearly every arm of the government, including by $424 million at the National Science Foundation, $4.7 billion at the Defense Department, and $3.2 billion at the Department of Energy.

Rasser says it’s good to see proposed funding for AI and quantum increase, since both are critical emerging areas. He recently coauthored a report that called for substantially more government funding for AI, noting that the technology could transform industries in the way that software has.

But Rasser worries that cutting overall funding for fundamental research will undermine progress and growth because innovations can emerge from many fields. “It’s just not a good trajectory,” he says.

Keep Reading
The latest on artificial intelligence, from machine learning to computer vision and more

The president’s budget is a proposal and is likely to be altered by Congress. But the plan signals an approach to scientific research that prioritizes areas that are seen as crucial to international competition and military advantage. AI and quantum technologies have received substantial investment from America’s big geopolitical rival, China, and both are being rushed into military service by Beijing.

AI has emerged as a powerful technology, with big tech companies investing billions into its development and harnessing it to build everything from self-driving cars to voice assistants.

Quantum computing and communications technologies, built on the peculiar properties of quantum physics, are far less proven, though they have the potential to deliver equally big payoffs someday. A quantum version of the internet, for instance, should guarantee perfect security, while quantum computers could crack now-unsolvable problems with relative ease.

During Trump’s time in office, AI and quantum technologies have become increasing areas of focus. The president launched the American AI Initiative in February 2019, outlining a national strategy for AI leadership. And Trump signed the National Quantum Initiative Act into law in December 2018, increasing funding for quantum computing and communications.

Today, AI researchers find themselves in hot demand and, increasingly, able to secure ready government funding. But some are wary of the White House plan.

“It looks like a mixed blessing,” says Subbarao Kambhampati, an AI professor at Arizona State University and a past president of the Association for the Advancement of Artificial Intelligence.

Kambhampati notes that the funding allocated for AI seems geared towards driving fundamental work in AI, which will help push new advances in the field. “I am happy to see funding for basic research,” he says.

But he warns that cutting funding for other areas of research may not only undermine progress in other fields but also have a knock-on effect on AI, because progress has often drawn from other areas. Studies of animal brains can inspire new designs for artificial neural networks, for example. “Neuroscience will be really relevant to AI in over the longer term,” he says.

Kelvin Droegemeier, director of the White House Office of Science and Technology Policy, defended the proposed drop in research funding in a call with reporters. “President Trump has made very clear that investing in early stage basic research is extremely important and this budget does that,” Droegemeier said. “I think it's a very responsible act on President Trump's part to make sure that we prioritize what are high importance activities are especially relative to great power competition.”


Dario Gil, director of IBM research and a member of the President’s Council of Advisors on Science and Technology, argues that government investment in AI will boost scientific discovery in general, thereby helping advance research in other areas. “The purpose is to accelerate discovery,” he says. “That is going to permeate every sector of the economy and national defense.”

Gil also suggests that, like the internet before it, quantum computers and communications networks may have unforeseen payoffs. “We need to see a significant acceleration of the investments, and this is a very good step in the direction,” he says.

He might be right, but it’s tricky to pick the winners in research and innovation. As Rasser says, “With basic research, you never know what’s going to pan out.”

Read more:

Continue Reading


Quantum SDP-Solvers: Better upper and lower bounds



Joran van Apeldoorn1,2, András Gilyén1,2, Sander Gribling1,2, and Ronald de Wolf1,2,3

1QuSoft, Amsterdam, the Netherlands.
2University of Amsterdam, the Netherlands.
3University of Amsterdam, the Netherlands.

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Brandão and Svore [14] recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.

We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $mapprox n$, which is the same as classical.

Semidefinite programs (SDPs) are an important tool in convex optimization tasks and approximation algorithms. They allow to optimize a linear function over positive semidefinite matrices, subject to linear constraints on those matrices, and they are solvable in polynomial time on a classical computer. Brand~ao and Svore recently gave a quantum algorithm for solving semidefinite programs that (in some regimes) is faster than the best-possible classical algorithm. In this paper we improve on their algorithm in several ways, in particular we obtain a 4-th root improvement in the running time with respect to the required precision. We also show strong limits for this particular approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry, and we prove some general limitations for quantum SDP-solvers.

► BibTeX data

► References

[1] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. toc, 8(6):121–164, 2012.

[2] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. jacm, 63(2):12:1–12:35, 2016. Earlier version in STOC’07.

[3] Andris Ambainis. Quantum walk algorithm for element distinctness. siamjc, 37(1):210–239, 2007. Earlier version in FOCS’04. arXiv: quant-ph/​0311001?.

[4] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In icalp46th, pages 99:1–99:15, 2019. arXiv: 1804.05058?.

[5] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv: 1904.03180?, 2019.

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In focs58th, pages 403–414, 2017. arXiv: 1705.01843?.

[7] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. quantum, 4:220, 2020. arXiv: 1809.00643?.

[8] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.

[9] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/​9605034?.

[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. prl, 114(9):090502, 2015. arXiv: 1412.4687?.

[11] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In focs56th, pages 792–809, 2015. arXiv: 1501.01715?.

[12] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. arXiv: quant-ph/​0005055?.

[13] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In icalp46th, pages 27:1–27:14, 2019. arXiv: 1710.02581?.

[14] Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In focs58th, pages 415–426, 2017. arXiv: 1609.05537?.

[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. quantum, 4:221, 2020. arXiv: 1809.01731?.

[16] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. rspa, 454(1969):339–354, 1998. arXiv: quant-ph/​9708016?.

[17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. siamjc, 46(6):1920–1950, 2017. arXiv: 1511.02306?.

[18] Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. qic, 17(1&2):41–64, 2017. arXiv: 1603.02940?.

[19] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. qic, 12(11&12):901–924, 2012. arXiv: 1202.5822?.

[20] George B. Dantzig. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, pages 339–347. John Wiley & Sons Inc., New York, N. Y., 1951.

[21] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv: quant-ph/​9607014?, 1996.

[22] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. siamjc, 35(6):1310–1328, 2006. Earlier version in ICALP’04. arXiv: quant-ph/​0401091?.

[23] Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. comb, 1(2):169–197, 1981.

[24] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.

[25] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph/​0208112?, 2002.

[26] Lov K. Grover. A fast quantum mechanical algorithm for database search. In stoc28th, pages 212–219, 1996. arXiv: quant-ph/​9605043?.

[27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In stoc51st, pages 193–204, 2019. arXiv: 1806.01838?.

[28] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. jacm, 42(6):1115–1145, 1995. Earlier version in STOC’94.

[29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. prl, 103(15):150502, 2009. arXiv: 0811.3171?.

[30] Shelby Kimmel. Quantum adversary (upper) bound. cjtcs, 2013:4:1–14, 2013. Earlier version in ICALP’12. arXiv: 1101.0797?.

[31] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? siamjc, 37(1):319–357, 2007. Earlier version in FOCS’04.

[32] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. arXiv: 1808.09266?, 2018.

[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. prl, 118(1):010501, 2017. arXiv: 1606.02685?.

[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. quantum, 3:163, 2019. arXiv: 1610.06546?.

[35] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In focs56th, pages 1049–1065, 2015. arXiv: 1508.04874?.

[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.

[37] Y. Nesterov and A. Nemirovski. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 1994.

[38] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. prl, 102(13):130503, 2009. arXiv: 0809.2705?.

[39] David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. prl, 103(22):220502, 2009. arXiv: 0905.2199?.

[40] James Renegar. “Efficient” subgradient methods for general convex optimization. siamjc, 26(4):2649–2676, 2016. arXiv: 1605.08712?.

[41] James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1–35, 2019. arXiv: 1512.07569?.

[42] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.

[43] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. siamjc, 26(5):1484–1509, 1997. Earlier version in FOCS’94. arXiv: quant-ph/​9508027?.

[44] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. Earlier version in NIPS’04.

[45] Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1–32, 2012. Earlier version in COLT’06.

Cited by

[1] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics”, arXiv:1806.01838.

[2] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, “Quantum machine learning: a classical perspective”, Proceedings of the Royal Society of London Series A 474 2209, 20170551 (2018).

[3] Patrick Rebentrost and Seth Lloyd, “Quantum computational finance: quantum algorithm for portfolio optimization”, arXiv:1811.03975.

[4] Joran van Apeldoorn and András Gilyén, “Quantum algorithms for zero-sum games”, arXiv:1904.03180.

[5] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation”, arXiv:1711.00465.

[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization”, arXiv:1612.01789.

[7] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, “Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning”, arXiv:1710.02581.

[8] Joran van Apeldoorn and András Gilyén, “Improvements in Quantum SDP-Solving with Applications”, arXiv:1804.05058.

[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang, “Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches”, arXiv:1901.03254.

[10] Simon Apers, “Quantum Walk Sampling by Growing Seed Sets”, arXiv:1904.11446.

[11] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Convex optimization using quantum oracles”, arXiv:1809.00643.

[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, “Quantum algorithms and lower bounds for convex optimization”, arXiv:1809.01731.

[13] Yimin Ge, Jordi Tura, and J. Ignacio Cirac, “Faster ground state preparation and high-precision ground energy estimation with fewer qubits”, arXiv:1712.03193.

[14] Ivan Bardet and Cambyse Rouzé, “Hypercontractivity and logarithmic Sobolev Inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates”, arXiv:1803.05379.

[15] Ashley Montanaro, “Quantum speedup of branch-and-bound algorithms”, arXiv:1906.10375.

[16] Johannes Bausch, Sathyawageeswar Subramanian, and Stephen Piddock, “A Quantum Search Decoder for Natural Language Processing”, arXiv:1909.05023.

The above citations are from SAO/NASA ADS (last updated successfully 2020-02-14 09:28:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2020-02-14 09:28:13: Could not fetch cited-by data for 10.22331/q-2020-02-14-230 from Crossref. This is normal if the DOI was registered recently.


Continue Reading