Acronyms Beyond NISQ

NISQ is a term coined by John Preskill1 circa 2018 and stands for “Noisy Intermediate-Scale Quantum”. The term is aimed to describe quantum computers that were not just toy few qubit systems, but systems of a slightly larger scale. This “slightly larger” is a bit hard to define, but roughly most people take it as what is achievable with a quantum computer that does not use error correction. Or in other word the “intermediate” means roughly “what you can do with the natural fidelities of your qubits” (with a fudge factor for those who want to plug their nose and use error mitigation.)

Now this is a blog, so I will give my opinion. And that is that word intermediate in NISQ drives me nuts. I mean in part because it is vague (intermediate between what?), but more because the word itself is a disaster. Intermediate comes to us from Latin, being a combination of inter, meaning “between”, and medius meaning “middle”. But this is silly how can there be a middle without being between? It’s like saying “middle middle”. Whenever I hear NISQ I am reminded of this bastard doubling, and I start working on a time machine to go back in time and work on etymological corrections (good short story idea: a society of time travelers whose sole goal is to bring reason to the etymological record).

A more interesting question than my own personal hangups on word origins is what should we call what exists on the other side of intermediate. My friend Simone Severini has used the term LISQ which stands for “Logical Intermediate-Scale Quantum”2. The idea, as I understand it, is to use this term to refer to the era where we start to construct the first error corrected quantum devices. In particular it is the place where instead of using raw physical qubits one instead uses some logical encoding to build the basic components of the quantum computer. (<high horse>Of course, all qubits are encoded, there is always a physical Hamiltonian with a much larger Hilbert space at work, what we call a qubit subsystem is a good approximation, but it is always an approximation.</high horse>). I am exciting that we are indeed seeing the ideas of quantum error correction being used, but I think this obscures that what is important is not that a qubit is use error correction, but how well it does that.

I want to propose a different acronym. Of course, I will avoid the use of that annoying term intermediate. But more importantly I think we should use a term that is more quantitative. In that vein I propose, in fine rationalist tradition, that we use the metric system! In particular the quantity that is most important for a quantum computer is really the number of quantum gates or quantum instructions that one can execute before things fall apart (due to effects like decoherence, coherent imprecision, a neutral atom falling out of its trapping potential, or a cataclysmic cosmic ray shower). Today’s best perform quantum computations have gotten signal out of their machine while reaching somewhere near the 1000 gate/instruction level3. We can convert this to a metric prefix, and we get the fine “Kilo-Instruction Scale Quantum”. Today’s era is not the NISQ era, but the KISQ era.

And as we start to move up the scale by using error correction (or somehow finding natural qubits with incredible raw fidelities) we then start to enter the regime where instead of being able to run a thousand instructions we start to be able to run a million instructions. This till be the “Mega-Instruction Scale Quantum” era or MISQ era. And I mean how cool will that be, who doesn’t love to say the word Mega (Just don’t drawl your “e” or you might stumble into politics). Then we can continue on in this vein:

  • 103 instructions = KISQ (kilo) = NISQ
  • 106 instructions = MISQ (mega)
  • 109 instructions = GISQ (giga)
  • 1012 instructions = TISQ (terra) <– Shor’s algorithm lives around here

An objection to this approach is that I’ve replaced the word intermediate with the word instruction and while we gain the remove of the “middle middle”, we now the vague term instruction. The word origin of instruction is a topic for another day, but roughly it is a combination of “in” and “to pile up”, so I would argue isn’t doesn’t have as silly an etymology as intermediate. But more to the point, an “instruction” has only an imprecise meaning for a quantum computer. Is it the number of one and two qubit gates? What about measurements and preparations? Why are we ignoring qubit count or gate speed or parallelism? How do we quantify it for architectures that use resource states? To define this is to fall down the rabbit hole of benchmarks of quantum computers4. Benchmarking is great, but it always reminds me of a saying my grandfather used to tell me “In this traitorous world, nothing is true or false, all is according to the color of the crystal through which you look”. Every benchmark is a myopia, ignoring subtleties at the cost of quantiative precision. And yes, people will fudge any definition of instruction to fit the strengths of their quantum architecture (*ahem* algorithmic qubit *ahem*). But terms like NISQ are meant to label gross eras, and I think its okay to have this ambiguity.

One thing I do like about using the metric prefix is a particularly pressing problem. While it has been a real challenge to find NISQ algorithms that have “practical” (whatever that means5) an equally pressing problem is what sort of quantum algorithms will be achievable in the MISQ era. The place where we have the most confidence in the algorithmic advantage offered by quantum computers, simulation and experimental math algorithms (like factoring), lie above the GISQ and probably in the TISQ region. Roughly what we need are quantum algorithms that are linear time algorithms, so that for instances sizes becoming non-trivial (say a thousand), their total spacetime volume is a this size squared. And while there has been work on algorithms in this era, I would not say that we confidently have algorithms we know will be practically useful in MISQ. And this MISQ/GISQ gap is extremely scary!

So long live the NISQ era! And onward and up to MISQ and beyond!

  1. “Quantum Computing in the NISQ era and beyond”, Preskill arXiv/1801.00862 ↩︎
  2. “Bye NISQ. Hello LISQ?”, Simone Severini LinkedIn post ↩︎
  3. As an example “Phase transition in Random Circuit Sampling” by the Google group (of which I’m a member) shows a signal for circuits with 32 cycles and 67 qubits. arXiv/2304.11119 ↩︎
  4. A prominent benchmark is Quantum Volume, defined in “Validating quantum computers using randomized model circuits” by Cross, Bishop, Sheldon, Nation, and Gambetta arXiv/1811.12926. This is a fine benchmark modulo that because Executives at BigCo’s apparently can be fooled by log versus linear scale, they really should have taken the log of the quantity they use to define the Quantum Volume. ↩︎
  5. My own personal opinion is that current claims of “quantum utility” are an oversell, or what we nowadays call quantum hype, but that is a subject for a beer at a quantum beer night. ↩︎

