Category Archives: The expert’s corner

You ask, we answer your questions related to the fascinating science at IQIM.

Quantum connections

Posted on by
2

We were seated in the open-air back of a boat, motoring around the Stockholm archipelago. The Swedish colors fluttered above our heads; the occasional speedboat zipped past, rocking us in its wake; and wildflowers dotted the bank on either side. Suddenly, a wood-trimmed boat glided by, and the captain waved from his perch.

The gesture surprised me. If I were in a vehicle of the sort most familiar to me—a car—I wouldn’t wave to other drivers. In a tram, I wouldn’t wave to passengers on a parallel track. Granted, trams and cars are closed, whereas boats can be open-air. But even as a pedestrian in a downtown crossing, I wouldn’t wave to everyone I passed. Yet, as boat after boat pulled alongside us, we received salutation after salutation.

The outing marked the midpoint of the Quantum Connections summer school. Physicists Frank Wilczek, Antti Niemi, and colleagues coordinate the school, which draws students and lecturers from across the globe. Although sponsored by Stockholm University, the school takes place at a century-old villa whose name I wish I could pronounce: Högberga Gård. The villa nestles atop a cliff on an island in the archipelago. We ventured off the island after a week of lectures.

Charlie Marcus lectured about materials formed from superconductors and semiconductors; John Martinis, about superconducting qubits; Jianwei Pan, about quantum advantages; and others, about symmetries, particle statistics, and more. Feeling like an ant among giants, I lectured about quantum thermodynamics. Two other lectures linked quantum physics with gravity—and in a way you might not expect. I appreciated the opportunity to reconnect with the lecturer: Igor Pikovski.

Cruising around Stockholm

Igor doesn’t know it, but he’s one of the reasons why I joined the Harvard-Smithsonian Institute for Theoretical Atomic, Molecular, and Optical Physics (ITAMP) as an ITAMP Postdoctoral Fellow in 2018. He’d held the fellowship beginning a few years before, and he’d earned a reputation for kindness and consideration. Also, his research struck me as some of the most fulfilling that one could undertake.

If you’ve heard about the intersection of quantum physics and gravity, you’ve probably heard of approaches other than Igor’s. For instance, physicists are trying to construct a theory of quantum gravity, which would describe black holes and the universe’s origin. Such a “theory of everything” would reduce to Einstein’s general theory of relativity when applied to planets and would reduce to quantum theory when applied to atoms. In another example, physicists leverage quantum technologies to observe properties of gravity. Such technologies enabled the observatory LIGO to register gravitational waves—ripples in space-time. 

Igor and his colleagues pursue a different goal: to observe phenomena whose explanations depend on quantum theory and on gravity.

In his lectures, Igor illustrated with an experiment first performed in 1975. The experiment relies on what happens if you jump: You gain energy associated with resisting the Earth’s gravitational pull—gravitational potential energy. A quantum object’s energy determines how the object’s quantum state changes in time. The experimentalists applied this fact to a beam of neutrons. 

They put the beam in a superposition of two locations: closer to the Earth’s surface and farther away. The closer component changed in time in one way, and the farther component changed another way. After a while, the scientists recombined the components. The two interfered with each other similarly to the waves created by two raindrops falling near each other on a puddle. The interference evidenced gravity’s effect on the neutrons’ quantum state.

Summer-school venue. I’d easily say it’s gorgeous but not easily pronounce its name.

The experimentalists approximated gravity as dominated by the Earth alone. But other masses can influence the gravitational field noticeably. What if you put a mass in a superposition of different locations? What would happen to space-time?

Or imagine two quantum particles too far apart to interact with each other significantly. Could a gravitational field entangle the particles by carrying quantum correlations from one to the other?

Physicists including Igor ponder these questions…and then ponder how experimentalists could test their predictions. The more an object influences gravity, the more massive the object tends to be, and the more easily the object tends to decohere—to spill the quantum information that it holds into its surroundings.

The “gravity-quantum interface,” as Igor entitled his lectures, epitomizes what I hoped to study in college, as a high-school student entranced by physics, math, and philosophy. What’s more curious and puzzling than superpositions, entanglement, and space-time? What’s more fundamental than quantum theory and gravity? Little wonder that connecting them inspires wonder.

But we humans are suckers for connections. I appreciated the opportunity to reconnect with a colleague during the summer school. Boaters on the Stockholm archipelago waved to our cohort as they passed. And who knows—gravitational influences may even have rippled between the boats, entangling us a little.

Requisite physicist-visiting-Stockholm photo

With thanks to the summer-school organizers, including Pouya Peighami and Elizabeth Yang, for their invitation and hospitality.

These are a few of my favorite steampunk books

Posted on by
Reply

As a physicist, one grows used to answering audience questions at the end of a talk one presents. As a quantum physicist, one grows used to answering questions about futuristic technologies. As a quantum-steampunk physicist, one grows used to the question “Which are your favorite steampunk books?”

Literary Hub has now published my answer.

According to its website, “Literary Hub is an organizing principle in the service of literary culture, a single, trusted, daily source for all the news, ideas and richness of contemporary literary life. There is more great literary content online than ever before, but it is scattered, easily lost—with the help of its editorial partners, Lit Hub is a site readers can rely on for smart, engaged, entertaining writing about all things books.”

My article, “Five best books about the romance of Victorian science,” appeared there last week. You’ll find fiction, nonfiction as imaginative as fiction, and crossings of the border between the two. 

My contribution to literature about the romance of Victorian science—my (mostly) nonfiction book, Quantum Steampunk: The Physics Of Yesterday’s Tomorrow—was  published two weeks ago. Where’s a hot-air-balloon emoji when you need one?

One equation to rule them all?

Posted on by
1

In lieu of composing a blog post this month, I’m publishing an article in Quanta Magazine. The article provides an introduction to fluctuation relations, souped-up variations on the second law of thermodynamics, which helps us understand why time flows in only one direction. The earliest fluctuation relations described classical systems, such as single strands of DNA. Many quantum versions have been proved since. Their proliferation contrasts with the stereotype of physicists as obsessed with unification—with slimming down a cadre of equations into one über-equation. Will one quantum fluctuation relation emerge to rule them all? Maybe, and maybe not. Maybe the multiplicity of quantum fluctuation relations reflects the richness of quantum thermodynamics.

You can read more in Quanta Magazine here and yet more in chapter 9 of my book. For recent advances in fluctuation relations, as opposed to the broad introduction there, check out earlier Quantum Frontiers posts here, here, here, here, and here.

How a liberal-arts education has enhanced my physics research

Posted on by
6

I attended a liberal-arts college, and I reveled in the curriculum’s breadth. My coursework included art history, psychology, biology, economics, computer science, German literature, archaeology, and chemistry. My major sat halfway between the physics major and the create-your-own major; the requirements consisted mostly of physics but included math, philosophy, and history. By the end of college, I’d determined to dive into physics. So I undertook a physics research assistantship, enlisted in a Master’s program and then a PhD program, and became a theoretical physicist. I’m now building a physics research group that spans a government institute and the University of Maryland. One might think that I became a physicist despite my art history and archaeology. 

My liberal-arts education did mortify me a little as I pursued my Master’s degree. Most of my peers had focused on physics, mathematics, and computer science while I’d been reading Aristotle. They seemed to breeze through coursework that I clawed my way through. I still sigh wistfully over math courses, such as complex analysis, that I’ve never taken. Meanwhile, a debate about the liberal arts has been raging across the nation. Debt is weighing down recent graduates, and high-school students are loading up on STEMM courses. Colleges are cutting liberal-arts departments, and educational organizations are broadcasting the value of liberal-arts educations.

I’m not an expert in public policy or school systems; I’m a physicist. As a physicist, I’m grateful for my liberal-arts education. It’s enhanced my physics research in at least five ways.

