Not yet retired from research
Last night, two papers appeared on the quantum physics arXiv that my coauthors and I have been working on for more than a year, and that I’m pretty happy about.
The first paper, with Guy Rothblum, is Gentle Measurement of Quantum States and Differential Privacy (85 pages, to appear in STOC’2019). This is Guy’s first paper that has anything to do with quantum, and also my first paper that has anything to do with privacy. (What do I care about privacy? I just share everything on this blog…) The paper has its origin when I gave a talk at the Weizmann Institute about “shadow tomography” (a task where you have to measure quantum states very carefully to avoid destroying them), and Guy was in the audience, and he got all excited that the techniques sounded just like what they use to ensure privacy in data-mining, and I figured it was just some wacky coincidence and brushed him off, but he persisted, and it turned out that he was 100% right, and our two fields were often studying the same problems from different angles and we could prove it. Anyway, here’s the abstract:
In differential privacy (DP), we want to query a database about n users, in a way that “leaks at most ε about any individual user,” even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure n quantum states, in a way that “damages the states by at most α,” even conditioned on any outcome of the measurement. In both cases, we can achieve the goal by techniques like deliberately adding noise to the outcome before returning it. This paper proves a new and general connection between the two subjects. Specifically, we show that on products of n quantum states, any measurement that is α-gentle for small α is also O(α)-DP, and any product measurement that is ε-DP is also O(ε√n)-gentle.Illustrating the power of this connection, we apply it to the recently studied problem of shadow tomography. Given an unknown d-dimensional quantum state ρ, as well as known two-outcome measurements E1,…,Em, shadow tomography asks us to estimate Pr[Ei accepts ρ], for every i∈[m], by measuring few copies of ρ. Using our connection theorem, together with a quantum analog of the so-called private multiplicative weights algorithm of Hardt and Rothblum, we give a protocol to solve this problem using O((log m)2(log d)2) copies of ρ, compared to Aaronson’s previous bound of ~O((log m)4(log d)). Our protocol has the advantages of being online (that is, the Ei‘s are processed one at a time), gentle, and conceptually simple.
Other applications of our connection include new lower bounds for shadow tomography from lower bounds on DP, and a result on the safe use of estimation algorithms as subroutines inside larger quantum algorithms.
The second paper, with Robin Kothari, UT Austin PhD student William Kretschmer, and Justin Thaler, is Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Here’s the abstract:
Given only a membership oracle for S, it is well-known that approximate counting takes Θ(√(N/|S|)) quantum queries. But what if a quantum algorithm is also given “QSamples”—i.e., copies of the state |S⟩=Σi∈S|i⟩—or even the ability to apply reflections about |S⟩? Our first main result is that, even then, the algorithm needs either Θ(√(N/|S|)) queries or else Θ(min{|S|1/3,√(N/|S|)}) reflections or samples. We also give matching upper bounds.We prove the lower bound using a novel generalization of the polynomial method of Beals et al. to Laurent polynomials, which can have negative exponents. We lower-bound Laurent polynomial degree using two methods: a new “explosion argument” that pits the positive- and negative-degree parts of the polynomial against each other, and a new formulation of the dual polynomials method.
Our second main result rules out the possibility of a black-box Quantum Merlin-Arthur (or QMA) protocol for proving that a set is large. More precisely, we show that, even if Arthur can make T quantum queries to the set S⊆[N], and also receives an m-qubit quantum witness from Merlin in support of S being large, we have Tm=Ω(min{|S|,√(N/|S|)}). This resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA.
Note that QMA is “stronger” than the queries+QSamples model in that Merlin’s witness can be anything, rather than just the specific state |S⟩, but also “weaker” in that Merlin’s witness cannot be trusted. Intriguingly, Laurent polynomials also play a crucial role in our QMA lower bound, but in a completely different manner than in the queries+QSamples lower bound. This suggests that the “Laurent polynomial method” might be broadly useful in complexity theory.
I need to get ready for our family’s Seder now, but after that, I’m happy to answer any questions about either of these papers in the comments.
Meantime, the biggest breakthrough in quantum complexity theory of the past month isn’t either of the above: it’s the paper by Anand Natarajan and John Wright showing that MIP*, or multi-prover interactive proof systems with entangled provers, contains NEEXP, or nondeterministic doubly-exponential time (!!). I’ll try to blog about this later, but if you can’t wait, check out this excellent post by Thomas Vidick.
Follow
Comment #1 April 19th, 2019 at 10:43 pm
For those looking for an even higher-level explanation of the NEEXP in MIP* result, I wrote a short story to try to convey some of the significance of this result: http://www.henryyuen.net/post/alice-and-bob-visit/
Comment #2 April 20th, 2019 at 2:05 am
I was about to write something about multi-paragraph abstracts being self-contradictory but then I saw the word “explosion” and please carry on.
Comment #3 April 20th, 2019 at 8:04 am
anon #2: When you’ve got a 40- or 80-page paper with lots of different results, I don’t really see what’s so weird about a multi-paragraph abstract; indeed such abstracts have become common in CS theory (browse the ECCC if you don’t believe me). The arXiv does have a length limit for abstracts, but we were within it.
If there’s a significant result in a paper that’s not mentioned in its abstract, chances are pretty good that the community will overlook that result and it will be lost to history (until, perhaps, it’s reproved by someone else later).
Comment #4 April 20th, 2019 at 8:06 am
Henry #1: Thanks!!
Comment #5 April 20th, 2019 at 12:59 pm
I’m kind of confused by the NEEXP⊆MIP* thing. Like, the whole idea of MIP as opposed to IP is that the verifier can interrogate multiple provers who can’t coordinate, right? If they can coordinate there might as well be only one, was my understanding. So I’m surprised that giving the provers this extra capability of shared entanglement increases what can be verified. I mean, I suppose entanglement can’t be used for communication, but it still seems backwards to me. Is there any simple explanation of how it can be that adding this sort of thing can increase the resulting complexity class rather than decreasing it? Are there non-quantum examples of this phenomenon, that might be easier to understand?
Comment #6 April 20th, 2019 at 1:58 pm
Have a nice Seder and Passover,
best,
LK.
Comment #7 April 20th, 2019 at 2:13 pm
Sniffnoy #5: You’ve put your finger precisely on what’s interesting and surprising about this result. Entanglement does not turn two provers into one, or let the provers communicate with each other. It lets the provers correlate their responses to questions in ways that wouldn’t be possible classically—both for better and for worse. Indeed, it’s far from obvious that MIP* even contains classical MIP, or in other words NEXP. That was proven in a 2012 breakthrough by Ito and Vidick: they showed how the Babai-Fortnow-Lund MIP protocol for NEXP could be “immunized” against entanglement. The new and surprising part is that, if the provers can share unlimited entanglement, then the verifier can ask them to carry out verification protocols that wouldn’t have been possible classically, in order to do verification even for languages far beyond NEXP.
Comment #8 April 20th, 2019 at 3:41 pm
Scott #7: Huh. Yeah, that’s really surprising! So I guess then if you gave the provers the classical analogue — which would be what, a shared stream of random bits? — then the protocol for immunizing against entanglement would still immunize against this classical analogue, since obviously this is weaker, and so the complexity class wouldn’t decrease. And since the Natarajan and Wright result really does exploit the quantum aspects, presumably it wouldn’t increase either, and you’d still have NEXP? Is that something anyone’s bothered to check?
Comment #9 April 20th, 2019 at 4:32 pm
Sniffnoy #8: With classical correlation only between the provers, it’s a theorem that you get exactly NEXP. And yes, this follows from the Ito-Vidick protocol not needing any entanglement in the honest case, though that’s an extremely roundabout way to prove it. With entanglement, we now know unconditionally (!!) that you get more.
Comment #10 April 21st, 2019 at 7:13 am
OK as someone who works in a vastly different field, I had to chuckle a bit at sentences like “rules out the possibility of a black-box Quantum Merlin-Arthur” and “Merlin’s witness cannot be trusted”. I’m sure every area has jargon that sounds amusing to laypeople, but this particularly tickled me today.
I hope you had a lovely Passover!
Comment #11 April 21st, 2019 at 10:44 am
Andrew #10: Four of the most important technical terms in theoretical computer science are Merlin, Arthur, Alice, and Bob. Physics terms like ‘quark,’ ‘Big Bang,’ and ‘black hole’ would sound similarly funny if you weren’t so used to them.
Comment #12 April 21st, 2019 at 3:42 pm
Sorry for also focusing on Natarajan and Wright, but I am trying to understand whether the algorithms in these MIP and MIP* theorems are something that could ever run to completion within the lifetime of human civilization, or whether these theorems are of purely intellectual and esthetic value; at most a potential source of inspiration for the design of analogous but actually tractable algorithms. Could a MIP or MIP* ever be built, and perform superhuman optimizations with potential real-life consequences?
Comment #13 April 21st, 2019 at 3:56 pm
Overheard at the Aaronson seder:
The Torah speaks of four types of student: the simple student, the wise student, the wicked student and the student who is too young to ask.
The simple student asks: “So, does this quantum thing mean the computer can try all possible values at the same time?” To him you shall say: “No: it means that sometimes we can use constructive and destructive interference to amplify the values we care about. Go read Preskill’s notes.”
The wise student asks: “How do the properties of quantum mechanics allow us to solve some period-finding problems exponentially faster than seems to be possible on a classical computer?” And you shall explain to him all the laws of the Quantum Fourier Transform, down to the last detail of magic state distillation.
The wicked student asks: “Would you like to invest in my quantum machine learning startup?” Saying “you” he excludes himself, implying it is only your money he will be wasting. Tell him: “No, and you should spend your time on studying, like you promised the department when they admitted you”. “They”, and not “we”, implying that if it had been up to you he would not have been admitted.
To the student who is too young to ask, you shall say: “What’s keeping you? When Scott was your age, he already had a PhD!”
———————————–
Many are the kindnesses God has bestowed upon us:
If he had given us quantum mechanics and not given us CSS codes……it would have been enough.
If he had given us CSS codes and not given us the threshold theorem……it would have been enough.
If he had given us the threshold theorem and not given us the Deutsch-Jozsa algorithm……it would have been enough.
If he had given us the Deutsch-Jozsa algorithm and not given us Grover search……it would have been enough.
If he had given us Grover search and not given us Shor’s algorithm……it would have been enough.
If he had given us Shor’s algorithm and not given us quantum recommendation systems……it would have been enough.
If he had given us quantum recommendation systems and not given us Tang’s algorithm……it would have been appreciated!
Comment #14 April 21st, 2019 at 4:13 pm
OK, this is hilarious. 😀
Comment #15 April 22nd, 2019 at 9:16 am
In the Vidick article:
“Building on this idea, NW develop a battery of delicate tests that provide the verifier the ability to control precisely what information gets distributed to each prover.”
Is there a connection between “delicate tests” and “gentle measurements” (from your article)?
Comment #16 April 22nd, 2019 at 9:25 am
fred #15: No. The tests Thomas is talking about are not gentle in the sense of not damaging the state much.
Comment #17 April 22nd, 2019 at 9:36 am
DavidM #13: LOL!! Thanks for that.
I confess that, after two Seders, I’ve stopped keeping Passover this year, after an incident at the JCC where they kicked my 6-year-old daughter out of the swimming pool on an invented pretext. She had already passed a swim test at the JCC two years ago, but they made her retake it, which it says nothing about in their own rules. Of course she easily passed again, but they failed her anyway for “using the wrong stroke”—something they hadn’t explained to her in advance! And they wouldn’t let her retake the test either.
After two years of living in Austin, I have yet to find a single suitable place to go swimming with my daughter—we can obviously now scratch off the JCC—and it’s seriously hurt my relationship with her, as swimming was the main father/daughter activity that we used to do together.
Anyway, my reasons for keeping Passover in the first place were entirely cultural, rather than theological or supernatural. And I now feel like, if this is the way the “Jewish community” (through its lifeguard representatives) is going to treat me, then I no longer want anything to do with the Jewish community.
But I guess I’ll keep this blog under its current name, at least until I think of a better one.
Comment #18 April 22nd, 2019 at 11:36 am
Scott, I know you didn’t ask, but I suggest you sit on this one for a while.
Comment #19 April 22nd, 2019 at 1:41 pm
arch1 #18: Of course I’ll sit on it. And of course there are many senses in which I can never stop being “Jewish,” regardless of what I do and how I raise my kids and whether or not I participate in any Jewish community.
But just to help you calibrate: two years ago, while I was driving with both kids screaming in the backseat, I bumped into another car in a parking lot. There was no actual damage to the other car, but the other driver was still enraged at me, made me give over my insurance information, etc. until I simply offered to write him a check for $1000 if he’d declare himself made whole by that (he agreed).
I was sufficiently shaken by this experience that I haven’t driven a car even once since then—relying entirely on Ubers and on Dana and others to drive.
Irrational, you say? An overreaction? Looking back on it, I only feel sorry that I didn’t stop driving even earlier. I’ve always hated driving, was mediocre at it, and resented the way the (pre-Uber) US basically forced you to do it. I feel happier and safer now that I’ve stopped.
So, sometimes a jolt like this is exactly what you need to do something that you should’ve done all along. Ask me again in two years, I guess. 🙂
Comment #20 April 22nd, 2019 at 1:58 pm
Wise students usually ask questions you do not know how to answer.
You seem to believe there is a conspiracy against your daughter. What does the JCC have against her?
Comment #21 April 22nd, 2019 at 3:03 pm
Yiftach #20: No, that’s wrong. I never attribute to conspiracy what can be adequately explained by a simple combination of idiocy and malice. 🙂
Comment #22 April 22nd, 2019 at 4:21 pm
Scott #19:
“Looking back on it, I only feel sorry that I didn’t stop driving even earlier.”
Thanks for the additional context (and the surprise ending). I wish I had a more sensitive rut-detector myself, as in some areas I tend to ‘stay the course’ beyond the time at which I really had enough info to conclude that a change would be for the better. Perhaps this is just a matter of paying more attention.
PS. You might owe parking-lot-guy a thank-you note:-)
Comment #23 April 22nd, 2019 at 5:16 pm
Good stuff, but you shouldn’t even make jokes about retiring from research at your age, remember that ~ half of the original founders of Quantum Mechanics, Born and Schrödinger, were 42 and 39 at the time of their most important contributions.
(I consider the discoverers of Quantum Mechanics to be Heisenberg, Dirac, Born and Schrödinger, in that order – sorry Jordan, you were just a techie)
Comment #24 April 22nd, 2019 at 7:05 pm
@Scott#17- It’s not fair to judge the Jewish Community by its lifeguards. It’s understandable if you want to avoid that particular pool, though.
Comment #25 April 22nd, 2019 at 8:27 pm
Michael #24: Due to my experiences in life, I’m extremely sensitive—no doubt oversensitive—to anything that seems to me even remotely like bullying, and especially to the arbitrary abuse of power against my kids. And if a place calls itself a “Jewish Community Center,” then I hold it to an even higher standard than I normally would for refraining from such behavior, and for making my family feel welcomed and valued. Is that my mistake?
Comment #26 April 22nd, 2019 at 9:33 pm
@Scott#25- Its wrong to judge the entire Jewish community by one Community Center.
Comment #27 April 23rd, 2019 at 6:48 am
1) Congrats on papers!
2) Congrats (or something) on having a blog post on research results end up with comments on Jewishness, Swimming, and Driving.
3) Congrats on joining the non-driving community! I’ve never learned how to drive (I have bad depth perception and was raised in New York) I rely on Uber, Darling, and friends. Before Uber it was Public Transportation, Darling, and the friends.
4) Some estimates say that using Uber is cheaper than buying and owning a car. There are probably some Caveats there, but it certainly could be made cheaper.
5) Traffic, Pollution- Not sure how that all works out.
Comment #28 April 23rd, 2019 at 7:30 am
Michael #26: Yes, you’re right. I should explain that Austin is unique in that most Jewish life in the entire city is concentrated in a single gated campus (donated by Michael Dell), with the JCC at its center and various synagogues (Reform, Conservative, Orthodox) surrounding the JCC. I.e., it’s a place where a single dispute with a single pool lifeguard really might make a person feel unwelcome to participate in the community for as long as they lived here.
Comment #29 April 25th, 2019 at 9:33 am
Scott #21
is it possible that you’ve been treated this way because your interest in keeping with your Jewish identity is purely cultural, and there’s a push to be more on the religious side of it?
Comment #30 April 25th, 2019 at 12:18 pm
fred #29: In this case, I can guarantee that the lifeguards, who might not have been Jewish themselves, had zero knowledge of or interest in which of the swimmers were Jews let alone religious Jews. JCC membership is open to anyone, just like membership at the Y, and many non-Jews go there. But I learned this week that there’s a problem with such arrangements: if anything goes wrong, then your dispute is with the leadership of a particular community (and not just with some random swimming pool operator), which could then imperil your future relationship with that community.
Comment #31 April 25th, 2019 at 4:00 pm
Scott, your quitting driving probably means Dana will have to drive more, which might start bugging her after a while. I hope you’ll start driving again if that happens, and that you’ll pick up on it (if it happens) even if she doesn’t say anything.
Is NEEXP known to be different from EEXP? From EEEXP? Are there other interesting problems in NEEXP? I seem to remember that the quantifier elimination procedure for real closed fields and for Presburger arithmetic are double-exponential. So it sounds like classical multi-prover can convince you of the truth of a proposition in Euclidean geometry (if you turn it into a question about real closed fields) while you can’t do that with the PCP theorem (since the proof might be too long). No idea if that’s interesting or what the entangled prover can do that’s better.
Comment #32 April 25th, 2019 at 5:44 pm
asdf #31: Dana supported my decision to quit. Psychologically, I can’t deal with horrible things being done to me, and I can deal even less with the possibility of doing horrible things to others. That means that I should not be behind the wheel.
No, NEEXP is not known to be different from EEXP—that’s just a scaled-up version of P vs NP. The only problems I’ve seen that require such high-up complexity classes to classify them, tend to be fairly arcane problems in logic (eg the decision problem for Presburger arithmetic).
Comment #33 April 25th, 2019 at 8:07 pm
Scott, ah, ok, if Dana is cool with it then great. I recommend still taking a drive around a quiet area now and then, to keep the reflexes. I quit driving for about 5 years because of a long distance move, and when I wanted to get a car again, I found I had completely forgotten how to drive and had to take driving school again starting from scratch. I won’t tell you (you mean like you’re doing now?) the bit about how Uber like Facebook is evil, since I’m sure you know already, heh.
I know that some iterated exponentials and logarithms turn up in number theory, but don’t know if those can be turned into interesting decision problems.
Comment #34 April 26th, 2019 at 7:55 am
@Scott#32- I’m not sure if quitting driving was right for you or not. However, there’s one thing you should keep in mind. You might have noticed that I brought up OCD a couple of times.People with OCD cannot get better unless they get comfortable with the possibility of doing horrible things to others. Scott Alexander could explain it to you better. (He could also tell you that it’s easier said than done.)
Comment #35 April 30th, 2019 at 3:06 pm
William Gasarch #24:
Uber is only cheaper as long as they avoid all the regulations, pay drivers way under the minimum wage, have suckers driving that don’t realize what they are doing to their car, etc. Eventually this will all be outlawed and Uber, etc., will be as expensive as traditional cabs.
The entire “gig economy” is a scam to avoid regulations and minimum wage laws.
Comment #36 May 1st, 2019 at 2:07 pm
There’s an Uber strike/shutdown called for May 8:
https://boingboing.net/2019/04/29/may-8.html
Comment #37 May 1st, 2019 at 2:12 pm
I should have included this: https://theconversation.com/ubers-9-billion-ipo-rests-on-drivers-80-plus-hour-workweeks-and-a-lot-of-waiting-115782
Scott, feel free to merge the two comments if WordPress supports that.
Comment #38 May 1st, 2019 at 11:01 pm
Can Scott Aaronson give good arguments for why a classical factorization algorithm does not exist?
Comment #39 May 2nd, 2019 at 1:17 am
Does anyone here know the current status of the Kelmans-Seymour conjecture?
https://en.wikipedia.org/wiki/Kelmans-Seymour_conjecture
The wiki page points to a series of legit-looking Arxiv preprints claiming to have a proof, but they are from 2016 and don’t mention having been submitted anywhere or that refereeing is in progress or anything like that. So of course, this comment section is the logical place to ask ;-).
Comment #40 May 2nd, 2019 at 7:31 pm
Yaqub #38: No, he cannot. He’s not even confident that there’s no such algorithm.
Comment #41 May 3rd, 2019 at 2:12 pm
You know, it only just occurred to me to ask, what about QMIP? Checking the complexity zoo, apparently it’s been known since 2012 that QMIP = MIP*! Like, whoa, that’s pretty surprising all by itself! For the same reason as has been mentioned above — QMIP is obviously at least MIP, while MIP* seems like it ought to be smaller.
Comment #42 May 3rd, 2019 at 2:14 pm
I suppose that also raises the question, what about QMIP*… (offhand I’d speculate that it’d still be equal to MIP*, but this is really not my area…)
Comment #43 May 5th, 2019 at 9:04 am
Regarding, MIP*, is there any known upper bound on it at all? I would expect a counting argument to show that MIP* is not ALL, (although I haven’t worked out the details). Is there any non-trivial upper bound?
Comment #44 May 5th, 2019 at 11:28 am
Joshua #43: I agree that MIP* is not ALL since we can enumerate the verifier strategies. For the upper bound question, though, it’s actually relevant whether we define MIP* using only limits of prover strategies with finite-dimensional entanglement, or using infinite-dimensional commuting-operator strategies. In the former case, we at least have an upper bound of Recursively Enumerable. In the latter case … well, we’d again have an RE upper bound if the Connes Embedding Conjecture holds, but otherwise I’m not sure! There’s also a result, using sum-of-squares hierarchies, which puts a coRE upper bound under conditions/assumptions that I forget, which combined with the RE upper bound would of course give you computability. Experts could tell you more.
Comment #45 May 11th, 2019 at 6:59 pm
To follow up on Scott’s answer: for the latter case (when we consider quantum provers in the commuting operator model), the complexity is upper bounded by coRE, because the Navascues-Pironio-Acin (NPA) SDP hierarchy (which is like a non-commutative sum of squares hierarchy) converges to the commuting operator value of a game *from above*. In other words, if the commuting operator value of a game is less than 1, then the NPA hierarchy will eventually discover this fact and terminate — but there are no bounds known on how long this will take.
If the commuting operator value of a game is equal to the (“standard”) tensor-product value of a game, then combining the NPA algorithm to give an upper bound on the quantum value, plus the exhaustive search algorithm to give a lower bound, will converge to the true value of the game.
However we don’t know if the commuting operator value of games are always equal to the tensor product value, so it is not clear that this NPA + exhaustive search combo algorithm always works to approximate the quantum value of a game.
Comment #46 May 24th, 2019 at 1:39 pm
What other problems are so far out in the complexity hierarchy and yet computable? My understanding is that very little “””natural””” problems exist out beyond NEEXP (heck, EXPTIME) before you start hitting RE or coRE. Babai once compared the complexity zoo to space, where there’s areas that are full of stuff and large spaces of emptiness between them. We see this too in computability theory, where I can’t name any natural Turing intermediate problems.
Relatedly, does anyone believe that MIP* could be undecidable?
Comment #47 July 3rd, 2019 at 8:09 pm
[…] made an appearance on this blog a few months ago, when I wrote about the new breakthrough by him and Anand Natarajan: namely, that MIP* (multi-prover interactive proofs […]
Comment #48 July 31st, 2019 at 7:38 pm
I was joking too. It would nice to see more mathy wording.