Archive for August, 2018

Lecture notes! Intro to Quantum Information Science

Sunday, August 26th, 2018

Someone recently wrote that my blog is “too high on nerd whining content and too low on actual compsci content to be worth checking too regularly.”  While that’s surely one of the mildest criticisms I’ve ever received, I hope that today’s post will help to even things out.

In Spring 2017, I taught a new undergraduate course at UT Austin, entitled Introduction to Quantum Information Science.  There were about 60 students, mostly CS but also with strong representation from physics, math, and electrical engineering.  One student, Ewin Tang, made a previous appearance on this blog.  But today belongs to another student, Paulo Alves, who took it upon himself to make detailed notes of all of my lectures.  Using Paulo’s notes as a starting point, and after a full year of procrastination and delays, I’m now happy to release the full lecture notes for the course.  Among other things, I’ll be using these notes when I teach the course a second time, starting … holy smokes … this Wednesday.

I don’t pretend that these notes break any new ground.  Even if we restrict to undergrad courses only (which rules out, e.g., Preskill’s legendary notes), there are already other great quantum information lecture notes available on the web, such as these from Berkeley (based on a course taught by, among others, my former adviser Umesh Vazirani and committee member Birgitta Whaley), and these from John Watrous in Waterloo.  There are also dozens of books—including Mermin’s, which we used in this course.  The only difference with these notes is that … well, they cover exactly the topics I’d cover, in exactly the order I’d cover them, and with exactly the stupid jokes and stories I’d tell in a given situation.  So if you like my lecturing style, you’ll probably like these, and if not, not (but given that you’re here, there’s hopefully some bias toward the former).

The only prerequisite for these notes is some minimal previous exposure to linear algebra and algorithms.  If you read them all, you might not be ready yet to do research in quantum information—that’s what a grad course is for—but I feel good that you’ll have an honest understanding of what quantum information is all about and where it currently stands.  (In fact, where it already stood by the late 1990s and early 2000s, but with many comments about the theoretical and experimental progress that’s been made since then.)

Also, if you’re one of the people who read Quantum Computing Since Democritus and who was disappointed by the lack of basic quantum algorithms in that book—a function of the book’s origins, as notes of lectures given to graduate students who already knew basic quantum algorithms—then consider these new notes my restitution.  If nothing else, no one can complain about a dearth of basic quantum algorithms here.

I welcome comments, bugfixes, etc.  Thanks so much, not only to Paulo for transcribing the lectures (and making the figures!), but also to Patrick Rall and Corey Ostrove for TA’ing the course, to Tom Wong and Supartha Podder for giving guest lectures, and of course, to all the students for making the course what it was.

  • Lecture 1: Course Intro, Church-Turing Thesis (3 pages)
  • Lecture 2: Probability Theory and QM (5 pages)
  • Lecture 3: Basic Rules of QM (4 pages)
  • Lecture 4: Quantum Gates and Circuits, Zeno Effect, Elitzur-Vaidman Bomb (5 pages)
  • Lecture 5: Coin Problem, Inner Products, Multi-Qubit States, Entanglement (5 pages)
  • Lecture 6: Mixed States (6 pages)
  • Lecture 7: Bloch Sphere, No-Cloning, Wiesner’s Quantum Money (6 pages)
  • Lecture 8: More on Quantum Money, BB84 Quantum Key Distribution (5 pages)
  • Lecture 9: Superdense Coding (2 pages)
  • Lecture 10: Teleportation, Entanglement Swapping, GHZ State, Monogamy (5 pages)
  • Lecture 11: Quantifying Entanglement, Mixed State Entanglement (4 pages)
  • Lecture 12: Interpretation of QM (Copenhagen, Dynamical Collapse, MWI, Decoherence) (10 pages)
  • Lecture 13: Hidden Variables, Bell’s Inequality (5 pages)
  • Lecture 14: Nonlocal Games (7 pages)
  • Lecture 15: Einstein-Certified Randomness (4 pages)
  • Lecture 16: Quantum Computing, Universal Gate Sets (8 pages)
  • Lecture 17: Quantum Query Complexity, Deutsch-Jozsa (8 pages)
  • Lecture 18: Bernstein-Vazirani, Simon (7 pages)
  • Lecture 19: RSA and Shor’s Algorithm (6 pages)
  • Lecture 20: Shor, Quantum Fourier Transform (8 pages)
  • Lecture 21: Continued Fractions, Shor Wrap-Up (4 pages)
  • Lecture 22: Grover (9 pages)
  • Lecture 23: BBBV, Applications of Grover (7 pages)
  • Lecture 24: Collision and Other Applications of Grover (6 pages)
  • Lecture 25: Hamiltonians (10 pages)
  • Lecture 26: Adiabatic Algorithm (10 pages)
  • Lecture 27: Quantum Error Correction (8 pages)
  • Lecture 28: Stabilizer Formalism (9 pages)
  • Lecture 29: Experimental Realizations of QC (9 pages)