(1) I learned to seek out, and take advantage of, context. Early in my first German-literature course, I’d just completed my first reading assignment. My professor told my class to fetch out our books and open them to the beginning. A few rustles later, we held our books open to page one of the main text. 

No, no, said my professor. Open your books to the beginning. Did anyone even look at the title page?

We hadn’t, we admitted. We’d missed a wealth of information, as the book contained a reproduction of an old title page. Publishers, fonts, and advertisement styles have varied across the centuries and the globe. They, together with printing and reprinting dates, tell stories about the book’s origin, popularity, role in society, and purposes. Furthermore, a frontispiece is worth a thousand words, all related before the main text begins. When my class turned to the main text, much later in the lecture, we saw it in a new light. Context deepens and broadens our understanding.

When I read a physics paper, I start at the beginning—the true beginning. I note the publication date, the authors, their institutions and countries, and the journal. X’s lab performed the experiment reported on? X was the world’s expert in Y back then but nursed a bias against Z, a bias later proved to be unjustified. So I should aim to learn from the paper about Y but should take statements about Z with a grain of salt. Seeking and processing context improves my use of physics papers, thanks to a German-literature course.

(2) I learned argumentation. Doing physics involves building, analyzing, criticizing, and repairing arguments. I argue that mathematical X models physical system Y accurately, that an experiment I’ve proposed is feasible with today’s technology, and that observation Z supports a conjecture of mine. Physicists also prove mathematical statements deductively. I received proof-writing lessons in a math course, halfway through college. One of the most competent teachers I’ve ever encountered taught the course. But I learned about classes of arguments and about properties of arguments in a philosophy course, Informal Logic. 

There, I learned to distinguish deduction from inference and an argument’s validity and soundness from an argument’s strength and cogency. I learned strategies for proving arguments and learned fallacies to criticize. I came to respect the difference between “any” and “every,” which I see interchanged in many physics papers. This philosophical framework helps me formulate, process, dissect, criticize, and correct physics arguments. 

For instance, I often parse long, dense, technical proofs of mathematical statements. First, I identify whether the proof strategy is reductio ad absurdum, proof by counterexample, or another strategy. Upon identifying the overarching structure, I can fill my understanding with details. Additionally, I check proofs by students, and I respond to criticisms of my papers by journal referees. I could say, upon reading an argument, “Something feels a bit off, and it’s sort of like the thing that felt a bit off in that paper I read last Tuesday.” But I’d rather group the argument I’m given together with arguments I know how to tackle. I’d rather be able to say, “They’re straw-manning my argument” or “That argument begs the question.” Doing so, I put my finger on the problem and take a step toward solving it.

(3) I learned to analyze materials to bits, then extract meaning from the analysis. English and German courses trained me to wring from literature every drop of meaning that I could discover. I used to write one to three pages about a few-line quotation. The analysis would proceed from diction and punctuation to literary devices; allusions; characters’ relationships with each other, themselves, and nature; and the quotation’s role in the monograph. Everything from minutia to grand themes required scrutiny, according to the dissection technique I trained in. Every pincer probe lifted another skein of skin or drew aside another tendon, offering deeper insights into the literary work. I learned to find the skeins to lift, lift them in the right direction, pinpoint the insights revealed, and integrate the insights into a coherent takeaway.

This training has helped me assess and interpret mathematics. Physicists pick a physical system to study, model the system with equations, and solve the equations. The next two steps are intertwined: evaluating whether one solved the equations correctly and translating the solution into the physical system’s behavior. These two steps necessitate a dissection of everything from minutia to grand themes: Why should this exponent be 4/5, rather than any other number? Should I have expected this energy to depend on that length in this way? Is the physical material aging quickly or resisting change? These questions’ answers inform more-important questions: Who cares? Do my observations shed light worth anyone’s time, or did I waste a week solving equations no one should care about?

To answer all these questions, I draw on my literary training: I dissect content, pinpoint insights, and extract meaning. Having performed this analysis in literature courses facilitates an arguably deeper analysis than my physics training did: In literature courses, I had to organize my thoughts and articulate them in essays. This process revealed holes in my argumentation, as well as connections that I’d overlooked. In contrast, a couple of lines in my physics homework earned full marks. The critical analysis of literature has deepened my assessment of solutions’ correctness, physical interpretation of mathematics, and extraction of meaning from solutions. 

(4) I learned what makes a physicist a physicist. In college, I had a friend who was studying applied mathematics and economics. Over dinner, he described a problem he’d encountered in his studies. I replied, almost without thinking, “From a physics perspective, I’d approach the problem like this.” I described my view, which my friend said he wouldn’t have thought of. I hadn’t thought of myself, and of the tools I was obtaining in the physics department, the way I did after our conversation. 

Physics involves a unique toolkit,1 set of goals, and philosophy. Physicists identify problems, model them, solve them, and analyze the results in certain ways. Students see examples of these techniques in lectures and practice these techniques for homework. But, as a student, I rarely heard articulations of the general principles that underlay the examples scattered across my courses like a handful of marbles across a kitchen floor. Example principles include, if you don’t understand an abstract idea, construct a simple example. Once you’ve finished a calculation, check whether your answer makes sense in the most extreme scenarios possible. After solving an equation, interpret the solution in terms of physical systems—of how particles and waves move and interact. 

I was learning these techniques, in college, without realizing that I was learning them. I became conscious of the techniques by comparing the approach natural to me with the approach taken in another discipline. Becoming conscious of my toolkit enabled me to wield it more effectively; one can best fry eggs when aware that one owns a spatula. The other disciplines at my liberal-arts college served as a foil for physics. Seeing other disciplines, I saw what makes physics physics—and improved my ability to apply my physics toolkit.

(5) I learned to draw connections between diverse ideas. Senior year of high school, my courses extended from physics to English literature. One might expect such a curriculum to feel higgledy-piggledy, but I found threads that ran through all my courses. For instance, I practiced public speaking in Reasoning, Research, and Rhetoric. Because I studied rhetoric, my philosophy teacher turned to me for input when introducing the triumvirate “thesis, antithesis, synthesis.”2 The philosophy curriculum included the feminist essay “If Men Could Menstruate,” which complemented the feminist book Wide Sargasso Sea in my English-literature course. In English literature, I learned that Baldassare Castiglione codified how Renaissance noblemen should behave, in The Book of the Courtier. The author’s name was the answer to the first question on my AP Modern European History exam. My history course covered Isaac Newton and Gottfried Wilhelm Leibniz, who invented calculus during the 17th century. I leveraged their discoveries in my calculus course, which I applied in my physics course. My physics teacher hoped that his students would solve the world’s energy problems—perhaps averting the global thermonuclear war that graced every debate in my rhetoric course (“If you don’t accept my team’s policy, then X will happen, leading to Y, leading to Z, which will cause a global thermonuclear war”). 

Threads linked everything across my liberal-arts education; every discipline featured an idea that paralleled an idea in another discipline. Finding those parallels grew into a game for me, a game that challenged my creativity. Cultivating that creativity paid off when I began doing physics research. Much of my research has resulted from finding, in one field, a concept that resembles a concept in another field. I smash the ideas together to gain insight into each discipline from the other discipline’s perspective. For example, during my PhD studies, I found a thread connecting the physics of DNA strands to the physics of black holes. That thread initiated a research program of mine that’s yielded nine papers, garnered 19 collaborators, and spawned two experiments. Studying diverse subjects trained me to draw creative connections, which underlie much physics research.

I haven’t detailed all the benefits that a liberal-arts education can accrue to a physics career. For instance, the liberal arts enhance one’s communication skills, key to collaborating on research and to conveying one’s research. Without conveying one’s research adroitly, one likely won’t impact a field much. Also, a liberal-arts education can help one connect with researchers from across the globe on a personal level.3 Personal connections enhance science, which scientists—humans—undertake.

