Ronak Ramvishal Tiwari WHU - Otto Beisheim School of Management |
Amir Hossein Moadab Washington State University |
Pavithra Sripathanallur Murali George Mason University |
There’s plenty of room at the bottom was the title of the lecture that Richard Feynman delivered in 1959. His talk at Caltech had more to do with what the future of information storage looked like, and that there was plenty of room available at the atomic level for the same. In the interest of this article however, we take a generalist view on the title of his talk and interpret it as “. . . plenty of room [for exploration] . . . ”. While Feynman was correct and we’ve indeed witnessed the meteoric rise in storage capabilities, the room for exploration has definitely squeezed a bit lately, with the debut of Quantum Computers. This article nevertheless is an attempt to give the reader i) a glimpse of status quo of computing at a quantum mechanical level, and ii) a peek into how algorithms differ in this bizarre way of computing. We believe that this write-up will invariably educate or inspire the next/current generation of OR/MS students who are interested in the subject and are adventurous enough to test out a new potential career path.
But why go Quantum?
For everyone who has even remotely thought or heard about quantum computing, the first question that probably comes to mind is – why quantum? To clear the air of suspense early, the answer is computational scalability and efficiency. A big caveat though, is that the scalability and efficiency aspects are a merit only for a selected set of problems.
Take, for instance, the Traveling Salesman Problem (TSP), a widely studied problem in the optimization literature. The problem in its simplest form is to determine the shortest possible route that a salesman should take to visit all the cities in his itinerary exactly once. What makes the problem hard is the need to know and calculate the lengths of all possible routes (yet)The problem is (polynomially) unsolvable, and hence difficult computationally for classical computers and remains inefficient even for large-scale supercomputing setups. On the other hand, quantum computers can leverage quantum mechanical properties such as superposition and entanglement to process multiple potential solutions simultaneously. This capability significantly speeds up calculations for complex optimization problems and high-dimensional simulations. If not for these colossal problem instances, conventional computers are perfectly capable and efficient at handling regular web browsing, chats, and everyday computing tasks.
What gives a Quantum Computer the computational superiority for some problems?
While we’ve partially answered this in the previous section, the question remains: how these quantum privileges are exactly utilized to realize computational advantages over a classical regime?
The best way to explain the microscopic machinery behind the computational advantage Quantum Computing offers is to start by understanding how a classical computer takes an input and processes it. It is by now clear that we have forced ourselves into a world represented in zeros and ones (or bits). This means that a classical computer reads a sequence of bits as inputs (say two numbers), does a pre-decided operation (say addition) on them through logic gates (i.e., AND, OR, XOR, etc.), and outputs another string of bits (sum of two numbers). The obvious disadvantage here is the asynchronous nature of doing things.
Alluding to our earlier example of TSP, the asynchronous approach would require every potential route to be fed into the operation (calculate path length) one by one. And if the number of possible routes is too many – this conventional approach breaks down pretty quickly, unless we discover a clever way to avoid having to calculate all possible path lengths altogether.One could argue that if it was possible to perform these operations synchronously (parallelly), it wouldn’t be too hard of a problem then? Although distributed and parallel computing, exploit the idea of parallel operations to a great extent, and there’s a lot that has been achieved in that space, it doesn’t solve the problem in general, and is costly – to cut to the chase.
Quantum superiority
Quantum Computers work in a fundamentally different manner and do away with the need of having classical bits in toto. They operate with what’s called a collection of ‘Qubits’ (short for Quantum Bits) instead. These qubits are quantum mechanical systems with two states essentially (e.g., photons with two polarization states). The peculiarity about these qubits however is their ability to co-exist in both the states at the same time. In other words, a qubit is in state 0 in some universe and state 1 in some other set of universes (at least theoretically according to Everett’s many-worlds interpretationPhysicists refer to this purported ability of parallel existence as superposition. Mathematically, this simply means – a qubit is in state 0 with some probability (say α) and in state 1 with probability β, and can be understood as a linear combination of the two states of the qubit (often described using Dirac notation as α |0⟩ + β |1⟩).
Recall from previous paragraphs – what limits us is the asynchronicity of inputs, which is a hard requirement in the classical regime. In the world of quantum computers, on the other hand, qubits can exist in a superposition of states and hence a superposition of inputs can be generated. For the TSP example, this means that an arrangement of qubits would enable us to feed multiple routes simultaneously and process them in parallel. This quantum parallelism is effectively the reason behind the computational superiority of quantum computers over the classical ones Nonetheless, parallelism comes with challenges – in this case, although the routes could be processed in parallel, one would still need to search through all the routes to select the best one. We address this in the following sections.
Have companies invested in the Quantum tech, what’s the state of the art, and who’s leading?
If you are scratching your head after what we just described in the section above, then you’re perfectly normal. Even the best of physicists, until this date, don’t exactly understand how nature’s micro-citizens behave like this. And in all humility, this should be treated as rather their best attempt to describe the quantum mechanical state of affairs. With that being said, giants like IBM, Google, Microsoft, Amazon, Alibaba, Baidu, Honeywell, and Intel, have ventured into this space and have poured in billions to test out the commercial possibilities of such quantum systems. In fact, countless new players have flocked into the space and seized the opportunity in both the software and hardware sides of the business (IBM and Amazon have put together some really good resources on the subject). For instance, D-Wave Systems has emerged very successful in testing and building out systems that operate on the principle of quantum annealing (different from the gate model of quantum computing which we will describe later) with limited use-cases in optimization.
Commercialization of the quantum technology is still a challenge given the astonishingly delicate and error-prone control environment that these qubits perform the computations in. In other words, the current generation of quantum computers, known as Noisy Intermediate-Scale Quantum (NISQ) devices, is capable of performing certain quantum calculations, but they are limited by noise, error rates, and the number of qubits they can reliably manage (Preskill, 2018). These systems cannot yet handle large-scale, real-world problems with full precision. This, unfortunately, is the state of the art. And according to ‘The Quantum Insider’, IBM is by far the leader in the quantum revolution. The Wikipedia page on the List of quantum processors confirms IBM’s lead in the race, as it features most entries from IBM with recent ones being IBM Condor (1221 Qubits) and IBM Heron (133 Qubits). Note that there’s a lot of wide-scale experimentation going on in the field, and no two companies are working with the same architecture, which might make direct comparison a bit unsound. For example, Google had already made headlines with its Sycamore processor, claiming quantum supremacy by solving a problem in 200 seconds which was later hugely criticized by the community (Cho, 2022). We therefore leave it up to the reader to decide who’s winning.
Quantum superiority is fine! but how to solve classical problems on these fancy devices?
Algorithms form the bridge between computing and problem solving; ergo, how to run algorithms on a quantum computer. Before venturing into the algorithms, we take a brief moment and turn to the customary intro that was intentionally skipped at the beginning of this article, i.e., conceptualization of the first quantum computer and the group of people who did it. Richard Feynman, Paul Benioff, and Yuri Manin were the collective first in the early 1980s to have solidified the idea of a quantum mechanical computation (Nature, 2022). More fundamental was Benioff’s work that theoretically described the Quantum equivalent of a Turing machine. Meaning, in theory, quantum turing machines (QTM) could use quantum algorithms to solve classical problems. Coming back to algorithms again, we’ve just established that a quantum computer would need quantum algorithms to solve the classical problems on it – what’s next is how these algorithms differ from their classical counterparts.
Before answering that, we would like to redirect the reader’s attention to the points we addressed at the end of section 2. We highlight that quantum parallelism would only allow us to process multiple inputs simultaneously, and additionally, we can still read only one output at a time. Therefore, the challenge is to make sure that after the parallel processing of a superposition of states as inputs, we measure the correct answer as an outcome. Luckily, quantum computers are equipped with two more special abilities in their arsenal that enable them in doing so; i.e., 1) Interference: the ability to interact with states of other qubits, and 2) Entanglement: ability to entangle with the states of other qubits. Quantum algorithms, essentially exploit these three effects (superposition, interference, and entanglement) to amplify the probability of measuring the correct answer. And, it is Quantum Logic Gates (QLG) through which these three effects are manifested onto Qubits. This collective setup of using QLGs to manifest the quantum effects on qubits, to achieve the desired outcomes is sometimes referred to as the gate model of quantum computing.
|
| Figure 1: A look into the Future? |
Grover’s Algorithm: a simple example
Keeping a general readership in mind, we form a basis of comparison around a search problem. Simply put, we’re interested in finding if a particular name exists in a finite list of m names. Classically, one would, in the worst case, need to look at all m names in the list (this is known as a complexity of O(N)). However, a quantum algorithm could be designed (in theory) to i) create a superposition of all possible answers (i.e., from index 1 to m) into an oracle (black box) function that then, ii) simultaneously evaluates this superposed input, and iii) marks the index where the name matches in the list. Despite the possibility of the oracle function evaluating multiple inputs simultaneously and marking the correct answer, the output that would be measured by such a system would still be a single index with probabilistic outcome. The next step, as a result, would be to find a way to increase the probability of having the correct answer being measured as the output. What we just described is a well-known quantum algorithm called Grover’s search algorithm (Grover, 1996), and it amplifies the probability of having the correct answer being measured as an output by repeatedly applying what’s called the Grover iteration. Grover’s algorithm promises to converge to the correct answer in √N iterations.
Even if the explanations behind the working of algorithms or superposition sound uncanny and abstract, companies indeed have to a certain degree succeeded in constructing the hardware to make all these advantages a reality. For example, IBM, Rigetti, and Google use the superconducting architecture, whereas companies like IonQ – trap ions, stabilize them, and nudge them with lasers to achieve the same quantum effects. The algorithms, in essence, then utilize a clever arrangement of Quantum Logic Gates (e.g., Hadamard gate for superposition, Toffoli gate for flipping the state of a qubit) that can be implemented on top of these architectures.
Grover’s quantum search is one of many possibilities the quantum realm can offer. Shor’s algorithm is another premier example with applications in cryptography. Research in quantum algorithms has seen immense strides of late, with Quantum Approximate Optimization Algorithms (QAOA), quantum subroutines for Simplex, and a host of other techniques being published in the premier OR journals at an increasing rate (See (Parekh, 2023)).
Applications and critics
Finally, it is out of the scope of this article to explain the physics behind these technologies, but it is still worthwhile to inspect industry use cases that were published recently. One such example is from automotive behemoth Volkswagen, which used it for the paint shop problem which is NP-hard. The webpage of D-Wave Systems highlights several industry applications in a lot of different verticals that utilize the quantum annealing setup to solve large-scale problem instances. In spite of the gargantuan investments being sucked into the field from all directions, quantum computing has found itself in the crosshairs of many prominent and active scientists in the field. Prof. Scott Aaronson is a theoretical computer scientist based at UT Austin and has questioned the very basis of going quantum. His major argument is the extended Church-Turing thesis, which posits that what can be computed physically, can be done using a Turing machine. Prof. Gil Kalai adds to the list of critics with many more experts. Surprisingly, there’s another end of the spectrum as well. On the flip side, an Australian startup Quantum Brilliance, for instance, has pledged to miniaturize the technology and make it accessible. With the general suspicion surrounding many ideas in the field, it is certainly going to be a fascinating area to keep an eye on. After all, in Feynman’s words, "The Nature isn’t classical dammit".
Quantum Computing continues to be surrounded by the air of doubt and the hope of optimism. While no one understands at a quantum mechanical level the exact reason why things happen the way they do, and if scalable quantum computers are soon going to be a reality or not – quantum algorithms and the theoretical computational advantages that they promise to provide have kept interest in the field growing at a consistent rate.
References
Cho, A., 2022. Ordinary computer matches google’s quantum computer. Science 377, 563–564.
Grover, L.K., 1996. A fast quantum mechanical algorithm for database search, in: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212–219.
Nature, 2022. 40 years of quantum computing - Nature Reviews Physics.
Parekh, O., 2023. Synergies between operations research and quantum information science. INFORMS Journal on Computing 35, 266–273.
Preskill, J., 2018. Quantum computing in the NISQ era and beyond. Quantum 2, 79.
Acknowledgements: We would like to thank Dr. Bismark Singh for taking time to review this article.