A 20th-century theoretical model of the way magnetism develops in cooling solids is driving the development of analog computers that could deliver results with much less electrical power than today’s super-computers. But the work may instead yield improved digital algorithms rather than a mainstream analog architecture.
Helmut Katzgraber, associate professor at Texas A&M in College Station, TX, argues, “There is a deep synergy between classical optimization, statistical physics, high-performance computing, and quantum computing. Those things really go hand in hand. Nature is the best optimizer out there. Lightning typically chooses the path of least resistance. A soap bubble will always give you the minimal surface.”
“Maybe we should go back to what we did in the 1930s and 1940s: we built special-purpose computers,” adds Katzgraber. The problem with such alternative architectures, he notes, is that the technology for such analog machines is at the level of digital computing in the 1940s. “Today we only have very limited machines and limited experience.”
One physical process that lies at the heart of a number of experimental machines is the annealing of a spin glass. The focus of a model developed by physicist Ernst Ising in the 1920s, a spin glass represents the highly disordered state of a hot magnetic material. In the initial state, the spins are not aligned with each other, but as the material cools, an annealing process leads to the spins slowly becoming aligned as the spins of individual atoms flip up and down.
In Ising’s model, a cost matrix that links each simulated atom to each of the others influences how the spins will align. The overall energy is captured in a Hamiltonian, a mathematical operator used in quantum mechanics. The operator represents the sum of individual energy states in the system. A prototype for one special-purpose computer that uses the Ising model is a long loop of fiber-optic cable in the E.L. Ginzton Laboratory at Stanford University in California.
The photonic machine at Stanford finds “approximate or exact solutions to the Ising problem,” says Stanford University researcher Peter McMahon. “Phrased this way, it sounds very restrictive. It’s more general than that one specific problem: it can be used for quadratic binary optimization problems, but it’s not so general that it can solve any optimization problem.”
The key is to develop a cost matrix that encapsulates the parameters to be optimized, and use that to drive the Hamiltonian to its lowest energy state. In principle, the physics-based simulation can find optimal solutions to certain problems in many fewer steps than classical digital techniques, but it is far from clear that the analog accelerators will prove to be faster than their digital counterparts.
The machine at Stanford is far from the first to attack optimization problems by emulating the behavior of Ising spin glasses. D-Wave Systems, Google, Microsoft, and a number of universities and computing companies are focusing on designs that use quantum effects to drive the annealing process.
Explains McMahon, “Quantum annealers are types of Ising machine. The leading quantum-annealing technologies are these superconducting circuits that use magnetic flux and circulating current rather than photons as the information in their systems. It’s now a fairly advanced technology compared to ours: D-Wave has been around for almost 20 years now.”
The major problems facing builders of computers that use the Ising model are scale and connectivity. Without scale, digital computers will easily outpace quantum annealers and other machines that exploit spin-glass behavior. At the beginning of 2017, D-Wave unveiled a machine that doubles the number of qubits to several thousand. Yet the D-Wave design is limited in terms of connectivity.
In the Ising model, the spin of each particle can couple to the spin of any of the others. The second-generation D-Wave can couple the spins of fewer than 10 qubits within each cluster. These clusters are aggregated into a tree-like structure called Chimera.
In 2008, Vicky Choi, then at D-Wave and now an assistant professor at Virginia Polytechnic Institute and State University, showed how problems could be split into groups that could be mapped onto the Chimera architecture. The cost was the use of more qubits to represent a problem than would be needed in a fully connected architecture.
McMahon says the photonic approach he works on has a fundamental advantage in terms of connectivity. “We’ve come up with a scheme that allows us to connect every spin to every other spin. We have built systems that are much larger than what people have been able to do before, in our case with up to 100 spins.”
In the photonic machines built by McMahon and colleagues at Stanford, and in a parallel experiment at NTT’s Basic Research Laboratories in Japan, photonic pulses pass a detector on each pass through the fiber. An electrical circuit tracks the state of each pulse and uses its stored cost matrix to apply a feedback signal that attempts to flip the phase of the photon, rather than its spin. “We only use the word ‘spin’ because the Ising Hamiltonian is related to spin,” McMahon says. “We don’t provide massive feedback to get an answer. We do it slowly over 100 or so round trips in a form of annealing that’s not quantum annealing. But the way in which we carry out the computation is very similar.”
McMahon says groups working with superconducting devices are now looking at similar architectures based on microwave-frequency photonics at chip rather than fiber scale, to build fully connected architectures.
There are other approaches to full connectivity. A group from The Institute of Photonic Sciences (ICFO) in Barcelona, Spain, developed a quantum annealer with full coupling. The machine uses trapped ions manipulated by lasers.
Says ICFO researcher Tobias Grass, “One can think of trapped ions as a lattice of spins. By shining light onto an ion, it is possible to flip the spin and at the same time create or annihilate a lattice vibration.”
The lattice motion can be modeled using phonons, particles that transfer vibrations. Grass continues, “Once created, this phonon travels through the lattice and might at some point be absorbed together with another spin flip at a different position. Since these phonons represent a collective motion of the lattice, they travel through the whole system, and therefore can couple any pair of spins.”
The fully coupled architectures have their own scaling limits. Grass says the mutual repulsion between ions makes scaling to 100 qubits difficult using today’s techniques. McMahon says the photonic architecture can increase the size of the system to 10,000 elements—each one represented by a photon travelling around the loop of fiber. “Maybe you could really push it and get to 50,000 or 100,000, but 10,000 is where it looks to get prohibitively expensive,” he notes.
Even with highly connected architectures, the performance of Ising machines varies depending on the problem as well as the connectivity. Katzgraber points to tests in which the couplings defined in the cost matrix were altered to gauge their effect on the computability of the problem.
“As the numbers were changed, the problem became much easier. It seems that the values of the interactions matter more than the architecture,” Katzgraber says. Changing from a well-connected structure to one based on the Chimera architecture might make it harder to solve some problems, he adds. “You want to have as many connections as possible because that will allow you to work on many different problems. But you can get pathological graphs; they get stuck.”
One way researchers at Google believe it may still be possible to harness their work on quantum annealing in the face of problem-specific hurdles is to use digital computers to decide when it makes sense to hand off a computation to the analog accelerator. However, the multiple research projects may simply find that classical techniques are more likely to outperform annealing-based machines.
The U.S. Defense Department’s Intelligence Advanced Research Projects Activity (IARPA) is funding some of the academic work to determine the most likely path of progress. Katzgraber says, “The goal of the IARPA program is not to build a working quantum computer but to prove beyond reasonable doubt if quantum annealing has a practical use or not. The goal is to either bury it or invest in it.”
The result of the work may use experience derived from annealing-based techniques to develop algorithms for classical computers, rather than new analog or quantum architectures. That has already happened in the field of satisfiability (SAT) solvers, Katzgraber says. Such a solver determines whether a Boolean formula made up of AND, OR, and NOT gates can be satisfied. It is possible to reframe the problem in a way that can be solved, on a small scale today, by quantum annealing.
“Satisfiability used to be an application for the IARPA program. We developed an approach to building SAT filters that’s so efficient that doing it in quantum devices will be a waste of time,” Katzgraber claims. “Every time quantum shows a success, classical tries to outperform it. You will see similar innovations driven by this.”
Further Reading
Bainbridge, L.
Ironies of automation. New Technology and Human Error, J. Rasmussen, K. Duncan, J. Leplat (Eds.). Wiley, Chichester, U.K., 1987, 271–283.
Albash, T., and Lidar, D.
Adiabatic Quantum Computing, ArXiv Preprints. ArXiv:1611.04471 (2016)
McMahon, P., Marandi, A., et al.
A fully-programmable 100-spin coherent Ising machine with all-to-all connections. Science. 10.1126/science.aah5178 (2016)
Grass, T., Raventós, D., Juliá-Díaz, B., Gogolin, C., and Lewenstein, M.
Quantum annealing for the number-partitioning problem using a tunable spin glass of ions. Nature Communications. 10.1038/ncomms11524 (2016)
Katzgraber, H.G., Hamze, F., Zhu, Z., Ochoa, A.J., and Munoz-Bauza, H.
Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly. Physical Review X. 5, 031026 (2015)
Join the Discussion (0)
Become a Member or Sign In to Post a Comment