Quantum in the wild

Sometimes quantum appears out of nowhere when you least expect it.

From the September 2, 2018 edition of the New York Times Magazine.

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. 

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.


  • 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.
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?

Self-correcting Fractals

A really exciting paper appeared on the arxiv today: A proposal for self-correcting stabilizer quantum memories in 3 dimensions (or slightly less), by Courtney Brell. It gives the strongest evidence yet that self-correcting quantum memories are possible in “physically realistic” three-dimensional lattice models. In particular, Courtney has constructed families of local Hamiltonians in 3D whose terms consist of X- and Z-type stabilizer generators and that show phase-transition behavior akin to the 2D Ising model for both the X- and Z-type error sectors. This result doesn’t achieve a complete theoretical solution to the question of whether self-correcting quantum memories can exist in principle, as I’ll explain below, but it makes impressive progress using a mix of rigorous analysis and physical argument.

First, what do I mean by “physically realistic”? Well, obviously I don’t mean physically realistic (without quotes)—that’s a much greater challenge. Rather, we want to abstractly characterize some features that should be shared by a physically realistic implementation, but with enough leeway that a theorist can get creative. To capture this, Courtney introduces the so-called Caltech Rules for a self-correcting quantum memory.

The phrase “the Caltech Rules” is (I believe) attributable to David Poulin. Quantum memory aficionados have been debating these rules in emails and private discussions for the last few years, but I think this is the first time someone has put them in print. As rules, they aren’t really set in stone. They consist of a list of criteria that are either necessary or seemingly necessary to avoid models that are self-correcting for trivial and unphysical reasons (e.g., scaling the coupling strengths as a function of n). In Courtney’s version of the rules, we require a model with finite-dimensional spins (so no bosonic or fermionic models allowed… this might be objectionable to some people), bounded-strength short-range interactions between the spins, a constant density of spins, a perturbatively stable degenerate ground space for the encoded states, an efficient decoding algorithm, and an exponential memory lifetime against low-temperature thermal noise. One might wish to add even more desiderata like translation-invariant couplings or a spectral gap (which is closely related to stability), but finding a self-correcting memory subject to these constraints is already a tall order. For some more discussion on these points, check out another awesome paper that came on the arxiv yesterday, an excellent review article on quantum memories at finite temperature by Ben Brown et al..

To motivate the construction, it helps to remember everyone’s favorite models, the Ising model and the Toric code. When the temperature T is zero, it’s easy to store a classical bit using the 1D Ising model; this is just a repetition code. Similarly, the 2D toric code can store quantum information at T=0. Both of these codes become unstable as memories at T\textgreater 0 because of the presence of string-like logical operators. The physical process by which these strings are created costs some energy, but then the strings can stretch and grow without any energy cost, and thermal fluctuations alone will create enough strings in a short time to cause a decoding failure. By contrast, the 2D Ising model can store a classical bit reliably for an exponential amount of time if you encode in the total magnetization and you are below the Curie temperature. The logical operators are now membranes that cost energy to grow. Similarly, the 4D toric code has such a phase transition, and this is because the X- and Z-type errors both act analogously to 2D Ising models with membranous logical operators.

Sierpinski carpet
Sierpinski carpet, with edges placed to form a “Sierpinski graph”.

The codes that Courtney defines are called embeddable fractal product codes (EFPC). The idea is that, if a product of two 1D Ising models isn’t a 2D self-correcting model, but a product of two 2D Ising models is a self-correcting memory, then what happens if we take two 1.5D Ising models and try to make a 3D self-correcting memory? The backbone of the construction consists of fractals such as the Sierpinski carpet that have infinite ramification order, meaning that an infinite number of edges on an associated graph must be cut to split it into two infinite components. Defining an Ising model on the Sierpinski graph yields a finite-temperature phase transition for the same reason as the 2D Ising model, the Peierls argument, which is essentially a counting argument about the density of domain walls in equilibrium with fixed boundary conditions. This is exactly the kind of behavior needed for self-correction.