As I began building my research group, I sought advice from an MIT professor who’d attended MIT as an undergraduate. He advised me to seek students who have unusual backgrounds, including liberal-arts educations. Don’t get me wrong; I respect and cherish the colleagues and friends of mine who attended MIT, Caltech, and other tech schools as undergraduates. Still, I wouldn’t trade my German literature and economics. The liberal arts have enriched my physics research no less than they’ve enriched the rest of my life.

1A toolkit that overlaps partially with other disciplines’ toolkits, as explained in (3).

2I didn’t help much. When asked to guess the last concept in the triumvirate, I tried “debate.”

3I once met a Ukrainian physicist who referred to Ilya Muromets in a conversation. Ilya Muromets is a bogatyr, a knight featured in Slavic epics set in the Middle Ages. I happened to have taken a Slavic-folklore course the previous year. So I responded with a reference to Muromets’s pals, Dobrynya Nikitich and Alyosha Popovich. The physicist and I hit it off, and he taught me much about condensed matter over the following months.

Quantum steampunk is heading to bookstores!

Posted on by
13

I’m publishing a book! Quantum Steampunk: The Physics of Yesterday’s Tomorrow is hitting bookstores next spring, and you can preorder it now.

As Quantum Frontiers regulars know, steampunk is a genre of literature, art and film. Steampunkers fuse 19th-century settings (such as Victorian England, the Wild West, and Meiji Japan) with futuristic technologies (such as dirigibles, time machines, and automata). So does my field of research, a combination of thermodynamics, quantum physics, and information processing. 

Thermodynamics, the study of energy, developed during the Industrial Revolution. The field grew from practical concerns (How efficiently can engines pump water out of mines?) but wound up addressing fundamental questions (Why does time flow in only one direction?). Thermodynamics needs re-envisioning for 21st-century science, which spotlights quantum systems—electrons, protons, and other basic particles. Early thermodynamicists couldn’t even agree that atoms existed, let alone dream that quantum systems could process information in ways impossible for nonquantum systems. Over the past few decades, we’ve learned that quantum technologies can outperform their everyday counterparts in solving certain computational problems, in securing information, and in transmitting information. The study of quantum systems’ information-processing power forms a mathematical and conceptual toolkit, quantum information science. My colleagues and I leverage this toolkit to reconceptualize thermodynamics. As we combine a 19th-century framework (thermodynamics) with advanced technology (quantum information), I call our field quantum steampunk.

Glimpses of quantum steampunk have surfaced on this blog throughout the past eight years. The book is another animal, a 15-chapter closeup of the field. The book sets the stage with introductions to information processing, quantum physics, and thermodynamics. Then, we watch these three perspectives meld into one coherent whole. We tour the landscape of quantum thermodynamics—the different viewpoints and discoveries championed by different communities. These viewpoints, we find, offer a new lens onto the rest of science, including chemistry, black holes, and materials physics. Finally, we peer through a brass telescope to where quantum steampunk is headed next. Throughout the book, the science interleaves with anecdotes, history, and the story of one woman’s (my) journey into physics—and with snippets from a quantum-steampunk novel that I’ve dreamed up.

On this blog, different parts of my posts are intended for different audiences. Each post contains something for everyone, but not everyone will understand all of each post. In contrast, the book targets the general educated layperson. One of my editors majored in English, and another majored in biology, so the physics should come across clearly to everyone (and if it doesn’t, blame my editors). But the book will appeal to physicists, too. Reviewer Jay Lawrence, a professor emeritus of Dartmouth College’s physics department, wrote, “Presenting this vision [of quantum thermodynamics] in a manner accessible to laypeople discovering new interests, Quantum Steampunk will also appeal to specialists and aspiring specialists.” This book is for you.

Painting, by Robert Van Vranken, that plays a significant role in the book.

Strange to say, I began writing Quantum Steampunk under a year ago. I was surprised to receive an email from Tiffany Gasbarrini, a senior acquisitions editor at Johns Hopkins University Press, in April 2020. Tiffany had read the article I’d written about quantum steampunk for Scientific American. She wanted to expand the press’s offerings for the general public. Would I be interested in writing a book proposal? she asked.

Not having expected such an invitation, I poked around. The press’s roster included books that caught my eye, by thinkers I wanted to meet. From Wikipedia, I learned that Johns Hopkins University Press is “the oldest continuously running university press in the United States.” Senior colleagues of mine gave the thumbs-up. So I let my imagination run.

I developed a table of contents while ruminating on long walks, which I’d begun taking at the start of the pandemic. In late July, I submitted my book proposal. As the summer ended, I began writing the manuscript.

Writing the first draft—73,000 words—took about five months. The process didn’t disrupt life much. I’m used to writing regularly; I’ve written one blog post per month here since 2013, and I wrote two novels during and after college. I simply picked up my pace. At first, I wrote only on weekends. Starting in December 2020, I wrote 1,000 words per day. The process wasn’t easy, but it felt like a morning workout—healthy and productive. That productivity fed into my science, which fed back into the book. One of my current research projects grew from the book’s epilogue. A future project, I expect, will evolve from Chapter 5.

As soon as I finished draft one—last January—Tiffany and I hunted for an illustrator. We were fortunate to find Todd Cahill, a steampunk artist. He transformed the poor sketches that I’d made into works of art.

Steampunk illustration of a qubit, the basic unit of quantum information, by Todd Cahill

Early this spring, I edited the manuscript. That edit was to a stroll as the next edit was to the Boston Marathon. Editor Michael Zierler coached me through the marathon. He identified concepts that needed clarification, discrepancies between explanations, and analogies that had run away with me—as well as the visions and turns of phrase that delighted him, to balance the criticism. As Michael and I toiled, 17 of my colleagues were kind enough to provide feedback. They read sections about their areas of expertise, pointed out subtleties, and confirmed facts.

Soon after Michael and I crossed the finished line, copyeditor Susan Matheson took up the baton. She hunted for typos, standardized references, and more. Come June, I was editing again—approving and commenting on her draft. Simultaneously, Tiffany designed the cover, shown above, with more artists. The marketing team reached out, and I began planning this blog post. Scratch that—I’ve been dreaming about this blog post for almost a year. But I forced myself not to spill the beans here till I told the research group I’ve been building. I shared about the book with them two Thursdays ago, and I hope that book critics respond as they did.

Every time I’ve finished a draft, my husband and I have celebrated by ordering takeout sandwiches from our favorite restaurant. Three sandwich meals are down, and we have one to go.

Having dreamed about this blog post for a year, I’m thrilled to bits to share my book with you. It’s available for preordering, and I encourage you to support your local bookstore by purchasing through bookshop.org. The book is available also through Barnes & Noble, Amazon, Waterstones, and the other usual suspects. For press inquiries, or to request a review copy, contact Kathryn Marguy at kmarguy@jhu.edu.

Over the coming year, I’ll continue sharing about my journey into publishing—the blurbs we’ll garner for the book jacket, the first copies hot off the press, the reviews and interviews. I hope that you’ll don your duster coat and goggles (every steampunker wears goggles), hop into your steam-powered gyrocopter, and join me.

Learning about learning

Posted on by
3

The autumn of my sophomore year of college was mildly hellish. I took the equivalent of three semester-long computer-science and physics courses, atop other classwork; co-led a public-speaking self-help group; and coordinated a celebrity visit to campus. I lived at my desk and in office hours, always declining my flatmates’ invitations to watch The West Wing. 

Hard as I studied, my classmates enjoyed greater facility with the computer-science curriculum. They saw immediately how long an algorithm would run, while I hesitated and then computed the run time step by step. I felt behind. So I protested when my professor said, “You’re good at this.” 

