Domain-wall encoding: how physics can help us compute better

QCi recently showed how domain-wall encoding can get better performance out of quantum hardware for practical optimization, as well as investigating opportunities to even do more. We’re summarizing our work for physics and computing non-experts on what this means, why these results are important, and the lessons to be learned about looking for advantages in unexpected places.

First, let’s discuss encoding.. Then we will get into specifics.

Encoding

The best way to think of encoding is how information is stored and processed in a computer, either classical or quantum. A crucial concept here is that the same information can be represented in multiple different ways. As a non-computer example, if I want to represent the concept of five objects, I can write the Arabic numeral 5, or use tally marks ||||. Both encodings are equally valid and represent the same thing, but they are useful for different purposes. For example, if I am doing accounting, and need to represent and add numbers in the thousands, tally marks will quickly become unwieldy. On the other hand, if I am trapped on an island and want to count the days, I have been stranded by scratching marks into a cliff, then tally marks are the more convenient option, going from day five to day six is simply adding another scratch (|||| goes to |||| |), nothing needs to be erased. Since erasing (and writing) is hard in this case, I choose an easier encoding. Classical computers also use encodings of information, they use something called binary encoding, strings of ones and zeros to represent commands and information. It is not obvious that this is the right choice for all quantum computing applications, and we discuss an example later where this definitely isn’t the best option.

Encoding is different from how information is physically stored. It is a more abstract level, for example an Arabic numeral 5 is the same encoding whether it is written in a book or painted on a sign. Similarly, a one or zero represented in a computer is the same encoding whether it is represented by the magnetization of part of a hard drive or the position of some electrons within RAM. As we show later, encodings can still be inspired by how physical systems work even if they are independent of how they are stored. Making encodings which can survive noise, where the storage is imperfect, is very important in quantum computing, and is also important in some classical applications, for example in communications.

Topological Defects

Now we can discuss the idea behind how the domain-wall encoding we have studied works. The simplest way to do this is to think of a classical analogy. Imagine you take a belt, (the kind used to hold up trousers,) twist and then buckle it so what was the inside becomes the outside when it meets the buckle. Without undoing the buckle, (or cutting the belt) there is no way to get rid of the half-twist which we have added. You can push it around and move it to different places in the belt, but it cannot be removed. This is the concept of a topological defect, the belt needs to twist somewhere because of the way it is buckled. This twist can be thought of as storing a small amount of information. The twist can be on the left side or the right side or the back. An untwisted belt does not store information in this way, there is no twist anywhere.

This notion of a feature which has to be somewhere to match what is going on at the boundaries (the belt buckle in our classical example), is what is called a topological defect. The key feature of topological defects is that they can be moved around locally, but cannot be destroyed without doing something drastic. Domain-wall encoding works exactly the way our twisted belt example works. It is based on creating a physical system called an Ising spin chain but with a twist. The variables want to take one value on one end and the opposite value on the other. Information is stored as where this twist or jump happens. In this way, a variable as big as we want (let’s call it a “discrete” variable) can be represented by binary (can only take two values) variables.

Mobius Strip

A Mobius strip is another interesting object for other, more mathematical reasons. This object is famous for being non-orientable, in other words there is no “inside” or “outside”. The simplest way to see this is to imagine taking a strip of paper and gluing it the same way we inserted the belt buckle, so that there is a twist where what would normally be the “inside” becomes the “outside”. If we trace along the strip of paper, we find that the line goes around twice before meeting itself, and we have traced along the entire strip.

Let’s try another experiment without a Mobius strip. Imagine it is made of clear material (so we don’t have to worry about which “side” something is on) and we want to glue arrows to it that point perpendicular to the direction of the strip, where adjacent arrows to always point the same direction. This is easily done if we glue the strip in a way which clearly has an inside and an outside, if we start gluing the arrows pointing up and each neighboring arrow points the same direction, then we end up meeting our initial “up” arrow with an arrow which is also facing up.

Let’s try the same thing with the Mobius strip. If we start with an arrow facing “up” the twist means that the arrow which comes to meet it will be facing “down”, as depicted in the image.

Even if we are allowed to flip the arrows we can’t “fix” this mismatch, there will always have to be a pair of neighboring arrows which point opposite directions somewhere, flipping the direction of an arrow just moves where this happens.