Splitting the Sierpinski graph into two infinite components necessarily cuts an infinite number of edges.

Using the adjacency of the Sierpinski graph, the next step is to use a toric code-like set of generators on this graph, paying careful attention to the boundary conditions (in particular, plaquette terms are placed in such a way that the stabilizer group contains all the cycles that bound areas of the fractal, at any length scale). Then using homological product codes gives a natural way to combine X-like and Z-like copies of this code into a new code that naturally lives in four dimensions. Although the natural way to embed this code requires all four spatial dimensions, it turns out that a low-distortion embedding is possible with distortion bounded by a small constant, so these codes can be compressed into three dimensions while retaining the crucial locality properties.

Remarkably, this construction gives a finite-temperature phase transition for both the X- and Z-type errors. It essentially inherits this from the fact that the Ising models on the Sierpinski graph have phase transitions, and it is a very strong indication of self-correcting behavior.

However, there are some caveats. There are many logical qubits in this code (in fact, the code has constant rate), and only the qubits associated to the coarsest features of the fractal have large distance. There are many logical qubits associated to small-scale features that have small distance and create an exponential degeneracy of the ground space. With such a large degeneracy, one worries about perturbative stability in the presence of a generic local perturbation. There are a few other caveats, for example the question of efficient decoding, but to me the issue of the degeneracy is the most interesting.

Overall, this is the most exciting progress since Haah’s cubic code. I think I’m actually becoming optimistic about the possibility of self-correction. It looks like Courtney will be speaking about his paper at QIP this year, so this is yet another reason to make it to Sydney this coming January.

QIP 2015

The website is up for QIP 2015, which will be held this year in beautiful Sydney, Australia. Here is a timeline of the relevant dates:

  • Submission of talks deadline: Sep 12, 2014
  • Submission of posters deadline: Oct 25, 2014
  • Decision on talks and posters submitted before talk deadline: Oct 20, 2014
  • Decision on posters submitted after talk deadline: Nov 15, 2014
  • Tutorial Session: Jan 10-11, 2015
  • Main Conference: Jan 12-16, 2015

And students, don’t worry, there are plans to include some student support scholarships, so we hope that many of you can attend. We’re looking forward to seeing you all here!

QIP 2014 accepted talks

This Thanksgiving, even if we can’t all be fortunate enough to be presenting a talk at QIP, we can be thankful for being part of a vibrant research community with so many different lines of work going on. The QIP 2014 accepted talks are now posted with 36 out of 222 accepted. While many of the hot topics of yesteryear (hidden subgroup problem, capacity of the depolarizing channel) have fallen by the wayside, there is still good work happening in the old core topics (algorithms, information theory, complexity, coding, Bell inequalities) and in topics that have moved into the mainstream (untrusted devices, topological order, Hamiltonian complexity).

Here is a list of talks, loosely categorized by topic (inspired by Thomas’s list from last year). I’m pretty sad about missing my first QIP since I joined the field, because its unusually late timing overlaps the first week of the semester at MIT. But in advance of the talks, I’ll write a few words (in italics) about what I would be excited about hearing if I were there.

Quantum Shannon Theory

There are a lot of new entropies! Some of these may be useful – at first for tackling strong converses, but eventually maybe for other applications as well. Others may, well, just contribute to the entropy of the universe. The bounds on entanglement rate of Hamiltonians are exciting, and looking at them, I wonder why it took so long for us to find them.

1a. A new quantum generalization of the Rényi divergence with applications to the strong converse in quantum channel coding
Frédéric Dupuis, Serge Fehr, Martin Müller-Lennert, Oleg Szehr, Marco Tomamichel, Mark Wilde, Andreas Winter and Dong Yang. 1306.3142 1306.1586
merged with
1b. Quantum hypothesis testing and the operational interpretation of the quantum Renyi divergences
Milan Mosonyi and Tomohiro Ogawa. 1309.3228

25. Zero-error source-channel coding with entanglement
Jop Briet, Harry Buhrman, Monique Laurent, Teresa Piovesan and Giannicola Scarpa. 1308.4283

