Imperative Family Languages The defining trait of imperative languages is that the programmer tells the computer “what to do”. The imperative languages ultimately derive from the Turing machine, a theoretical construct used by Alan Turing to formally define computability. For languages in the imperative family, a line of code like “x = 1 + 2” means “take the values 1 and 2, add them, and store the result in a variable called x.” The Turing Machine - (source: Wikipedia) The machine operates on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine. It has a head that, at any point in the machine's operation, is positioned over one of these cells, and a state selected from a finite set of states. At each step of its operation, the head reads the symbol in its cell. Then, based on the symbol and the machine's own present state, the machine writes a symbol into the same cell, and moves the head one step to the left or the right, or halts the computation. The choice of which replacement symbol to write and which direction to move is based on a finite table that specifies what to do for each combination of the current state and the symbol that is read. Non-Structured Programming (e.g. Assembly) The model of the computer here is essentially a glorified calculator. Instead of pressing buttons on a calculator, data (including all button press equivalents from a real calculator: 1, 2, 3, +, -, M+, M-, etc.) are read in serially from memory. Primitives: add/subtract/multiply/divide floats or ints Load/store data (Conditionally) Jump to a place in memory Stop computation Features: Mutability (instructions change the data to be the answer rather returning the answer) All variables are global, since they correspond to physical locations in the processor Insanely fast Poor readability Procedural/Structured Programming (FORTRAN, C, shell) I’m grouping two concepts together since they are so similar. Procedural programming was the idea that code should be grouped into distinct subunits (typically called routines or subroutines), while structured programming was the idea that all programs need only consist of serial statements, if statements, and loop statements. When taken together, they form the basis of familiar, systems languages. Primitives: Native machine data types: Int, float, char, str, bool Arrays (sometimes static, sometimes dynamic) Pointers If statements, for statements, while statements Data structures (think JSON-style, but with fields declared at compile time) Functions (which are really subroutines) Importing code from other files Features Mutability (we are free to overwrite variables, and often do so to save space) Portable (the same code runs on every processor, as long as a compiler exists) Really quite fast. Only hand-tuned assembly is faster. Object Oriented Programming (SmallTalk, C++, Java, Python, JavaScript) Object oriented programming (OOP) techniques were developed by Alan Kay in the 1960’s. The major idea was to combine data and the functions that operate on that data into a single entity called an object. OOP saw a dramatic rise in popularity with the advent of the Graphical User Interface (GUI), which became the predominant form of commercial software and was particularly suited for object oriented programming. Programs in the OOP paradigm consist of objects calling one another, or the user directly interacting with them. Primitives: Everything from procedural/structured programming Objects (a data structure that also includes functionalities called methods) Instance variables (public or private) Methods (functions that access or modify instance variables) Classes (a recipe for making a new object) Constructor function that generates a new object Destructor function that destroys an object cleanly Static methods & variables that are not a part of instantiated objects Features: Slower than Procedural / Structured program due to increased overhead Encapsulation (internal member variables can’t be accessed directly) Inheritance (extend existing code through subclassing) Polymorphism (code that works for class A automatically works for all subclasses) Declarative Family Languages Declarative Family languages focus on telling the computer “what you want” not “how to do it”. Declarative languages are typically closer to mathematics than computer technology, and tend to follow the lambda calculus formalism rather than the turing machine formalism. This is OK because in the 1940’s, the Church-Turing thesis provided mathematical proof that all lambda calculable functions can be computed by a Turing machine and vice versa. In a declarative language, a line of code like “x = 1 + 2” means “x is defined as 1 + 2.” Lambda Calculus - (source: Wikipedia) Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing lambda terms and performing reduction operations on them. Functional Languages (e.g. Erlang, Haskell, Elixir) Functional languages are characterized by their use of higher order functions; that is functions that accept other functions as input or return other functions as results. This necessitates first class functions, which are variables that contain (or, “are defined as”) functions. One example of a higher order function is the map function, which takes a list of data and a function and returns a list where the function has been applied to each element in the list. The general idea of functional programming is that rather than manipulating the input data until we have the result we want, we manipulate functions until we have the function that yields the result we want given the input data. Primitives: Functions (in the most low-level functional languages, even numbers are defined in terms of functions!) Basic types like ints, floats, strings, etc. are usually included as well Recursion (it is common to use recursion in place of loop statements) Linked lists rather than arrays for handling multiple data points Pattern matching is often preferred in place of if statements Closures (first class functions that remember their enclosing lexical scope) Features: Immutability (once x is defined as 4, x is always 4) Conceptually difficult (Haskell in particular is notorious for this) Slower than comparable procedural/structured code, but can still be faster than object oriented code. Expressive (using higher-level declarations means we don’t need to talk as much about implementation details) Logic Programming Languages (e.g. Prolog) *disclaimer: I have no actual experience with logic programming languages Logic programming languages are based on formal logic approaches in mathematics. These languages are designed to take a series of statements or rules and automatically find values that satisfy those rules. For example, a sudoku solver would be easily expressible in a logic language. One highly-researched application is in Boolean Satisfiability (SAT), which is used industrially in computer hardware design. Primitives: Symbols Predicates Constraints Features: Even more conceptually challenging than functional programming Describe the problem rather than describe the solution Query languages (e.g. SQL, SMARTS (yes, the chemistry one)) Query languages are used in databases to allow the user to retrieve data. The most common one is Structured Query Language (SQL), but many database-specific variants exist. In general, the user declares the form of the data they want, along with some criteria, and the language runtime then interprets the request and translates it into a series of lookups that ultimately result in the correct data being returned. Primitives: Data (typically text) Search terms Functions Boolean operators (AND, OR, NOT) Wildcards Features: Not widely used to build large programs Data is immutable (can’t be changed during a typical query)
What is quantum computing? In the early 1980s, Richard Feynman noted that it is exponentially costly to compute the behavior of large quantum mechanical systems. He further pointed out that this proves that at least some computations can only be practically performed by a quantum system, namely, trivially, the prediction of the behavior of the said system. Since then, much progress has been made to formulate more abstract problems that can be proven to require a quantum computer for a practical solution. One such problem is the factorization of large numbers. A certain class of cryptographic algorithms, specifically the RSA algorithm, are secure only because it is impossible to factor a sufficiently large number with practical resources. In 1994, Peter Shor described what is known as Shor’s Algorithm, which could be used to practically factor large numbers on a quantum computer and thus break all RSA-based cryptography. This would be a very big deal because a lot rests on the security of cryptography. While there are cryptographic algorithms that do not rest on factoring numbers, most believe that those would be similarly susceptible to different, not yet described quantum algorithms. The implications for information security are apparent, but the rise of cryptocurrencies adds another, very direct incentive: If someone clandestinely broke the algorithm used in a cryptocurrency network, they could conceivably walk away with billions of dollars in profits before the breach was detected and the value of the currency collapsed. However, Shor’s algorithm requires a very large quantum computer, much larger than can be practically built today or in the foreseeable future. More importantly, it depends on error-free quantum computation, which can be achieved on real hardware only with sophisticated error correction mechanisms that are the subject of ongoing research and will further increase the required system size by many orders of magnitude. For this reason, it is generally believed that practical quantum computers that can solve useful quantum problems are many decades in the future. Progress in quantum supremacy In order to make more immediate progress, then, current research is mainly directed towards proving quantum supremacy, i.e. finding a problem that demonstrates quantum supremacy in practice on actual quantum computer hardware. Because of the large gap between current hardware and what would be needed for useful problems, such problems tend to be highly esoteric and of little practical value. Still, they are essential for the field to move forward. These efforts have recently had some success. In particular, Google reported in 2019 that they had achieved quantum supremacy on a 53-qbit quantum computer named Sycamore. The problem that was solved is to predict the probability distribution of a quantum random number generator, which is classically hard (10,000 years), but practical (200 seconds) for a quantum computer. The catch here is that there is nothing useful about a random generator with that particular distribution. Google’s quantum computer is based on superconducting Josephson junctions, one of a variety of implementations of quantum computers. It is beyond the scope of this article to survey the hardware landscape, but we will point out one other promising technology for quantum computing, the photonic chip. Will it help with Drug Discovery? Drug discovery has many different areas in which computing can play an important role, and, in general, any of them could be amenable to quantum computing. Here, we want to mention just two of them: Quantum chemistry and machine learning. Non-practitioners can be forgiven to get confused by the co-occurrence of two entirely different concepts that may be relevant in drug discovery: Quantum chemistry and Quantum computing. Quantum chemical simulation has been around for decades. It involves the approximate computation of the properties of electronic orbitals, which in turn could, in theory, fully describe the behavior of molecules from first principles. Normally, when a lab or company does quantum chemistry, there is no connection to quantum computing. However, quantum chemistry does illustrate Feynman’s original recognition that quantum systems are very hard to simulate classically, and research is underway to bring quantum computing to quantum chemistry. Quantum machine learning is another promising application of quantum computing in drug discovery, simply because machine learning itself has found numerous applications. If machine learning could be sped up substantially using quantum computing, drug discovery would undoubtedly benefit. Researchers from IBM and MIT have recently proposed quantum machine learning algorithms. The broad applicability of such methods guarantees that this will be a very active field of research in the foreseeable future. What does all this mean for today’s practitioners in computational drug discovery? It is important to realize that there is a lot of hyperbole in the mainstream press, and also, unfortunately, in certain parts of the scientific literature, on how likely or how soon quantum computing will change everything. Amongst the more serious voices, some are creating the impression that this will happen anytime now; others advise caution and patience. Still, others think that the path to utility is entirely too steep. Regardless of attitude, it is clear that there are enormous hurdles in realizing practical quantum computers, both in the hardware and in the error correction mechanisms that will be necessary. Any real benefits from the application of quantum computing in drug discovery are very likely decades away. However, those potential benefits are huge, so it is prudent for the practitioner to keep mind and eyes open, while also maintaining skepticism in the face of breathless hyperbole. Cyclica’s Position Enormous hurdles exist in realizing practical quantum computers, both in the hardware and in the error correction mechanisms that will be necessary. Thus, any real benefits from applying quantum computing in drug discovery are very likely decades away. However, those potential benefits are huge, so it is prudent for the practitioner to keep mind and eyes open while also maintaining skepticism in the face of breathless hyperbole. We should keep an eye on Xanadu, who impresses by their photonic chip and their open approach to quantum software development. An alliance of some form could be beneficial, demonstrating that we are looking beyond the present and are willing to invest in the future, even when there is no imminent practical benefit.
