Quantum Advantage

Update (22 May 2017): This Scirate thread seems to have touched a nerve. Since this was previously buried in the comments here, it’s worth promoting to the top of the post. I think that “quantum computational supremacy” addresses the concern. Basically, we use “quantum” as an adjective for our peer group, which makes the analogy to “white” too strong. Adding “computational” emphasizes that it is the computation, not the people, that are supreme.


I’ve had quite a few conversations lately about a comment I left on Scirate. The paper at that link, “Quantum advantage with shallow circuits” by Sergey Bravyi, David Gosset, Robert Koenig, shows a provable separation between analogous classes of quantum and classical circuits, even when the quantum circuit is restricted to nearest-neighbor gates on a 2D grid. This is a fantastic result! My comment, however, wasn’t regarding the result, but rather the title of the paper. I’m just happy that they called it a “quantum advantage” instead of using that other term…

The term “quantum supremacy” is the fashionable name for the quantum experiments attempting to beat classical computers at some given task, not necessarily a useful one. According to current usage, the term (strangely) only applies to computational problems. The theoretical and experimental work towards demonstrating this is wonderful. But the term itself, as any native English speaker can tell you, has the unfortunate feature that it immediately calls to mind “white supremacy”. Indeed, one can even quantify this using a Google ngram search for *_ADJ supremacy over all books in Google’s corpus between 1900 and 2008:

None of these terms has a particularly good connotation, but white supremacy (the worst on the list) is an order of magnitude more common than the others and has, on net, been growing since the 30s. For almost every native speaker that I’ve talked to, and quite a few non-native speakers as well, the taint of this is hard to escape. (For speakers of German or French, this word is a bit like “Vormachtstellung” or “collaboration” respectively.)

The humor surrounding this term has always been in bad taste — talking about “quantum supremacists” and jokes about disavowing their support — but it was perhaps tolerable before the US election in November. Given that there are several viable alternatives, for example “quantum advantage” or even “quantum superiority”, can we please agree as a community to abandon this awful term?

This isn’t about being PC. And I’m not trying to shame any of the people that have used this term. It’s just a poor word choice, and we don’t have to be stuck with it. Connotations of words matter: you don’t say someone is “scrawny” if you mean they are thin, even though my thesaurus lists these words as synonyms. Given the readily available alternatives, the only case I can think of for “supremacy” at this point is inertia, which is a rather poor argument.

So please, say it with me now: quantum advantage.

Update: Ashley Montanaro points out that “advantage” should potentially be reserved for a slight advantage. I maintain that “superiority” is still a good choice, and I also offer “dominance” as another alternative. Martin Schwarz suggests some variation of “breaking the X barrier”, which has a nice feel to it. 

Posted in Quantum | 24 Comments

Seattle for QIPers

QIP 2017 is coming to Seattle, hosted by the QuArC group at Microsoft, January 16-20 (with tutorials on the 14th and 15th). If you have some spare moments, maybe you arrive early, or maybe you are planning for the afternoon off, here are some ideas for things to do around the wonderful city I call home.

Be a Tourist!

  • Take a trip up to the Seattle Center (approximately 1 mile walk from Hotel).  There you can take a ride to top of the Space Needle ($22), which has some great views when it is sunny (ha!).  Music or Star Trek fan?  Check out Paul Allen’s collection of toys and memorabilia Museum of Pop Culture ($30), which has two very geeky exhibits right now, Star Trek and Indie Game Revolution.  Or if you are secure in your ability to not knock over stuff worth more than it’s weight in gold, check out the Chihuly Garden and Glass ($22, combine with a trip to Space Needle for $36).  Kids and family in tow?  Can’t go wrong with the Pacific Science Center ($27.75 adults, $11.75 kids) and the Seattle Children’s Museum ($10.50).
  • Visit Pike’s Place Market (about 0.5 mile walk from Hotel).  See them toss fish!  Visit the original Starbucks (sssshhh it was actually the second).  Like your politics off the chart? Check out Left Bank Books which has a seriously eclectic collection of books.  While you’re at it, if you’re playing tourist, you might as well walk on down to the waterfront where you can take a ride on the Seattle Great Wheel ($13) or check out the Aquarium ($50 ouch) (we had a party there a few years back, yes we ate Sushi in front of the octopus.)
  • Architect buff on the cheap?  Check out the Seattle Central Library (a little over a half mile from Hotel).  Sculpture buff on the cheap?  Walk around the Olympic Sculpture Park (little over a mile from the Hotel).  These are in completely different directions from the Hotel.
  • Museums?  Seattle Art Museum has a nice collection ($25) but my favorite these days is the Museum of History and Industry (Little over 1 mile walk, $20).  The MoHaI is located in south Lake Union, a location that has been transformed dramatically in the last few years since Amazon relocated to the area.  Count the number of cranes!
  • So it turns out the Seattle you see today was built over the top of the Seattle that used to be, and, while I’ve never done it, everyone I know who has done it, loves the Seattle Underground Tour.  Note that if you combine this tour with reading about earthquakes in the PNW you might give yourself some anxiety issues.  Seattle is in the middle of boring a long tunnel under it’s downtown to replace the gigantic monstrosity of the viaduct, sadly I don’t think there are any tours of the tunnel boring machine, Big Bertha.

Be a Geek!

  • Ada’s Technical Books is in the Capital Hill Neighborhood (bus or Lyft).  It’s not as crazy as some university town bookstore, but has a good collection of non-standard science and tech books.
  • Elliot Bay Bookstore again in Capital Hill is no Powell’s but it’s still rather good.
  • Fantagraphics bookstore and gallery.  You’ll know if you want to go to this if you recognize the name.

See a Show!

Get Out and About!

  • We’ve a ton of snow right now.  Snoqualmie is closest, great for beginners or if you’re just craving a quick ski or board.  For the more serious, Baker, Crystal, and Stevens Pass are all recommended.  I like Crystal a bit more, on clear days the view of Mt. Rainier is spectacular.
  • Take a ferry over to Bainbridge Island.  This is one of my top recommendations in the summer, but even in the winter it’s a nice trip.  (Other summer recommendation is to rent a Kayak and kayak around Lake Union, but it’s too cold to do that this time of year.)
  • If you’re up for a nice stroll, head over to Discovery Park or take a walk on the Alki beach in West Seattle (both require a ride to get there from Hotel, though you could walk down and take the water taxi on weekdays.)  Closer by to the Hotel, head over to Myrtle Edwards Park.

Neighborhoods

  • Seattle is a city of neighborhoods, each of which, believes that they have their own style!  Each of these except Belltown or Downtown are a bus, cab, or rideshare away.  Really there is too much to cover here, but here are a few short notes:
    • Belltown: This is the neighborhood just north of downtown where the Hotel is located.  Used to be sketchy but now has lots of luxury condos.  Shorty’s is a dive with pinball and hot dogs.  People seem to love Tilikum Place Cafe though I have not been there.  If you want a traditional expensive steakhouse, El Gaucho is great, though I think the Metropolitan Grill in downtown is better (both pricey!)  Since this is a quantum conference, I would be remorse to not point out that Belltown is the site of Some Random Bar, which I believe has good crab nachos.  If you crave a sweet donut, Top Pot Donuts is literally just up the street from the hotel.
    • Fremont: Is still an eclectic neighborhood, though not quite as far out as it used to be.  It’s annual solstice parade is the only day it is legal to ride your bike nude in Seattle.   Tons of places to eat and drink here, I recommend Brouwers (great beer selection, frites), Revel (Korean fusion, no reservations), and Paseo (cuban sandwiches OMG delicious) but there are a ton more in the neighborhood.   Theo’s chocolate does factory tours and also supplies a great smell to the neighborhood (along with another smell from the nearby dispensaries!)  Also if you’re up this way you can see a huge troll under a bridge, a rocket ship, and a statue of Lenin (who sometimes gets dressed in drag).
    • Ballard: Originally a Scandinavian fishing community, these days it’s hip as Seattle hip gets.  Sunday year round farmer’s market.  When many people think of the Pacific Northwest they think of fish, but really I think where Seattle really shines is in shellfish.  The Walrus and the Carpenter is a great place to affirm this claim.
    • Capital Hill: East of downtown, Seattle’s most vibrant district.  Fancy restaurants: Altura, Poppy.
    • University District: Lots of cheap eats for UW students.  In the summer I recommend renting a kayak from Agua Verde, a Mexican restuarant/kayak rental joint
    • South Lake Union: Amazon land, totally transformed over the last few years. I’ve had good luck at re:public.  Shuffleboard at Brave Horse Tavern.

Morning Run

I’d probably head over to the Sculpture park and run up Myrtle Edwards Park: here is a mapmyrun route.

Seattle

