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.
- 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).
- Measurement based, also called one-way quantum computing. This is still in its conceptual stage.
- Topological quantum computing, which is being developed by Microsoft but is still in very early stages of physical realization of even one qubit.
- 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.
Risk Warning: Cryptocurrency is a unregulated virtual notoriously volatile instrument with a high level of risk. Any news, opinions, research, data, or other information contained within this website is provided for news reporting purposes as general market commentary and does not constitute investment or trading advice.