And by popular request, here are the 2017 problem sets!

I might post solutions at a later date.

Note: If you’re taking the course in 2018 or a later year, these sets should be considered outdated and for study purposes only.


Notes and Updates (Aug. 27)

Here’s a 184-page combined file. Thanks so much to Robert Rand, Oscar Cunningham, Petter S, and Noon van der Silk for their help with this.

If it wasn’t explicit: these notes are copyright Scott Aaronson 2018, free for personal or academic use, but not for modification or sale.

I’ve freely moved material between lectures so that it wasn’t arbitrarily cut across lecture boundaries. This is one of the reasons why some lectures are much longer than others.

I apologize that some of the displayed equations are ugly. This is because we never found an elegant way to edit equations in Google Docs.

If you finish these notes and are still hankering for more, try my Quantum Complexity Theory or Great Ideas in Theoretical Computer Science lecture notes, or my Barbados lecture notes.  I now have links to all of them on the sidebar on the right.

Thank you, world!

Wednesday, August 15th, 2018

1. This post has no technical content.  As the tag indicates, it’s entirely “Nerd Self-Help”—thoughts I’ve recently found extremely helpful to me, and that I’m hopeful some others might be able to apply to their own life situations.  If that doesn’t interest you, feel free to skip.

2. I’m using the numbered list format simply because I have a large number of interrelated things to say, and getting each one down precisely seems more important than fashioning them into some coherent narrative.

3. For someone who walks around every day wracked by neurosis, social anxiety, tics, and depression, I’m living an unbelievably happy and fulfilling life.  For this I’m profoundly grateful—to “the universe,” but much more so, to the family and friends and colleagues who’ve made it possible.

4. On bad days, I’ve cursed fate for having placed me in a world to which my social skills were so poorly adapted.  On good days, though, I’ve thanked fate for letting me thrive in such a world, despite my social skills being so maladapted to it.  My ability to thrive in this world owes everything to the gifts of modernity, to the stuff Steven Pinker talks about in Enlightenment Now: the decline of violence, the rule of law, the freedom from hunger, disease, and war, but most of all the rise of science.  So I have a personal reason to be grateful for modernity and to care deeply about its preservation—and to detest Trump and all the other would-be autocrats who’d gleefully take an ax to it.  Like hothouse plants, nerds can flourish only in artificially safe environments.  I don’t often enough express my gratitude for having been born into a world that contains such environments, so I’m taking the opportunity to do so today.

5. I got back a few days ago from a wonderful visit to Mexico City—thanks so much to Sergio Rajsbaum, Luis González, and all my other new friends there for helping to organize it.  I gave three talks at UNAM, one of the largest universities on earth.  I ate … well, the best Mexican food I ever tasted.  I saw amazing sights, including the National Museum of Anthropology, which has hall after hall full of Aztec and Maya artifacts of a grandeur one normally associates with ancient Egypt, Greece, or Rome.  Go there if you want a visceral sense for the scale of the tragedy wrought by the conquistadors.  (On the other hand, having seen the decorated ceremonial knives, the skulls of children whose hearts were ripped out while still beating, I do have to count the end of human sacrifice as a net positive.)

6. The trip was surreal: I discussed quantum computing and philosophy and Mexican history over enchiladas and tequila.  I signed copies of my book, lectured, met fans of this blog.  There was lots of good-natured laughter about the tale of my arrest, and stern reminders to be careful when ordering smoothies.  A few people I met shared their own stories of being harassed by US police over trivial mishaps (e.g., “put your hands on the car,” rifle aimed, over a parking violation), exacerbated of course by their being Mexicans.  One colleague opined that he preferred the Mexican system, wherein you and the officer just calmly, politely discussed how many pesos would make the problem go away.  But then, from time to time, I’d check my phone and find fresh comments accusing me of being a thief, a nutcase incapable of functioning in society, a racist who wants to be treated differently from blacks and Latinos (the actual view expressed in my post was precisely the opposite of that), or even a money-grubbing Jew hyperventilating about “anuddah Shoah.”

7. The real world has a lot to be said for it.  Maybe I should spend more time there.

8. Thanks so much to everyone who sent emails or left comments expressing sympathy about my arrest—or even who simply found the story crazy and amusing, like a Seinfeld episode.  Meanwhile, to those who berated me for being unable to function in society: does it bother you, does it present a puzzle for your theory, that rather than starving under a bridge, I’m enjoying a career doing what I love, traveling the world giving lectures, happily married with two kids?  Do I not, if nothing else, illustrate how functional a non-functional person can be?