Enjoy Seattle, it’s a fun town!  I recommend, generally, shellfish, thai food, and coffee.  Also you can play the fun people guessing game: “software engineer or not” (advanced players can score points for Amazon or Microsoft sub-genres).  Also: if you don’t want to look like a tourist, leave the umbrella at home.  You know it rains more every year in New York city, right?

Posted in Quantum, Seattle | 5 Comments

5 Years!

Five years ago I (it’s me Dave Bacon former supposed pseudo-professor and one time quantum pontiff) jumped off the academic ship, swam to shore, and put on a new set of clothes as a software developer for Google. Can it really have been five years? Well I should probably update this blog so my mom knows what I’ve been up to.

  • I helped build and launch Google Domains. From quantum physics professor to builder of domain name registrar. I bet you wouldn’t have predicted that one! Along the way I was lucky to be surrounded by a team of software engineers who were gracious enough to tell me when I was doing silly things, and show me the craft that is a modern software development. I may now, in fact, be a real software developer. Though this just means that I know how much I still need to master.
  • We built a cabin! Well, we worked with wonderful architects and buiders to construct “New Caelifera” over in the Methow Valley (about 4 hours east of Seattle).
    New CaeliferaI have to say that this was one of the funnest things I’ve done in my life. Who knew a dumpy software engineer could also be an aesthete. Even cooler, the end result is an awesome weekend place that you have to drive through a National Park to get to. I’ve been super spoiled.
  • Lost: my sister, Catherine Bacon, and my dog, the Test Dog. Life is precious and we should cherish it!
  • Gained: a new puppy, Imma Dog Bacon. Imma dog? You’re a dog! Imma Dog!
    Imma Dog
  • Hobbies. arXiv:1605.03266. The difference between being a hobby scientist and a professional scientist is that when you’re a professional it’s “Fail. Fail. Fail. Fail. Fail. Fail. Fail. Fail. Fail. Success!” and when you’re a hobbiest it’s “Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Fffffffaaaaaiiiiiillllll. Success?” Yes I’m that guy that reads your quantum computing papers at night after work for fun.

So maybe I’ll write another blog post in five years? Or maybe I should resurrect the Pontiff. I saw the Optimizer the other day, and he suggested that since it’s hard for me to blog about quantum computing stuff what with Google involved as it is, I could blog about stuff from the past. But I’m more of a promethean than a pastoralist. It didn’t occur to me until later that there is an alternative solution, one that is particularly appealing to a quantum dude like myself: maybe I should start blogging about an alternative universe? I’ve always liked Tlön, Uqbar, Orbis Tertius.

Posted in Self: Meet Center. Center: Meet Self., Where's Dabacon? | 3 Comments

Hazards of “Shut up and calculate”

Three quantum physicists show why no interpretation is the worst.

Posted in Uncategorized | Leave a comment

What If Papers Had APIs?

API is an abbreviation that stands for “Application Program Interface.” Roughly speaking an API is a specification of a software component in terms of the operations one can perform with that component. For example, a common kind of an API is the set of methods supported by a encapsulated bit of code a.k.a. a library (for example, a library could have the purpose of “drawing pretty stuff on the screen”, the API is then the set of commands like “draw a rectangle”, and specify how you pass parameters to this method, how rectangles overlay on each other, etc.) Importantly the API is supposed to specify how the library functions, but does this in a way that is independent of the inner workings of the library (though this wall is often broken in practice). Another common API is found when a service exposes remote calls that can be made to manipulate and perform operations on that service. For example, Twitter supports an API for reading and writing twitter data. This later example, of a service exposing a set of calls that can manipulate the data stored on a remote server, is particularly powerful, because it allows one to gain access to data through simple access to a communication network. (As an interesting aside, see this rant for why APIs are likely key to some of Amazon’s success.)

jdrzxAs you might guess, (see for example my latest flop Should Papers Have Unit Tests?), I like smooshing together disparate concepts and seeing what comes out the other side. When thinking about APIs then led me to consider the question “What if Papers had APIs”?

In normal settings academic papers are considered to be relatively static objects. Sure papers on the arXiv, for example, have versions (some more than others!) And there are efforts like Living Reviews in Relativity, where review articles are updated by the authors. But in general papers exist, as fixed “complete” works. In programming terms we would say that are “immutable”. So if we consider the question of exposing an API for papers, one might think that this might just be a read only API. And indeed this form of API exists for many journals, and also for the arXiv. These forms of “paper APIs” allow one to read information, mostly metadata, about a paper.

But what about a paper API that allows mutation? At first glance this heresy is rather disturbing: allowing calls from outside of a paper to change the content of the paper seems dangerous. It also isn’t clear what benefit could come from this. With, I think, one exception. Citations are the currency of academia (last I checked they were still, however not fungible with bitcoins). But citations really only go in one direction (with exceptions for simultaneous works): you cite a paper whose work you build upon (or whose work you demonstrate is wrong, etc). What if a paper exposed a reverse citation index. That is, if I put my paper on the arXiv, and then, when you write your paper showing how my paper is horribly wrong, you can make a call to my paper’s api that mutates my paper and adds to it links to your paper. Of course, this seems crazy: what is to stop rampant back spamming of citations, especially by *ahem* cranks? Here it seems that one could implement a simple approval system for the receiving paper. If this were done on some common system, then you could expose the mutated paper either A) with approved mutations or B) with unapproved mutations (or one could go ‘social’ on this problem and allow voting on the changes).

What benefit would such a system confer? In some ways it would make more accessible something that we all use: the “cited by” index of services like Google Scholar. One difference is that it could be possible to be more precise in the reverse citation: for example while Scholar provides a list of relevant papers, if the API could expose the ability to add links to specific locations in a paper, one could arguably get better reverse citations (because, frankly, the weakness of the cited by indices is their lack of specificity).

What else might a paper API expose? I’m not convinced this isn’t an interesting question to ponder. Thanks for reading another wacko mashup episode of the Quantum Pontiff!

Posted in Extralusionary Intelligence, Science 2.0, The Loony Bin Called Academia | 13 Comments

QIP 2015 Talks Available

Talks from QIP 2015 are now available on this YouTube channel. Great to see! I’m still amazed by the wondrous technology that allows me to watch talks given on the other side of the world, at my own leisure, on such wonderful quantum esoterica.

Here also are links to the Pontifical live-blogging and the QIP schedule of talks.

Posted in Quantum Computing, Science 2.0 | Leave a comment

QIP 2015 business meeting

A QIP 2015 epilogue: our notes from the business meeting. See also this post by Kaushik Seshadreesan.

Business Meeting Report

local organizing committee report

Finance:
$193,545 – $191,467 = $2,478 profit!
registration income: $185,340
refunds, about $3,000
external sponsorships: $30,450, and another $5k due later
total income before tax: $212,900
after tax: $193,545

Expenses:
tutorial: $5,296
main program: $47,941
banquet: $120*270 = $32,400
admin: $10k
travel support for about 41 junior researchers: $34k+
invited speakers: $45k estimated
rump session: $10,600 estimated
best student paper prize: $700
other/misc: $5k
total: $191,467

Registration:

total: 276
in 2014: 261 (early before 31 oct, 169; standard by 30 nov, 68; late by 31 dec, 29)
in 2015: 15 (on-site 10)
no-show: 10

It’s great that the budget was balanced to about 1%. However, what to do about the little bit of extra money? This is a perpetual problem. Runyao had a nice simple idea: just send it to next year’s QIP and use it for travel support for junior researchers.

Program Committee Report:

197 talk-or-poster submissions (1 withdrawn) (In Barcelona, there were 222 but this decrease probably reflects the distance to Sydney rather than anything about the field.)

3 PC members for each submission, and 25 submissions per PC member.
3 weeks of refereeing, 2 weeks of discussion.
Much faster than a typical theoretical CS conference

39 accepts, including 2 mergers 20% accept
SC invited 3 more speakers 40 talks in the program
6 of these recommended to SC for plenary status
one best student paper

There were 601 reviews, at least 3 per submission
There were 142 external reviewers and 220 external reviews.

In the first round there were 102 posters accepted. 5 poster-only submissions, all rejected talk-or-poster submissions

92 more posters 90 accepted… one out of scope and one wrong.

About 40 people withdrew their posters or simply didn’t put up a poster.

We could have accepted about 20-30 more good papers. Future choice: accept more papers? This implies parallel sessions (if we decide to accept all of those good-enough-for-QIP papers). There are pros and cons of this. Pro: more people will be happy, and better representation of research. The Con is that the community will be more split, the conference needs two medium-size lecture rooms (but what about the plenary talks?).

Anecdotal feedback from authors: some reviews were sloppy. On the other hand, with only 3 weeks of refereeing we cannot expect too much. CS reviewers are more detailed and more critical.

