How Mechanics Found In Nature Could Make Quantum Computing A Reality

Unfortunately, although it’s conceptually simple to work it out, no one has come up with an algorithm that is efficient enough to run at speed for tasks with more than a short list of destinations. The naive approach of adding up the total distances for all possible routes results in a combinatorial explosion of calculations. Computer scientists have tried all manner of tricks to bring it down from the order of n-factorial needed for the naive approach. But you still wind up with a running time on the order of two to the power of the number of destinations.

If you aren’t scheduling an entire lifetime of sales visits, that reduction is still pretty useful. But when you consider that the same type of problem lies at the heart of applications such as DNA sequencing, assembling complex printed circuit boards, guiding robots around a production line or managing two-way energy grids in real time, this is a heavy computational overhead that quickly becomes intractable. Even a list of 60 destinations computed with the fastest conventional method comes close to a billion trillion options to analyse.

Is there a better way? It depends on whether you want precise or close enough. Nature has some hints for the latter.

Around 40 years ago, several groups of mathematicians and computer scientists realised that basic thermodynamics could be harnessed to do almost the same job far more quickly. At the time, they proposed systems that mimicked in a digital computer the random behaviour of excited molecules to act as the inspiration for digital algorithms. This would, in effect, bounce down a slope of possibilities to land on an answer that might not be the absolute minimum distance, but is generally close enough for most purposes.

Feel the noise

It is perhaps a little perverse to use a digital algorithm to emulate noisy, random behaviour in error-free digital logic. Nature can do noisy and random gradient descent left to its own devices. Embracing nature’s own mechanics has helped bring quantum computing’s introduction forward. At the moment, engineers working on mainstream, gate-based quantum computers are struggling to work out how to deal with the many ways in which qubits (the quantum analogues of classical bits) can lose information, even sitting in a liquid-helium cooled bath meant to prevent them from destabilising. Choosing methods that are far more tolerant of noise and errors helps work around that. And some have taken that path.

At the company’s annual conference in January, D-Wave Systems’ CEO Alan Baratz was keen to distinguish his hardware from the other quantum architectures. “We chose a quantum path that has allowed us to get to commercial first, and years ahead of anybody else.”

The machines sold by D-Wave, in common with experimental machines developed for a time by some of the tech giants before they focused on gate-based architectures, have their basis in a mathematical model. This has found its way into a variety of engineering problems, including the earliest algorithms that worked out where to place the many thousands of subcircuits that make up a silicon chip.

Physicist Ernst Ising developed the model that now carries his name in the 1920s when trying to work out the problem set by his teacher Wilhelm Lenz to calculate how the spins of electrons in a hot molten metal like iron would form magnetic domains as it cooled and solidified. In the model’s initial state, the spins are completely random. 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.

Ising on the cake

In the Ising model, a matrix links each simulated atom to each of the others. The number in each position determines how much influence each atom will have on a target elsewhere in the system. Not surprisingly, an atom modelled as being far away will have limited influence compared to a near neighbour, but if there are large domains already pushing in one direction, their effects will override outlier neighbours. The lowest energy state for a magnetic material is for the spins to align with each other, but that does not need to be the case for a synthetic Ising model: you can choose to influence the costs in many ways that reflect the needs of an algorithm, including that of the travelling salesperson problem. Minimising the distance in this context is synonymous with minimising energy.

The overall energy of the system being modelled can be captured in a Hamiltonian, a mathematical operator that is instrumental in quantum mechanics. That in turn provides a natural link to architectures such as D-Wave’s, which is designed to use electronic coupling as well as quantum entanglement between qubits to provide the necessary connections between the particle spins. However, there are questions as to how much the quantum aspect of their construction actually helps.

D-Wave’s is far from the only method for implementing an imitation of an Ising model in hardware. The claimed quantum advantage may be an illusion in practice. As with gate-based quantum computers that use superconducting elements, you cannot easily connect more than a handful of neighbouring qubits in a superconducting quantum machine. Though there are applications where this is not a huge problem, there are others where you need the system to be able to determine how even widely scattered elements influence each other. But these can still work. Around 15 years ago, former D-Wave scientist Vicky Choi showed that it is possible to map these problems on to the quantum architecture, but this kind of remapping comes at the cost of more qubits to represent the problem.

In the mid-2010s, researchers working at Stanford University and a separate group at NTT’s basic research laboratory in Japan pumped up to 100 photons into a long loop of fibre-optic cable and used them to act as Ising states. Though the photons do not interact with each other directly, they could be coupled to every other photon’s state with a little help. An electrical circuit that monitored each pulse as it passed a detector then used the numbers stored in memory to apply the weights from the cost matrix. If high enough, a second circuit would flip the photon’s phase.

