To solve a variant of the chess-inspired N-queens problem, researchers at the University of Innsbruck propose a quantum simulation using a “chessboard” of laser-trapped atoms in a resonant chamber. [Image: University of Innsbruck/V. Torggler et al., Quantum, doi: 10.22331/q-2019-06-03-149]
Recent years have seen impressive advances in hardware platforms for potential quantum computers. Yet the toughest quantum nut to crack actually may lie on the application side—specifically, in finding problems, and problem-solving algorithms, for which quantum computers have a clear advantage over their classical kin.
Researchers at Austria’s University of Innsbruck have proposed a novel test for one such “quantum supremacy” problem (Quantum, doi: 10.22331/q-2019-06-03-149). At the heart of their proposal? A tiny chessboard of laser-trapped atoms.
N queens, N×N squares, NP-hard
The work of the Innsbruck team, led by Wolfgang Lechner, revolves around a well-known mathematical riddle called the N-queens problem, first posed in 1848 by the German chess player Max Bezzel and studied in detail by the 19th-century polymath Carl Friedrich Gauss.
The crux of the problem is simply stated: For N queens placed on a chessboard of N×N squares, what are the configurations in which the queens can be arranged such that none of the queens threaten any other—that is, such that none lie on the same row, column or diagonal? For a small N, the problem isn’t that tough, but the number of possible combinations quickly mounts into the billions as N gets into the area of more than a couple dozen.
Moreover, it turns out that a restricted variant of the problem—one in which some queens are fixed in place, and queens are excluded from certain diagonals on the board—is known to be a so-called NP-hard computational problem, with variants, for N > 21, that can’t be solved in any reasonable time using classical algorithms. That, according to the Innsbruck group, makes the problem a ripe candidate as a test of a possible quantum-computing advantage over classical machines.
A proposed testbed
As a route toward a solution of this chess-inspired problem, Lechner’s group proposes that experimentalists might use a tiny “chessboard”—a 2-D N×N optical lattice, in which N ultracold atoms, representing the queens, are trapped in particular nodes. An anisotropic optical field would allow the atoms the possibility of tunneling in only one direction (the x direction), which turns out to be adequate to capture the full range of possible positions.
The atom trap would be placed in a resonant cavity to intensify long-range interactions. The atoms themselves would be nudged into interactions with one another through scattering from pump laser light from three directions, and the excluded diagonals would be enforced by repulsive optical potentials (using, for example, light sheets and optical tweezers).
Taking advantage of quantum superposition
Using this platform to find solutions to the N-queens problem would involve calculating a ground-state Hamiltonian—the mathematical operator describing the full system’s energy state—that corresponds to solutions to the N-queens problem. (Lechner and his colleagues mathematically derive such a Hamiltonian in the paper.) The system would be then prepared in a superposed quantum state, and allowed to evolve adiabatically until it had reached that ground state.
One of the study coauthors, OSA member Helmut Ritsch, noted in a press release accompanying the work that it is this advantage of quantum superposition that could allow the platform to converge on solutions faster than a classical computer. Because the cooled atoms “behave like waves and can test many possibilities at the same time,” he said, “it quickly becomes apparent whether there is a valid solution according to chess rules for the given conditions.”
Optical readout
Interestingly, the news that a solution had been found could be read out entirely optically on the platform, from the pump strengths and configurations corresponding to the ground-state Hamiltonian. Specifically, the team’s calculations suggest that a simple intensity read-out would allow one to determine whether a solution had been found by the simulator, since “a state corresponding to the solution of the N-queens problem scatters less photons than all other states.” Homodyne detection of the output field quadratures, meanwhile, would provide some insight into the actual atom positions, though full position information for a given solution would require use of a quantum gas microscope.
In an e-mail to OPN, Lechner noted that, while his team had laid out the roadmap, the actual implementation would be left to others. “We are a theoretical physics group, so we will not build the experiment ourselves,” he said, adding that an “interesting aspect” of the work is that “all ingredients that are required” are already available in quantum physics labs, and so no new technology is required to run the test.
Indeed, the team sees the result as significant in that it offers one potential route for exploring the problem of quantum supremacy using today’s tools, with numbers of trapped atoms (qubits) well within current capabilities. “This combinatorial problem,” the team writes, “may serve as a benchmark to study a possible quantum advantage in intermediate-size near-term quantum experiments.”