Do we want the 3-page abstract format? There was not much discussion on this point, but Ronald de Wolf said that the costs outweigh the benefits in his opinion. We don’t have strong opinions. Steve likes them but thinks maybe two pages would be enough. Aram thinks we could do without them, or could go to 4 pages so the physicists could use their PRL and the computer scientists could use the first 4 pages of their long version. Apparently no one in the audience had strong opinions on this either, since there was no discussion of this point. Hopefully the next PC chair at least thinks carefully about this instead of going with the default.

Do we want to have the abstracts on the website? Again, there was no discussion of this point, but RdW thinks this is generally a good idea (and us Pontiffs agree with him).

Should we make the reviews public (subject to caveats)? E.g., something like what was done for TQC 2014, where lightly edited reviews were posted on SciRate. The answer is obviously yes. 🙂 We made a case for partial open reviewing, and the slides are here. The “partial” here is important. I think a lot of people have misinterpreted our proposal and counter-proposed a compromise in which only edited summaries of reviews of reports are posted for accepted papers; this is funny because it is essentially what we did for TQC 2014! It is true that in implementing this the details are extremely important, including instructions to the PC & subreviewers and the explanations of the system to authors and the public (e.g. crucially including the fact that published reviews are not meant to explain acceptance/rejection or even to label as “good” or “bad” but rather to add perspective). Probably these points should be in a longer post.

QIP 2016 will be held in Banff, with Barry Sanders chairing the local organizing committee.

Bids for QIP 2017 are being put in by Zürich and Seattle with local organizing committee chairs of Rotem Arnon Friedman and Krysta Svore respectively. (I mention chairs because my understanding is that no matter how large the committee is, they do a \Omega(1) fraction, or even a 1-o(1) fraction, of the total work.) A straw poll of attendees shows slight favor for Zürich. Krysta said that MSR would probably still be interested in hosting in 2018, when the geographic case for Seattle would be stronger. Neither place will be as glorious as Sydney in January, but Seattle winters are pretty mild (although gray).

Stephanie Wehner presented the results of a poll that showed support for parallel sessions (about 50% of respondents favored this over options like dropping plenary talks, dropping the free afternoon, shorter talks or doing nothing). Others, like Daniel Gottesman, complained that the poll seemed to be asking how to increase the number of talks, rather than whether we should. A show of hands at this point (from an audience that by now had become pretty small, perhaps in part because there was free beer at the rump session at this point) showed an audience roughly evenly divided between supporting and opposing an increase in the number of talks. The Trinity of Pontiffs are divided on the parallel question, but of course it doesn’t have to be all or nothing. We might try an experiment doing parallel talks on one day (or even half-day) out of five, so we can see how we like it.

Posted in Conferences, Liveblogging | Leave a comment

QIP 2015 zombie-blogging, Day 5

Today’s highlight: an algorithm running in time O(n^{59}), also known as “polynomial time” or “efficient”.

Joseph Fitzsimons and Thomas Vidick.
A multiprover interactive proof system for the local Hamiltonian problem(Plenary Talk)
abstract arXiv:1409.0260

Thomas begins by reminding everyone about what NP is and mentions that Super Mario is NP-complete. However, I solved it as a child and saved the princess from Bowser. I’m not sure what the implications of this are for P vs. NP. Knowing that Super Mario is in NP saves me from having to learn it. I just reduce it to 3-SAT.

All problems in NP have a local verification procedure because of the NP-completeness of 3-SAT. But we still need to know the whole proof, right?

There is a nice way to make proof verification completely local, and that is to introduce more than one prover. We introduce a familiar cast of characters: Merlin and Arthur. Arthur is the referee and is allowed to ask two non-communicating Merlins to prove something to him. The value is defined to be \omega(G) = \sup_{\textrm{Merlins}} \textrm{Pr}[\text{Arthur accepts}]. We need to ensure that this scheme is both sound and complete. A stronger version known as the PCP theorem has the following interesting property. Arthur can do some pre-processing and then just check a constant number of clauses to get a high probability of soundness.

The 3-local Hamiltonian problem is a well-known complete problem for QMA. Here one is given a local Hamiltonian on n qubits with a promise that the ground state energy is either less than a or greater than b, with a-b \ge 1/\mathrm{poly}(n) (the “promise gap”), and one must decide which is the case.

In the quantum setting, we allow the Merlins to share initial entanglement, but they can’t communicate after that. Now the value is denoted by \omega^*(G) = \sup_{\textrm{Merlins}} \textrm{Pr}[\text{Arthur accepts}]. The star denotes this additional quantum entanglement shared by the Merlins.

Can Arthur use the entangled Merlins to his advantage, to recognize languages beyond NP? The Peres-Mermin “magic square” game makes this unclear since at least in some cases the Merlins can “cheat” and use entanglement to increase the acceptance probability. But it was shown [KKMTV 08, IKM 09] that Arthur can still use entangled Merlins to at least recognize languages in NP. An aside: this, like most previous work, viewed the entanglement between the Merlins mostly as a drawback to be mitigated using techniques like monogamy relations that force the provers to use strategies that resemble unentangled strategies.

To illustrate the difficulties, suppose we have a 1D Hamiltonian with nearest-neighbor interactions. Suppose that these are anti-ferromagnetic so that the unique ground state of each two-qubit term is the singlet, which we say has zero energy. This is of course highly frustrated and the ground-state energy will be proportional to the number of qubits. But a naive two-prover proof system would allow us to be convinced that the ground-state energy is zero. Suppose we can split the qubits into even and odd layers that are mutually commuting. We can have Merlin-1 take the odd qubits and Merlin-2 take the even qubits. We choose a random interaction, say on sites j and j+1, and ask Merlin-1 for one of them and Merlin-2 for the other. But this doesn’t work. The Merlins need only share a singlet state which they just return regardless of which question we ask.

The main result is a five-player game for the 3-local Hamiltonian problem. The messages from the Merlins to Arthur are quantum, but very short. The value of the game with n classical questions, 3 answer qubits, and with 5 players is QMA-hard to compute to within a 1/\mathrm{poly}(n) factor. Consider the ground state of the Hamiltonian encoded in the 5-qubit code. We will require the five Merlins to each have one share of these encoded qubits, so each Merlin has n qubits.

The protocol is as follows. Pick a random clause H_l on qubits i,j,k and either:

  1. energy check
    1. ask each Merlin for his share of i,j,k
    2. decode
    3. measure H_l
  2. code check
    1. ask one Merlin for his share of i,j,k
    2. ask other Merlins for their share of i
    3. verify that qubits lie in code subspace.

The intuition is that the Merlins are forced to be in a code space, with the states of 4 Merlin constraining the fifth. How is this proven?

The most general Merlin strategy is to share a state |\psi\rangle and to respond to a request for qubit i by applying a unitary U_i, or to a request for i,j,k with the unitary V_{i,j,k}. We would like to argue that any such strategy can be turned into a method for extracting all n qubits from the state |\psi\rangle.

This will be done using a method similar to a mosquito drinking blood: as it extracts blood it replaces the volume of liquid with its saliva. Here we extract a qubit i using U_i (actually U_i^{(1)}, \ldots, U_i^{(5)}), and then replace those qubits with halves of EPR pairs and then each prover applies U_i^\dagger. Actually, the other halves of the EPR pairs are never used so even a maximally mixed state would work. The point is just to put something there, effectively performing a logical SWAP.

This work also leads to a natural reformulation of the quantum PCP conjecture: Constant-factor approximations to the entangled value of a quantum game with entangled provers \omega^*(G) are QMA hard. The result is a first step in this direction by solving the case of a 1/\mathrm{poly}(n) factor.

Another consequence is for MIP and related complexity classes. MIP(c,s) refers to the class of problems with a multi-prover interactive proof with completeness c and soundness s. In this language the PCP theorem implies that NEXP=MIP(1,1/2).

In the quantum case Thomas proved that NEXP \subseteq (Q)MIP^*(1,1/2) in an earlier breakthrough. This work shows now that QMA_{EXP} is contained in MIP*(1-2^{-p}, 1-2^{-2p}), proving for the first time that entanglement increases the power of quantum proof systems. Here “proving” is in the usual complexity-theory sense, where we have to make some plausible assumption: in this case, that \text{QMA}_{\text{EXP}} \not\subseteq \text{NEXP}.

During the questions, Ronald de Wolf and Daniel Gottesman pointed out that you might be able to reduce it from 5 Merlins to 4 by using error-detecting codes, or even 3 by using qutrit quantum error-detecting codes. Or what about 2 using approximate QECC? (This last probably won’t work.)


Sergey Bravyi and Matthew Hastings. On complexity of the quantum Ising model
abstract arXiv:1410.0703

(This talk was presented by the heroic David Gosset because Sergey didn’t get a visa in time.)

