Unconventional Computing: Applications, Hardware, Algorithms

Quantum computing, and more generally unconventional computing, have seen an explosive development within the past five years. A comprehensive treatment of the subject would require a series of lengthy articles. The selection of topics covered here is not intended to be fully representative of the subject but rather a very limited sample – a teaser – seen through the lenses of operations research, operations management and applied physics, emphasizing the near-term computational possibilities, motivated by practical applications that naturally fit in the framework of nonlinear integer programming. This is the newly created field of quantum integer programming (QuIP) [1]. For a traditional introduction to quantum computing that focuses on gate/circuit model and quantum complexity theory, see Rieffel and Polack [2].

Motivating Applications

Problems requiring a high degree of parallelism are ill-suited to the traditional von Neumann computing architecture, the framework for conventional digital computing, where instructions are fetched from memory and executed in a largely sequential process. These performance limits are apparent to any computer gamer or cryptocurrency miner who has used a graphics processing unit (GPU). Many of the most challenging computational tasks involve solving large combinatorial optimization problems and are important in applications as diverse as finance, drug discovery, cancer genomics, machine learning, message decoding, resource optimization and scheduling, of which most belong to the category of nondeterministic polynomial (NP)-hard or NP-complete problems.

These problems can be modeled as nonlinear integer programs, where the difficulty arises both from having constrained integer (binary) variables, as well as complicated nonconvex, nonlinear objective functions. The increasing importance of solving such problems heuristically coupled with an increasing number of problems that are unsolvable with traditional computers in any reasonable amount of time has motivated researchers to investigate alternative computing models and novel algorithms.

Unconventional Computing

The 20th century hardware development relied on a computational model by Turing, an architecture by von Neumann, digital logic gates based on Boole, electronics based on transistors (and integrated chips) based on quantum mechanics, and algorithms based on sequential state computation. This is known as the first quantum revolution.

Now entering the third decade of the 21st century, we are witnessing the next revolution: a computational model based on Ising, with non-von-Neumann architecture, analog evolution without a central clock, spintronics based on magnetic spins that also rely on quantum mechanics – thus the name second quantum revolution – and optoelectronics with algorithms designed for collective state computation. This is unconventional (or nontraditional) computing.

Quantum Computing

Quantum computing is just one example of unconventional computing. There are (at least) four types of quantum computing. Regardless of which type, the core commonality is that we are manipulating superpositions of zeroes and ones, and not “already formed” zeroes and ones. These are called quantum bits, or qubits. They are very different from bits. This is the quintessential feature of quantum mechanics that has no classical counterpart. This makes quantum computing unconventional. Four types of quantum computing are as follows.

1. Circuit (or gate)-based, the ones you hear most about because Google and IBM are investing heavily in it. This is “conventional or mainstream quantum computing.” Even within this category, there are two types: (a) based on transmons (Google, IBM) and (b) trapped ions (ionQ).
2. Measurement based, also called one-way quantum computing. This is still in its conceptual stage.
3. Topological quantum computing, which is being developed by Microsoft but is still in very early stages of physical realization of even one qubit.
4. Ising-based, also referred to as Adiabatic quantum computing, or quantum annealing. This is being developed by D-Wave (in Canada) [3]; see Figure 1. This most directly maps to combinatorial optimization problems.

The Ising model presents a unique paradigm for tackling combinatorial optimization problems [4]. It describes a type of collective state computing rather than sequential state computing.

Conventional Hardware for Ising Computing

Artificial intelligence and machine learning (AI/ML) applications demand greater performance from computing hardware. This has led Amazon, Apple, Microsoft and Google (with tensor processing units or TPUs) to design their own chips, either in-house (like Amazon with their acquisition of Annapurna Labs) or with chip designers such as Arm (recently acquired by Nvidia). This has put immense pressure on traditional providers of chips such as Intel (who acquired Habana Labs) and AMD (who recently acquired Xilinx).

There are many Ising classical approximation algorithms available today that we can run on conventional machines as well as GPUs and TPUs (Figure 2). Taking this to the next level, Toshiba and Fujitsu have developed the Simulated Bifurcation Machine (SBM) and Digital Annealer. These are examples of quantum-inspired hardware, where existing CMOS-based technology is used to architect hardware that attempts to solve the Ising model. Table 1 lists some available Ising solvers and their capabilities.

Figure 3: Stanford Coherent Ising Machine

