Grid of atoms is both a quantum computer and an optimization solver

Quantum computing has entered a bit of an awkward period. There have been clear demonstrations that we can successfully run quantum algorithms, but the qubit counts and error rates of existing hardware mean that we can’t solve any commercially useful problems at the moment. So, while many companies are interested in quantum computing and have developed software for existing hardware (and have paid for access to that hardware), the efforts have been focused on preparation. They want the expertise and capability needed to develop useful software once the computers are ready to run it.

For the moment, that leaves them waiting for hardware companies to produce sufficiently robust machines—machines that don’t currently have a clear delivery date. It could be years; it could be decades. Beyond learning how to develop quantum computing software, there’s nothing obvious to do with the hardware in the meantime.

But a company called QuEra may have found a way to do something that’s not as obvious. The technology it is developing could ultimately provide a route to quantum computing. But until then, it’s possible to solve a class of mathematical problems on the same hardware, and any improvements to that hardware will benefit both types of computation. And in a new paper, the company’s researchers have expanded the types of computations that can be run on their machine.

Maintaining neutrality

QuEra’s qubits are based on neutral atoms, a well-established technology that’s also used by at least one other quantum computing startup. Typically, neutral atoms are used in general-purpose, gate-based quantum computers, which can perform calculations through a series of logical operations performed on the qubits. While these can potentially perform any calculation, there are specific calculations that can be completed on gate-based quantum computers that could not be calculated by a traditional computer.

In the gate-based mode of a neutral atom quantum computer, the spin of the nucleus is used as a qubit. The atoms can be moved and held in place by laser light, which creates traps where it’s energetically favorable for the atoms to sit. By moving these traps, it’s possible to place any two atoms next to each other and perform joint operations on them. Normally, the electron cloud prevents the nuclear spin from interacting with anything, which makes for a very stable qubit. But the spin can be addressed after exciting the atom to a Rydberg state, where one of its electrons is excited to very high energies, creating a distant cloud that barely remains bound to the atom.

So, neutral atoms provide all the tools needed for gate-based quantum computing: a long-lived quantum state, the ability to set and read that state, and the ability to arbitrarily connect any two qubits by placing them in close proximity. But, as with other gate-based quantum computers, the qubit count are too low and error rates are too high at the moment for anything more than demonstrations.

But there’s the alternative mode of operation, which QuEra is calling an “analog mode.” This is based on a phenomenon called the Rydberg blockade, a quantum phenomenon where the presence of one atom in the Rydberg state reduces the probability of any other nearby atoms from ending up in the same state. By controlling the distance between atoms, you can effectively create situations where only one member of a pair of atoms can enter the state.

This allows a set of two (or more) atoms to entangle in a quantum superposition. You can place the atoms at a distance where only one of them can enter the Rydberg state and then bathe both in enough light to excite an electron. Only one of them can respond, and there’s no way to determine in advance which of them will. Until you measure, both atoms are equally likely to be in the Rydberg state—they’re in a superposition. And, just as in other entangled systems, measuring one atom means the second has to be in the opposite state.

Constraints upon constraints

Now imagine placing a third atom in a line with the other two. All the atoms enter a superposition of states, but because of the Rydberg blockade, there are only two stable, low-energy configurations: both atoms at the end are in the Rydberg state, or only the middle atom is in that state—the geometry adds constraints to the system. Changing the geometry alters the constraints; if the three atoms were arranged in a triangle with equal-length sides, then there are three stable end states that are all equally probable, each with a single atom in the Rydberg state.

Adding more atoms places additional constraints on the stable end states of the system, with the exact nature of these states depending on the geometry. And the people at QuEra recognized that small clusters of atoms that have one set of constraints could be bridged by atoms to an additional cluster with completely different constraints. This leaves the final state set by the combination of the two constraints. And the process could be repeated until the geometry dictated a large set of constraints on the system’s ground state.

These constraints could represent a form of a math problem called a maximum weight independent set. The geometry represents the properties of the set you want, and the ground state(s) it settles into represent members of the set with specific properties. “We take advantage of the fact that [the atoms] don’t necessarily interact with one another to put them in specific geometries,” said QuEra’s Alex Keesling “And this can be a grid, or it can be a graph problem that you literally represent with where the atoms are placed relative to one another.”

One of the key features of this type of problem is that, as sets grow in size, it becomes increasingly difficult to find these maximal sets using classical computers. The other is that it’s what’s called an NP-complete problem, which means that any other NP-complete problem can be transformed so that solving a maximum weight independent set problem will provide a solution to it. This means that operating QuEra’s machine in this mode can potentially solve a wide range of math problems.

Useful solutions?

Regarding real-world problems, challenges to maximum weight independent set problems can provide the equivalent of optimizations. An example used by QuEra is figuring out where to locate branches of a retail giant so that you minimize the probability that one branch will cannibalize sales from another. These problems are typically hard to find solutions for because doing so requires testing all possible configurations, and that grows dramatically as the number of options—the number of shopping centers in which stores could be placed, in this example—goes up.

The nice thing about running optimization problems on this hardware is that errors aren’t as problematic as they are for gate-based algorithms. “Errors can still occur, but they’re less disastrous,” Keesling told Ars. “What you’re doing is that you’re preferring one particular solution, which is the right solution. But as you introduce errors, little by little, you’re deviating from the perfect solution, but not by much.” If you view the set of potential solutions as a two-dimensional landscape, and the correct answer as a peak on the landscape, each error only moves you a small distance away from that peak. The resulting answer is still likely to be close to optimal, since it’s high on the peak’s slopes.

If this sounds familiar, it may be because it’s similar to how quantum annealers, like the one offered by D-Wave, arrive at solutions. The big difference is that the formal mathematics behind solving maximum weight independent set problems is much more thoroughly worked out.

But, with the new paper, the parallels go a bit deeper. D-Wave hardware natively solves problems called quadratic unconstrained binary optimization problems (QUBOs). And a new paper that includes QuEra scientists among its authors describes how QUBOs can be transformed so that they run on the company’s hardware. It also describes how to factor numbers on the QuEra machine.