The transverse Ising model (TIM) is important for several reasons. For one thing, this model is ubiquitous in the theory of phase transitions. It’s a good model of certain non-universal quantum devices like the D-wave machine. And the recent breakthrough of Cubitt and Montenaro shows that the TIM appears naturally as a possible intermediate complexity class.

We would love to understand the quantum annealing (QA) algorithm of Farhi et al., and unfortunately we won’t be able to do that here. But we can use it to help us understand a target-simulator model that lets us do reductions of various Hamiltonian complexity problems. An example, if we have a simulator QA machine that has TIM Hamiltonians, then it is unlikely that we can simulate a target QA machine that has access to 2-local Hamiltonians (which are BQP complete). The simulator TIM machine is contained in BQP \cap postBPP, which is unlikely to equal BQP.

Recall the class of “stoquastic” local Hamiltonians. These are local Hamiltonians with “no sign problem”, meaning that all off-diagonal matrix elements in the computational basis are real and non-positive. There is a natural complexity class, StoqMA, that captures the complexity of these Hamiltonians.

StoqQMA is like QMA but Arthur can only apply reversible classical gates (CNOT, Toffoli) and measure some fixed qubit in the X basis. He accepts iff the measurement outcome is +. He can use 0 and + ancillas.

StoqMA’s relation to other complexity classes:

  • P \subseteq NP \subseteq MA \subseteq StoqMA \subseteq QMA \subseteq A_0PP
  • StoqMA \subseteq SBP \subseteq PostBPP
  • SBP \subseteq AM \subseteq \Pi_2

(A_0PP and SBP are approximate counting classes.)

Main result: The local Hamiltonian problem for TIM on degree-3 graphs is StoqMA-complete. This sharpens the Cubitt and Montenaro classification by linking the TIM directly to StoqMA.

In the ferromagnetic TIM, the coupling terms are all positive and the Z-field is uniform. Another result is a polynomial-time approximation algorithm for the partition function of the ferromagnetic TIM. This generalizes and in fact makes use of a result of Jerrum & Sinclair from 1993. The run time is polynomial: O(n^{59}). Awesome. Taking the log of the partition function, one gets the free energy within an additive constant, and at low temperature, this approximates the ground state.


Rafael Chaves, Christian Majenz, Lukas Luft, Thiago O. Maciel, Dominik Janzing, Bernhard Schölkopf and David Gross.
Information-Theoretic Implications of Classical and Quantum Causal Structures
abstract arXiv:1407.3800

Given some empirically observable variables, which correlations between these are compatible with a presumed causal structure? This is a fundamental problem in science, as illustrated by the following situation. You would like to claim that smoking causes cancer. But all you have is correlation data… and correlation doesn’t imply causation. So when can we make that inference?

One of the main ideas of this work is to use entropies rather than probabilities in order to avoid headaches associated with nonconvex structure that appears in previous approaches to answering these types of questions.

Classically, Directed Acyclic Graphs (DAG) have edges encoding a causal relationship between the nodes that they connect. Conditional Independences (CIs) are encoded by a DAG; this is the causal structure. A given probability distribution is compatible with a given causal structure if it fulfills all of the CI constraints implied by a given DAG.

Marginal Scenarios: Usually, for a variety of reasons, not all variables in a DAG are observable.

Probabilities compatible with a causal structure are expressible by a polytope, within which they must fall, e.g. Bell’s theorem. However, in an example due to Geiger and Meek, which is symmetric and consisting of three unseen variables each causing two of the three observable events, A, B, and C, we have a geometry that is non-convex.

Classically, going to the entropic description, we get a description of marginal causal entropic cones in terms of the entropic Bell inequalities framework pioneered by Braunstein & Caves in 1988.

A variant of this is the common ancestor problem.

Quantumly, there is not a unique definition of what the causal structure is. What should we use? Informally it should specify the dependencies between a collection of quantum states and classical variables. We use 3 kinds of nodes,

  • Classical
  • Quantum states
  • Quantum operations, i.e. CPTP maps

Because measurement affects a quantum system, some CIs that are classically valid cannot be defined in the quantum case. But independencies still hold and we can use data processing inequality. One consequence is a strengthening of the IC inequality, and allows it to be generalized eg to quantum messages. (see also 1210.1943).


Nicolas Delfosse, Jacob Bian, Philippe Guerin and Robert Raussendorf.
Wigner function negativity and contextuality in quantum computation on rebits
abstract arXiv:1409.5170

What makes quantum computing work? Many explanations have been proffered in the past: entanglement, contextuality, superposition and interference, and even quantum discord. While it seems fair to say that we really have no idea what makes a quantum computer “work” so well, we do have some ideas for some specific models.

The main result of this talk is that contextuality is a necessary resource for universal quantum computation with magic states on rebits. Pro: these are two-level systems; Con: these are not qubits, only “rebits”.

Mermin’s square and Mermin’s star are state-independent proofs of contextuality. They look as if they will spoil the party. But in fact they help.

Previous work by Anders and Browne ’09 showed that contextuality powers measurement based quantum computation, and in 2014 Howard et al. showed that contextuality powers quantum computation with magic states.

In the setting of quantum computation by state injection, we have a restricted family of gates (e.g. Clifford gates) and we have some noisy version of a state that cannot be prepared from that gate set and starting with computational basis states. Which properties must a fiducial state possess in order to “promote” a restricted model of Clifford gates to a universal quantum computer? In work by Joe Emerson’s group, this was answered for odd-prime dimensional qudits that we need:

  • Wigner function negativity
  • Contextuality

Hudson’s theorem characterizes the set of pure states with non-negative Wigner functions: it is precisely the set of state that are Gaussian, aka stabilizer states in the discrete setting. Clifford operations cannot introduce (Wigner) negativity through gate operations, and so that makes negativity a resource for initial magic states. All of this works out very cleanly in the case of odd-prime dimensions.

Mermin’s magic square implies that not all contextuality can be attributed to states. This seems to ruin our “resource” perspective. Not all contextuality that’s present can be attributed to states. What’s worse, Mermin’s square yields a contextuality witness that classifies all 2-qubit quantum states as contextual.

To deal with this, we move to rebits, so that the density matrix \rho is restricted to be real with respect to the computational basis for all times. We also have to use a restricted gate set that is CSS-preserving, and purely Clifford. This also affects the state preparations and measurements that are allowed, but let’s skip the details.

Now there is a d=2 Hudson’s theorem: A pure n-rebit state has a non-negative Wigner function if and only if it is a CSS stabilizer state.

Wigner non-negativity then implies that Pauli measurements on \rho are described by a non-contextual hidden variable model. Equivalently contextuality implies negativity of the Wigner function, in our rebit/CSS setting.

There is no contradiction with the Mermin magic square because of the rebit property and the CSS restriction: we cannot measure ZX and XZ simultaneously. Only all-X and all-Z Pauli operators can be measured simultaneously.


Ramis Movassagh and Peter Shor.
Power law violation of the area law in quantum spin chains
abstract arXiv:1408.1657

We’ve already discussed the area law and its important implications for the efficient simulation of gapped 1-dimensional spin systems. We believe that an area law holds for higher-dimensional spin systems if the Hamiltonian is gapped. We also know that 1-dimensional spin-chains can in general be QMA-complete, but the spectral gap shrinks in the hard cases.

These authors have a series of papers on this larger project.
On a spin chain with qudits and random interactions that are projectors of rank r, they showed that

  • The ground state is frustration free but entangled when d \leq r \leq d^2/4.
  • Schmidt ranks were known, but gap/entropy weren’t known.

Then Irani and Gottesman-Hastings used the type of Hamiltonians from 1-d QMA-hardness constructions to obtain Hamiltionians with 1/poly(n) gap and O(n) entropy. The local dimension is “O(1)” but in a CS rather than physics sense (i.e. the constants are big). Some condensed matter theorists have dismissed these Hamiltonians as “fine-tuned.”

Previous work by these authors had frustration-free, 1/poly(n) gap and O(log n) entanglement, but this could still be explained away as being “critical” since this entropy scaling matched what one expected from conformal field theory.

The latest results, with entanglement entropy O(\sqrt{n}) and the same guarantees on the spectral gap, do not match any of the condensed matter theorists’ explanations. They only require spins of dimension 5, so they are much closer to a natural model.

The “Motzkin state” is the ground state in question here that they construct, as they use something called Motzkin paths to construct this Hamiltonian. The ground state of the original construction was a superposition of all Motzkin walks on a chain of length 2n.

We say a Motzkin state is the superposition of all Motzkin walks. A Motzkin walk is a walk that starts at 0, ends at 0, remains nonnegative, and goes up or down or remains level at each intervening step. Our Mozkin walks can have two kinds of up step and two kinds of down step. Our Hamiltonian introduces a penalty for violating the Motzkin rule.