9. It’s possible that my kids will grow up with none of the anxiety or depression or neuroticism or absentmindedness that I’ve had.  But if they do have those problems … well, I’m thankful that I can provide them at least one example of what it’s possible to do in life in spite of it!

10. On SneerClub, someone opined that not only was I an oblivious idiot at the smoothie counter, I must also be oblivious to how bad the incident makes me look—since otherwise, I would never have blogged about it.  I ask my detractors: can you imagine, for one second, being so drunk on the love of truth that you’d take the experiences that made you look the most pathetic and awkward, and share them with the world in every embarrassing detail—because “that which can be destroyed by the truth should be”?  This drunkenness on truth is scary, it’s destabilizing, it means that every day you run a new risk of looking foolish.  But as far as I can introspect, it’s also barely distinguishable from the impulse that leads to doing good science: asking the questions everyone else knows better than to ask, clarifying the obvious, confessing one’s own doofus mistakes.  So as a scientist, I’m grateful to have this massive advantage, for all its downsides.

11. Of the hundreds of reactions to my arrest, some blamed me, some the police, some both and some neither.  As I mentioned before, there was an extremely strong and surprising national split, with Americans siding with the police and non-Americans siding with me.  But there was also an even deeper split: namely, almost everyone who already liked me found the story funny or endearing or whatever, while almost everyone who already hated me found in it new reasons for their hate.  I’ve observed this to be a general phenomenon: within the range of choices I’d realistically consider, none of them seem to do anything to turn enemies into friends or friends into enemies.  If so, then that’s a profoundly liberating realization.  It means that I might as well just continue being myself, saying and doing what seem reasonable to me, without worrying about either winning over the SneerClubbers or losing the people who like this blog.  For neither of those is likely to happen–even if we ignore all the other reasons to eschew overreliance on external validation.

12. Every week or so I get emails from people wanting to share their spiritual theories with me, and to illustrate them with color diagrams.  Most such emails go straight to my trash folder.  This week, however, I received one that contained a little gem of insight:

I realize you are professionally reluctant to admit that Spirit actually exists. However, it is obvious to me from your blog that you are personally committed to what I might label “spiritual development.” You are continually pushing yourself and others to be more self-aware, reflect on our actions and assumptions, and choose to become our best selves.

I can only imagine how much pain and psychic energy it costs you to do that so publicly and vulnerably. But that is precisely why so many of us love you; and others hate you, because they are understandably terrified of paying that same price.

13. To those who’ve called me a terrible person, based on how they imagine I’d respond in hypothetical scenarios of their own construction, I make one request.  Before passing final judgment, at least exchange emails with me, or meet me, or otherwise give me a chance to differentiate myself from your internal bogeyman.  Ask me for grad school advice, or comments on your CS idea, or whatever—and with nothing in it for me, and swamped with similar requests, see how much time I spend trying to help you.  Or ask me to donate to your favorite charity, and see if I do it.  Or tell me about misconduct by a prominent member of my community, and see how I respond.  See if any of this is noticeably affected by your race, religion, gender, sexual orientation, or anything else besides the honesty of your request.

14. None of the above are hypotheticals for me.  Once I was given firsthand reports, which I judged to be extremely credible, about a serial sexual harasser of women in the math and TCS communities.  The victims had already pursued formal complaints, but with an unsatisfactory resolution.  In response, I immediately offered to publish the perpetrator’s name on this blog along with the evidence and accusations, or help in any other way desired.  My offer was declined, but it still stands if the victims were to change their minds.

15. My mom once told me that, having been hippies concerned about overpopulation, she and my dad weren’t planning to have any kids.  When they finally decided to do so, it was in order to “spite Hitler.”  I felt incredibly proud to have that be the reason for my birth.  Every time I think about it, it fills me with a renewed urge to stand up for whatever seems most human and compassionate, regardless of how unpopular.

16. Going forward, if I ever (hypothetically) experience a relapse of the suicidal thoughts that characterized part of my life, I’m going to say to myself: no.  Not only will I remain alive, I’ll continue to enjoy my family and friends and research and teaching, and mentor students, and get involved in issues I care about, and otherwise make the most of life.  And if for no other reason, I’d do this in order that Arthur Chu could remain, as he put it, “unhappy about [my] continued existence”!  Admittedly, spiting Chu and his chorus of SneerClubbers is far from the only reason to continue living, but it’s a perfectly sufficient reason in itself.  And this will be an impenetrable shield against suicidal thoughts.  So thanks, Arthur!

