For a quantum computing optimist, Scott Aaronson spends an impressive amount of time trying to figure out what quantum computers can’t do. A computer science professor at the University of Texas at Austin and a Simons Investigator, Aaronson pushes the boundaries of both classical and quantum computing to better understand what they can and can’t do. “I try to understand the ultimate limitations of algorithms,” he says. “It goes hand in hand with understanding what is possible.”

Classical computers run on bits. Each bit can be 0 or 1, on or off. Quantum computers instead use quantum bits, or qubits, that can exist in superpositions of states. In a superposition of states, each state has a number called an amplitude associated with it. In some ways, an amplitude is similar to a probability, but instead of the positive probabilities we are familiar with, these numbers are complex. (Complex numbers consist of numbers of the form x + iy, where x and y are both real numbers and i is the square root of -1. Complex numbers provide a two-dimensional rather than one-dimensional set of numbers to work with.) By carefully manipulating the amplitudes associated with different states so that correct answers are amplified and incorrect ones cancel out, a quantum algorithm can achieve a massive speed advantage in calculations for some problems compared with a classical computer.

Or so it would seem. But at the heart of any discussion about the relative merits of quantum versus classical computing is a nagging uncertainty called ‘P versus NP.’ This problem concerns how quickly the amount of time it takes to solve a problem grows as a function of the input size. There are some problems — factoring large numbers is one famous example — that no one knows how to solve in what is known as polynomial time. (That is, the time to run the algorithm is a polynomial function of the size of the input, such as n² or n^500,000.) Instead of polynomial time, the best-known classical algorithms to solve these problems have a number of steps that grows exponentially with the size of the inputs. For large inputs, exponential growth completely overwhelms polynomial growth.

Problems that are known to have polynomial-time solutions are considered ‘easier’ than problems that don’t have such solutions, which computer scientists colloquially call ‘hard.’ But for some of these hard problems, including integer factoring, it is easy to check whether a proposed solution is correct. The best-known algorithms for integer factoring take exponential time to implement, but it only takes polynomial time to multiply two numbers and check whether their product is the desired number. “We don’t have the mathematical tools right now to prove unconditionally that most of the problems we think are hard really are hard,” Aaronson says. The P versus NP problem, which has a million-dollar bounty on its head, asks whether the problems that seem hard to solve but easy to check are actually hard to solve at all.

Aaronson and his collaborator Avi Wigderson have also done substantial research on what is known as the algebrization barrier, which they identify as one of the main obstacles to showing that P and NP are indeed different.

The fact that P versus NP and related questions are still unsettled makes the true extent of quantum advantages difficult to ascertain. In the 1990s, Peter Shor developed an algorithm for factoring numbers in polynomial time using a quantum computer. It is leaps and bounds more efficient than the best-known classical algorithms, but that doesn’t necessarily mean there aren’t similarly efficient classical algorithms no one has yet been clever enough to find.

Shor’s algorithm for factoring large numbers so far seems to be a special case. For most problems, Aaronson and other researchers have found that quantum computers have only a limited, though often substantial, speedup over classical algorithms. So far, other than for factoring, quantum simulation and a few other tasks, quantum algorithms usually cannot take an exponential-time problem and turn it into a polynomial-time problem.

Google, IBM and other research teams have recently built 50-qubit quantum computers, with about twice as many qubits and many orders of magnitude more computational power than what had previously been available. (Data about the performance of these computers may not be available for some time.) Past the 50-qubit point, another uncertainty starts to creep in. If you start using quantum computers to solve computationally expensive problems that aren’t easy to check, how do you check your work? “There’s a bit of irony here,” Aaronson says. “For the problems that we know how to attack in the near future, the only way we know how to verify the quantum computer’s results is essentially to simulate the whole computation on a classical computer. But the very fact that you can do the latter calculation means that the quantum computer isn’t doing something that’s impossible for classical computers.” Of course, the quantum computer will move more quickly. Computations that take seconds to perform on a 50-qubit computer may take days to verify on a classical computer. But verifying the result of computations on a 100-or 200-qubit system could very well become functionally impossible for a classical computer.

When people think about the applications of quantum computing, they often start worrying about the security of current cryptographic systems. For example, RSA (Rivest–Shamir–Adleman), a common public-key cryptosystem, relies on the difficulty of factoring large numbers for its security. Aaronson points out that, although eventually quantum computers could break existing public-key cryptography, there are other cryptographic systems waiting in the wings that we don’t know how to break — not even with a quantum computer.

Aaronson is even more excited about another application of quantum computing: simulation. What better to simulate complicated chemical interactions, down to the quantum mechanical level, than a computer that runs on quantum mechanics itself? “Once you’re confident the device is working, you can start using it to simulate molecules that have never existed,” he says. While some of the problems that quantum computers could solve seem to be hard for the sake of being hard (indeed, much cryptography relies on such questions), simulating complicated chemical interactions could have a tangible impact on a range of questions in physics, chemistry and biology. Although quantum-computing-aided drug discoveries are still a long way off, the next few years could lay the groundwork for the application of quantum physics to several areas of scientific research.