The reason that these states can lead to entanglement is that the amount that it goes “up” on the left half of a cut must equal the amount that it goes “down” in the right half.

Combinatorially we know how many Motzkin walks there are of height m, number of kinds of step s, and length n. Turning the sum into an integral and doing saddle point integration we get the entanglement.

One can implement the constraints of a colored Motzkin walk with local constraints, and these become the terms in the local Hamiltonian. You can get an upper bound on the spectral gap using the variational principle. The lower bound can be obtained using similar techniques as the previous results by the authors and others.

Is there a continuum limit for these models? Can we rigorously prove these results with an external magnetic field that can eliminate the need for boundary conditions? Are there frustration-free Hamiltonians with unique ground states and no boundary conditions that violate the area law by large factors?


Hector Bombin.
Gauge color codes and Single-shot fault-tolerant quantum error correction (Plenary Talk)
abstract-89 arXiv:1311.0879 abstract-90 arXiv:1404.5504

Fault-tolerant gates are great, but they can’t be done in a transversal way and still be universal. This is the celebrated Eastin-Knill theorem. In the context of topological quantum error-correcting codes, there is a natural relaxation of the notion of transversal gates to finite-depth quantum circuits [Bravyi-Koenig’09].

Color codes are an interesting class of topological stabilizer codes that allows for a transversal implementation of a T gate in three dimensions. It generally saturates the Bravyi-Koenig bound on the Clifford hierarchy for transversality. Hector has generalized his color codes to a subsystem code version. The recent important paper by Paetznick and Reichardt introduced the notion of gauge fixing that lets us jump between different codes with different transversality restrictions, and this let’s us sidestep the Eastin-Knill theorem. The new gauge color codes can be combined with this gauge-fixing idea to move between conventional color codes and gauge color codes. In these two codes, there are two different sets of operations that together are universal.

In typical fault-tolerant methods, we make noisy syndrome measurements and we repeat them several times to avoid errors. The decoding step is a global classical calculation and the correction is a transversal quantum operation. Hector’s new paradigm of single-shot fault tolerance is a way to avoid the multiple rounds requirement in the old method.

3D color codes turn out to be single-shot fault tolerant (SSFT). This is because the gauge degrees of freedom have some redundancy and this can be used to make inferences about which stabilizer measurements might have been faulty. The notion of SSFT is closely linked to the notion of self-correction via the physical mechanism of confinement. As a simple example, consider the ferromagnetic Ising model in a symmetry-broken state below the critical temperature. Anti-aligned magnetic domains are confined in this phase. The following week Poulin gave a talk at Coogee that was skeptical about the possibility of single-shot fault tolerance. Definitely this notion needs to be made more precise.

Suppose we want to do fault-tolerant error correction in a gauge color code. A faulty gauge syndrome will be one with endpoints, and we can repair the gauge syndrome, with the branching points of the result giving the new syndrome. Importantly, the gauge syndrome is unconfined; it is random except for the fixed branching points. The effective wrong part of the gauge syndrome, however, is confined. Each connected component has branch points with neutral charge. Therefore the branching points exhibit charge confinement. This sounds intriguing, but none of the Pontiffs really understand the details.

Gauge fixing to either Z or X with give you either a transversal implementation of either T or HTH, and this lets you perform arbitrary gates on the encoded logical qubit.

Bonus Result: 3d quantum computation, with local operations and constant time overhead, but global classical computation. This uses the 3d color code for computation with a stack of 2d codes for memory; see arXiv:1412.5079 for details.


Courtney Brell.
Self-correcting stabilizer quantum memories in 3 dimensions or (slightly) less
abstract arXiv:1411.7046

We’ve previously blogged about this very interesting result here. But now there’s a problem! The thermodynamic considerations all still seem to hold, and the Hausdorff dimension of the code is still 3 or less, but the specific embedding theorem that Courtney had used previously doesn’t not apply. Therefore, it is still open if this code can be embedded in 3 dimensions with constant density. Courtney is currently working to fix the proof, but for now the embeddability of these codes is downgraded to a conjecture.

Courtney also gave a heuristic argument for why this embeddability conjecture might be true. In the limit of low lacunarity (which is basically a measure of how much a fractal violates translation invariance) there is a simple condition that says that the density of a projection stays bounded.

Two interesting tools that Courtney uses for the thermodynamic arguments that might have broader interest are the GKS inequality, which says that adding ferromagnetic interactions cannot reduce ferromagnetic order, and Merlini-Gruber duality, which is a duality similar to the Kramers-Wannier duality used to prove the phase transition in the Ising model.


Henrik Wilming, Rodrigo Gallego and Jens Eisert.
Universal operations in resource theories and local thermodynamics
abstract arXiv:1411.3754

This talk takes a resource-theory approach to thermodynamics. The goal is to extract work from a state, given various types of permitted free operations and a possibly limited ability to change the Hamiltonian by investing work. For each class of operations, the Gibbs state is a “free” state, analogous to product states in entanglement theory. The options are

  • weak thermal contact: Bringing the system in contact with the heat bath puts it into thermal equilibrium.
  • thermal operations: More generally are any energy-conserving unitary operations on the heat bath and the system. A much larger set of operations than weak thermal contact.
  • A still larger class of maps comprises all quantum channels that have the Gibbs state as a fixed point: call these Gibbs-preserving (GP) maps. GP maps can sometimes take a point below the thermal curve to a little bit above, without violating the 2nd law.

How effective these different models are at extracting work depends on the class of Hamiltonians allowed. If any Hamiltonians are allowed then there is a collapse and weak thermal contact can do as well as GP maps (and of course also thermal operations), essentially extracting all surplus free energy of a state. If we restrict the class of possible Hamiltonians then separations between these models are possible, in part because it’s harder to deal efficiently with off-diagonal terms in the density matrix.

Posted in Conferences, Liveblogging | 2 Comments

QIP 2015 dead-blogging, Day 4

Warning for typical QIP attendees —
This first talk may have some implications for the real world 🙂

Andrea Mari, Vittorio Giovannetti, Alexander S. Holevo, R. Garcia-Patron and N. J. Cerf.
Majorization and entropy at the output of bosonic Gaussian channels.
Previous Title: Quantum state majorization at the output of bosonic Gaussian channels (Plenary Talk)
abstract arXiv:1312.3545

The solution of the Gaussian optimizer conjecture by Giovannetti, Holevo, and Garcia-Patron has led to enormous progress on a web of interconnected connected conjectures about Gaussian channels. This includes the phase space majorization conjecture, the additivity and minimum output Renyi entropies conjectures, strong-converse theorems for the classical capacity of gaussian channels, the entropy-power inequality conjecture, and more! The only remaining open questions are the entropy-photon number inequality and the quantum capacity.

The proof uses a decomposition of Gaussian channels. Every phase-insensitive Gaussian channel is equivalent to a quantum-limited attenuator followed by a quantum-limited amplifier. Every phase-contravariant Gaussian channel is equivalent to a quantum-limited attenuator followed by a quantum-limited amplifier followed by a noiseless phase conjugation.

It also uses an old result about quantum beam splitters. How can the output of a beamsplitter be distinguished from two independent broadcasts of the same source? Answer: only if the broadcast was a coherent state. Therefore we have the “golden property” of a quantum beam splitter: the only input states producing pure output states for a quantum limited attenuator are coherent states.

The main result of this talk is a proof of the majorization conjecture. This addresses the question: what is the minimum noise or disorder achievable at the output state, optimizing over all possible input states? The output from a coherent input state majorizes all other output states. Namely, if \Phi is a Gaussian channel, then
\Phi(\lvert\alpha\rangle\!\langle\alpha\rvert) \succ \Phi(\rho) for all \rho,  \lvert\alpha\rangle.

The proof uses the decomposition results mentioned above, concavity of entropy, and the breakthrough results of Giovannetti, Holevo, and Garcia-Patron. A similar result holds for any Renyi p entropy for p > 1. There is also a phase space majorization result.

Here is an awesome summary of what this research project has accomplished.
solved.


Runyao Duan and Andreas Winter. No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number. Previous title: Zero-Error Classical Channel Capacity and Simulation Cost Assisted by Quantum No-Signalling Correlations
abstract arXiv:1409.3426

Coming the morning after the conference dinner, Andreas beings with a “hangover summary” of the main results:

  1. C_0(G) \le \log \vartheta(G) (sometimes known to be strict)
  2. C_{0,E}(G) \leq \log \vartheta(G)
  3. C_{0,NS}(G) = \log \vartheta(G)

On the LHS we have the asymptotic zero-error capacity of a channel, assisted either by nothing (C_0), entanglement (C_{0,E}) or no-signalling correlations (C_{0,NS}). On the RHS we have the Lovasz theta number (see below) which can be calculated efficiently using semidefinite programming.