17. Four years ago, I received hundreds of moving responses to comment 171.  But perhaps the most touching were from several female classmates who I’d had crushes on back in the depressed period I wrote about, and who said some variant of: “it’s a shame you never asked me, because I liked you and would’ve gladly said yes.”  One of these classmates, bless her heart, recently asked me to share this information, as an encouragement to young nerdy readers who might find themselves in the same situation I was in.  Four years ago, a few feminists lectured me that the crippling fear I’d suffered was good, a feature rather than a bug: if only every other predatory nerdbro would be paralyzed by the same fear!  (That is, when they weren’t also lecturing me that the fears were ridiculous and existed only in my head.)  But the women who wrote to me are also left-wing feminists.  So if you confess your feelings to someone, know that no one who despises that decision, who considers it ‘problematic’ and ‘entitled’ and ‘privileged’ and all the rest of the modern litany of just-die-already words, can pretend to speak for all feminists.  I love my wife and my children, and wouldn’t go back in time to change my life’s trajectory if I could.  But you, readers, armed with wisdom I lacked, can reach a happy place in your lives a hell of a lot faster than I did.

18. While this has been beneath the surface of a huge number of my posts, it seems worth bringing out explicitly.  On certain blogs and social media sites, I’m regularly described as a “leftist troll,” a “pathetic, mewling feminist,” or a “rabid establishment liberal.”  On others I’m called a “far-right Zionist” or an “anti-feminist men’s rights advocate.”  It’s enough to make even me confused.  But here’s how I choose to define my stance: my party is the Party of Psychological Complexity.  Our party platform consists of Shakespeare’s plays, the movie The Breakfast Club, the novels of Mark Twain and Philip Roth and Rebecca Goldstein, classic Simpsons and Futurama, and anything else that tries to grapple with human nature honestly.  For most of the past few centuries, the Party of Psychological Complexity has been in a coalition with the political left, because both were interested in advancing Enlightenment ideals, ending slavery and female subjugation and other evils, and broadening humankind’s circles of empathy.  But the PoPC and the political left already split once, over the question of Communism, and today they split again over the morality and the wisdom of social justice vigilantism.

19. Here in the PoPC, our emphasis on the staggering complexity of the individual conscience might seem hard to square with utilitarian ethics: with public health campaigns, Effective Altruism, doing the greatest good for the greatest number, etc.  But the two philosophies actually fit beautifully.  In the PoPC, our interest (you might say) is in the psychological prerequisites to utilitarianism: in the “safe spaces” for the weird and nerdy and convention-defying and literal-minded in human nature that need to get established, before discussion about the best ways to fight malaria or global warming or nuclear proliferation or plastic in the oceans can even begin.

20. On leftist forums like SneerClub, whenever I’m brought up, I’m considered a dangerous reactionary—basically Richard Spencer or Alex Jones except with more quantum query complexity.  Yet, while there are differences in emphasis, and while my not being in politics gives me more freedom to venture outside the Overton window, my views on most contemporary American issues are hard to distinguish from those of Barack Obama, who I consider to have been a superb president and a model of thoughtful leadership.  If you want to understand how racist demagogues managed to take over the US—well, there was a perfect storm of horribleness, with no one decisive factor.  But it surely didn’t help that the modern social-justice left so completely disdains coalition-building, so values the purity of the Elect above all else, that it cast even progressive Obama supporters like me into its lowest circle of Hell.

21. Open yourself up to the complicated and the true in human nature.  Don’t be like Donald Trump or Arthur Chu, two men who represent opposite poles of ideology, yet who have in common that they both purposefully killed what was complicated in themselves.  For those two, winning is all that matters—they’ve explicitly said so, and have organized their entire lives around that principle.  But winning is not all that matters.  When I stand before the Lord of Song, even though it all went wrong, the only word on my lips will be “hallelujah”–because while I have many faults, I did make some room in life for beauty and truth, even at the expense of winning.  Though everything temporal turns to dust, I experienced some moments of eternity.

22. I can already predict the tweets: “No, Scott Aaronson, your weird numbered ruminations won’t save you from being the privileged douchebag who you fundamentally are.”  How was that?  Let me try another: “Aaronson embarrasses himself yet again, proves he doesn’t get why nerd culture is totally f-cked up.”  Here in the Party of Psychological Complexity, we’re used to this stuff.  We don’t fare well in social media wars, and we’ll gladly lose rather than become what we detest.  And yet, over the long run—which might be the very long run—we do mean to win, much like heliocentrism and quantum mechanics ultimately triumphed over simpler, more soundbite-friendly rivals.  Complex ideas win not through 140-character flinged excrement but through conversations, long-form essays, discourse, verbal technologies able to transfer large interconnected bundles of thoughts and emotions from one mind to another one that’s ready for such things.

