This post originates from a project submission for the Non-Trivial Fellowship. First in a series of posts.
Introduction:
Quantum Computation is currently a field which is experiencing rapid technological development. It has been demonstrated to be able to perform certain specific, crucial tasks dramatically faster than can be done classically. Despite this, there has currently not been much focus on the technology in the EA Forum (case in point: 10 posts on the Forum tagged under Quantum Computing versus 2431 under AI Safety, a crucial issue, at the time of writing).
Clearly, then, Quantum Computing is neglected. I was particularly interested and ultimately decided to launch a research project exploring if there are pressing important world issues that are Important, Neglected, and Classically Intractable, and feasible for quantum computation. It may be noted that it will take a lot of dedicated investment to foster this technology in its current embryonic, decoherent state, and ultimately, since classical computers are superior for general-purpose everyday computation, one needs a really good reason to use quantum technology over classical.
For this reason, my project sought out to show that there are indeed pressing world issues and areas of interest to EAs where Quantum Computation could have an edge in mitigating existential risk. Note that this research project serves as a rough overview or roadmap - I am in no way an expert on Quantum Science and Technology and much of the information is still in flux, given how new this field is. This article is written so that it is universally accessable to non-quantum computer scientists: I first give an overview all in one place demonstrating the simplest general speedups for the community, and then demonstrate applications of these speedups for our target goal of getting off of the Precipice.
Background: A Quantum Edge?
Though Richard Feynman conceived of the idea to utilize quantum mechanics for computation decades earlier, noting that “if you want to make a simulation of nature, you’d better make it quantum mechanical," the very first demonstration that quantum computers could offer a fundamental speedup over classical ones was in 1985, when David Deutsch invented a problem that could be solved exponentially faster using quantum computation. He later improved upon his solution in 1992, working with a colleague to produce the Deutsch-Jozsa Algorithm. This algorithm exploits the specific property of Quantum Interference to solve the problem of determining whether a black-box function (or oracle) mapping bit-strings of size n (e.g., (0,1)n) to bits (e.g., (0,1)) is either constant or balanced. The best known deterministic classical algorithm requires 2n−1+1 queries to the function in order to categorize it with certainty, but in theory, a fault-tolerant quantum computer could deterministically solve the problem in one query, regardless of the number of bits in the input space, an exponential speedup.
This algorithm inspired further research, and Deutsch’ problem was eventually categorized as an example of an Abelian Hidden Subgroup Problem, a class of problems to which Quantum Computers are likely to provide exponential speedups. It was the first concrete piece of evidence that quantum computation may be able to perform tasks intractable to classical computers. Nowadays, there are many more overarching speedups known, and current research is primarily focused on physically realizing optimal quantum computers. From here, the issue turns to finding relevant target issues that would make use of this technology significantly more economically worthwhile, for example, then the abstruse problem of classifying functions as constant or balanced. In response, the key research questions are: are there any key areas of interest where quantum computation could revolutionize approaches towards mitigating existential risk, and if so, would there be a significant cost associated with neglecting those approaches?
Overview:
Speedups:
There are now many general problem areas where quantum computers have been demonstrated to perform better than the best known classical algorithm. Many speedups are enabled by 1) the Quantum Fourier Transformation, 2) Grover’s Quantum Search Algorithm, or 3) Quantum Hamiltonian Simulation of quantum mechanical systems. (This serves mainly as a general discussion of known overarching quantum advantages; for specific existential risk benefits, feel free to skip to the next section)
In 1994, mathematician Peter Shor developed a well-known quantum algorithm for factoring integers in polynomial time. This was particularly significant as factoring was believed (but not proven) to be a hard problem for classical computers. More technically, it is a problem known to be in the complexity class NP (the set of all problems for which a solution may be verified in polynomial time a.k.a. efficiently), that was believed to not be in the subset complexity class P (the set of all problems for which a solution may be found in polynomial time a.k.a. efficiently). Shor’s algorithm actually solved the problem of order-finding, as it was demonstrated that being able to solve the order-finding problem entails the ability to factor. The key ingredient in Shor’s algorithm was the element of the Quantum Fourier Transformation, which enables the specific subroutine of phase estimation: given a unitary operator and an input eigenstate, the algorithm approximates with high accuracy the phase of the corresponding eigenvalue. The key point of note was that if a problem can be efficiently converted into a phase estimation problem (such as the factoring/order-finding problem), then it can be efficiently solved on a quantum computer (provided efficient procedures to implement controlled versions of the operator and generate an eigenstate).
Note that a classical computer can perform the exact same algorithm for factoring. Why, then, should computer scientists care about Shor’s Algorithm, especially if quantum computers are very costly to utilize? The key point comes down to computational complexity theory. Quantum computers can perform this Fourier Transformation highly efficiently (in quadratic time) whereas the best known classical algorithm, the Fast Fourier Transform, takes an exponential number of gates. This means that Quantum Computers can execute a Fourier Transform of quantum mechanical amplitudes specifically exponentially faster than the best known classical algorithm, which could, for example, make the task of factoring hundred digit numbers used in RSA go from intractable using Shor’s Algorithm to highly efficient. There are caveats to this speedup - for example: since quantum amplitudes cannot be accessed by direct measurement, we cannot use the QFT to execute general Fourier Transformations of classical data. For this reason, utilizing this speedup is a little more subtle than classically. We require specific utilization of certain quantum properties in order to find feasible applications, and performing period-finding, discrete logarithms, and more generally solving Abelian hidden subgroup problems are currently the primary applications. A number of key quantum algorithms utilize the hidden subgroup problem such as Deustch-Josza, Bernstein-Vazirani, Simon, and Shor. This is currently one promising quantum speedup.
Quantum Search Algorithm:
Just two years after Shor discovered his landmark quantum algorithm for factoring in polynomial time, mathematician Lov Grover made another key discovery for Quantum Computation. Grover’s Algorithm allows one to speed up the process of unstructured search quadratically, which, while less dramatic than the exponential speedup of the Fourier Transform, is still significant for difficult problems. The most extraordinary aspect of Grover’s Algorithm is its generality: though initially conceived to speed up database searches, it can actually quadratically speed up many tasks where one must find a solution state given efficient search heuristics. For example, identifying Hamiltonian cycles, political redistricting, and combinatorial optimization can be performed via this algorithm. For this reason, it is one of the most general-purpose quantum algorithms.
Grover’s Algorithm is somewhat more classically intuitive than other algorithms. The first step in the algorithm is to prepare a quantum superposition of all possible states (correct and incorrect) using a Walsh-Hadamard transform. Then, one must apply a search heuristic, or oracle, to this state, which simultaneously checks all possible states in one query and marks desired states (via a negative phase, provided for example by phase kickback). Checking solutions in parallel, however, does not provide any quantum advantage on its own, as Scott Aaronson dutifully reminds us on his blog, as measurement procures a single random outcome of no use. What is needed, then, is the Grover Diffusion Operator, which performs an operation called inversion about the mean, or amplitude amplification . This somewhat increases the probability of obtaining the marked/desired outcomes while slightly diminishing the probability of the unmarked solutions that did not pass the search heuristic. Repeating the oracle and diffusion operator roughly O(√N) times, where N is the size of the search space, will produce a quantum state where the probability of obtaining a correct solution is near certain. The key point in generating this speed up is that the oracle must be an efficient subroutine, so this algorithm only works to speed up NP problems. In addition, the search space must be well defined. Given these two components, however, Grover’s Algorithm provides a general purpose speedup that can be used to significantly make a plethora of problems from risk analysis to optimization more feasible.
Quantum Hamiltonian Simulation:
The initial application of Quantum Computation proposed by Feynman, simulation of complex quantum systems is another fundamental speedup provided by quantum computers. The underlying idea is that the evolution of many quantum mechanical systems, such as would arise in chemistry, for example, are governed by differential equations simply too complicated for a classical computer to solve. For many systems of interest (such drug simulation), the Hamiltonians/energy functions become far too complicated to simulate classically due to the sheer number of variables. In fact, simulating quantum systems is an exponentially hard problem classically. Developments have demonstrated, however, that there are many Hamiltonians which can indeed be efficiently simulated on a quantum computer. If a problem can be reduced to an efficient Hamiltonian Simulation, this algorithm could be an ideal choice, for example in drug discovery or chemistry.
Where could Quantum Computing have an edge in mitigating existential risk?
My research has identified a number of applications of these speedups which are particularly relevant to the mitigation of existential risk. Part of my project is to use this research as a roadmap so further effective altruists or researchers in the industry can invest further into promising areas. I have a variety of sources from peer-reviewed research papers to general overviews and economic reports. The caveat, however, is that many of these speedups are ones that will be relevant only once we have fault tolerant quantum computers (with the exception of current applications in chemistry and optimization). For that reason, I recognized that developing the field further will require resources - as such, I have only listed applications here such that the investment into the field will ultimately be fruitful for mitigating existential risk.
Optimization and Risk Analysis:
Optimization is one general application feasible with quantum computation. It can be performed either by quantum search or by other methods such as with a quantum annealer. This speedup is already being used commercially, for example to efficiently assign flight gates at the Frankfurt Airport in Germany. It’s also being widely used in finance, such as in portfolio optimization, and other key financial objectives. But a key application for mitigating existential risk could be performing risk analysis (verified on small quantum computers) to improve decision making in scenarios that could be too complicated for classical computers. This could be of key interest to effective altruists, as the ability to simulate a number of methods to perform some goal and select the least risky option could crucial for institutional decision making; in particular for figuring out how to find the most tractable solution to important and neglected problems while accepting the least risk.
Biotechnology:
There are a number of promising areas for quantum research in the biotechnology industry, most hinging on speedups provided by Grover’s Algorithm and Quantum Hamiltonian Simulation. An important example is drug discovery: drugs are case studies of quantum mechanical systems with no feasible simulation classically. Quantum technology could drastically speed up this process from over 15 years to a matter of months or weeks, allowing research that would overall be less costly and orders of magnitude more efficient than in today’s world. Quantum Computers can also exploit optimization to solve the molecular docking problem (often the first step in drug design), and use the phase estimation algorithm to find the ground-state energy of certain Hamiltonians relevant in drug design. In 2021, Wong and Chang described a version of Grover’s Algorithm specifically tailored to perform quadratically faster protein structure prediction and Mustafa et.al described an algorithm exploiting the variational quantum eigensolver to solve the protein-folding problem. ONe could also use the quantum capability to solve the traveling salesman problem faster in order to aid drug distribution, as sometimes the problem is not deriving a new drug rather than distributing known cures, putting needles into arms faster.
Overall, there are many feasible biomedical applications that can be performed using the basic speedups described. For this reason, quantum computation could have a key edge in biosecurity research. The ability to reduce the drug/vaccine testing window could be critical in the wake of an engineered pandemic, as the ability to quickly develop biotechnology in response to a novel pathogen could make all the difference between the preservation of humanity’s potential and our falling off the precipice, alike to the massive value discrepancy between losing 99% of the population and 100%. In addition, such drugs could improve the human condition, allowing us to find compounds that could alleviate aggravating disease that affects many humans around the world. Quantum Technology could also allow us to efficiently distribute vaccines for lethal but curable pathogens to impoverished nations around the globe. Thus, biotechnology research is currently one of the most promising areas for using quantum computation for the mitigation of x-risk.
Climate Change:
There are many ways in which Quantum Computing could help alleviate the climate crisis, mostly due to innovation of improved, green technology as well as the creation of carbon-capture technology. The climate crisis gives a case study example of an anthropogenic risk; our rapid industrialization and economic growth fueled by fossil fuels have created a situation where we must rapidly improve our technology to achieve a net-zero emission economy. McKinsey has identified five key areas in which Quantum Computation could have an edge to saving the planet. Quantum Hamiltonian Simulation and Grover’s Algorithm could both be used to yield more efficient batteries, a key alternative energy source, and more accurate forecasting of weather and energy yield could lead to rapid growth for solar and wind energy, allowing us to select locations that receive maximum solar intensity or wind power. Quantum Computing could also reduce the carbon impact of industrial materials such as cement, engineer high-efficiency solar panels, and make our fertilizers for plant and livestock farming much more environmentally sustainable, among other benefits. In addition, Greene-Diniz et.al demonstrated that Quantum Computing can also design carbon-capture technology, so rather than simply halting emissions, we could create technology to reverse past harm using variational quantum algorithms. Since climate action needs to happen now, rapid investment in the quantum computing industry could be key for offsetting impacts, keeping warming to 1.5º C (a 0.5º improvement from the Paris Agreement’s target).
Machine Learning :
Quantum Computation could revolutionize the field of machine learning. Two known applications are the Quantum Support Vector Machine for classification and Quantum Principal Component Analysis, an unsupervised learning quantum algorithm. One current bottleneck in artificial intelligence for classical computers is the need to process and optimize a dramatic amount of information according to the cost function, but Quantum Optimization algorithms could be significantly beneficial to this end. The HHL algorithm for preparing state solutions to linear systems is also promising, though as noted by Aaronson, there are a couple of drawbacks in practical use of the algorithm that make its use in Quantum Machine Learning subroutines more subtle than initially expected.
However, this area is not particularly promising for the mitigation of existential risk, particularly for unaligned artificial general intelligence. For example, AI researchers Sevilla and Moreno conclude that they do not anticipate significant benefit from quantum technology in the field of AI Alignment, as Quantum Computing is primarily devoted to algorithmic speedup rather than formalized insights into novel algorithms. They do not expect advantages in either incentive design or active oversight, for the reason that quantum computing can be modeled as a “black box accelerator” that simply speeds up algorithms, which is not needed for current research. For that reason, one might not expect quantum computation to be particularly useful for Technical AI Alignment Research.
Conclusions:
In conclusion, my research has identified specific areas of existential risk in which quantum computers may have a unique computational edge. Risk Analysis, Biosecurity, and addressing Climate Change all appear to be promising applications, with well-defined, tractable solutions. Given the extraordinarily development of quantum computing over the past few years, (projected to grow from $412 million in 2020 to $8.6 billion in 2027) it is reasonable to expect that use of this technology will be both feasible and high-performing, allowing efficient solutions of certain problems that are classically intractable, such as protein-folding or battery design. I advise further research and exploration into this transformative technology that will allow the EA community to foster its development to lead towards the largest positive impact we can possibly create for humanity.
First in a series of posts. Upcoming posts will focus on the ethics of quantum computation, risks of neglecting, and counterfactual impacts.
I am not the only quantum computing PhD student I know with an interest in AI existential safety, and there’s a reason for that: I don’t think quantum computing is going to be that useful that soon. That’s not to say that I’m pessimistic about it! But my timelines for AI and useful quantum computers are pretty similar, and that does not favour the latter.
Regardless, there’s a lot of funding for quantum computing and no good reason I see for EA to get involved. Let me make a few illustrative comments.
A concerningly motivated start.
I’ve no interest in fighting about D-Wave and assigning flights at Frankfurt airport, though I will note that their devices do not attempt to perform gate-based quantum computation.
Unrelatedly, people like to do things with their quantum computers. Usually, they are motivated by publicity.
Then you refer to an ability for quantum computers to solve the travelling salesman problem faster in order to aid drug distribution. The problem is NP-complete, so we only see a trivial Grover-type quadratic speedup. And…really? Drug distribution? This is a subset of shipping route optimisation. These companies are aware of quantum computing, and don’t need EA’s help.
You finish by throwing around a number of material design claims. But like everything you’ve mentioned here, none of these things are neglected, and it’s not clear why EA should be involved.