I now see that we were focusing on different facets of learning. I rued my lack of intuition. My classmates had gained intuition by exploring computer science in high school, then slow-cooking their experiences on a mental back burner. Their long-term exposure to the material provided familiarity—the ability to recognize a new problem as belonging to a class they’d seen examples of. I was cooking course material in a mental microwave set on “high,” as a semester’s worth of material was crammed into ten weeks at my college.

My professor wasn’t measuring my intuition. He only saw that I knew how to compute an algorithm’s run time. I’d learned the material required of me—more than I realized, being distracted by what I hadn’t learned that difficult autumn.

We can learn a staggering amount when pushed far from our comfort zones—and not only we humans can. So can simple collections of particles.

Examples include a classical spin glass. A spin glass is a collection of particles that shares some properties with a magnet. Both a magnet and a spin glass consist of tiny mini-magnets called spins. Although I’ve blogged about quantum spins before, I’ll focus on classical spins here. We can imagine a classical spin as a little arrow that points upward or downward.  A bunch of spins can form a material. If the spins tend to point in the same direction, the material may be a magnet of the sort that’s sticking the faded photo of Fluffy to your fridge.

The spins may interact with each other, similarly to how electrons interact with each other. Not entirely similarly, though—electrons push each other away. In contrast, a spin may coax its neighbors into aligning or anti-aligning with it. Suppose that the interactions are random: Any given spin may force one neighbor into alignment, gently ask another neighbor to align, entreat a third neighbor to anti-align, and having nothing to say to neighbors four and five.

The spin glass can interact with the external world in two ways. First, we can stick the spins in a magnetic field, as by placing magnets above and below the glass. If aligned with the field, a spin has negative energy; and, if antialigned, positive energy. We can sculpt the field so that it varies across the spin glass. For instance, spin 1 can experience a strong upward-pointing field, while spin 2 experiences a weak downward-pointing field.

Second, say that the spins occupy a fixed-temperature environment, as I occupy a 74-degree-Fahrenheit living room. The spins can exchange heat with the environment. If releasing heat to the environment, a spin flips from having positive energy to having negative—from antialigning with the field to aligning.

Let’s perform an experiment on the spins. First, we design a magnetic field using random numbers. Whether the field points upward or downward at any given spin is random, as is the strength of the field experienced by each spin. We sculpt three of these random fields and call the trio a drive.

Let’s randomly select a field from the drive and apply it to the spin glass for a while; again, randomly select a field from the drive and apply it; and continue many times. The energy absorbed by the spins from the fields spikes, then declines.

Now, let’s create another drive of three random fields. We’ll randomly pick a field from this drive and apply it; again, randomly pick a field from this drive and apply it; and so on. Again, the energy absorbed by the spins spikes, then tails off.

Here comes the punchline. Let’s return to applying the initial fields. The energy absorbed by the glass will spike—but not as high as before. The glass responds differently to a familiar drive than to a new drive. The spin glass recognizes the original drive—has learned the first fields’ “fingerprint.” This learning happens when the fields push the glass far from equilibrium,1 as I learned when pushed during my mildly hellish autumn.

So spin glasses learn drives that push them far from equilibrium. So do many other simple, classical, many-particle systems: polymers, viscous liquids, crumpled sheets of Mylar, and more. Researchers have predicted such learning and observed it experimentally. 

Scientists have detected many-particle learning by measuring thermodynamic observables. Examples include the energy absorbed by the spin glass—what thermodynamicists call work. But thermodynamics developed during the 1800s, to describe equilibrium systems, not to study learning. 

One study of learning—the study of machine learning—has boomed over the past two decades. As described by the MIT Technology Review, “[m]achine-learning algorithms use statistics to find patterns in massive amounts of data.” Users don’t tell the algorithms how to find those patterns.

xkcd.com/1838

It seems natural and fitting to use machine learning to learn about the learning by many-particle systems. That’s what I did with collaborators from the group of Jeremy England, a GlaxoSmithKline physicist who studies complex behaviors of many particle systems. Weishun Zhong, Jacob Gold, Sarah Marzen, Jeremy, and I published our paper last month. 

Using machine learning, we detected and measured many-particle learning more reliably and precisely than thermodynamic measures seem able to. Our technique works on multiple facets of learning, analogous to the intuition and the computational ability I encountered in my computer-science course. We illustrated our technique on a spin glass, but one can apply our approach to other systems, too. I’m exploring such applications with collaborators at the University of Maryland.

The project pushed me far from my equilibrium: I’d never worked with machine learning or many-body learning. But it’s amazing, what we can learn when pushed far from equilibrium. I first encountered this insight sophomore fall of college—and now, we can quantify it better than ever.

1Equilibrium is a quiet, restful state in which the glass’s large-scale properties change little. No net flow of anything—such as heat or particles—enter or leave the system.

Project Ant-Man

Posted on by
3

The craziest challenge I’ve undertaken hasn’t been skydiving; sailing the Amazon on a homemade raft; scaling Mt. Everest; or digging for artifacts atop a hill in a Middle Eastern desert, near midday, during high summer.1 The craziest challenge has been to study the possibility that quantum phenomena affect cognition significantly. 

Most physicists agree that quantum phenomena probably don’t affect cognition significantly. Cognition occurs in biological systems, which have high temperatures, many particles, and watery components. Such conditions quash entanglement (a relationship that quantum particles can share and that can produce correlations stronger than any produceable by classical particles). 

Yet Matthew Fisher, a condensed-matter physicist, proposed a mechanism by which entanglement might enhance coordinated neuron firing. Phosphorus nuclei have spins (quantum properties similar to angular momentum) that might store quantum information for long times when in Posner molecules. These molecules may protect the information from decoherence (leaking quantum information to the environment), via mechanisms that Fisher described.

I can’t check how correct Fisher’s proposal is; I’m not a biochemist. But I’m a quantum information theorist. So I can identify how Posners could process quantum information if Fisher were correct. I undertook this task with my colleague Elizabeth Crosson, during my PhD. 

Experimentalists have begun testing elements of Fisher’s proposal. What if, years down the road, they find that Posners exist in biofluids and protect quantum information for long times? We’ll need to test whether Posners can share entanglement. But detecting entanglement tends to require control finer than you can exert with a stirring rod. How could you check whether a beakerful of particles contains entanglement?

I asked that question of Adam Bene Watts, a PhD student at MIT, and John Wright, then an MIT postdoc and now an assistant professor in Texas. John gave our project its codename. At a meeting one day, he reported that he’d watched the film Avengers: Endgame. Had I seen it? he asked.

No, I replied. The only superhero movie I’d seen recently had been Ant-Man and the Wasp—and that because, according to the film’s scientific advisor, the movie riffed on research of mine. 

Go on, said John.

Spiros Michalakis, the Caltech mathematician in charge of this blog, served as the advisor. The film came out during my PhD; during a meeting of our research group, Spiros advised me to watch the movie. There was something in it “for you,” he said. “And you,” he added, turning to Elizabeth. I obeyed, to hear Laurence Fishburne’s character tell Ant-Man that another character had entangled with the Posner molecules in Ant-Man’s brain.2 

John insisted on calling our research Project Ant-Man.

John and Adam study Bell tests. Bell test sounds like a means of checking whether the collar worn by your cat still jingles. But the test owes its name to John Stewart Bell, a Northern Irish physicist who wrote a groundbreaking paper in 1964. 

Say you’d like to check whether two particles share entanglement. You can run an experiment, described by Bell, on them. The experiment ends with a measurement of the particles. You repeat this experiment in many trials, using identical copies of the particles in subsequent trials. You accumulate many measurement outcomes, whose statistics you calculate. You plug those statistics into a formula concocted by Bell. If the result exceeds some number that Bell calculated, the particles shared entanglement.