28. Bound entangled states with secret key and their classical counterpart
Maris Ozols, Graeme Smith and John A. Smolin. 1305.0848
It’s funny how bound key is a topic for quant-ph, even though it is something that is in principle purely a classical question. I think this probably is because of Charlie’s influence. (Note that this particular paper is mostly quantum.)

3a. Entanglement rates and area laws
Michaël Mariën, Karel Van Acoleyen and Frank Verstraete. 1304.5931 (This one could also be put in the condensed-matter category.)
merged with
3b. Quantum skew divergence
Koenraad Audenaert. 1304.5935

22. Quantum subdivision capacities and continuous-time quantum coding
Alexander Müller-Hermes, David Reeb and Michael Wolf. 1310.2856

Quantum Algorithms

This first paper is something I tried (unsuccessfully, needless to say) to disprove for a long time. I still think that this paper contains yet-undigested clues about the difficulties of non-FT simulations.

2a. Exponential improvement in precision for Hamiltonian-evolution simulation
Dominic Berry, Richard Cleve and Rolando Somma. 1308.5424
merged with
2b. Quantum simulation of sparse Hamiltonians and continuous queries with optimal error dependence
Andrew Childs and Robin Kothari.
update: The papers appear now to be merged. The joint (five-author) paper is 1312.1414.

