by Chinmay Nirkhe (IBM Research and UC Berkeley)
In the parable of the blind men and the elephant, a group of blind men encounters a very large object, unbeknownst to them that it is indeed an elephant. They start exploring the object by touch, with each blind man trying to understand the small fraction of the object in front of him. But each blind man feels a different part of the elephant, such as its trunk, its tusks, its feet, etc. For instance, one feels the elephant’s trunk and remarks, “This feels like a thick snake.” Each develops a different view as to what the object he encounters must be, as each of the blind men is offered only a small perspective on the global object.
Only once the blind men bicker and argue over their different views do they finally agree that they are observing something greater and finally recognize that the object they are observing is an elephant. In other words, only from the union of the small local views — each local view being indistinguishable from other objects (such as the elephant’s trunk and a snake) — are the blind men able to surmise that the global object in front of them is an elephant.
Today, we consider a variation on the parable more suited for our modern understanding of physics. In this parable, instead of one object that the blind men observe, there are two. The blind men approach the first object, and each man goes to his location around the object. The first man feels the front of the object and again remarks, “This feels like a thick snake,” while the other men then proceed to feel the object in front of them and make observations as to what they feel. The men then proceed to the second object and again proceed to make observations as to what they feel. The first man again remarks, “This feels like a thick snake,” and, curiously, each blind man makes the exact same observation for the second object as he did for the first. The blind men confer and note that since each man’s observations were the same for both objects and together they had observed the entirety of both objects, then the two objects must be the same and therefore the same elephant. They must have been presented with the same elephant twice.
But what if the blind men were wrong and they were truly observing two very different objects? Is it possible that the two objects were very different but were the same under every local observation? Well, it is possible if they were quantum elephants! An amazing property of two pure quantum objects is that their local views can be exactly the same and yet globally the states are very different (even orthogonal). We call such quantum objects locally indistinguishable, and they are fundamentally interesting objects in quantum information theory. For one, due to being locally indistinguishable, these quantum states (objects) have the property that their entanglement is nontrivial — in this case, this means that for the state to be expressed as the output of a quantum circuit, the depth of the circuit required is large. If a high-depth quantum circuit is required, then this means that the state is far from all classical states and is fundamentally quantum.
Locally indistinguishable quantum states are easy to concoct, but it is far more interesting when locally indistinguishable quantum states are “naturally” occurring. A physicist might phrase this as a local Hamiltonian system (i.e., a quantum energy landscape) with the property that after cooling the system to its minimum energy (temperature), the state of the system is a locally indistinguishable quantum state — i.e., is there any hope that a group of blind physicists go on a trek through the quantum jungle and stumble upon a pair of quantum elephants?
The study of quantum error correction has been a fruitful source of examples of locally indistinguishable states that are the exact solutions (zero-energy solutions) to local Hamiltonian systems. A fundamental consequence of being able to correct all errors on a small region of the state along with the no-cloning theorem is that the codewords of quantum error-correcting codes are locally indistinguishable. This also means that the codewords are nontrivial. And so, we’ve known for a while that locally indistinguishable states are solutions to local Hamiltonians but at zero energy!
But the reality of the quantum jungle is that just being locally indistinguishable at zero energy is not good enough because physicists will never experience the quantum jungle at zero temperature. At best, we will bring the system to a constant temperature above zero. Can quantum elephants survive in such harsh climates, or are they forced to decohere into classical ones?
In a recent result with co-authors Anurag Anshu (Harvard University) and Nikolas Breuckmann (University College London), we were able to prove that there exists a local Hamiltonian for which every low-energy state is a nontrivial state. Putting it another way, we were able to show that every low-energy state of the Hamiltonian was approximately locally indistinguishable from some other state — i.e., there were small variations in the quantum elephants but not enough that we could distinguish every elephant in the entire herd.
Our result suggests that there could exist physical systems that demonstrate complex robust entanglement in the low-energy subspace. We give a particular example of a physical system that lives in a hyperbolic 4D space that satisfies this property. The physical system we analyze is an optimal-parameter quantum error-correcting code, which was recently shown to exist by multiple recent results; the one we analyze in particular is the construction by Leverrier and Zémor.
In terms of metaphors, Anshu, Breuckmann, and I were able to finally certify that — in the comfortable confines of the quantum error-correction zoo, specifically designed for the care of quantum fauna — the new exhibit constructed by Leverrier and Zémor is a safe habitat for quantum elephants to frolic in (even at warmer temperatures). And since we can raise quantum elephants in the zoo, perhaps we will find some frolicking out and about in the quantum corners of the universe, perhaps grazing on the bulk of a black hole.
As you might expect, our result was not motivated by the burgeoning field of quantum ecology (just wait six months and you will find such a paper on arXiv), but by a deeper connection to computational complexity theory. Our proof of robustness resolves, in the affirmative, the “no low-energy trivial states” (NLTS) conjecture by Freedman and Hastings, which asked if there exists a construction of local Hamiltonians so that every low-energy state is nontrivial. The NLTS statement is a necessary consequence of a long-standing open conjecture in quantum complexity theory called the quantum PCP conjecture. The quantum PCP conjecture is about the computational complexity of a central problem from the field of condensed matter physics: calculating the ground energy of a local Hamiltonian system. Hamiltonian systems describe the dynamics of objects governed by the laws of quantum mechanics and are the quantum analogs of constraint satisfaction problems. The conjecture derives its name from the classical probabilistically checkable proofs (PCP) theorem, which is widely considered the crown jewel of complexity theory. The quantum PCP conjecture, due to its connections to the hardness of approximation and efficient verification, is fundamental to improving our understanding of Hamiltonian complexity.
So the next challenge for any intrepid quantum ecologist is to study how to embed computation into the low-energy subspace of the local Hamiltonian. We know that the ground space of a local Hamiltonian problem is capable of describing computation, but we are unsure of whether that extends any further. We suspect that the objects required for the quantum PCP conjecture will be inspired by quantum error correction but will look necessarily different. So the search is on, for the quantum megafauna that both captures the complexity of nondeterministic quantum computation and can frolic happily in the zoo at warm temperatures.
PS: Much of the work and its prior results were solved at the Simons Institute’s various programs on quantum computation over the past five years. We thank the Simons Institute for its support.
PPS: Only after finishing writing this blog post did I learn that my collaborator on an earlier work leading up to the NLTS theorem, Henry Yuen, wrote a blog post for Quantum Frontiers also about quantum interactive proofs through the parable of the blind men and the elephant. And there is the paper on quantum platypuses. Maybe quantum computing has more to do with ecology than I initially thought!