We needed a variation on Bell’s test. In our experiment, every trial would involve hordes of particles. The experimentalists—large, clumsy, classical beings that they are—couldn’t measure the particles individually. The experimentalists could record only aggregate properties, such as the intensity of the phosphorescence emitted by a test tube.

Adam, MIT physicist Aram Harrow, and I concocted such a Bell test, with help from John. Physical Review A published our paper this month—as a Letter and an Editor’s Suggestion, I’m delighted to report.

Can you distinguish my coauthor Adam Bene Watts from John Stewart Bell?

For experts: The trick was to make the Bell correlation function nonlinear in the state. We assumed that the particles shared mostly pairwise correlations, though our Bell inequality can accommodate small aberrations. Alas, no one can guarantee that particles share only mostly pairwise correlations. Violating our Bell inequality therefore doesn’t rule out hidden-variables theories. Under reasonable assumptions, though, a not-completely-paranoid experimentalist can check for entanglement using our test. 

One can run our macroscopic Bell test on photons, using present-day technology. But we’re more eager to use the test to characterize lesser-known entities. For instance, we sketched an application to Posner molecules. Detecting entanglement in chemical systems will require more thought, as well as many headaches for experimentalists. But our paper broaches the cask—which I hope to see flow in the next Ant-Man film. Due to debut in 2022, the movie has the subtitle Quantumania. Sounds almost as crazy as studying the possibility that quantum phenomena affect cognition.

1Of those options, I’ve undertaken only the last.

2In case of any confusion: We don’t know that anyone’s brain contains Posner molecules. The movie features speculative fiction.

Random walks

Posted on by
4

A college professor of mine proposed a restaurant venture to our class. He taught statistical mechanics, the physics of many-particle systems. Examples range from airplane fuel to ice cubes to primordial soup. Such systems contain 1024 particles each—so many particles that we couldn’t track them all if we tried. We can gather only a little information about the particles, so their actions look random.

So does a drunkard’s walk. Imagine a college student who (outside of the pandemic) has stayed out an hour too late and accepted one too many red plastic cups. He’s arrived halfway down a sidewalk, where he’s clutching a lamppost, en route home. Each step has a 50% chance of carrying him leftward and a 50% chance of carrying him rightward. This scenario repeats itself every Friday. On average, five minutes after arriving at the lamppost, he’s back at the lamppost. But, if we wait for a time T, we have a decent chance of finding him a distance \sqrt{T} away. These characteristic typify a simple random walk.

Random walks crop up across statistical physics. For instance, consider a grain of pollen dropped onto a thin film of water. The water molecules buffet the grain, which random-walks across the film. Robert Brown observed this walk in 1827, so we call it Brownian motion. Or consider a magnet at room temperature. The magnet’s constituents don’t walk across the surface, but they orient themselves according random-walk mathematics. And, in quantum many-particle systems, information can spread via a random walk. 

So, my statistical-mechanics professor said, someone should open a restaurant near MIT. Serve lo mein and Peking duck, and call the restaurant the Random Wok.

This is the professor who, years later, confronted another alumna and me at a snack buffet.

“You know what this is?” he asked, waving a pastry in front of us. We stared for a moment, concluded that the obvious answer wouldn’t suffice, and shook our heads.

“A brownie in motion!”

Not only pollen grains undergo Brownian motion, and not only drunkards undergo random walks. Many people random-walk to their careers, trying out and discarding alternatives en route. We may think that we know our destination, but we collide with a water molecule and change course.

Such is the thrust of Random Walks, a podcast to which I contributed an interview last month. Abhigyan Ray, an undergraduate in Mumbai, created the podcast. Courses, he thought, acquaint us only with the successes in science. Stereotypes cast scientists as lone geniuses working in closed offices and silent labs. He resolved to spotlight the collaborations, the wrong turns, the lessons learned the hard way—the random walks—of science. Interviewees range from a Microsoft researcher to a Harvard computer scientist to a neurobiology professor to a genomicist.

You can find my episode on Instagram, Apple Podcasts, Google Podcasts, and Spotify. We discuss the bridging of disciplines; the usefulness of a liberal-arts education in physics; Quantum Frontiers; and the delights of poking fun at my PhD advisor, fellow blogger and Institute for Quantum Information and Matter director John Preskill. 

A quantum walk down memory lane

Posted on by
1

In elementary and middle school, I felt an affinity for the class three years above mine. Five of my peers had siblings in that year. I carpooled with a student in that class, which partnered with mine in holiday activities and Grandparents’ Day revues. Two students in that class stood out. They won academic-achievement awards, represented our school in science fairs and speech competitions, and enrolled in rigorous high-school programs.

Those students came to mind as I grew to know David Limmer. David is an assistant professor of chemistry at the University of California, Berkeley. He studies statistical mechanics far from equilibrium, using information theory. Though a theorist ardent about mathematics, he partners with experimentalists. He can pass as a physicist and keeps an eye on topics as far afield as black holes. According to his faculty page, I discovered while writing this article, he’s even three years older than I. 

I met David in the final year of my PhD. I was looking ahead to postdocking, as his postdoc fellowship was fading into memory. The more we talked, the more I thought, I’d like to be like him.

Playground

I had the good fortune to collaborate with David on a paper published by Physical Review A this spring (as an Editors’ Suggestion!). The project has featured in Quantum Frontiers as the inspiration for a rewriting of “I’m a little teapot.” 

We studied a molecule prevalent across nature and technologies. Such molecules feature in your eyes, solar-fuel-storage devices, and more. The molecule has two clumps of atoms. One clump may rotate relative to the other if the molecule absorbs light. The rotation switches the molecule from a “closed” configuration to an “open” configuration.

Molecular switch

These molecular switches are small, quantum, and far from equilibrium; so modeling them is difficult. Making assumptions offers traction, but many of the assumptions disagreed with David. He wanted general, thermodynamic-style bounds on the probability that one of these molecular switches would switch. Then, he ran into me.

I traffic in mathematical models, developed in quantum information theory, called resource theories. We use resource theories to calculate which states can transform into which in thermodynamics, as a dime can transform into ten pennies at a bank. David and I modeled his molecule in a resource theory, then bounded the molecule’s probability of switching from “closed” to “open.” I accidentally composed a theme song for the molecule; you can sing along with this post.

That post didn’t mention what David and I discovered about quantum clocks. But what better backdrop for a mental trip to elementary school or to three years into the future?

I’ve blogged about autonomous quantum clocks (and ancient Assyria) before. Autonomous quantum clocks differ from quantum clocks of another type—the most precise clocks in the world. Scientists operate the latter clocks with lasers; autonomous quantum clocks need no operators. Autonomy benefits you if you want for a machine, such as a computer or a drone, to operate independently. An autonomous clock in the machine ensures that, say, the computer applies the right logical gate at the right time.

What’s an autonomous quantum clock? First, what’s a clock? A clock has a degree of freedom (e.g., a pair of hands) that represents the time and that moves steadily. When the clock’s hands point to 12 PM, you’re preparing lunch; when the clock’s hands point to 6 PM, you’re reading Quantum Frontiers. An autonomous quantum clock has a degree of freedom that represents the time fairly accurately and moves fairly steadily. (The quantum uncertainty principle prevents a perfect quantum clock from existing.)

Suppose that the autonomous quantum clock constitutes one part of a machine, such as a quantum computer, that the clock guides. When the clock is in one quantum state, the rest of the machine undergoes one operation, such as one quantum logical gate. (Experts: The rest of the machine evolves under one Hamiltonian.) When the clock is in another state, the rest of the machine undergoes another operation (evolves under another Hamiltonian).

Clock 2

Physicists have been modeling quantum clocks using the resource theory with which David and I modeled our molecule. The math with which we represented our molecule, I realized, coincided with the math that represents an autonomous quantum clock.