These arrows, which can face one of two directions, behave exactly like the Ising variables mentioned before. They can take two values. Since the location where the arrows don’t match is movable, this can store information and is exactly the idea behind the domain-wall encoding. The domain-wall is the point where the arrows point in the opposite direction, a wall between all pointing up and all pointing down.

There is one more small trick behind the encoding. Instead of using a joined strip, it is more efficient to use a system which is like a segment of the twisted strip, where one end acts like the “next” arrow points up and the other end acts like the “next” arrow points down. This detail isn’t important for understanding the principle of how this method works but is important for making the encoding efficient in practice.

Discrete Variables

Discrete variables appear often in optimization problems. For example, consider a routing problem where a truck can take any of three roads, a microchip design problem where a component can be placed any of four places, a scheduling problem where an event can happen at any of seven times, or a planning problem where facility which can be built in one of ten locations. In the real-world, choices are often not binary, but computers, even quantum computers, usually are. Therefore discrete-to-binary encodings, like the domain-wall encoding,g are highly useful for using quantum computers to solve real problems.

There are other discrete-to-binary encodings, a popular choice being one-hot encoding, where a constraint can be applied so that only one variable is “hot.” In other words takes a “one” as opposed to “zero” value. Working out the math a one-hot encoding requires one more binary variable per discrete variable. This is where the detail mentioned at the end of the last section is important. Experimentally, yiou can see that one-hot encoding performs worse on a quantum annealer .

Quadratic Interactions

Another type of encoding is to use the same binary encoding a classical computer uses. This has the advantage that for every binary variable you add, the number of possibilities which can be represented doubles (two for a single binary variable, four for two binary variables, eight for three, etc…). This type of encoding comes at a cost however. The problem itself becomes much harder to represent.

An important feature about both the domain-wall and one-hot encoding is that interactions between pairs of discrete variables can be represented as interactions between only pairs of binary variables. This type of pairwise interaction is known as a quadratic interaction. These are the type of interactions available on current quantum annealers. It is likely that higher-than-quadratic interactions will be harder to implement (require deeper circuits) on gate-model quantum computers.

There are ways to build higher order interactions using quadratic interactions and adding extra variables. However, a key result of our work https://arxiv.org/abs/2108.12004 is to show that for any interesting problems this is a losing proposition. In other words, the number you need to add more new variables than you gain from a more efficient encoding. This argument was done by counting degrees-of-freedom; how many independent “controls” adding a new binary variable gives you. In fact, we found that it isn’t possible to have a more efficient encoding of general interactions between pairs of discrete variables than the domain-wall encoding.

Why is Domain-Wall Encoding Better?

A key part of our work was also to understand why domain-wall encoding gives better results. What we found is that the actual physics itself seems to do better at solving the problem with this encoding. In particular, a quantum annealer can be thought of as cooling a system down. The colder the temperature where it stops moving, the better answers you get. Domain-wall encoding was able to keep solving the problem while it was colder than one-hot encoding. This makes sense, from a physics perspective, since the “twist” like topological defect we made should be easier to move than it would be to update a one-hot constraint.

Think about the example with the arrows on a Mobius strip.We only have to flip one arrow to change the value which is encoded. This result is likely to also apply to gate model algorithms such as QAOA (the Quantum Approximate Optimization Algorithm), which can roughly be thought of as “simulating” quantum annealing. We chose to use quantum annealers since larger devices are available right now, and therefore more interesting problems can be investigated.

The Bottom Line

While the domain-wall encoding and the results showing that it is the most efficient method available are exciting by themselves, there is another reason this work is exciting. It shows one the fundamentally exciting aspects of quantum computing; the fact that it touches so many fields. It shows that these fields can contribute in surprising ways.

In this case, physics has inspired a better encoding, which is generally thought to be the domain of computer science. This shows the value of bringing new ways of thinking to other fields, in this case bringing the principles of a common type of physical systems to the realm of computing.

This work also shows the importance of how the problem is encoded relates to its ability to solve a problem. This means that the underlying physics of the device should be considered when choosing how to encode information, a perspective which is often overlooked in traditional computer science where the goal is often to abstract away the underlying physical device.

Co-written by Raouf Dridi and Jesse Berwald.