23. Try every hour of every day to extend your sympathetic imagination to those who are unlike you (those who are like you don’t need such a strenuous effort).  And carve this message of universal compassion onto your doorposts, and bind it to your wrists, and put it for a sign on your foreheads.  There is no ideology that relieves us of the need to think and to feel: that’s my ideology.

24. When people give feedback about this blog’s topics, they seem roughly evenly split between those who beg for more quantum computing and other technical posts that they can actually learn from, and those who beg for more nontechnical posts that they can actually understand!  The truth is that, from the very beginning, this has never been a quantum computing or theoretical computer science blog—or rather it has been, but only incidentally.  If you had to sum it up in one sentence, I suppose this blog has been about surviving and thriving as a quantum complexity theorist in a world that isn’t designed for quantum complexity theorists?

25. But I’ll tell you what: my next post will be a quantum computing one, and I’ll make it worth the wait.  What else could I do by way of thanks to the world, and (more to the point) my family, friends, and readers?

Beyond fiction

Wednesday, August 8th, 2018

I now know firsthand what it’s like to be arrested by armed police officers, handcuffed, and sharply interrogated, while one’s wife and children look on helplessly.  This is not a prank post.

It happened in Philadelphia International Airport.  As someone who was born in Philadelphia, and who’s since visited ~40 countries on 6 continents and flies every week or two, I’ve long considered PHL possibly the most depressing airport on the planet (and the competition is fierce).

I’d just eaten dinner with my wife Dana and our two kids in a food court—after a day of travel that had already, before this happened, involved a missed flight and a lost suitcase, owing to a chain of mishaps that I’d (probably melodramatically) been describing to Dana as insane beyond the collective imagination of Homer and Shakespeare and Tolstoy and the world’s other literary giants to invent.  Again, that was before my arrest.

Two large uniformed men with holstered pistols saw me as we were exiting the airport, surrounded and handcuffed me, and demanded that I confess.

“I’m … sorry, officers,” I managed.  “I don’t understand what this is about.”

“Stop the games.  You know exactly what you took.  We have it all on video.  Where is it?”

Me, a thief?  I felt terrified to be at the beginning of a Kafka story.  But if I’m going to be brutally honest about it, I also felt … secretly vindicated in my irrational yet unshakeable beliefs that

  1. the laws of probability are broken, capricious horribleness reigning supreme over the universe,
  2. I’m despised by a large fraction of the world just for being who I am, and
  3. it’s only a matter of time until big, scary armed guys come for me, as they came for so many other nerdy misfits.

I almost wanted to say to the police: where have you been?  I’ve been expecting you my whole life.  And I wanted to say to Dana: you see??  see what I’ve been telling you all these years, about the nature of the universe we were born into?

Dana, for her part, was remonstrating with the officers that there must be some misunderstanding, that her husband was often absentminded but it’s completely impossible that he stole anything.  The officers brushed her away, told her to remove the kids from the situation.

“Are you gonna come clean?” one of the cops barked at me.  “We know you took it.”

“I didn’t take anything.”  Then I thought it over more.  “Or if somehow I did … then I’m certain that it would’ve been an accident, and I’d be more than happy to fix the…”

“Wait, if you did?  It sounds like you just confessed!”

“No, I definitely didn’t steal anything.  I’m just saying it’s possible that I might have mistakenly…”

“Your answers are rambling and all over the place.  Stop making up stories.  We know you did it.”

I’m not proud of myself for the next part, but the officers were so serious, and somehow I had to make them realize the sheer comical absurdity of what was happening.  “Look, I’m a computer science professor,” I said.  “I’ve never stolen a penny in my life, and it’s not something I’d ever…”

“Yeah, well I’m a police officer.  I’ve seen a lot in my thirty years in this job.  This is not about who you are, it’s about what you did.”

But what did I do?  After many more attempts to intimidate me, I was finally informed of the charge: “that smoothie place over there says you stole cash from their tip jar.”  Huh? How much?  One of the officers returned from the smoothie bar, and said, a bit sheepishly: “they say it was $4.”

Now a vague recollection came into sharper focus.  Yes, I had bought a berry smoothie for my daughter and a sparkling grapefruit juice for me.  I’d paid with a debit card, for reasons that I don’t remember, even though I normally pay cash.  My mind was elsewhere: on the missed flight, the lost suitcase, the brazen behavior of American Airlines (about which more later).  Then, completely forgetting I hadn’t paid cash this time, I looked down for my change: $4 in an unmarked plastic change cup.  I collected the change, put it in my wallet, then completely forgot about it.