Think of the molecular switch as a machine that operates (mostly) independently and that contains an autonomous quantum clock. The rotating clump of atoms constitutes the clock hand. As a hand rotates down a clock face, so do the nuclei rotate downward. The hand effectively points to 12 PM when the switch occupies its “closed” position. The hand effectively points to 6 PM when the switch occupies its “open” position.

The nuclei account for most of the molecule’s weight; electrons account for little. They flit about the landscape shaped by the atomic clumps’ positions. The landscape governs the electrons’ behavior. So the electrons form the rest of the quantum machine controlled by the nuclear clock.

Clock 1

Experimentalists can create and manipulate these molecular switches easily. For instance, experimentalists can set the atomic clump moving—can “wind up” the clock—with ultrafast lasers. In contrast, the only other autonomous quantum clocks that I’d read about live in theory land. Can these molecules bridge theory to experiment? Reach out if you have ideas!

And check out David’s theory lab on Berkeley’s website and on Twitter. We all need older siblings to look up to.

The shape of MIP* = RE

Posted on by
12

There’s a famous parable about a group of blind men encountering an elephant for the very first time. The first blind man, who had his hand on the elephant’s side, said that it was like an enormous wall. The second blind man, wrapping his arms around the elephant’s leg, exclaimed that surely it was a gigantic tree trunk. The third, feeling the elephant’s tail, declared that it must be a thick rope. Vehement disagreement ensues, but after a while the blind men eventually come to realize that, while each person was partially correct, there is much more to the elephant than initially thought.

6-blind-men-hans-1024x6541-1

Last month, Zhengfeng, Anand, Thomas, John and I posted MIP* = RE to arXiv. The paper feels very much like the elephant of the fable — and not just because of the number of pages! To a computer scientist, the paper is ostensibly about the complexity of interactive proofs. To a quantum physicist, it is talking about mathematical models of quantum entanglement. To the mathematician, there is a claimed resolution to a long-standing problem in operator algebras. Like the blind men of the parable, each are feeling a small part of a new phenomenon. How do the wall, the tree trunk, and the rope all fit together?

I’ll try to trace the outline of the elephant: it starts with a mystery in quantum complexity theory, curves through the mathematical foundations of quantum mechanics, and arrives at a deep question about operator algebras.

The rope: The complexity of nonlocal games

In 2004, computer scientists Cleve, Hoyer, Toner, and Watrous were thinking about a funny thing called nonlocal games. A nonlocal game G involves three parties: two cooperating players named Alice and Bob, and someone called the verifier. The verifier samples a pair of random questions (x,y) and sends x to Alice (who responds with answer a), and y to Bob (who responds with answer b). The verifier then uses some function D(x,y,a,b) that tells her whether the players win, based on their questions and answers.

All three parties know the rules of the game before it starts, and Alice and Bob’s goal is to maximize their probability of winning the game. The players aren’t allowed to communicate with each other during the game, so it’s a nontrivial task for them to coordinate an optimal strategy (i.e., how they should individually respond to the verifier’s questions) before the game starts.

The most famous example of a nonlocal game is the CHSH game (which has made several appearances on this blog already): in this game, the verifier sends a uniformly random bit x to Alice (who responds with a bit a) and a uniformly random bit y to Bob (who responds with a bit b). The players win if a \oplus b = x \wedge y (in other words, the sum of their answer bits is equal to the product of the input bits modulo 2).

What is Alice’s and Bob’s maximum winning probability? Well, it depends on what type of strategy they use. If they use a strategy that can be modeled by classical physics, then their winning probability cannot exceed 75\% (we call this the classical value of CHSH). On the other hand, if they use a strategy based on quantum physics, Alice and Bob can do better by sharing two quantum bits (qubits) that are entangled. During the game each player measures their own qubit (where the measurement depends on their received question) to obtain answers that win the CHSH game with probability \cos^2(\pi/8) \approx .854\ldots (we call this the quantum value of CHSH). So even though the entangled qubits don’t allow Alice and Bob to communicate with each other, entanglement gives them a way to win with higher probability! In technical terms, their responses are more correlated than what is possible classically.

The CHSH game comes from physics, and was originally formulated not as a game involving Alice and Bob, but rather as an experiment involving two spatially separated devices to test whether stronger-than-classical correlations exist in nature. These experiments are known as Bell tests, named after John Bell. In 1964, he proved that correlations from quantum entanglement cannot be explained by any “local hidden variable theory” — in other words, a classical theory of physics.1 He then showed that a Bell test, like the CHSH game, gives a simple statistical test for the presence of nonlocal correlations between separated systems. Since the 1960s, numerous Bell tests have been conducted experimentally, and the verdict is clear: nature does not behave classically.

Cleve, Hoyer, Toner and Watrous noticed that nonlocal games/Bell tests can be viewed as a kind of multiprover interactive proof. In complexity theory, interactive proofs are protocols where some provers are trying to convince a verifier of a solution to a long, difficult computation, and the verifier is trying to efficiently determine if the solution is correct. In a Bell test, one can think of the provers as instead trying to convince the verifier of a physical statement: that they possess quantum entanglement.

With the computational lens trained firmly on nonlocal games, it then becomes natural to ask about their complexity. Specifically, what is the complexity of approximating the optimal winning probability in a given nonlocal game G? In complexity-speak, this is phrased as a question about characterizing the class MIP* (pronounced “M-I-P star”). This is also a well-motivated question for an experimentalist conducting Bell tests: at the very least, they’d want to determine if (a) quantum players can do better than classical players, and (b) what can the best possible quantum strategy achieve?

Studying this question in the case of classical players led to some of the most important results in complexity theory, such as MIP = NEXP and the PCP Theorem. Indeed, the PCP Theorem says that it is NP-hard to approximate the classical value of a nonlocal game (i.e. the maximum winning probability of classical players) to within constant additive accuracy (say \pm \frac{1}{10}). Thus, assuming that P is not equal to NP, we shouldn’t expect a polynomial-time algorithm for this. However it is easy to see that there is a “brute force” algorithm for this problem: by taking exponential time to enumerate over all possible deterministic player strategies, one can exactly compute the classical value of nonlocal games.

When considering games with entangled players, however, it’s not even clear if there’s a similar “brute force” algorithm that solves this in any amount of time — forget polynomial time; even if we allow ourselves exponential, doubly-exponential, Ackermann function amount of time, we still don’t know how to solve this quantum value approximation problem. The problem is that there is no known upper bound on the amount of entanglement that is needed for players to play a nonlocal game. For example, for a given game G, does an optimal quantum strategy require one qubit, ten qubits, or 10^{10^{10}} qubits of entanglement? Without any upper bound, a “brute force” algorithm wouldn’t know how big of a quantum strategy to search for — it would keep enumerating over bigger and bigger strategies in hopes of finding a better one.

Thus approximating the quantum value may not even be solvable in principle! But could it really be uncomputable? Perhaps we just haven’t found the right mathematical tool to give an upper bound on the dimension — maybe we just need to come up with some clever variant of, say, Johnson-Lindenstrauss or some other dimension reduction technique.2

In 2008, there was promising progress towards an algorithmic solution for this problem. Two papers [DLTW, NPA] (appearing on arXiv on the same day!) showed that an algorithm based on semidefinite programming can produce a sequence of numbers that converge to something called the commuting operator value of a nonlocal game.3 If one could show that the commuting operator value and the quantum value of a nonlocal game coincide, then this would yield an algorithm for solving this approximation problem!

Asking whether this commuting operator and quantum values are the same, however, immediately brings us to the precipice of some deep mysteries in mathematical physics and operator algebras, far removed from computer science and complexity theory. This takes us to the next part of the elephant.

The tree: mathematical foundations of locality