Classical zero-error capacity depends only on the transition graph, not the probabilities. A useful notion is that of confusability graph, which is an undirected graph on the input symbols of the channel where two symbols are confusable if there is a nonzero probability of confusing them. This encodes the combinatorics of the channel in a natural way. For example, product channels have a product confusability graph whose adjacency matrix is the tensor product of the confusability graphs of the factor channels. (More precisely I+ A(N\times N') = (I+A(N)) \otimes (I + A(N')).)

The largest codebook for this channel is given by the independence number of the confusability graph; this gives the optimal zero-error capacity. It’s unfortunately NP-complete to compute this property of a graph, and even approximating it is NP hard. However, a seminal result due to Lovasz gives a convex relaxation of this into a semidefinite program, the Lovasz theta number.

\alpha(G) \leq \vartheta(G) = \max \mathrm{Tr}(BJ)  \mbox{ s.t. } B\succeq 0,\ \mathrm{Tr} B=1,\ B_{xy} = 0 \mbox{ for all } x,y \in G
Another useful bound is the so-called fractional packing number, obtained by writing down the natural integer program for independence number and replacing the w_x\in \{0,1\} constraint with 0\leq w_x \leq 1, then observing that the upper bound is superlative:
\leq \alpha^*(\Gamma) = \max_x w_x \mbox{ s.t. } w_x \geq 0, \mbox{ and } \forall y \sum_x \Gamma(y|x) w_x \leq 1.
Minimizing over \Gamma consistent with G gives \alpha^*(G) = \min_{\Gamma\sim G} \alpha^*(\Gamma).

Crucially, both the Lovasz theta number and the fractional packing number are multiplicative, and therefore they bound not only the independence number, but also the capacity. Andreas said something surprising: If f(G) is multiplicative and satisfies \alpha(G) \leq f(G) \leq \vartheta(G), then we must have f(G) = \vartheta(G)! This is unpublished still, but follows from the beautiful formula [personal communication from Winter, via my memory, so hopefully not too wrong]:
\vartheta(G) = \sup_H \frac{\alpha(G\times H)}{\vartheta(H)}.
Compare with a similar formula for the fractional packing number:
\alpha^*(G) = \sup_H \frac{\alpha(G\times H)}{\alpha(H)}.

An example, in fact the usual example, is the “typewriter graph”. This has an input x\in\mathbb{Z}_5 and output y \in \{x,x+1\}. Then \alpha(G) = 2, \alpha(G\times G) =5 > \alpha(G)^2, \vartheta(G) = \sqrt{5} (thus giving a tight upper bound on the capacity) and \alpha^*(G) = 5/2.

We would like to close the gap provided by the above relaxations by allowing additional resources in the encoding and decoding. Shannon did this in his 1956 paper by allowing feedback, and we can also add entanglement and no-signaling correlations.

The Lovasz theta number is in fact an upper bound to the entanglement-assisted zero-error capacity, which sometimes is larger than the unassisted zero-error capacity. This gives an operational (but partial) explanation of why the Lovasz theta function is not always a tight upper bound.

On the other hand, the fractional packing number is equal to the non-signalling-assisted capacity, which is an awesome and nontrivial result.

Now what about the quantum case? Here things get even cooler, although not everything is as well understood. For quantum channels, the quantum generalizations of the transition and confusability graphs are given by the following correspondences:
K = \text{span}\{E_i\} and S = K^\dag K = \text{span} \{E_i^\dag E_j\}.

The authors have also also generalized (as in Will Matthews’ talk earlier) the notion of no-signalling operations to ones that take quantum inputs and outputs. Just as the classical no-signalling polytope is a small linear program, this quantum set has a nice SDP characterization.

Now consider \Upsilon(K) = \max \sum_x s_X \mbox{ s.t. } 0 \leq R_x \leq s_x \Pi_x^\perp\sum_x (R_x + s_x \Pi_x) = I. This is
\leq A(K) = \max \sum_x s_x \mbox{ s.t. } 0 \leq s_x, \sum_x s_x \Pi_x \leq I.
Then the “most amazing thing”, according to Andreas, is the following theorem:
C_{0,NS}(K) = \lim \frac{1}{n} \log \Upsilon(K^{\otimes n}) = \log A(K).
Note that this is not just an inequality, but an actual equality!

They show actually that \Upsilon(K^{\otimes n}) \ge n^{-c} A(K)^n.
The proof is reminiscent of the recent and inexplicably not-invited Fawzi-Renner breakthrough on the quantum conditional mutual information.

Now in terms of G, instead of K, \min A(K) = \vartheta(G), which is the first information-theoretic application of the Lovasz theta function.

Some of the closing remarks were that

  • SDP formulas for assisted capacity and simulation cost (one shot)
  • SDPs can regularize to relaxed SDPs!
  • Capacity interpretation of Lovasz theta number
  • Is there a gap between C_{0,E}(G) and \log\vartheta(G)?
  • Is regularization necessary?

Mario Berta, Omar Fawzi and Volkher Scholz.
Quantum-proof randomness extractors via operator space theory;
abstract arXiv:1409.3563

This talk is about producing high-quality (i.e. nearly uniform) randomness from [necessarily longer] strings that contain “lower-quality” randomness. Tools for doing this are called extractors; other closely related tools are condensers and expanders. Why would we need to do this? Well suppose we start with some uniform randomness and then leak some information about it to an adversary (Eve). Then Eve’s subjective view of our randomness is no longer uniform. Applying an extractor can make it again close to uniform. Even in a non-cryptographic setting they can be useful. Suppose we run a randomized algorithm using some large uniformly random seed. Conditioned on the output of this algorithm, the seed will no longer be uniformly random. If we want to continue using it, maybe even for later steps of a larger algorithm, we will need to clean it up using something like an extractor.

This establishes the need for extractors and their crucial property: their goal is to make a string random conditioned on some other string (e.g. Eve’s knowledge, or the earlier outputs of the randomized algorithm; call this the “side information”). This talk will consider the case when side information is in fact quantum. Conditioning on quantum things is always tricky, and one hint that the math here will be nontrivial is the fact that “operator space theory” is in the title.

One unpleasant fact about extractors is that they cannot be deterministic (this is a useful exercise for the reader). So they usually use some extra input, guaranteed to be uniform and independent of the source. The smallest possible seed size is logarithmic in the input size. Also the number of output bits can be (more or less) no larger than the min-entropy of the source. So the key parameters are the input size, the input min-entropy, the input seed size, the number of output bits and their trace distance from being uniform and independent of the side information.

One example of a nice classical result is the leftover hash lemma.

Can we still get the same result if adversary is quantum? This will have implications for privacy amplification in q crypto and also (not sure why about this one) properties of q memory.

Here min-entropy becomes the conditional min-entropy, which involves a maximization over all guessing strategies and measures knowledge of an adversary with access to a q system correlated with the source.

The main result here is a mathematical framework to study this, based on operator space theory. Why operator space? We can define C(Ext, k) to be the maximum advantage for a classical adversary against the extractor Ext on sources with k bits of min-entropy. The key insight is that this is a norm, specifically an operator norm. Sources with \geq k bits of min-entropy correspond to probability distributions (i.e. \|x\|_1 \leq 1) with all entries \leq 2^{-k}, (i.e. \|x\|_\infty \leq 2^{-k}). The intersection of these two constraints defines a centrally symmetric convex set (if we subtract off the uniform distribution, I suppose), which can then define a norm. One other example of such a hybrid norm is the family of Sobolev norms. Now the achievable bias is like the maximum 1-norm of the output of such a vector when we act on it with the extractor Ext, which we can think of a linear map. So this is an operator norm, i.e. the norm of Ext is the max of the norm of Ext(x) divided by the norm of x, where we measure the numerator in the l_1 norm and the denominator in this funny hybrid norm.

The advantage of a quantum adversary is Q(Ext, k) which is like the cb (completely bounded) version of the above. Basically suppose that instead of the entries of x being numbers they are matrices. This is kind of like what team Madrid did with nonlocal games.

They also define an SDP relaxation which has the advantage of being efficiently computable.

It follows trivially from the definitions that
C(Ext,k) \leq Q(Ext,k) \leq SDP (Ext, k).

The nontrivial stuff comes from the fact that the SDP relaxations are in some cases analytically tractable, e.g. showing that small-output and high input entropy extractors are quantum-proof (i.e. secure against quantum adversaries).

A nice open question: Given that there is an SDP, can we define a convergent hierarchy?


Richard Cleve, Debbie Leung, Li Liu and Chunhao Wang.
Near-linear construction of exact unitary 2-designs
abstract