After a minute, an employee angrily pointed down at a tray that the plastic cup was on (though not clearly at the cup itself), and said “hey, the tips go here!”  So I took a dollar from my wallet and put it on the tray.  I thought: this guy has some chutzpah, to demand a tip, and for an over-the-counter smoothie!  But whatever, he probably needs the dollar more than I do.  So if it will make him stop being angry…

But he was still angry.  He repeated: “this here is for tips!”

I said something to the effect of: “yeah, I know–that’s what you just told me, isn’t it?  So that’s why I just left you a tip!”  Sheesh.

At no point did he ever say, “you accidentally took from the tip jar,” or any other statement that would’ve clarified his meaning.

As I turned and walked away, I thought: yes, this is the strange world I was born into.  A world where people yell at me for not tipping at a smoothie bar–is that expected? I didn’t think it was–and then continue yelling even after I do.  But what did I expect?  Did I expect, as a nerdy outsider, to be able to buy normal people’s toleration with mere money?

As soon as I figured out what had happened, of course I offered to pay back the smoothie bar, not merely the $3 I still owed them, but $40 or whatever other amount would express my goodwill and compensate them for their trouble.  But the smoothie bar returned the $40 that I’d asked Dana to give them—I was unable to bring it myself on account of being handcuffed—and refused to press charges.  (In fact, apparently the employees hadn’t wanted to involve the police at all.  It was the manager, who hadn’t seen what happened, who’d insisted on it.)

So with no case, the police finally had no choice but to let me go–though not before giving me a stern lecture about never again putting my hands on stuff that’s not mine.


A week later, I’m still processing the experience.  In the rest of the post, I’d like to reflect on some lessons I think I learned from it.


First, it’s said that “a conservative is a liberal who’s been mugged; a liberal is a conservative who’s been arrested.”  It’s true: there are aspects of being arrested that are hard to understand until you’ve been through it.  While I’m white (well, insofar as Ashkenazim are), and while both officers who interrogated me happened to be African-Americans, what I went through further increased my sympathy for the many minority victims of aggressive policing.  Sitting in your armchair, it’s easy to think: in a liberal democracy, as long you know you did nothing wrong, even if you got arrested, frisked, detained, there’d probably be no real need to panic.  All you’d need to do is calmly clear up the misunderstanding and be back on your merry way.

But at least in my experience, an actual arrest isn’t like that.  The presumption of innocence, Miranda rights, all the things you might learn about in civics class—none of it seems to play any role.  From the very beginning, there’s an overwhelming presumption of guilt.  Everything you say gets interpreted as if you’re a red-handed criminal trying to fabricate a story, no matter how strained and how ludicrous such an interpretation might become.

And something strange happened: the officers seemed so certain I was guilty, that after only a few minutes I started to feel guilty.  I still had only a hazy sense of my “crime,” but I knew I was going to be punished for it, and I only hoped that the punishment wouldn’t tear me away from my family and previous life forever.

I came away from this incident with a visceral feel for just how easy it would be to procure a false confession from someone, which I didn’t have before but which will now stay with me as long as I live.


Second, it occurred to me that the sight of me, stuttering and potbellied complexity blogger, shackled and interrogated by armed policemen demanding that he confess to the theft of $3 from an airport stand, is a decent visual metaphor for much of my life.  If you doubt this, simply imagine Arthur Chu or Amanda Marcotte in place of the police officers.

It’s like: my accusers arrive on the scene committed to a specific, hostile theory of me: that I’m a petty thief of smoothie bars, let’s say, or a sexual-harassment-loving misogynist.  With all due modesty, people who know me might say that it’s not merely that I don’t fit the theory, that I happen to be innocent of the charge.  Rather, it’s that I’m one of the most astronomically, ridiculously unlikely people to fit the theory you could ever meet.  Not because I’m especially saintly, but simply because I already walk around all day feeling like my right to exist is conditional and might be revoked at any minute.  Breaking the normal people’s rules is the last thing on my agenda!  And yes, I still often feel that way, even as a professor with an endowed chair and awards and whatever.  The only times when I really relax, among strangers, is when everyone’s there to discuss ideas.

But my accusers don’t know any of that, or they refuse to believe it.  Everything I say gets interpreted in the light of the hostile theory, and therefore serves only as further confirmation of it.  Ironically—and this is key—the very unusual personality traits that make me so unlikely to be an offender, are also what throw off my accusers’ detection algorithms, and make them double down on their wrong theory.  When I’m trapped, I tend to fall back on the only tools I know: argument, openness, frank confession of my mistakes and failings, sometimes a little self-deprecating humor.  Unfortunately, I find this often backfires, as my accusers see in my vulnerability a golden opportunity to mount another wretched evildoer above their fireplace.