35. Nested quantum walk
Andrew Childs, Stacey Jeffery, Robin Kothari and Frederic Magniez.
(not sure about arxiv # – maybe this is a generalization of 1302.7316?)

Quantum games: from Bell inequalities to Tsirelson inequalities

It is interesting how the first generation of quantum information results is about showing the power of entanglement, and now we are all trying to limit the power of entanglement. These papers are, in a sense, about toy problems. But I think the math of Tsirelson-type inequalities is going to be important in the future. For example, the monogamy bounds that I’ve recently become obsessed with can be seen as upper bounds on the entangled value of symmetrized games.
4a. Binary constraint system games and locally commutative reductions
Zhengfeng Ji. 1310.3794
merged with
4b. Characterization of binary constraint system games
Richard Cleve and Rajat Mittal. 1209.2729

20. A parallel repetition theorem for entangled projection games
Irit Dinur, David Steurer and Thomas Vidick. 1310.4113

33. Parallel repetition of entangled games with exponential decay via the superposed information cost
André Chailloux and Giannicola Scarpa. 1310.7787

Untrusted randomness generation

Somehow self-testing has exploded! There is a lot of information theory here, but the convex geometry of conditional probability distributions also is relevant, and it will be interesting to see more connections here in the future.

5a. Self-testing quantum dice certified by an uncertainty principle
Carl Miller and Yaoyun Shi.
merged with
5b. Robust device-independent randomness amplification from any min-entropy source
Kai-Min Chung, Yaoyun Shi and Xiaodi Wu.

19. Infinite randomness expansion and amplification with a constant number of devices
Matthew Coudron and Henry Yuen. 1310.6755

29. Robust device-independent randomness amplification with few devices
Fernando Brandao, Ravishankar Ramanathan, Andrzej Grudka, Karol Horodecki, Michal Horodecki and Pawel Horodecki. 1310.4544

The fuzzy area between quantum complexity theory, quantum algorithms and classical simulation of quantum systems. (But not Hamiltonian complexity.)

I had a bit of trouble categorizing these, and also in deciding how surprising I should find each of the results. I am also somewhat embarrassed about still not really knowing exactly what a quantum double is.

6. Quantum interactive proofs and the complexity of entanglement detection
Kevin Milner, Gus Gutoski, Patrick Hayden and Mark Wilde. 1308.5788

7. Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups
Hari Krovi and Alexander Russell. 1210.1550

16. Purifications of multipartite states: limitations and constructive methods
Gemma De Las Cuevas, Norbert Schuch, David Pérez-García and J. Ignacio Cirac.

Hamiltonian complexity started as a branch of quantum complexity theory but by now has mostly devoured its host

A lot of exciting results. The poly-time algorithm for 1D Hamiltonians appears not quite ready for practice yet, but I think it is close. The Cubitt-Montanaro classification theorem brings new focus to transverse-field Ising, and to the weird world of stoquastic Hamiltonians (along which lines I think the strengths of stoquastic adiabatic evolution deserve more attention). The other papers each do more or less what we expect, but introduce a lot of technical tools that will likely see more use in the coming years.

13. A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Zeph Landau, Umesh Vazirani and Thomas Vidick. 1307.5143

15. Classification of the complexity of local Hamiltonian problems
Toby Cubitt and Ashley Montanaro. 1311.3161

30. Undecidability of the spectral gap
Toby Cubitt, David Pérez-García and Michael Wolf.

23. The Bose-Hubbard model is QMA-complete
Andrew M. Childs, David Gosset and Zak Webb. 1311.3297

24. Quantum 3-SAT is QMA1-complete
David Gosset and Daniel Nagaj. 1302.0290

26. Quantum locally testable codes
Dorit Aharonov and Lior Eldar. (also QECC) 1310.5664

Codes with spatially local generators aka topological order aka quantum Kitaev theory

If a theorist is going to make some awesome contribution to building a quantum computer, it will probably be via this category. Yoshida’s paper is very exciting, although I think the big breakthroughs here were in Haah’s still underappreciated masterpiece. Kim’s work gives operational meaning to the topological entanglement entropy, a quantity I had always viewed with perhaps undeserved skepticism. It too was partially anticipated by an earlier paper, by Osborne.

8. Classical and quantum fractal code
Beni Yoshida. I think this title is a QIP-friendly rebranding of 1302.6248

21. Long-range entanglement is necessary for a topological storage of information
Isaac Kim. 1304.3925

Bit commitment is still impossible (sorry Horace Yuen) but information-theoretic two-party crypto is alive and well

The math in this area is getting nicer, and the protocols more realistic. The most unrealistic thing about two-party crypto is probably the idea that it would ever be used, when people either don’t care about security or don’t even trust NIST not to be a tool of the NSA.

10. Entanglement sampling and applications
Frédéric Dupuis, Omar Fawzi and Stephanie Wehner. 1305.1316

36. Single-shot security for one-time memories in the isolated qubits model
Yi-Kai Liu. 1304.5007

Communication complexity

It is interesting how quantum and classical techniques are not so far apart for many of these problems, in part because classical TCS is approaching so many problem using norms, SDPs, Banach spaces, random matrices, etc.

12. Efficient quantum protocols for XOR functions
Shengyu Zhang. 1307.6738

9. Noisy Interactive quantum communication
Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette and Falk Unger. 1309.2643 (also info th / coding)


I hate to be a Philistine, but I wonder what disaster would befall us if there WERE a psi-epistemic model that worked. Apart from being able to prove false statements. Maybe a commenter can help?

14. No psi-epistemic model can explain the indistinguishability of quantum states
Eric Cavalcanti, Jonathan Barrett, Raymond Lal and Owen Maroney. 1310.8302

??? but it’s from THE RAT

update: A source on the PC says that this is an intriguing mixture of foundations and Bell inequalities, again in the “Tsirelson regime” of exploring the boundary between quantum and non-signaling.
17. Almost quantum
Miguel Navascues, Yelena Guryanova, Matty Hoban and Antonio Acín.

FTQC/QECC/papers Kalai should read 🙂

I love the part where Daniel promises not to cheat. Even though I am not actively researching in this area, I think the race between surface codes and concatenated codes is pretty exciting.

18. What is the overhead required for fault-tolerant quantum computation?
Daniel Gottesman. 1310.2984

27. Universal fault-tolerant quantum computation with only transversal gates and error correction
Adam Paetznick and Ben Reichardt. 1304.3709

Once we equilibrate, we will still spend a fraction of our time discussing thermodynamics and quantum Markov chains

I love just how diverse and deep this category is. There are many specific questions that would be great to know about, and the fact that big general questions are still being solved is a sign of how far we still have to go. I enjoyed seeing the Brown-Fawzi paper solve problems that stumped me in my earlier work on the subject, and I was also impressed by the Cubitt et al paper being able to make a new and basic statement about classical Markov chains. The other two made me happy through their “the more entropies the better” approach to the world.

31. An improved Landauer Principle with finite-size corrections and applications to statistical physics
David Reeb and Michael M. Wolf. 1306.4352

32. The second laws of quantum thermodynamics
Fernando Brandao, Michal Horodecki, Jonathan Oppenheim, Nelly Ng and Stephanie Wehner. 1305.5278

34. Decoupling with random quantum circuits
Winton Brown and Omar Fawzi. 1307.0632

11. Stability of local quantum dissipative systems
Toby Cubitt, Angelo Lucia, Spyridon Michalakis and David Pérez-García. 1303.4744

Scientific Birthdays –Toffoli gate honored on namesake's 70'th

P1030110aTommaso Toffoli’s 3-input 3-output logic gate, central to the theory of reversible and quantum computing, recently featured on a custom cake made for his 70’th birthday.
Nowadays scientists’ birthday celebrations often take the form of informal mini-conferences, festschrifts without the schrift.  I have had the honor of attending several this year, including ones for John Preskill’s and Wojciech Zurek’s 60’th birthdays and a joint 80’th birthday conference for Myriam Sarachik and Daniel Greenberger,  both physics professors at City College of New York.  At that party I learned that Greenberger and Sarachick have known each other since high school.  Neither has any immediate plans for retirement.
Greenberger Sarachik 80th birthday symposium

4 Pages

Walk up to a physicist at a party (we could add a conditional about the amount of beer consumed by the physicist at this point, but that would be redundant, it is a party after all), and say to him or her “4 pages.”  I’ll bet you that 99 percent of the time the physicist’s immediate response will be the three words “Physical Review Letters.”  PRL, a journal of the American Physical Society, is one of the top journals to publish in as a physicist, signaling to the mating masses whether you are OK and qualified to be hired as faculty at (insert your college name here).  I jest!  (As an aside, am I the only one who reads what APS stands for and wonders why I have to see the doctor to try out for high school tennis?)  In my past life, before I passed away as Pontiff, I was quite proud of the PRLs I’d been lucky enough to have helped with, including one that has some cool integrals, and another that welcomes my niece into the world.
Wait, wht?!?  Yes, in “Coherence-Preserving Quantum Bits” the acknowledgement include a reference to my brother’s newborn daughter.  Certainly I know of no other paper where such acknowledgements to a beloved family member is given.  The other interesting bit about that paper is that we (okay probably you can mostly blame me) originally entitled it “Supercoherent Quantum Bits.”  PRL, however, has a policy about new words coined by authors, and, while we almost made it to the end without the referee or editor noticing, they made us change the title because “Supercoherent Quantum Bits” would be a new word.  Who would have thought that being a PRL editor meant you had to be a defender of the lexicon?  (Good thing Ben didn’t include qubits in his title.)
Which brings me to the subject of this post.  This is a cool paper.  It shows that a very nice quantum error correcting code due to Bravyi and Haah admits a transversal (all at once now, comrades!) controlled-controlled-phase gate, and that this, combined with another transversal gate (everyone’s fav the Hadamard) and fault-tolerant quantum error correction is universal for quantum computation.  This shows a way to not have to use state distillation for quantum error correction to perform fault-tolerant quantum computing, which is exciting for those of us who hope to push the quantum computing threshold through the roof with resources available to even a third world quantum computing company.
What does this have to do with PRL?  Well this paper has four pages.  I don’t know if it is going to be submitted or has already been accepted at PRL, but it has that marker that sets off my PRL radar, bing bing bing!  And now here is an interesting thing I found in this paper.  The awesome amazing very cool code in this paper  is defined via its stabilizer


This takes up a whopping 4 lines of the article.  Whereas the disclaimer, in the acknowledgements reads

The U.S. Government is authorized to
reproduce and distribute reprints for Governmental pur-
poses notwithstanding any copyright annotation thereon.
Disclaimer: The views and conclusions contained herein
are those of the authors and should not be interpreted
as necessarily representing the official policies or endorse-
ments, either expressed or implied, of IARPA, DoI/NBC,
or the U.S. Government.

Now I’m not some come-of-age tea party enthusiast who yells at the government like a coyote howls at the moon (I went to Berkeley damnit, as did my parents before me.)  But really, have we come to a point where the god-damn disclaimer on an important paper is longer than the actual definition of the code that makes the paper so amazing?
Before I became a ghost pontiff, I had to raise money from many different three, four, and five letter agencies.  I’ve got nothing but respect for the people who worked the jobs that help supply funding for large research areas like quantum computing.  In fact I personally think we probably need even more people to execute on the civic duty of getting funding to the most interesting and most trans-form-ative long and short term research projects. But really?  A disclaimer longer than the code which the paper is about?  Disclaiming, what exactly?  Erghhh.


This is a rare gem: Four lectures on quantum mechanics by Paul Dirac… on YouTube! Here’s the first one.

Also, the Q+ online lecture series continues to go strong, bringing in a steady stream of high-quality speakers. This month constitutes the “Nobel lecture”, and will be given by Dietrich Leibfried of NIST Boulder, in lieu of Dave Wineland, on April 23rd at 5pm UK time. The title is “Towards scalable quantum information processing and quantum simulation with trapped ions”, and it’s sure to be a great talk. Though the number of live video streams will be limited, you can go to the Q+ website to reserve a spot, or wait until after the lecture and watch a recording.

Reflections on the Discord Bubble

The following is a guest post by Marco Piani.
A couple of months ago Steve wrote a post on “the discord bubble“. Let me try to provide a summary of his post and of his thoughts.
There have been too many works, too often of insufficient quality either technically or conceptually (“pointless” works in Steve’s words) about a property of quantum systems and correlations—the so-called quantum discord—that has not been proven yet to be key in our understanding of nature or of the `inner workings’ of quantum information processing. That is, such flurry of activity does not appear to be justified and is rather due to “hype”; most importantly, the product of such activity is way too often of questionable quality. Steve goes on to suggest that the bubble needs to be put under control, so that we would go down to a reasonable rate of publications on the subject, hopefully of higher average quality. In order to assess such quality, Steve proposes some rules of thumb—check them out in Steve’s post—to be applied hopefully by the authors themselves. In his words, Steve’s intention was

“not to trash the subject as intrinsically uninteresting; rather, [he wanted] to highlight the epidemic of pointless papers that constitute the discord bubble. [He hoped] that thinning the herd will increase the quality of the results in the field and decrease the hype surrounding it, because it has really gotten completely out of control.”

While I found Steve’s post essentially to the point and I furthermore highly appreciated his invitation to highlight in the comments good research on quantum discord—because there is good research on the topic—I feel that there is room for more reflection and discussion, in particular within—but of course not limited to—the community working on discord-related problems. To start it, I would like to express some of my own opinions.

Is there a bubble? What is it at its origin?

Yes, there is a bubble. Yes, there is too much hype. Yes, there are too many papers on the subject that are of questionable quality.
On one hand, the subfield of the `general quantumness of correlations’—as I like to think of discord and related concepts—still lacks a killer application to justify the present level of activity. The explosion of interest in the subfield was in a good part due to hints that such quantumness could help explain the quantum advantage in some noisy models of (limited) quantum computation. Such hints, to my knowledge, remain just hints; that is, too little to justify so many papers. We are still searching for a task/protocol that convincingly highlights discord or similar related properties as `resources’  or `the key’ in a general enough scenario—see this related post by Valerio Scarani. On the other hand, as Steve pointed out, many papers on discord are characterized by a low scientific merit, technically and/or conceptually.
I believe that the “discord bubble” is due to a combination of several factors, which have all come together to create the `perfect bubble’. Some are:
1) we live in a “publish or perish” (academic) world: if hype starts to be generated regarding a topic, many researchers will flock to that topic in the hope to score well in the number and kind of publications—high-impact journals—and the corresponding citations they are bound to get;
2) when there is a `new’ topic (like `discord’ with respect to the good ol’ `entanglement’) the technical and conceptual threshold to contribute new results is lower; on the other hand, quantum information is by now a mature field and new exciting results in `traditional’ theoretical topics—quantum Shannon theory, quantum error correction, quantum computation, … —require a high level of expertise and skills;
3) some form of `confirmation bias’: positive statements on the value and significance of new and old results on the topic are easily accepted and perpetuated, especially in light of 1) and 2).
Let me stress that these factors are mostly independent of the topic itself—discord. I am pretty sure that other fields of science have their own bubbles.