The mystery about the quantum value versus the commuting operator value of nonlocal games has to do with two different ways of modeling Alice and Bob in quantum mechanics. As I mentioned earlier, quantum physics predicts that the maximum winning probability in, say, the CHSH game when Alice and Bob share entanglement is approximately 85%. As with any physical theory, these predictions are made using some mathematical framework — formal rules for modeling physical experiments like the CHSH game.

In a typical quantum information theory textbook, players in the CHSH game are usually modelled in the following way: Alice’s device is described a state space \mathcal{H}_A (all the possible states the device could be in), a particular state |\psi_A\rangle from \mathcal{H}_A, and a set of measurement operators \mathcal{M}_A (operations that can be performed by the device). It’s not necessary to know what these things are formally; the important feature is that these three things are enough to make any prediction about Alice’s device — when treated in isolation, at least. Similarly, Bob’s device can be described using its own state space \mathcal{H}_B, state |\psi_B\rangle, and measurement operators \mathcal{M}_B.

In the CHSH game though, one wants to make predictions about Alice’s and Bob’s devices together. Here the textbooks say that Alice and Bob are jointly described by the tensor product formalism, which is a natural mathematical way of “putting separate spaces together”. Their state space is denoted by \mathcal{H}_A \otimes \mathcal{H}_B. The joint state |\psi_{AB}\rangle describing the devices comes from this tensor product space. When Alice and Bob independently make their local measurements, this is described by a measurement operator from the tensor product of operators from \mathcal{M}_A and \mathcal{M}_B. The strange correlations of quantum mechanics arise when their joint state |\psi_{AB}\rangle is entangled, i.e. it cannot be written as a well-defined state on Alice’s side combined with a well-defined state on Bob’s side (even though the state space itself is two independent spaces combined together!)

The tensor product model works well; it satisfies natural properties you’d want from the CHSH experiment, such as the constraint that Alice and Bob can’t instantaneously signal to each other. Furthermore, predictions made in this model match up very accurately with experimental results!

This is the not the whole story, though. The tensor product formalism works very well in non-relativistic quantum mechanics, where things move slowly and energies are low. To describe more extreme physical scenarios — like when particles are being smashed together at near-light speeds in the Large Hadron Collider — physicists turn to the more powerful quantum field theory. However, the notion of spatiotemporal separation in relativistic settings gets especially tricky. In particular, when trying to describe quantum mechanical systems, it is no longer evident how to assign Alice and Bob their own independent state spaces, and thus it’s not clear how to put relativistic Alice and Bob in the tensor product framework!

In quantum field theory, locality is instead described using the commuting operator model. Instead of assigning Alice and Bob their own individual state spaces and then tensoring them together to get a combined space, the commuting operator model stipulates that there is just a single monolithic space \mathcal{H} for both Alice and Bob. Their joint state is described using a vector |\psi\rangle from \mathcal{H}, and Alice and Bob’s measurement operators both act on \mathcal{H}. The constraint that they can’t communicate is captured by the fact that Alice’s measurement operators commute with Bob’s operators. In other words, the order in which the players perform their measurements on the system does not matter: Alice measuring before Bob, or Bob measuring before Alice, both yield the same statistical outcomes. Locality is enforced through commutativity.

The commuting operator framework contains the tensor product framework as a special case4, so it’s more general. Could the commuting operator model allow for correlations that can’t be captured by the tensor product model, even approximately56? This question is known as Tsirelson’s problem, named after the late mathematician Boris Tsirelson.

There is a simple but useful way to phrase this question using nonlocal games. What we call the “quantum value” of a nonlocal game G (denoted by \omega^* (G)) really refers to the supremum of success probabilities over tensor product strategies for Alice and Bob. If they use strategies from the more general commuting operator model, then we call their maximum success probability the commuting operator value of G (denoted by \omega^{co}(G)). Since tensor product strategies are a special case of commuting operator strategies, we have the relation \omega^* (G) \leq \omega^{co}(G) for all nonlocal games G.

Could there be a nonlocal game G whose tensor product value is different from its commuting operator value? With tongue-in-cheek: is there a game G that Alice and Bob could succeed at better if they were using quantum entanglement at near-light speeds? It is difficult to find even a plausible candidate game for which the quantum and commuting operator values may differ. The CHSH game, for example, has the same quantum and commuting operator value; this was proved by Tsirelson.

If the tensor product and the commuting operator models are the same (i.e., the “positive” resolution of Tsirelson’s problem), then as I mentioned earlier, this has unexpected ramifications: there would be an algorithm for approximating the quantum value of nonlocal games.

How does this algorithm work? It comes in two parts: a procedure to search from below, and one to search from above. The “search from below” algorithm computes a sequence of numbers \alpha_1,\alpha_2,\alpha_3,\ldots where \alpha_d is (approximately) the best winning probability when Alice and Bob use a d-qubit tensor product strategy. For fixed d, the number \alpha_d can be computed by enumerating over (a discretization of) the space of all possible d-qubit strategies. This takes a doubly-exponential amount of time in d — but at least this is still a finite time! This naive “brute force” algorithm will slowly plod along, computing a sequence of better and better winning probabilities. We’re guaranteed that in the limit as d goes to infinity, the sequence \{ \alpha_d\} converges to the quantum value \omega^* (G). Of course the issue is that the “search from below” procedure never knows how close it is to the true quantum value.

This is where the “search from above” comes in. This is an algorithm that computes a different sequence of numbers \beta_1,\beta_2,\beta_3,\ldots where each \beta_d is an upper bound on the commuting operator value \omega^{co}(G), and furthermore as d goes to infinity, \beta_d eventually converges to \omega^{co}(G). Furthermore, each \beta_d can be computed by a technique known as semidefinite optimization; this was shown by the two papers I mentioned.

Let’s put the pieces together. If the quantum and commuting operator values of a game G coincide (i.e. \omega^* (G) = \omega^{co}(G)), then we can run the “search from below” and “search from above” procedures in parallel, interleaving the computation of the \{\alpha_d\} and \{ \beta_d\}. Since both are guaranteed to converge to the quantum value, at some point the upper bound \beta_d will come within some \epsilon to the lower bound \alpha_d, and thus we would have homed in on (an approximation of) \omega^* (G). There we have it: an algorithm to approximate the quantum value of games.

All that remains to do, surely, is to solve Tsirelson’s problem in the affirmative (that commuting operator correlations can be approximated by tensor product correlations), and then we could put this pesky question about the quantum value to rest. Right?

The wall: Connes’ embedding problem

At the end of the 1920s, polymath extraordinaire John von Neumann formulated the first rigorous mathematical framework for the recently developed quantum mechanics. This framework, now familiar to physicists and quantum information theorists everywhere, posits that quantum states are vectors in a Hilbert space, and measurements are linear operators acting on those spaces. It didn’t take long for von Neumann to realize that there was a much deeper theory of operators on Hilbert spaces waiting to be discovered. With Francis Murray, in the 1930s he started to develop a theory of “rings of operators” — today these are called von Neumann algebras.

The theory of operator algebras has since flourished into a rich and beautiful area of mathematics. It remains inseparable from mathematical physics, but has established deep connections with subjects such as knot theory and group theory. One of the most important goals in operator algebras has been to provide a classification of von Neumann algebras. In their series of papers on the subject, Murray and von Neumann first showed that classifying von Neumann algebras reduces to understanding their factors, the atoms out of which all von Neumann algebras are built. Then, they showed that factors of von Neumann algebras come in one of three species: type I, type II, and type III. Type I factors were completely classified by Murray and von Neumann, and they made much progress on characterizing certain type II factors. However progress stalled until the 1970s, when Alain Connes provided a classification of type III factors (work for which he would later receive the Fields Medal). In the same 1976 classification paper, Connes makes a casual remark about something called type II_1 factors7:

We now construct an embedding of N into \mathcal{R}. Apparently such an embedding ought to exist for all II_1 factors.

This line, written in almost a throwaway manner, eventually came to be called “Connes’ embedding problem”: does every separable II_1 factor embed into an ultrapower of the hyperfinite II_1 factor? It seems that Connes surmises that it does (and thus this is also called “Connes’ embedding conjecture“). Since 1976, this problem has grown into a central question of operator algebras, with numerous equivalent formulations and consequences across mathematics.

In 2010, two papers (again appearing on the arXiv on the same day!) showed that the reach of Connes’ embedding conjecture extends back to the foundations of quantum mechanics. If Connes’ embedding problem has a positive answer (i.e. an embedding exists), then Tsirelson’s problem (i.e. whether commuting operator can be approximated by tensor product correlations) also has a positive answer! Later it was shown by Ozawa that Connes’ embedding problem is in fact equivalent to Tsirelson’s problem.

Remember that our approach to compute the value of nonlocal games hinged on obtaining a positive answer to Tsirelson’s problem. The sequence of papers [NPA, DLTW, Fritz, JNPPSW] together show that resolving — one way or another — whether this search-from-below, search-from-above algorithm works would essentially settle Connes’ embedding conjecture. What started as a funny question at the periphery of computer science and quantum information theory has morphed into an attack on one of the central problems in operator algebras.

MIP* = RE

We’ve now ended back where we started: the complexity of nonlocal games. Let’s take a step back and try to make sense of the elephant.

Even to a complexity theorist, “MIP* = RE” may appear esoteric. The complexity classes MIP* and RE refer to a bewildering grabbag of concepts: there’s Alice, Bob, Turing machines, verifiers, interactive proofs, quantum entanglement. What is the meaning of the equality of these two classes?

First, it says that the Halting problem has an interactive proof involving quantum entangled provers. In the Halting problem, you want to decide whether a Turing machine M, if you started running it, would eventually terminate with a well-defined answer, or if it would get stuck in an infinite loop. Alan Turing showed that this problem is undecidable: there is no algorithm that can solve this problem in general. Loosely speaking, the best thing you can do is to just flick on the power switch to M, and wait to see if it eventually stops. If M gets stuck in an infinite loop — well, you’re going to be waiting forever.

MIP* = RE shows with the help of all-powerful Alice and Bob, a time-limited verifier can run an interactive proof to “shortcut” the waiting. Given the Turing machine M‘s description (its “source code”), the verifier can efficiently compute a description of a nonlocal game G_M whose behavior reflects that of M. If M does eventually halt (which could happen after a million years), then there is a strategy for Alice and Bob that causes the verifier to accept with probability 1. In other words, \omega^* (G_M) = 1. If M gets stuck in an infinite loop, then no matter what strategy Alice and Bob use, the verifier always rejects with high probability, so \omega^* (G_M) is close to 0.

By playing this nonlocal game, the verifier can obtain statistical evidence that M is a Turing machine that eventually terminates. If the verifier plays G_M and the provers win, then the verifier should believe that it is likely that M halts. If they lose, then the verifier concludes there isn’t enough evidence that M halts8. The verifier never actually runs M in this game; she has offloaded the task to Alice and Bob, who we can assume are computational gods capable of performing million-year-long computations instantly. For them, the challenge is instead to convince the verifier that if she were to wait millions of years, she would witness the termination of M. Incredibly, the amount of work put in by the verifier in the interactive proof is independent of the time it takes for M to halt!

The fact that the Halting problem has an interactive proof seems borderline absurd: if the Halting problem is unsolvable, why should we expect it to be verifiable? Although complexity theory has taught us that there can be a large gap between the complexity of verification versus search, it has always been a difference of efficiency: if solutions to a problem can be efficiently verified, then solutions can also be found (albeit at drastically higher computational cost). MIP* = RE shows that, with quantum entanglement, there can be a chasm of computability between verifying solutions and finding them.

Now let’s turn to the non-complexity consequences of MIP* = RE. The fact that we can encode the Halting problem into nonlocal games also immediately tells us that there is no algorithm whatsoever to approximate the quantum value. Suppose there was an algorithm that could approximate \omega^* (G). Then, using the transformation from Turing machines to nonlocal games mentioned above, we could use this algorithm to solve the Halting problem, which is impossible.

Now the dominoes start to fall. This means that, in particular, the proposed “search-from-below”/”search-from-above” algorithm cannot succeed in approximating \omega^* (G). There must be a game G, then, for which the quantum value is different from the commuting operator value. But this implies Tsirelson’s problem has a negative answer, and therefore Connes’ embedding conjecture is false.

We’ve only sketched the barest of outlines of this elephant, and yet it is quite challenging to hold it in the mind’s eye all at once9. This story is intertwined with some of the most fundamental developments in the past century: modern quantum mechanics, operator algebras, and computability theory were birthed in the 1930s. Einstein, Podolsky and Rosen wrote their landmark paper questioning the nature of quantum entanglement in 1935, and John Bell discovered his famous test and inequality in 1964. Connes’ formulated his conjecture in the ’70s, Tsirelson made his contributions to the foundations of quantum mechanics in the ’80s, and about the same time computer scientists were inventing the theory of interactive proofs and probabilistically checkable proofs (PCPs).

We haven’t said anything about the proof of MIP* = RE yet (this may be the subject of future blog posts), but it is undeniably a product of complexity theory. The language of interactive proofs and Turing machines is not just convenient but necessary: at its heart MIP* = RE is the classical PCP Theorem, with the help of quantum entanglement, recursed to infinity.

What is going on in this proof? What parts of it are fundamental, and which parts are unnecessary? What is the core of it that relates to Connes’ embedding conjecture? Are there other consequences of this uncomputability result? These are questions to be explored in the coming days and months, and the answers we find will be fascinating.

Acknowledgments. Thanks to William Slofstra and Thomas Vidick for helpful feedback on this post.

  1. This is why quantum correlations are called “nonlocal”, and why we call the CHSH game a “nonlocal game”: it is a test for nonlocal behavior. ↩
  2. A reasonable hope would be that, for every nonlocal game G, there is a generic upper bound on the number of qubits needed to approximate the optimal quantum strategy (e.g., a game G with Q possible questions and A possible answers would require at most, say, 2^{O(Q \cdot A)} qubits to play optimally). ↩
  3. In those papers, they called it the field theoretic value. ↩
  4. The space \mathcal{H} can be broken down into the tensor product \mathcal{H}_A \otimes \mathcal{H}_B, and Alice’s measurements only act on the \mathcal{H}_A space and Bob’s measurements only act on the \mathcal{H}_B space. In this case, Alice’s measurements clearly commute with Bob’s. ↩
  5. In a breakthrough work in 2017, Slofstra showed that the tensor product framework is not exactly the same as the commuting operator framework; he shows that there is a nonlocal game G where players using commuting operator strategies can win with probability 1, but when they use a tensor-product strategy they can only win with probability strictly less than 1. However the perfect commuting operator strategy can be approximated by tensor-product strategies arbitrarily well, so the quantum values and the commuting operator values of G are the same. ↩
  6. The commuting operator model is motivated by attempts to develop a rigorous mathematical framework for quantum field theory from first principles (see, for example algebraic quantum field theory (AQFT)). In the “vanilla” version of AQFT, tensor product decompositions between casually independent systems do not exist a priori, but mathematical physicists often consider AQFTs augmented with an additional “split property”, which does imply tensor product decompositions. Thus in such AQFTs, Tsirelson’s problem has an affirmative answer. ↩
  7. Type II_1 is pronounced “type two one”. ↩
  8. This is not the same as evidence that M loops forever! ↩
  9. At least, speaking for myself. ↩