Or, to go even further out on a psychoanalytic limb: I sometimes get the sense that it gradually does dawn on my accusers that I’m not who they thought I was.  And then, far from prompting an apology, that realization seems to make my accusers even angrier, as if my throwing off their model of reality so badly, was an even worse offense than actually being guilty of whatever they thought!  A thief, a misogynist, they know how to handle.  But a living, breathing adversarial example for their worldview?

Dana, who watched the entire arrest, tells me that the central mistake I made was to try to reason with the police officers: “you say I took $3 that wasn’t mine?  If so, then I’m sure it was an accident, so let’s try to figure out what happened so we can fix it…”  In Dana’s view, what I saw as an earnest desire to get to the bottom of things, came across to grizzled cops only as evasiveness and guilt.  She says it would’ve been far better if I’d categorically denied: “no, I did not steal.  That’s completely absurd.  Please release me immediately.”

I’ve asked myself: how do you live in a world where, again and again, you can choose the hard right path over the easy wrong one, and then see your choice gleefully wielded against you?  Where you can spill your guts out to your accusers, in a desperate attempt to talk with them not as hardened warriors, but one confused and vulnerable human to another–and your reward is (to take one example) your picture in Salon above the headline “The Plight of the Bitter Nerd”?

The only way to live in such a world, as far as I can see, is to remind yourself that sometimes openness and vulnerability work.  In the course of my arrest, the two officers gradually differentiated themselves into a “good cop” and a “bad cop.”  While the “bad cop” treated me till the end like an unrepentant kleptomaniac being freed on a technicality, the “good cop,” who talked to me and Dana much more, became almost apologetic: “look man, when we get a call that someone stole money, we have to treat it like that’s the situation, you understand what I’m saying?  And then if it’s not, well then it’s not.”  Likewise, Arthur Chu recently tweeted that he’s “unhappy about [my] continued existence”–i.e., on a straightforward reading, that he wants me to die.  But I try to remind myself every day that the human race doesn’t consist solely of Arthur Chus (or Amanda Marcottes, or Lubos Motls, or SneerClub posters, or Paul Manaforts or Donald Trumps).  The world contains millions of women and men of every background and ideology who want actual dialogue, many of whom I’m lucky to count as friends, many of whom I met through this blog.  Vulnerability is possible because the world is not uniformly evil.


Third, I emerged from my arrest with a self-help technique that’s probably well-known to somebody, but that was new to me, and that I hope others will find as useful as I’m finding it.  Here it is: when something freakishly bad happens to you, draw a directed graph of all the known causes of the event, and the causes of the causes, and so forth as far back as you can trace them.  Also draw all the known measures that could have blocked the causal path leading to the bad event, and what prevented those measures from working or from being tried.

For example: why did I end up in handcuffs?  Firstly because, earlier in the day, Lily threw a temper tantrum that prevented us from packing and leaving for Logan Airport on time.  Because there was also heavy traffic on the way there.  Because we left from Harvard Square, and failed to factor in the extra 10 minutes to reach the airport, compared to if we’d left from MIT.  Because online check-in didn’t work.  Because when we did arrive, (barely) on time, the contemptuous American Airlines counter staff deliberately refused to check us in, chatting as we stewed impotently, so that we’d no longer be on time and they could legally give our seats away to others, and strand us in an airport with two young kids.  Because the only replacement flight was in a different terminal.  Because, in the stress of switching terminals–everything is stressful with two kids in an airport–I lost our suitcase.  Because the only shuttle to get back to the terminal went around the long way, and was slow as molasses, and by the time I returned our suitcase had been taken by the bomb squad.  Because the stress of such events bears down on me like an iron weight, and makes me unable to concentrate on the reality in front of me.  Because the guy at the smoothie counter and I failed to communicate.  Because the police chose to respond (or were trained to respond), not by politely questioning me to try to understand what had happened, but by handcuffing me and presuming guilt.

I actually drew the graph, filled a notebook page with it–and when I searched it for answers, neither I nor the world got off easily.  Looking over the strange chain of events that led to my arrest, I could find much to support my “default narrative,” that the laws of probability are broken and the universe is grotesquely awful.  But also, my belief in the universe’s grotesque awfulness clearly played a role in the events.  Had I been able maintain a calm demeanor, I would not have made so many mistakes.

Again and again, I screwed up.  Again and again, airport personnel responded to my honest mistakes with a maximum of cold bureaucracy rather than commonsense discussion: the booting from the flight, the bomb squad, the handcuffs.