Is it worth working on discord and related issues?

Quantum information processing aims at exploiting quantum features to provide us with new, powerful means to manipulate information. Reaching this goal requires the best possible understanding of such features.
More specifically for our case, there are quantum features that 1) are proper of bi- and multi-partite systems (i.e., they do not have a real correspondent for single systems)  and 2) do not reduce to entanglement, e.g, they can be present also in the absence of entanglement.  For example, one of these properties is related to the celebrated no-cloning theorem; another one is the unavoidable disturbance introduced by local measurements. In this sense there is a `general quantumness of correlations’, which, for the above reasons, I believe is worth investigating.
Of course, an argument like “[PROPERTY] could be useful, so we should study it” is not  enough, if not substantiated. There should be some concrete evidence and some convincing perspective of such usefulness in order to motivate the related investment of resources. I think that what we know about the general quantumness of correlations, although not enough to justify the number of papers dealing with it, satisfies these requirements, at least partially. More clearly:
We have concrete evidence that the general quantumness of correlations is a useful concept to consider.
Such usefulness goes from foundations—e.g., addressing the measurement problem and the emergence of classicality—to the alternative take on the no-cloning theorem mentioned above, to the study of quantum effects in the `locking’ of classical correlations in quantum information theory.
On the other hand:
We have not yet found a way to think about and exploit the general quantumness of correlations that makes such quantumness worthy of the central stage of quantum information processing, or of the title of `resource’.
As mentioned above, the protocols so far designed that pinpoint discord as the relevant `resource’ at play can be considered contrived. More generally, I doubt that discord will ever achieve a status of resource similar to entanglement. I rather believe that, for example, discord is—with the risk of sounding like I am trying to be witty—something that makes it possible to make something else impossible. For example, discord makes it impossible to access `in a classical way’  part of the information content of correlations.
All in all, I do believe that the general quantumness of correlations will further prove its usefulness, both as a conceptual tool and as concrete property present in distributed systems. What we have to remember is that such usefulness is not well established and that most of the work on the subject should still go in the direction of clarifying the value and applicability of the concept rather than, e.g., calculating discord in all sorts of physical systems.
Let me add that I consider the study of the general quantumness of correlations also as an attempt to think about the quantum from a different/larger perspective—different/larger with respect to what was previously done. In my case, thinking in terms of the `general quantumness of correlations’ has helped me, for example, to better understand entanglement itself.

