# The sign problem(s)

The thirteen-month-old had mastered the word “dada” by the time I met her. Her parents were teaching her to communicate other concepts through sign language. Picture her, dark-haired and bibbed, in a high chair. Banana and mango slices litter the tray in front of her. More fruit litters the floor in front of the tray. The baby lifts her arms and flaps her hands.

Dada looks up from scrubbing the floor.

“Look,” he calls to Mummy, “she’s using sign language! All done.” He performs the gesture that his daughter seems to have aped: He raises his hands and rotates his forearms about his ulnas, axes perpendicular to the floor. “All done!”

The baby looks down, seizes another morsel, and stuffs it into her mouth.

“Never mind,” Dada amends. “You’re not done, are you?”

His daughter had a sign(-language) problem.

So does Dada, MIT professor Aram Harrow. Aram studies quantum information theory. His interests range from complexity to matrices, from resource theories to entropies. He’s blogged for The Quantum Pontiff, and he studies—including with IQIM postdoc Elizabeth Crossonthe quantum sign problem.

Imagine calculating properties of a chunk of fermionic quantum matter. The chunk consists of sites, each inhabited by one particle or by none. Translate as “no site can house more than one particle” the jargon “the particles are fermions.”

The chunk can have certain amounts of energy. Each amount $E_j$ corresponds to some particle configuration indexed by $j$: If the system has some amount $E_1$ of energy, particles occupy certain sites and might not occupy others. If the system has a different amount $E_2 \neq E_1$ of energy, particles occupy different sites. A Hamiltonian, a mathematical object denoted by $H,$ encodes the energies $E_j$ and the configurations. We represent $H$ with a matrix, a square grid of numbers.

Suppose that the chunk has a temperature $T = \frac{ 1 }{ k_{\rm B} \beta }$. We could calculate the system’s heat capacity, the energy required to raise the chunk’s temperature by one Kelvin. We could calculate the free energy, how much work the chunk could perform in powering a motor or lifting a weight. To calculate those properties, we calculate the system’s partition function, $Z$.

How? We would list the configurations $j$. With each configuration, we would associate the weight $e^{ - \beta E_j }$. We would sum the weights: $Z = e^{ - \beta E_1 } + e^{ - \beta E_2} + \ldots = \sum_j e^{ - \beta E_j}$.

Easier—like feeding a 13-month-old—said than done. Let $N$ denote the number of qubits in the chunk. If $N$ is large, the number of configurations is gigantic. Our computers can’t process so many configurations. This inability underlies quantum computing’s promise of speeding up certain calculations.

We don’t have quantum computers, and we can’t calculate $Z$. Can we  approximate $Z$?

Yes, if $H$ “lacks the sign problem.” The math that models our system models also a classical system. If our system has $D$ dimensions, the classical system has $D+1$ dimensions. Suppose, for example, that our sites form a line. The classical system forms a square.

We replace the weights $e^{ - \beta E_j }$ with different weights—numbers formed from a matrix that represents $H$. If $H$ lacks the sign problem, the new weights are nonnegative and behave like probabilities. Many mathematical tools suit probabilities. Aram and Elizabeth apply such tools to $Z$, here and here, as do many other researchers.

We call Hamiltonians that lack the sign problem “stoquastic,” which I think fanquastic.Stay tuned for a blog post about stoquasticity by Elizabeth.

What if $H$ has the sign problem? The new weights can assume negative and nonreal values. The weights behave unlike probabilities; we can’t apply those tools. We find ourselves knee-deep in banana and mango chunks.

Solutions to the sign problem remain elusive. Theorists keep trying to mitigate the problem, though. Aram, Elizabeth, and others are improving calculations of properties of sign-problem-free systems. One scientist-in-the-making has achieved a breakthrough: Aram’s daughter now rotates her hands upon finishing meals and when she wants to leave her car seat or stroller.

One sign problem down; one to go.

With gratitude to Aram’s family for its hospitality and to Elizabeth Crosson for sharing her expertise.

1For experts: A local Hamiltonian is stoquastic relative to the computational basis if each local term is represented, relative to the computational basis, by a matrix whose off-diagonal entries are real and nonpositive.

This entry was posted in Real science, Reflections, Theoretical highlights by Nicole Yunger Halpern. Bookmark the permalink.