What Can’t a Quantum Computer Compute?

Quantum computers can do many amazing things, but they are not universal, general purpose computers. This informal paper lists some of the computational tasks which simply don’t align very well with the capabilities of even the best of current general-purpose quantum computers.

In a nutshell:

• Quantum computers offer some awesome features, but they lack most of the features of a general purpose Turing machine which are offered by all classical computers. A quantum computer is more of a specialized coprocessor than a general purpose computer. Some of the basic features of a classical computer can be mimicked by a quantum computer, but unless your algorithm exploits quantum parallelism to a dramatic degree, it will generally not gain any significant advantage over a classical computer.

Before getting into use cases where quantum computing is not a good fit, first some general caveats and notes:

1. Many, most, if not virtually all current use of quantum computing is for proof of concept projects or research rather than production-quality, production-scale, production-ready projects. The guidance in this paper is more focused on planning for longer-term production-quality, production-scale, production-ready projects. So, yes, maybe you can make your toy application run of a quantum computer, but that may not be a solid indicator of whether your full application will be appropriate and effective on the quantum computers of tomorrow. Remember, the goal is a dramatic advantage over classical computing, and at production-scale and meeting ambitious business requirements.
2. Hybrid quantum/classical algorithms have great potential and are a way to get around the limitations of pure-quantum computing, but the issue remains the degree of parallelism which can be achieved in the purely quantum portions of the algorithms. Or, more to the point, the degree to which sequential and iterative, non-parallel processing in a purely classical algorithm can be transformed into quantum parallelism with a dramatic performance advantage over a purely classical solution.
3. The use of the term task here is generally referring to processing which occurs solely in a single quantum circuit (program.) There may be more than one quantum task, and there may be other tasks which are implemented on classical computers.
4. The D-Wave Systems quantum computer is an entirely different case from gate-based quantum computers. D-Wave supports only a very specific algorithm — so the question is whether your application aligns with that algorithm and your data aligns with the number of D-Wave qubits. D-Wave may come closest to supporting production applications, but even then, only in relatively narrow niches, and only in some limited cases.
5. Timeframe — this paper focuses primarily on current and near-term quantum computers (so-called NISQ devices.) Much of the guidance here will still apply for medium-term quantum computers, and possibly even longer-term quantum computers.
6. It is presumed that a true universal quantum computer, which combines the full features of a classical computer with the power of a quantum computer in a single machine with zero latency, will not be available in the near-term. When true universal quantum computers do become available 5–10 years from now, they will be a game changer, eliminating many but not all of the limitations expressed in this paper.
7. For the near-term foreseeable future, algorithm designers must accept that quantum error correction (QEC) will not be available. Qubits and gates will be somewhat noisy, but improving incrementally as each year goes by.
8. For the near-term foreseeable future, algorithm designers must accept that quantum phase estimation is not practical, except in limited, special cases
9. For the near-term foreseeable future, algorithm designers must accept that quantum Fourier transforms are not practical, except in limited, special cases.
10. A general rule is that the first step to developing a quantum algorithm is to attempt to directly map the application problem into a raw physics problem which can be expressed in terms of features which align with the raw physics capabilities of the qubits and quantum logic gates. If such a mapping feels too problematic for your problem, there’s a good chance it won’t be appropriate for solution using solely a quantum computer.
11. A second general rule if the application problem cannot be cleanly mapped to a raw physics problem is to consider a hybrid solution, partitioning the problem into classical and quantum parts, but only if there are clear portions of the problem which do map cleanly to the raw physics of qubits and quantum logic gates — and for which quantum parallelism for each quantum portion has a clear and dramatic benefit over a purely classical solution.
12. Never underestimate the cleverness of brilliant mathematicians, physicists, computer scientists, and others at coming up with very creative solutions to problems previously believed to be intractable or impractical.
13. Unfortunately, in many cases extreme cleverness is required to achieve a successful quantum computing solution to a problem. Unlike classical computing, direct and brute force solutions are not as likely to uncover the full power of quantum parallelism, which too-often requires extreme cleverness. If your organization lacks the talent or budget to hire or contract the level of staff needed to discover extremely clever solutions you may have difficulty fully exploiting quantum parallelism.
14. Sophisticated technical staff is needed. While some organizations may be able to handle sophisticated quantum computing projects, many organizations may not have the level of sophisticated technical talent in-house or be financially able to budget for outsourcing of the sophisticated technical talent which is required for sophisticated quantum computing solutions. Without access to the appropriate level of technical staff, an organization can’t complete a given quantum computing application even if they do have access to the required quantum computing hardware.
15. Lack of availability of sophisticated outsourced technical talent. While there may indeed be quantum computing vendors and consulting firms who do in fact have technical talent of the level of sophistication needed for sophisticated quantum computing projects, scheduling issues and competing demand may mean that an organization may not be able to outsource the necessary sophisticated technical staff required for a given quantum computing project which would otherwise be practical if such technical talent were available. Without access to the appropriate level of technical staff, an organization can’t complete a given quantum computing application even if they do have access to the required quantum computing hardware.
16. Data quality is essential — the quality of the results of a quantum algorithm won’t be any better than the quality of the input data. You could have the most exquisite and perfect quantum algorithm imaginable, flawless in every way, but if the input data is problematic, the results of this beautiful algorithm will be highly suspect. Relevant factors include garbage in/garbage out, low precision, varying precision, unknown precision, garbled data, missing data, out of range data, and data cleansing. Preprocessing is a valuable tool to deal with data quality issues, but the algorithm must be able to handle problematic data to some degree, even if only in the classical portions of a hybrid algorithm, and the raw input data quality might be too problematic for even the best preprocessor. Ultimately, actual data quality might preclude an ideal sophisticated quantum computing solution.
17. For general guidance on the types of applications appropriate for quantum computing, see What Applications Are Suitable for a Quantum Computer?.
18. All of the caveats and rules expressed in this paper are general in nature — there will almost always be exceptions. If you follow the guidance expressed here, generally you will be happy with the results.