What should people who work or consider working on discord do? What about the rest of the quantum information community?

The effort worth investing—as individual researchers, as a scientific (in particular, quantum information) community, and as a society (e.g., in terms of funding)—in the study of the general quantumness of correlations is not easy to determine. This actually holds in general, for essentially any research subject. What is worrisome about a bubble, is that it can reduce the efficiency of the procedures in place—in particular the peer-review process—to shape the activity of the community, to reallocate its resources, and to induce researchers to adopt a good practice. [We actually know that the peer-review process, in particular in the standard form associated to publication in journals, does not work perfectly in general.]  As personal experience goes, I have often rejected low-quality papers on discord only to see them published in another journal. So it is important to recognize the presence of a bubble and bring the problem to the attention of the community, so that extra care can be taken in assessing the value of papers, both in terms of correctness and relevance. While I endorse Steve’s rules of thumb to assess the quality of papers related to discord, I would like to address the problem of the discord bubble with a list of suggestions mostly comprising general good practices.
So, to the people working/interested in working on discord:
a) re-evaluate why you are working on the topic. A useful exercise it that of imagining explaining to someone who is NOT already working on discord why he should be interested in investigating the subject. If whatever reason you provide is based on previous results in the field, make sure that you have checked the source at a sufficient level of detail to be sure that those results—and in particular any related strong claim—would be convincing for him, and, most importantly, that they are convincing for you;
b) be aware of the large body of work that already exists in quantum information processing: what you think is new and exciting may well be already known (either published, or easy to see and part of the `folklore’);
c) analyze critically your work and that of the others, both as author and as referee: cite only literature that is significant and relevant to your paper and reject papers that do not provide substantial advance in neither understanding nor applications;
d) focus on providing more—and possibly conclusive—evidence that the study of the quantumness of correlations is justified: we need `killer applications’ and `killer concepts’;
e) entanglement theory has been a very fruitful field of study because entanglement is a fundamental concept and it can be understood/analyzed as a resource in a reasonable, operationally justified framework—that of distant labs, where the quantum operations allowed are only local, at most coordinated by classical communication. Trying to mimic successful stories might be a good idea, but there are dangers involved. Let us avoid creating the Bizzarro version of entanglement.
To the rest of the quantum information community:
Be critical and open-minded at the same time.
While complaining about the existence of a discord bubble is more than reasonable and, from my point of view, quite welcome, attacking the study of discord per se is unjustified. Please challenge whoever makes claims that are too strong, question observations and calculations that you judge irrelevant, push people who work on discord to meet the highest standards in international research, reject papers when they do not meet such standards. But please do not dismiss a talk or a paper just because it deals with discord; evaluate it only on the basis of its specific scientific merit.  Furthermore, if you feel like it, you can ponder for some minutes on questions like “Is there anything quantum about a distributed quantum state that is not solely due to entanglement?”, and “Can we make use of it?”.

On the fractal nature of bubbles

The best results of recognizing that there is a `discord bubble’ and of taking corresponding action—maybe on the lines suggested above—would be, on one hand, to improve the research activity on discord, and, on the other hand, to avoid the risk that the subject and the people working on it acquire a bad reputation.
Let me mention that there are scientists who think that research on quantum computation is itself a bubble—see this post by Scott Aaronson. Is this further proof that bubbles can have a fractal structure? Of course the `accusation’ of being bubbles is at different levels for discord and quantum information, and not just in the sense of the `fractal level’. The criticism towards quantum computing is mostly about its realizability, while discord, although a useful conceptual tool, has not convincingly been proven to be a `resource’, even in theory.  Nonetheless, there is something in common about the two accusations of being a bubble: hype—again. Indeed, Scott writes about the accusations of the quantum computing skeptic M. I. Dyakonov:

“Dyakonov fumes about how popular articles, funding agency reports, and so forth have overhyped progress in quantum computing, leaving the conditions out of theorems and presenting incremental advances as breakthroughs.  Here I sadly agree.”

So, let me add a point to the above list of suggestions:
f) try to reduce—or at least do not contribute to—the hype.
This will have the effect of making the topic of discord less attractive for people whose work will not actually improve the standing of the topic, and improve its reputation within the quantum information community, potentially attracting good researchers.
The above-mentioned post by Scott is also notable for having started a high-quality discussion in the comments section on whether quantum computing deserves the accusation of being a bubble. It would be great to have a similar discussion on discord in the comments below. I expressed already my personal opinion: we are in front of a discord bubble, but there is merit in studying the general quantumness of correlations. I would be particularly happy to have a discussion on whether—and why—my opinion is too harsh or too mild, and to receive, as Steve already asked in his post, motivated suggestions about works that should survive a `pop’ of the discord bubble.