Graver Augmented Multi-seed Algorithm

The algorithms needed for Ising-based devices are very different than those that have been created for Turing machines. An important intermediate step in any algorithm that connects combinatorial optimization to Ising models is QUBO, quadratic unconstrained binary optimization. However, naively transforming a constrained optimization problem into a QUBO – where the objective function and the constraints are combined into one expression – and feeding it into an Ising solver does not provide speedup, nor is it scalable.

To better take advantage of Ising solvers, it helps to decompose the problem, separating the objective function from the constraints, and building on primal methods to solve integer programs through the use of Graver Augmented Multi-seed Algorithm (GAMA) test-sets [6, 7]. This approach was not explored in the context of conventional computing because it relies on computing a test set (that is very large) and the availability of several feasible solutions (that are themselves hard to find). With Ising solvers, however, it has become possible for certain important classes of specially structured optimization problems – well suited for applications in finance, genomics and supply chains – to obtain samples of partial test sets and feasible solutions in reasonable time [8, 9].

Beginning with several feasible solutions (“seeds”), the Graver test-set elements are used to augment – an interior-point lattice-walk – these solutions to obtain a collection of local minima. Choosing the best among these local minima is the heuristic GAMA (Figure 5). Examples of its computational performance on hundreds of structured problems (quadratic assignment and quadratic semi-assignment) with nonconvex, nonlinear constrained binary variables, and on cancer genomic applications, can be found in Alghassi et al. [8, 9].

Figure 5: Graver Augmented Multi-seed Algorithm (GAMA)

Hybrid Future

Cloud quantum (and Ising) computing is already here (Figure 6), through Amazon Braket, D-Wave and IBM. The future will be a hybrid between classical and unconventional computing. We do not have to wait for decades to have fault-tolerant quantum bits (qubits) in sufficient numbers and connectivity [10]. Ising computing can boost these features much sooner. R&D on a wide variety of different types of unconventional computing are progressing in parallel, competing and collaborating, and time will tell if one or more will emerge as dominant add-ons, preferred partners to classical computing, which, by the way, is not going to go away anytime soon.

Figure 6: Cloud quantum computing

Acknowledgments

Collaborators include post-doctoral researchers at the Tepper Quantum Computing Group Hedayat Alghassi (IBM) and Raouf Dridi (QCI); professors Peter McMahon (Cornell), Anil Prabhakar and Prabha Mandayam (IIT-Madras), Aaron Danner (NUS); Davide Venturelli (NASA); Sanjay Padhi (Amazon); and CMU Ph.D. student David Bernal.

As first published in INFORMS.

References

1. David Bernal, Sridhar Tayur and Davide Venturelli, 2020, “Quantum Integer Programming (QuIP),” https://bernalde.github.io/QuIP/.
2. Eleanor G. Rieffel and Wolfgang H. Polak, 2011, “Quantum Computing: A Gentle Introduction,” MIT Press.
3. Tameem Albash and Daniel A. Lidar, 2018, “Adiabatic quantum computation,” Reviews of Modern Physics, Vol. 90, No. 1, Article no. 015002.
4. Andrew Lucas, 2014, “Ising formulations of many NP problems,” Frontiers in Physics, Vol. 2, No. 5.
   Peter L. McMahon, Alireza Marandi, Yoshitaka Haribara, Ryan Hamerly, Carsten Langrock, Shuhei Tamate, Takahiro Inagaki, et al., 2016, “A fully programmable 100-spin coherent Ising machine with all-to-all connections,” Science, Vol. 354, No. 6312, pp. 614-617.
5. Michele Conforti, Gerard Cornuejols and Giacomo Zambelli, 2014, “Integer Programming,” Springer.
6. Hedayat Alghassi, Raouf Dridi and Sridhar Tayur, 2019, “Graver bases via quantum annealing with application to non-linear integer programs,” arXiv preprint: 1902.04215.
7. Hedayat Alghassi, Raouf Dridi and Sridhar Tayur, 2019, “GAMA: A novel algorithm for non-convex integer programs,” arXiv preprint: 1907.10930.
8. Hedayat Alghassi, Raouf Dridi, A. Gordon Robertson and Sridhar Tayur, 2019, “Quantum and quantum inspired methods for de novo discovery of altered cancer pathways,” bioRxiv: 845719.
9. John Preskill, 2018, “Quantum Computing in NISQ era and beyond,” arXiv preprint: 1801:00862.