Annealing power

Though it may deliver results using less energy, annealing in any of the current hardware architectures is not necessarily a fast process, even if it sidesteps the laborious comparisons of classical computing algorithms. The quantum versions rely on adiabatic manipulations in which no energy gets transferred into the array to avoid disrupting the delicate states. The system relies on tiny fluctuations to, in effect, gently shake the components into a new energy state, each one lower than its predecessor. This puts a heavy constraint on how quickly the computer can arrive at an answer. And it might not arrive at the right answer, or anything close to it, if there is some local minimum that is far away from the target but there is a large barrier that prevents the system escaping into a lower-energy state. The conventional workaround for this is to run the algorithm multiple times to see if it converges on a single answer, or to simply find the best option that it uncovers.

One potential factor in favour of the quantum machines such as D-Wave’s is that tunnelling may help speed up the annealing process and also dodge the risk of the system dropping into a false minimum from which it cannot escape. Even so, claims that the ability to tunnel is quicker and more efficient remain unproven. Several research projects have failed to identify a built-in quantum advantage, at least so far. Maybe we do not need to cool and carefully manipulate qubits at all and just aim to be ‘quantum inspired’.

Do you need a physical representation of the Ising spins at all? At the same time Stanford and others were building their non-quantum machines, Lucas Brady and Wim van Dam working at the University of California at Santa Barbara argued in a paper written almost a decade ago that it was just as efficient for many practical applications to simulate the tunnelling effect with widely used Monte Carlo methods on conventional computers. Other researchers found there was limited evidence for a quantum speed-up versus simulated annealing, although there were some situations where the speed-up could be demonstrated.

Recognising that hardware-assisted simulation could work just as well, Japan-based Fujitsu and NTT have built separate digital simulations of Ising machines, with subtly different aims. Working in concert with the Tokyo Institute of Technology, NTT implemented an annealing algorithm on field-programmable gate arrays (FPGAs) of the kind used in cellular base stations and some machine-learning accelerators. During the telecom company’s research conference in 2021, NTT senior research scientist Satoshi Kako said the developers see it partly as an interim machine: one used to try out different ways to use annealing at high speed while the company’s teams continue to work on physical Ising machine implementations that may prove to be more energy efficient than the digital simulations.

Fujitsu, on the other hand, sees the custom digital chip – which, like the NTT’s FPGA implementation, supports a massive amount of parallelism and provides the ability to connect some 8,000 variables in an all-to-all configuration – as an alternative to using analogue electronic or photonic components to analyse the interactions. So far, the results have been promising, according to Keisuke Fukada, a researcher at Waseda University who has worked with Fujitsu’s digital-annealing research group. In work presented at last year’s Conference on Adiabatic Quantum Computing, he claimed his benchmarks on two algorithms, one of them the travelling salesperson problem, showed the digital annealer was able to complete a wider variety of tasks more quickly than both software simulation and physical Ising machines, some of which were unable to handle the larger problems.

Another option, and one exploited by start-up Fixstars as well as Toshiba (another of the Japanese giants working in this space), is to run the simulated annealing algorithms on GPUs. There is a lot in common between the gradient descent used for artificial intelligence (AI) training with the gradient descent of annealing.

This approach has the advantage of being more scalable and can exploit a number of the instructions the latest GPUs offer for machine learning, though they may demand more energy per operation than dedicated hardware. Running on the Nvidia A100 class of processor, Fixstars’ Amplify engine can support as many as 128,000 variables. Like NTT, Fixstars management sees its engine as also being useful for prototyping code for the physical Ising machines: the same software development kit can act as a front-end for quantum and other accelerators.

The quantum advantage

This digital work may make the quantum machines and other hardware emulations of Ising spin glasses look like a dead end, particularly when you consider the heavy overhead of converting many real-world problems into a form these machines can process. But it is clear that several of the hardware companies are hedging their bets, anticipating a point at which the physical Ising machines can pull ahead.

In an analysis of how well quantum annealing could work in coordinating cellular base stations, which now need the ability to optimise transmissions across many antennas in real time, researchers from Princeton University and University College London estimated it might be the mid-2030s before quantum annealers demonstrate enough power efficiency to take over from digital simulations run on digital computers.

Though the quantum advantage remains elusive, that may change with a new generation of hardware. According to D-Wave, experiments on early versions of the Zephyr architecture, which should launch before the end of 2024, have shown that higher connectivity between the qubits and the ability to maintain coherence for longer than the current machines will result in higher speed.

Whether that will be enough to outpace the digital emulations will need to wait until the machines can be tested head-to-head. It may turn out once again that the quantum and other work on physical machines can be readily harnessed by conventional digital hardware.