The basic idea of a unitary t-design is that it is a discrete set of unitary operators that exactly reproduce the first t moments of the Haar measure, i.e. the uniform measure on the unitary group. This construction lets us sample efficiently and still reproduce important properties of the Haar measure. But we don’t just want constructions with small cardinality, we also want them to have efficient gate complexity.

The speaker jokingly says, “unfortunately, these have a lot of applications.” This includes randomized benchmarking, decoupling and error-tolerant QKD schemes. There is another joke about how decoupling doesn’t mean breaking up (romantic) couples. But if Alice and Bob are entangled, and one passes through a decoupling map, then they end up nearly separable! That sounds like a breakup to me. Note that a weaker randomizing map would merely leave them with a data hiding state, which I suppose corresponds to the facebook status “It’s Complicated.” These jokes are still in focus groups, so please forgive them.

We would like to have unitary designs that have low gate complexity. The main result of this talk is a Clifford-only unitary 2-design that uses O(n \log n \log \log n) gates, but it assumes an extension of the Riemann hypothesis. Without this hypothesis, they also have a non-Clifford construction with the same complexity, and a Clifford-only scheme with complexity O(n \log^2 n \log \log n). Sampling uniformly from the Clifford group has gate complexity O(n^2/\log n), so this is an improvement.

One can construct these 2-designs by writing gates in the form S^{\otimes n} H^{\otimes n} M_r, where the matrix M_r has a decomposition with low complexity that is the main technical contribution of the authors. By using the result that Pauli mixing by conjugation implies unitary 2-design, one only needs to consider certain forms of the matrix M_r. Ronald de Wolf suggested that these results could be improved a bit further by using the fast integer multiplication algorithms due to Fürer.


Carl Miller and Yaoyun Shi.
Universal security for randomness expansion. Previous title: Universal security for quantum contextual devices
abstract arXiv:1411.6608

Carl opens his talk by saying that this result has been a goal of the U of M group for the past four years. It then proceeds in suitably epic fashion by looking up the definition of randomness from The Urban Dictionary (highlight: “A word often misused by morons who don’t know very many other words.”) and moving onto modern cryptographic standards (skipping, though, this gem).

This talk follows the research program laid out by Colbeck in 2006, where he suggested that one might take the output of some CHSH games, verify that the winning probability is higher than the optimal classical value, and then apply a deterministic extractor. Difficulties here involve quantum side information, information locking, and the other nuisances that composable security was invented to address. Vazirani-Vidick showed in 2011 that this was possible if in the honest case the Bell inequality is violated optimally, last QIP Miller and Shi showed it worked with some not-quite-perfect value of the CHSH game and the current result extends this to any beyond-classical value of the game.

One the key technical ingredients is a new uncertainty principle.
We will not fully do it justice here. Roughly it is as follows. Define
Y = \text{tr} [\rho_+^{1+\epsilon} + \rho_-^{1-\epsilon}] / \text{tr}[\rho^{1+\epsilon}] and X = \text{tr} [\rho_0^{1+\epsilon}] / \text{tr} [\rho^{1+\epsilon}] where \{\rho_0,\rho_1\} and \{\rho_+,\rho_-\} are the post-measurement states resulting from a pair of anticommuting measurements on \rho. Given this, the Miller-Shi uncertainty principle states that the pair (X,Y) must fit into a particular region of the plane. (see eq (2.2) of their paper for a bit more detail.)

The proof uses the “uniform convexity of the S_{1+\epsilon} norm” due to Ball, Carlen, & Lieb (see also this note). Carl suggests there are more applications. Fernando Brandao and I [Aram] have one! Stay tuned.

At one point Carl says: “By an inductive argument (which actually takes 20 pages), we see that…”

The result can then be generalized beyond X-Z measurements to any pair of non-commuting measurements.

Now what about totally untrusted devices? These too can be forced, using a VV-like approach, to act in a way as though they are performing non-commutative measurements.

This can be generalized even further to Kochen-Specker inequalties and contextuality games, modulo some mild assumptions on how the device works.

open problems: what resources are used? This uses a linear amount of entanglement, for example. For any experimentalists watching (for whom entanglement is scarce and randomness abundant), this part of the talk must sound funny.

Neil J. Ross and Peter Selinger.
Optimal ancilla-free Clifford+T approximation of z-rotations (Plenary Talk)
abstract arXiv:1403.2975

Solovay-Kitaev was all about geometry, but recently the field of quantum compiling has shifted to algebraic number theory, following the path-breaking 2012 paper by Kliuchnikov, Maslov, and Mosca.

Some number theory: In the ring \mathbb{Z}[\sqrt{2}] define (a+b\sqrt{2})^{\bullet} = a-b\sqrt{2} and the norm N(a) := \sqrt{a^\bullet a}.

Applying the bullet operation (a Galois automorphism of the number field) to a compact interval yields a discrete unbounded set. The 1-d grid problem is, given finite intervals A, B \subset \mathbb{R}, find an element of A\cap B^{\bullet}. Generically there will be O(|A|\cdot |B|) solutions, and these are easy to find when both |A| and |B| are large, corresponding to a fat rectangle (when \mathbb{Z}[2] is viewed as a 2-d lattice). When we have a long thin rectangle we can convert it into this case by rescaling.

The 2-d grid problem: Now we consider \mathbb{Z}[\omega] for \omega=\exp(2\pi i /8). This turns into a more complicated set intersection problem on a 2-d lattice whose details we omit. But just like the rescaling used for 1-d, now we use a more complicated set of shearing operators to transform the problem into one where the solutions are easier to find. But we need an extra property: the “uprightness” of the rectangles.

Main Theorem: Let A and B be two convex sets with non-empty interior. There is is a grid operator G such that both G(A) and G^\bullet(B) are both 1/6 upright. Moreover, it can be efficiently computed.

Theorem [Matsumoto-Amano ’08]
Every Clifford + T single-qubit operator W can be uniquely written in the form
W = (T | eps) (HT | SHT)* C,
where C is a Clifford.

Exact synthesis of the Clifford+T operators was solved by Kliuchinikov, Maslov, and Mosca. If You have W a 2-by-2 unitary operator, then it is Clifford+T iff the matrix elements are all of the form \frac{1}{2^{k/2}} \mathbb{Z}[\omega]) where \omega = \sqrt{i}. Moreover, if \det W = 1, then the T-count of the resulting operator is equal to 2k-2.

The upshot of this is that if you have a factoring oracle then the algorithm gives circuits of optimal T-count. In the absence of such an oracle, then this returns a nearly optimal T-count, namely the second-to-optimal T-count m plus a term of order O(\log\log 1/\epsilon).


Adam Bouland and Scott Aaronson.
Generation of Universal Linear Optics by Any Beamsplitter
abstract arXiv:1310.6718

Are there any interesting sets of beamsplitter-type quantum gates that don’t generate either only permutation matrices or arbitrary unitaries? The main result is that if one has a two-level unitary of determinant 1 and with all entries non-zero, then it densely generates SU(m) or SO(m) for m \ge 3. In other words, any beamsplitter that mixes modes is universal for three or more modes. Another way to say this is that for any beamsplitter b, either b is efficiently classically simulable or else it is universal for quantum optics. This is a nice dichotomy theorem. The proof requires the classification of the finite subgroups of SU(3), which was, surprisingly, completed only in 2013. (It was written down in 1917 as “an exercise for the reader” but educational standards have apparently come down since then.)


Isaac Kim.
On the informational completeness of local observables
abstract arXiv:1405.0137

2014 has seen some of the most exciting news for quantum conditional mutual information since strong subadditivity.

The goal of this talk is to try to find a large class of interesting states S such that quantum state tomography and quantum state verification can be done efficiently. We would like to also have that if a state is in S then we can efficiently verify that fact.

At one point in the intro, Isaac says that a point is “…for the experts, err, for the physicists.” Then he remembers who his audience is. Later he says “for this audience, I don’t have to apologize for the term ‘quantum conditional mutual information'”.

This talk proposes a class S_n that has this verification property in time O(n) where n is the number of particles. Any state in S_n is defined by a set of O(1)-particle local reduced density operators.

Isaac first reviews the approach to matrix product state tomography, which uses the parent Hamiltonian of a matrix product state to show that any (injective) MPS is completely determined by a local set of observables. This result is a generalization of the MPS tomography result to higher dimensions, but with the important difference that there is no need for a global wavefunction at all!
The main result, roughly speaking, is that there exists a certificate \epsilon(\{\rho_k \mathcal{N}_k\}) such that
|\rho - \rho'|_1 \le \epsilon(\{\rho_k \mathcal{N}_k\}).

Local density matrices can (approximately) reconstruct the global state. Previously this was done assuming that the global state is a low-bond-dimension MPS. But that’s in a sense circular because we have to make a (strong) assumption about the global state. This work allows us to do this purely using local observables. Awesome.