Qafblog

“We are in a box,” says me.

“Do you see some radium hooked up to a crazy steampunk device with skulls and crossbones and yellow, definitely yellow, but maybe also neon green or wavey blue?” says Qubitslets.

“No I think we put ourselves in the box,” says me. “I don’t see any radium.”

“Maybe we’re in that branch of the wave function where we’ve transmogrified ourselves into a simulation. And we’re in a box because those post capitalists are too damn cheap to simulate us outside of a small goddamn box. Just like new Seattle townhouses. We’re in the cheap Android version of a tech bros afterlife. Do you see brass?”

“No brass,” says me, “but there is something growing in the corner.”

“A tunnel?” asks Qubitslets, “Remember that tunnel we were digging to the moon? I’ve been thinking about the replica symmetry breaking structure of our many tunnel passages to the moon. Maybe we should leverage quantum effects? Jesus, did I just say that? Have I been infected with Goldman Socks ibank spin 3/2s disease? At least I’m a fermion I guess. Not like those collective Marxist bosons over at Google Vultures.”

“I will remind you of the last time we used quantum effects,” says me. “We ended up changing the vacuum state from suck to blow. Luckily it was an unstable equilibrium, and because we are particle theorists and not cosmologists, we didn’t have to think ‘equilibrium of the Higgs-Anderson-Goldstone field with respect to what?’, so the universe just relaxed back to its current vacuum. I sure do miss the werewolves from that old vacuum, though. No, the thing growing in the corner is in a jar.”

“Crap”, says Qubitslets, “we’ve been quarantined!”

Suddenly the Medium Cryostat materializes from The Void. “There is no virus and if there were viruses they would be foreign viruses with foreign RNA and a sheath of foreignness so tricky in its conformal structure we would need a wall to stop it. Because there is no virus, which there certainly isn’t, we must build walls around us and between us and under us. The Great Walling must begin. And we must stay behind our walls and only go out to visit our grandma if she is in a nursing home but we can only do that if we test grandma for foreign viruses, which don’t exist, and, of course we must stay six feet from any particle in the universe. A foreign virus has a Compton wavelength of six feet, I am told.”

“In light of us not being afraid of viruses, because they don’t exist, we will need to plan for how The Great Economy can survive the foreign viruses, if they existed. Stock buybacks were insurance claims for the future antibodies the corporations of The Great Economy would need during The Great Walling, so we should cash out their claims. Because of the uniform structure of economic strata across our Great County, we can use the base minimum wage to pay the minimum required to sustain minimal substance for those impacted by the viruses. If the viruses existed.”

“But we must also not forget what made this a Great Country, again. Never forget the resilience of our people to the scientific method, again. Of the possibility of our citizens being able to think in terms of counterfactuals, again. And of our dedication to spring break and Easter services and a Latin homily about licentious spring breakers, which no, does not arouse the Medium Cryostat. Amen. Oops, I mean Again.”

“And because we are a generous Medium Cryostat, and we know that living behind walls is hard (but necessary because maybe viruses), we shall provide to every home everywhere a jar of Sourdough Levain. Lactobacilli and yeast for all, because nothing says that you aren’t scared of invisible microscopic viruses like cooking with a self reproducing jar of sticky goo.”

“Hooray!” says Qubitslets, “we get to bake bread!”

“Did I ever tell you about the time my girl forgot to feed the starter,” says me ,”and the starter died, and in the tears that fell into the hooch that was all that remained, I could see that the relationship was over by studying the way the waves spread and reflected off the walls of the jar?”

“I bet we can study the exponential growth of the yeast and use that to model viruses,” says Qubitslets. “As physicists we know that only simple models that use physics concepts can be used for public health decisions.”

“Or maybe in the replication of the yeast, we’ll discover that we are just cellular automata or hypergraphs transforming under some crowdsourced update rule.”

“But no brass,” says Qubitslets.

“Yeah, no brass.”

** This post is a tribute to the best blog that every was, ever will be, and ever could be. Fafblog you are greatly missed.

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 Computers Are…

Quantum computers are

  • Blue versions of classical computers [1] [2] [3][4]
  • Blue or grey abstract patterns [1] [2][3][4][5][6]
  • A bunch of connectors [1][2]
  • Blurred out chips [1]
  • What goes inside the dilution fridge [1][2][3]
  • Closed dilution fridges [1]
  • Part of a flag [1]
  • A button near the enter key [1]
  • Icy cold really big atoms [1]

Quantum computers are so many things (and no I will not add “all at once” to the end of this sentence)!  I’d be excited to hear about even more things that are quantum computers.

Un-renunciation

Can pontiffs un-retire (un-renunciate)?  I mean, I retired from being a pontiff way before it was cool.  But now the sweet siren call of trying to figure out whether there is really a there there for noisy intermediate scale quantum devices has called me back.   I think it may be time to start doing a little bit of quantum pontificating again.  My goal, as always, will be to bring down the intellectual rigor among quantum computing blogs.  And to show you pictures of my dog Imma, of course.
Cue bad joke about unitary dynamics and quantum recurrences in 3, 2, 1, 0, 1, 2, 3, …
 

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?

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.

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!