The list in this paper is not meant to be exhaustive, but simply representative of the range of computing tasks which are not appropriate for a quantum computer as such machines currently exist and are currently envisioned for the relatively near-term foreseeable future.

A quantum computer is not appropriate for computing tasks such as:

1. Computing pi to an arbitrarily large number of digits. A new paper by Adam Brown of Google and Stanford which came out shortly after I wrote those words suggests learning the digits of pi using Grover’s algorithm to simulate the counting of collisions of two billiard balls and a wall — it looks intriguing, but even if it does work for fairly small numbers of digits (5–10, maybe 20?), it doesn’t seem likely to work well for a large number of digits (50, 100, 1,000, a million, a billion, a trillion — the record using a classical computer is 2.7 trillion digits) since it relies on small-angle rotations of qubits and the count (all of the digits of pi that have been learned) must fit within the qubits of a single quantum computer, which has no ability to do any I/O or be networked as a distributed system. Circuit depth and coherence time are also problematic factors. For now, a classical computer seems a much better choice for computing pi to a large number of digits.
2. Computing trigonometric functions (e.g., SIN, COS, TAN) to an arbitrarily large number of digits.
3. Computing irrational numbers (e.g., SQRT(2)) to an arbitrarily large number of digits.
4. Computing factorials for large, arbitrary numbers.
5. Computing exponentials for large or non-integer numbers to an arbitrarily large number of digits.
6. Computing Taylor series expansion for an arbitrarily large number of terms or digits of precision. Such as trigonometric functions (sin, cos) and square root.
7. Factoring very large numbers, such as semiprimes used for public-key encryption (2048 or 4096 bits), in the near to medium term. Or even factoring more modest but still large numbers in the 128 to 512 bit range.) Whether Shor’s algorithm would actually work in a practical sense for very large numbers is dubious (e.g., the precision which could be achieved for phase of a qubit), even for a large-scale fault-tolerant quantum computer. For example, even if it works in theory, the number of repetitions needed for the quantum circuit needed for order-finding to get a statistically significant result may be too large to be practical.
8. Anything requiring conditionals, looping, or nested function calls. Although such logic can be performed in classical code for a hybrid solution, the quantum portions, quantum parallelism in particular, cannot rely on those features. Note: Rigetti does have a couple of very limited features for conditional execution and looping, but they implicitly measure qubits, which collapses their quantum state, making these features unusable within quantum parallelism. Their current doc, as of this writing, indicates that “Classical control flow is not yet supported on the QPU” and I haven’t seen any published papers which use these features.
9. Complex logic, requiring conditionals, looping, or external function calls, simply will not work within quantum parallelism. Any such complex logic must be factored out into classic code, so that the quantum circuit is straight-line logic.
10. Extended sequential processing, such as for a very long list of input data. Quantum circuits need to be relatively short. In some cases the input can be broken into chunks, but it can quickly become questionable whether much of a dramatic quantum advantage will remain.
11. Anything requiring a full Turing machine. Including complex logic, conditionals, loops, and function calls.
12. Any computation requiring dynamic heap memory allocation.
13. Any computation requiring real numbers with a significant number of fractional decimal digits.
14. Any computation requiring floating point numbers. If calculations cannot be reduced to integers or fixed-point scaled integers, or to the raw physical properties of qubits is not appropriate for a quantum computer, although it still could be true that portions of such computations might still be possible on a quantum computer if all of the floating point computations can be factored out and executed on a classical computer.
15. Anything requiring a strictly deterministic, exact result rather than a probabilistic or statistical or approximate result. Multiple runs, aggregation, and statistical averaging can be used to approximate deterministic and exact results, but not in the absolute, strictly deterministic manner characteristic of classical computing. Quantum computation is probabilistic by definition, by its very nature — its foundation on quantum mechanics. The sponsors and users of a quantum computing project must be very comfortable with the notion that approximate results are good enough.
16. Blindly transferring a classical algorithm to a quantum computer. Redesign is needed. Significant redesign. Commonly a complete, from-scratch redesign.
17. Automatically translating a classical algorithm to a quantum algorithm. The degree of redesign will vary, although there may be commonality for some niches.
18. An expectation that conversion of legacy classical code to quantum circuits can be automated, wholly or even a significant fraction.
19. Large legacy classical applications where nobody really knows exactly what is going on in all of the nooks and crannies of the code. What is needed is great clarity about well-defined portions of the code which can be redesigned and rewritten as clean, tight, streamlined quantum circuits. Even then, one must ask what fraction of the classical code can actually be replaced with such small and tight quantum circuits — it won’t do much (any) good to have 2% of the classical code run 1,000 times faster.
20. Natural language processing of raw text or raw audio media. Some niche aspects of NLP may be appropriate, subject to all of the other guidance in this paper. It may be possible for a quantum computer to process natural language once it has been parsed by a classical computer program into semantic units such as words, punctuation, and semantic boundaries and organized in the form of states in a graph or network that could be transformed into quantum state, but not processed as raw characters, text, or raw audio. Generation of raw text or raw audio is also beyond the capabilities of a quantum computer, and would generally need to be classical post-processing of any semantic graph or network that a quantum computer might generate.
21. Text processing in general — characters, strings, and words or symbols.
22. Theorem prover.
23. Symbolic manipulation.
24. Spell checker — and corrector.
25. Semantics checker — and corrector.
26. Video processing. Too much data.
27. Large image processing. Very small images, maybe.
28. Audio processing. Too much data.
29. Text search engine. Too much data with too little structure. No, Grover’s algorithm won’t help.
30. Structured and semi-structured database access. Sorry, Grover’s algorithm is not appropriate for general database access. For example, even a simple btree lookup algorithm has complexity O(log2(N)) compared to the complexity of O(SQRT(N)) — 20 vs. 1,000 steps for 1 million items.
31. Big Data — high volumes of data.
32. Use of complex data structures. Data for a quantum computer must have a simple, linear arrangement, corresponding to the simple structure of qubits and quantum states. Any complex data structures would need to be mapped to simple linear form by classical code before it could be processed on a quantum computer.
33. Machine learning for high volumes of data. Smaller volumes, yes or maybe.
34. Traditional data processing — payroll, records, accounting.
35. Financial transactions — where balances must be maintained precise to the penny. Financial applications of a more approximate and statistical nature (e.g., portfolio rebalancing and trade settlement allocation) are more appropriate for quantum computing.
36. Real-time signal processing — any data which changes after the quantum circuit has begun execution would require the full circuit to be re-executed. A quantum computer itself has no capability for directly accessing real-time signals.
37. Output. The only output for a quantum circuit is the final, measured state of the qubits.
38. I/O. The only input for a quantum circuit is any data which is explicitly encoded into the gate structure of the circuit. The only output is the measured state of the qubits upon completion of the execution of the quantum circuit.
39. Real-time control. Not having any ability for I/O of any sort, a quantum computer has no capability for controlling real-time devices, such as process control for an industrial plant. Any real-time control would have to be made by a classical computer.
40. Media playback or recording. Again, not having any ability for I/O of any sort, a quantum computer has no capability for playing media files or recording media files. Recording and playback of media data would need to be done using a classical computer.
41. Real-time media processing. Again, not having any ability for I/O of any sort, a quantum computer has no capability for processing media data streams, such as a live feed from a video camera or microphone. Real-time processing of media data streams would need to be done using a classical computer.
42. Network access or web service access. Again, not having any ability for I/O of any sort, a quantum computer has no capability for making use of network resources or web services. A classical computer would have to perform such access with the quantum computer used only as if it were a computational subroutine.
43. Network server or web server. Again, not having any ability for I/O of any sort, a quantum computer has no capability for being used as a network server or a web server. A classical computer would have to act as the server, accessing the quantum computer only as if it were a computational subroutine.
44. Distributed quantum computing. Again, not having any ability for I/O of any sort, quantum computers have no capability for communicating with each other directly. Classical computers would have to act as the distributed nodes, each accessing its associated quantum computer only as if it were a computational subroutine.
45. Quantum communication is a unique capability entirely distinct from quantum computing at this stage. Quantum computers have no capability for communicating with each other at this time and for the foreseeable future in any way, let alone using quantum communication. Quantum communication uses flying qubits (photons transported over large distances, while quantum computers use stationary qubits which never move, although trapped-ion qubits can in theory be shuttled over short distances.
46. Quantum networking is a purely theoretical concept, not yet well enough formulated, let alone developed, to be considered for practical applications in even the medium term (3–7 years.) Sometimes confused with quantum communication between classical computers.
47. Any problem which cannot be reduced to a relatively short sequence of quantum mechanical unitary operations — a directed acyclic graph of quantum logic gates.
48. Any pure quantum algorithm which does not rely heavily on quantum parallelism — initializing a register of k qubits using a Hadamard transform to simultaneously process 2^k quantum states, with k significantly more than a few qubits, say 16–20 qubits or more. Fewer qubits of quantum parallelism is appropriate for proof of concept projects, but not appropriate for production applications, since it is unlikely to have a dramatic advantage over classical computing. You wouldn’t use a quantum computer to get a 25%, 50%, 100%, or even 400% advantage — 1,000X to 1,000,000X is more reasonable, as a starting point. Unless your quantum code is utilizing quantum parallelism in a dramatic manner, you might as well stick with classical code. Granted, there may be applications or organizations where an application using less than 16 qubits is considered a reasonable advantage over the comparable number of classical computers operating in parallel.
49. A hybrid quantum/classical algorithm where the quantum advantage of the quantum portions of the algorithm is not very dramatic, typically meaning quantum parallelism with a Hadamard transform of fewer than 16–20 qubits. If the 2^k possible values of a Hadamard transform can readily be parceled out to 2^k parallel classical processors (e.g., dozens, hundreds, or even thousands of classical machines), then the quantum computer is not offering a defensible advantage. Granted, there may be applications or organizations where an application using less than 16 qubits is considered a reasonable advantage over the comparable number of classical computers operating in parallel.
50. Modeling of complex systems with a large number of entities (greater than available qubits), although maybe the computation can be factored so that portions can execute on a quantum computer even if other portions can only be executed on a classical computer with a significant amount of memory.
51. Modeling of complex systems with a number of entities comparable to the number of qubits, unless the computations can be reduced to raw physical operations which can be directly performed between qubits.
52. Any application requiring an audit trail or explanation for actions and decisions which occur within quantum circuits. Any audit trail or explanation must occur in classical code, such as a hybrid application. Any quantum logic must be a strict black box where you can see and record only the raw inputs and the raw outputs, with no intermediate results, particularly when quantum parallelism is used, which is the intended common case. The probabilistic nature of quantum computing can also mean that there are multiple results, each with its own explanation, for the exact same inputs.
53. Cracking post-quantum encryption. By definition, post-quantum encryption (post-quantum cryptography) is designed to be quantum-resistant so that it cannot even in theory be cracked using even the most powerful quantum computer.
54. Regular expression pattern matching. Complex logic required.
55. Calculate median of n unordered numbers.
56. Count 0’s or 1’s of 2^n quantum states.
57. Man-rated systems. Safety is critical — nondeterministic, probabilistic, or approximate results are unacceptable. Transportation control (non-routing), elevator control (non-routing), safety systems, medical devices, air traffic control (non-routing.) Routing is safe since approximate solutions are fine.
58. Complex Adaptive Systems (CAS).
59. Climate modeling.
60. Navier–Stokes equations.
61. Finite Element Analysis (FEA).

Probabilistic computing

Some applications may not need the raw power of a quantum computer, but do need a unique feature of quantum computing: the native ability to generate true random numbers. A pure Turing machine cannot generate true, non-pseudo random numbers, by definition, since they are not computable classically.

That may not be a sufficient reason to use a quantum computer, but depending on the particulars of the application it might.

Technically, the generation of true random numbers can still be performed on a classical computer, but only with additional hardware, driver software, or interactive user input which permits collection of entropy from the environment. Alternatively, network access to a random number generation server can supply true random numbers, but then they are not being generated on the classical computer on which the application is running.

Hybrid quantum/classical computing

Granted, larger problems can frequently be decomposed into smaller tasks, some of which can then be performed on a quantum computer, with the results of those quantum tasks combined using classical glue code — this is the hybrid approach to quantum computing, but those smaller tasks must require a large amount of processing to justify the use of a quantum computer. An example would be a variational quantum eigensolver (VQE) and similar iterative algorithms.

Universal quantum computer

Someday, eventually, we will see a merger of classical and quantum computing — what I call a universal quantum computer — where classical and quantum features can be freely mixed, but even then you wouldn’t be able to perform quantum parallelism over a classical computation — although a sufficiently smart compiler should be able to translate many classical constructs into equivalent quantum computing operations (gates), but even then there would still be limits to how much computational flexibility you would be allowed when performing a computation under quantum parallelism.

What’s next?

I’ll occasionally update the lists in this paper as I discover new items and as quantum computing technology advances.

Over time — years? — some of the items may even be removed from the lists. But not soon, unless I simply made a mistake.

I also intend to produce a separate paper on Quantum computing Personas, Use Cases, and Access Patterns.

For more of my writing: List of My Papers on Quantum Computing.