The talk proceeds by giving a reconstruction procedure by which a global state \rho' can be reconstructed from the marginals of a state \rho, and by showing conditions under which \rho\approx \rho'. The global state is completely determined by the local reduced density operators if the conditional quantum mutual information is zero.

Theorem 1: If \rho_{AB} = \sigma_{AB} and \rho_{BC} = \sigma_{BC} then
\frac{1}{4} \|\rho_{ABC} - \sigma_{ABC}\|_1^2 \leq I(A:C|B)_\rho + I(A:C|B)_\sigma

This is nice, but the upper bound depends on global properties of the state. (Here we think of AB and BC as “local” and ABC as “global.” Don’t worry, this will scale well to n qubits.)

To proceed we would like to upper bound the QCMI (quantum conditional mutual information) in terms of locally observable quantities. This is a straightforward but clever consequence of strong subadditivity. Specifically
I(A:C|B) \leq S(CF) - S(F) + S(BC) - S(B)
for any system F.
For judicious choice of regions, and assuming a strong form of the area law conjecture (S(A) = a |\partial A| - \gamma + o(1) in 2-d), this bound is effective.

We can then build up our reconstruction qubit-by-qubit until we have covered the entire system.

Applications:

  • quantum state tomography: Measure local observables and check the locally computable upper bound. If the latter is small, then the former contains sufficient information to reconstruct the global wavefunction.
  • quantum state verification: Similar except we want to just check whether our physical state is close to a desired one

Bartek Czech, Patrick Hayden, Nima Lashkari and Brian Swingle.
The information theoretic interpretation of the length of a curve
abstract arXiv:1410.1540

At ultra-high energies, we need a theory of quantum gravity to accurately describe physics. As we move down in energy scales, vanilla quantum field theory and eventually condensed-matter physics become relevant. Quantum information theory comes into play in all three of these arenas!

One of the principal claims of this talk is that quantum information is going to be central to understanding holography, which is the key concept underlying, e.g., the AdS/CFT correspondence. Quantum gravity theories in negatively curved spacetimes (saddle-like geometries) seem to have a duality: one Hilbert space has two theories. The duality dictionary helps us compute quantities of interest in one theory and map the solutions back to the other theory. It turns out that these dictionaries often involve computing entropic quantities.

A funny feature of AdS space is that light can reach infinity and bounce back in finite time! This acts just like boundary conditions (at infinity) and simplifies certain things. Inside the bulk of AdS space, geodesics are (in the Poincare disk model) just circular arcs that meet the boundary at right angles. When there is matter in the bulk, these get deformed. We’d love to be able to interpret these geometric quantities in the bulk back in the CFT on the boundary.

The Ryu-Takayanagi correspondence links the length of a geodesic in the bulk with the entanglement entropy in the CFT on the boundary. This can be related (using e.g. work by Calabrese & Cardy) to the central charge of the CFT. A really neat application of this correspondence is a very simple and completely geometric proof of strong subadditivity due to Headrik and Takayanagi (with the important caveat that it applies only to a restricted class of states, namely those states of CFTs that have gravity duals).

The new result here is to generalize the Ryu-Takayanagi correspondence to general curves, not just geodesics. The main result: there is a correspondence between the length of convex curves in the bulk and the optimal entanglement cost of streaming teleportation communication tasks that Alice and Bob perform on the boundary.

Posted in Conferences, Liveblogging | 4 Comments

QIP 2015 “live”-blogging, Day 3

We promise we’ll finish posting these soon! Day 3 was only a half day of talks with a free afternoon, and the rainy weather of the first two days finally subsided just in time.

Jean-Pierre Tillich
Decoding Quantum LDPC Codes
abstract

LDPC codes are families of sparse codes, meaning that the stabilizers are all low weight, and we usually also require that each qubit partakes in at most a constant number of stabilizers. That is, the parity check matrix is both row and column sparse with constant sparsity per row and column.

The classical versions of these codes are ubiquitous; your cell phone uses LDPC codes, for example. One of the principle advantages of (classical) LDPC codes is that they have good minimum distance, constant rate, and have fast nearly optimal decoders. A new variant called spatially coupled LDPC codes are a universal way (i.e., independent of the channel) to get capacity for most memoryless channels of interest with a low-complexity decoder.

Unfortunately, the quantum case is largely open still, and the speaker admitted in the first moment that he wasn’t going to solve everything during his talk. Leaving aside the question of distance of quantum LDPC codes, one of the reasons why decoding a quantum code is hard is that any error E has the same syndrome as ES if S is in the stabilizer group. This added degeneracy creates an extra freedom that is difficult to account for in a decoder. You want to find the most likely coset, rather than the most likely error.

In a classical LDPC code, the Tanner graph (the bipartite graph whose nodes are bits and checks with edges whenever a collection of bits partake in the same check) is nearly tree-like (it’s an expander) and so message passing algorithms perform nearly at capacity. In the quantum case, the Tanner graph contains many 4-cycles, and message passing decoders get stuck in loops and don’t converge.

Bravyi, Suchara, and Vargo have recently had a breakthrough where they were able to decode a very special quantum LDPC code near the hashing bound: the toric code. But didn’t we already know how to decode the toric code? Yes, of course, there are many good decoders for this code. However, none of them achieve a performance that decodes X and Z errors simultaneously with performance approximately equal to the maximum a posteriori (MAP) decoder.

There are also a new idea, pioneered for polar codes by Renes, Dupuis, and Renner and expanded by Delfosse and Tillich, to use asymmetric codes and decoders. If you are going to decode X first and then Z, why not use a stronger code for X errors, decode them first, and then use the advantage to help you decode the Z after that? Using this idea, you can provably achieve the hashing bound asymptotically.

He concludes with some bright spots: recent global analysis of local decoders (such as the recent work by Hastings on hyperbolic codes), and tricks like entanglement-assisted codes or spatially coupled quantum LDPC codes might lead to capacity achieving decoders soon.


Fernando Pastawski and Beni Yoshida.
Fault-tolerant logical gates in quantum error-correcting codes
abstract arXiv:1408.1720

A great intro: “My paper is at 1408.1720 + PRA…I forgot the full journal reference. You can look it up, which is what people usually do.” Or they just get it from the arxiv!

Fault-tolerant logical gates are central objects in quantum computation. We need them to suppress the spread of errors in computations. Unfortunately, there is a somewhat stringent no-go theorem due to Eastin and Knill that says you cannot have a universal set of transversal gates. (There are various ways around this theorem, such as recent work by Paetznick and Reichard.)

Recently, Bravyi and Koenig have generalized this work. They extend the notion of transversal gate to the idea of a constant-depth circuit and show that constant-depth circuits restrict the allowable gates performable in topological codes to certain levels of the Gottesman-Chuang hierarchy. The main idea of the proof is to use a cleaning lemma. If you can split your code into m+1 correctable regions, then you can only implement gates in level m of the Clifford hierarchy. In particular, D-dimensional topological codes can be split into D+1 correctable regions, so we can only implement gates at level D in the hierarchy.

What Yoshida and Pastawski have done is show that if you have a code with a loss tolerance threshold p_{\mathrm{loss}} > 1/n for some number n, then any transversal gate must be in P_{n-1}. If you have a P_n logic gate, then p_{\mathrm{loss}} \ge 1/n.

Another result is that if a stabilizer Hamiltonian in 3-dimensions has a fault-tolerantly implementable non-Clifford gate, then the energy barrier is constant. The proof is simple: we can split the 3-d chunk of code into correctable regions that have string-like shapes, so there must exist a string-like logical operator for these codes, hence the energy barrier is constant. Beautifully simple!

If you have a topological stabilizer code in D dimensions with an mth level logical gate, then the code distance is at most d\le O(L^{D+1-m}). This improves a bound of Bravyi-Terhal that didn’t take advantage of this m factor.

Lastly, we can consider subsystem codes. In D-dimensions, fault-tolerant gates are in P_D (as long as the code distance grows at least logarithmically in the system size).


For the remaining session, it turns out that no Pontiffs were in the audience. However, we had mostly seen these results in other venues or read them before. They are great results, so go read the papers! We hope the trackback to the arxiv is a small compensation to the authors for our failure to blog these interesting talks.

Marco Piani and John Watrous.
Einstein-Podolsky-Rosen steering provides the advantage in entanglement-assisted subchannel discrimination with one-way measurements
abstract arXiv:1406.0530


Stefan Baeuml, Matthias Christandl, Karol Horodecki and Andreas Winter.
Limitations on Quantum Key Repeaters
abstract arXiv:1402.5927


William Matthews and Debbie Leung.
On the power of PPT-preserving and non-signalling codes
abstract arXiv:1406.7142

Posted in Conferences, Liveblogging | 1 Comment