We tend to think of bureaucracy as a mere nuisance, the person behind the counter at the Department of Motor Vehicles who makes you wait all day and then sends you home to get a different form of ID.  In my view, though, the bureaucratic impulse is one of the worst evils of which the human mind is capable.  It is, after all, the impulse that once sent trainloads of Jewish children to their deaths because that was the policy and there were no documents stating that any exception should be made in this case.  Today it’s the impulse that rounds up and deports people who’ve lived in the US for decades, sometimes served in the army, etc., and that separates screaming children from their parents.  To me, the mindset that willingly carries out such orders is almost more terrifying than the mindset that gives the orders in the first place.  I don’t mean to suggest, of course, that my arrest was even a trillionth as bad as those other things; at most I got a tiny, accidental taste of many less fortunate people’s daily reality.  But it’s worth remembering: every time you exercise official power over another person without even trying to talk it over first, clear up any honest misunderstandings, find out if there’s a reasonable explanation, you’re surrendering to one of the most destructive impulses in the history of civilization.

May we each strive to kill the bureaucrat in us and nurture the human being.


Unrelated Announcements:

I’m in Mexico City this week, to participate in a computer science and philosophy conference at UNAM and then give a broad quantum computing talk at CViCom 2018.  Because of this, responses to this post might be delayed.

(Update: But I’m having a wonderful time in Mexico!  Lots of delicious mole and horchata, and no arrests so far.  Today I gave my survey talk on P vs. NP.  I opened with the following icebreaker: “As a computer scientist speaking in a philosophy institute, I apologize that my talk will contain very little philosophy  Also, as an American speaking in Mexico, I apologize for our president.”)

My friend Elette Boyle asked me to announce that the 2018 CRYPTO conference, to be held in Santa Barbara, will be preceded by exciting workshops, including one that I’ll be speaking at myself entitled Beyond Crypto: A Theory Perspective.  Register now if you’re interested.

Huge congratulations to Costis Daskalakis, my former MIT colleague, for winning the Nevanlinna Prize for his work in algorithmic game theory!  While I don’t pretend to understand their work, congratulations to the four new Fields Medalists as well.

I put a new preprint online: Quantum Lower Bound for Approximate Counting Via Laurent Polynomials.

I’ve added a new blog to my blogroll: The Unit of Caring. I’ve been impressed by the author’s moral adeptness: when she addresses contentious debates among nerds, rationalists, feminists, SJWs, etc. etc., she often seems perfectly balanced on an atom-thin tightrope, even as some of us are plummetting left and right.

I forgot to mention this earlier, but I’m now a donor to the campaign of Beto O’Rourke, as he strives to unseat the quisling Ted Cruz in my adopted home state of Texas.  Americans: please consider donating as well!


Further Thoughts (Aug. 9):

  1. I wholeheartedly endorse an observation that many commenters (on this blog and elsewhere) made independently: that what really happened, is that I was forced to live out an episode of Seinfeld or Curb Your Enthusiasm.  To my detractors, I say the following: try for one minute to imagine how pathological, narcissistic, far outside the human norm, etc. etc. you could make Seinfeld or George or Kramer or Elaine seem, if their misadventures from any given episode were described and analyzed with clinical detachment.  (Or you were never a Seinfeld fan, then I guess this argument fails and we have nothing to say to each other.)
  2. I feel like some commenters are imposing their own after-the-fact knowledge (“c’mon, it was obviously a tip jar, he must be lying!”).  Dana, who’s generally more grounded than I am, saw their whole setup and agreed it was profoundly non-obvious that the tiny, unmarked plastic cup was supposed to be for tips, particularly to someone who was extremely stressed and not concentrating.  And when the employee later talked about tips, he didn’t indicate the cup so I didn’t make a connection.
  3. Most importantly: I wish to clarify that I don’t regard the police officers who handcuffed and interrogated me as having been “evil” in any sense.  I even took a liking to the “good cop,” the one who implicitly acknowledged the situation’s surreal absurdity by the end (although maybe that’s the whole point of a “good cop”?).  Having said that, I’m still rattled by the way the “bad cop” treated me as an unrepentant thief even to the end, even after the situation had been cleared up to everyone else’s satisfaction.  And I stand by my view that there was no need to handcuff me in front of my wife and young children, when I’d shown not a single subatomic particle of resistance.
  4. Speaking of which, let me now relate the most interesting and unexpected part of the reaction to my story.  Again and again, I found that fellow Americans, even nominally left-wing ones, sided with the police, said that I was crazy and guilty as charged and should’ve expected much worse, etc.  And again and again, commenters from Australia and New Zealand sided with me 300%, said that handcuffing someone over such a trivial mishap was a ludicrous overreaction, which would be totally unheard of in their countries and which confirms all the bad things they’ve heard about the US.  So maybe the rational conclusion is that I should be learning to enjoy vegemite in preparation for a move down under?