Published in · 9 min read · Feb 8, 2022
--
By Bryce Fuller and Ryan Mandelbaum
Companies and research institutions hope that quantum computers will be able to deepen our understanding of the universe while solving some problems beyond the reach of classical computers — some of society’s most pressing problems. However, what those problems are, and how much better a quantum computer will solve them, is a complicated question.
Though hype may suggest otherwise, quantum computers aren’t all-powerful computational devices capable of solving intractable problems like the halting problem. Rather, they’re processors built on an architecture that we hope will allow them to do anything a classical computer can do, with extra capabilities or increased performance for some problems afforded by their quantum nature. Fully understanding quantum computers’ potential abilities, and how they stack up against classical computers, requires a deep dive into computational complexity theory. Most important to the quantum-interested is a theoretical list of the problems that a quantum computer can easily solve called BQP — bounded-error quantum polynomial time.
Since you’re here, I assume you understand the basics of classical and quantum computers. If not, you can check out our learning materials here. If you just need a refresher: classical computers are machines that represent and solve problems using logic operations acting on many physical units that can take on one of two states, called bits. Quantum computers also operate using logic and bits, and thus can theoretically do anything a classical computer can do. However, quantum computers’ quantum bits follow the mathematics of waves during the calculation. This means that each bit can enter superposition (taking on multiple values at once), entangle with one another (creating correlations between qubits stronger than the rules of classical probability allow) and interfere (forcing some combinations of qubit values to become more likely and some to become less likely). Measuring a quantum state implemented on a quantum computer immediately returns only classical information — strings of binary code. You can tell whether quantum effects happened by observing many runs of your algorithm.
Today’s quantum computers are inherently noisy, thus hampering their overall ability. Researchers are working to develop error correction schemes so that these computers can achieve their theoretical potential.
Below, We’ve put together a list of complexity classes you should know, and where BQP fits into the picture. Please note that, in trying to translate these to plain language, there’s plenty of nuance that we haven’t captured. If you see someplace you think our explanations are misleading, feel free to message one of us on Qiskit Slack.
P — Polynomial Time. P is the most familiar complexity class: problems that a deterministic Turing machine — a model of classical computation which manipulates symbols presented in an order using a set of rules — can solve with polynomial time resources. Computers require resources in order to solve problems, with time, energy, and number of bits serving as some of the most important ones. For any type of problem in P, the amount of time required to solve or check it increases based on some polynomial as the problem size increases. So, if the size of the problem is x, then the amount of time it takes would be x^n, where n is a constant number. The things your computer does on a day-to-day basis are mostly in P — multiplication, for example.
Theorists think of these types of problems as “easy” for computers to solve, but this is easy in theory, not in practice. The polynomial n could be extremely large — 100, 1,000, 1,000,000, etc., as long as it’s a constant number, making for some extremely difficult-to-solve problem types in P. Implementing a given algorithm on different computing hardware can also change the polynomial. However, P is meant to abstract away the implementation details and exist as a coarse-grained classification so that we can say something fundamental about the nature of these problems.
NP — Nondeterministic polynomial time. NP is a complexity class that includes the types of problems for which a deterministic Turing machine can check whether a solution is correct in polynomial time. NP includes all of P — but also problem types for which we don’t know whether or not a polynomial time solution exists. This class includes problem types like factoring large numbers, where it’s hard to pull big numbers apart but easy to check that two factors multiply back into the first number. NP forms the crux of one of mathematics’ most important unanswered questions: it’s unproven whether or not there exists a P solution for every NP problem type, a question known as P vs. NP. Attempts to solve P vs. NP have given mathematicians lots of reasons to believe (but again, no proof) that NP does not equal P — that NP really does contain problem types that are not solvable in polynomial time.
Please note that that throughout the text, we’re talking about “problem types,” not “problem instances.” “Factoring” is a type of problem, while “factoring 15” is a problem instance. An algorithm that can crack an instance of a hard problem might be in P, but we’re more interested in algorithms that solve the entire problem type, like Shor’s Factoring algorithm designed to factor any number.
NP-Hard — Expanding outward from NP are the NP-Hard problem types, those which are at least as hard as the hardest types of problems in NP. This class includes a slice of NP (more on that below), but also other problem types that might not be in NP. NP-Hard problems often seem to exhibit a sort of unstructuredness — combinatorial behavior with lots of knobs to turn, making solvers feel as if they must rely on randomness and guessing in order to find answers.
NP-Complete — At the intersection of NP and NP-Hard is NP-Complete, the NP-Hard problem types that themselves are in NP. NP-Hard, including NP-Complete, demonstrates an interesting symmetry: You can convert a solver for an NP-Hard problem type into a solver of any NP problem using polynomial resources. In other words, finding a solver for an NP-Hard type of problem gives you the key to unlock every problem in NP (which, trivially, also includes every problem in P). This implies that if you found a polynomial time solution to any type of NP-Complete problem, you would have found that P=NP. That has not happened, nor is it expected to happen — it’s not expected that a polynomial time solution exists for anything in the NP-Hard or NP-Complete complexity class on any physically realizable computer.
NP-Complete includes some very popular problems that computer scientists speak often about such as 3-SAT and the traveling salesman problem. Sudoku is NP-Complete if you require the algorithm to solve any n x n grid (that’s thinking about Sudoku as a problem type), but is in P for algorithms meant to solve specific-size instances.
BPP — Okay, we’re not quite at quantum stuff, but we’re getting there: around P you can draw a fuzzy line representing BPP, or bounded-error probabilistic polynomial time. Before now, we only spoke about “resources” as computational time, then there’s also computational space (we’ll get to that momentarily). But what if we added randomness as a resource that computers could use? Randomness is something a regular computer can’t necessarily simulate, that we’d have to feed the computer. BPP is a complexity class of problems that we can solve and check in polynomial time with the added ability that we’re allowed to incorporate random processes to help solve the problem — and they’re bounded, meaning that the algorithm must return the right answer with a probability higher than a set constant greater than a half. It is not proven, but strongly assumed, that BPP is equal to P.
If you take away BPP’s bound — you just require the algorithm to return the answer more than half the time (but its rate of correctness can be arbitrarily close to 1/2) then you have a far more powerful complexity class called PP or probabilistic polynomial time.
BQP — Finally, we’ve arrived in quantumland with bounded-error quantum polynomial time. These are the things that a quantum computer — that is, a computer with the extra power of superposition, entanglement, and interference — can solve in polynomial time with less than a set amount of error. And now, for the most disappointing part of this blog: The boundary of BQP is a hazy line. This line sits between BPP and PP, including some (but unclear how much) of NP, and some things outside of NP.
So, a quantum computer with bounded error can solve all types of problems in P and BPP in polynomial time. It can solve some NP types of problems in polynomial time, with factoring via Shor’s algorithm serving as the most popular example. It’s not clear whether it can efficiently solve anything in the NP-Complete class—but researchers suspect it cannot. There’s plenty unproven about how complexity classes relate to one another, and BQP is yet another complexity class whose boundaries aren’t strictly defined.
Not everything is completely hazy, however, and we know that BQP is more powerful than BPP. Researchers have recently proven that BQP includes some kinds of problems outside NP, technically, outside the even bigger complexity class PH. Solutions to problem types in that class are hard for a classical computer to find or check. This means that, even on the unlikely chance someone proves that P=NP, there will still be BQP problem types that a classical computer can’t crack. However, even this relationship has some haze, since it’s unanswered as to whether P is equal to a larger complexity class that contains P, NP, and PH, called PSPACE — problem types you can solve using polynomial computational space. It’s thought not, but again, unproven.
For many interesting types of problems, just how much value a quantum computer can provide lies in P versus NP. For example, quantum can tackle things in NP like factoring. But until we prove that P does not equal NP, there’s always the off chance that some classical solution in P exists for some kind of NP problem we’ve developed a good quantum algorithm for. If you prove that factoring has no polynomial-time classical solution, congratulations, you’ve just proven that P does not equal NP, and you’ve earned yourself a million dollars!
However, there’s more to providing computational value than waiting until a proof of P vs. NP emerges. Quantum computing developers think that speedups from a big polynomial to a smaller polynomial’s worth of resources will still be useful — the kind of speedup Grover’s algorithm offers, for example, though note that resources required by quantum error correction place a further limit on those kinds of speedups. At the end of the day, these constant-factor speedups matter a great deal, but they can be hard to pin down because they require you to factor in the messy details of your computer’s design, rather than working with idealized formulations like Turing machines.
Research is emerging that there exist core advantages to computing with quantum over classical. Researchers have proven several theoretical separations between computing with quantum bits over classical bits when you pit them against one another in an even fight, such as forcing the classical computer to only run noisy, constant-depth circuits. Proofs like these have demonstrated that quantum scratch space is inherently more powerful than classical scratch space. And there still exists those BQP solutions to problem types outside of NP, though work remains to figure out how these algorithms might provide societal or business value — that’s outside the realm of theoretical computer science.
Of course, hardware developers must still create error-corrected quantum processors capable of running these algorithms. We’re biased, but we’re confident that’ll happen soon enough.
So, what can a quantum computer really do? It’s not totally clear and still requires that we develop powerful enough hardware. But we know that quantum computers can efficiently solve problems intractable to today’s best classical algorithms, that some separation really does exist between quantum and classical computers, and that BQP contains polynomial solutions even to problems outside of NP. And, with more research and hardware development, hopefully we’ll be able to access those advantages and more.
