Three Types of Quantum Algorithms and Quantum Applications

This informal paper proposes a unified framework for categorizing quantum algorithms and quantum applications into three types based on the degree of computational complexity in terms of the types of hardware resources required.

By quantum application, this paper is referring to applications for quantum computing, and not applications for quantum communication, quantum teleportation, quantum metrology, quantum sensing, or quantum networking. Quantum algorithm applies only to quantum computing in all cases.

If you came here looking for information about the kinds of applications which are appropriate for quantum computing, see this informal paper:

• What Applications Are Suitable for a Quantum Computer?

Key motivations:

1. I wanted to highlight the prospect of using advanced, high-performance quantum simulators, especially when comparable physical quantum computers with the desired number of qubits, coherence time, or connectivity are either not yet available at all or are not yet common, cheap, and readily available.
2. And to highlight the use of quantum-inspired algorithms on classical computers.
3. To highlight hybrid quantum/classical algorithms and applications relative to pure quantum algorithms and applications.
4. And also to highlight algorithms and applications which may not yet be practical due to limited near-term quantum computers, but might be expected to become available in the foreseeable future.
5. And to highlight proposed or suggested algorithms and applications which are not really on any practical horizon, at this time.
6. I wanted a unified framework for expressing these and other issues that relate to the degree of hardware support for quantum computing in general and quantum parallelism in particular.

Algorithms vs. applications:

Before we dive directly into the types in the unified framework, we need to say a few things about algorithms and applications. It is frequently convenient or tempting to treat quantum algorithms and quantum applications as synonyms, which is okay to some extent, but there are some important distinctions:

1. The overall thrust of this paper applies equally well to both quantum algorithms and quantum applications.
2. Every application has at least one algorithm.
3. Many or even most applications have more than one algorithm.
4. A particular algorithm might be used in multiple applications.
5. Algorithms and code are not quite the same concept, although many people treat them as synonyms. An algorithm is a more abstract expression of the intentions of a computation — what is intended to be accomplished — and tends to be light on implementation details, while code is a representation of an algorithm which provides all of the implementation details — the how to flesh out the what of the algorithm. A quantum circuit is the quantum computing equivalent of classical code.
6. There tends to be a lot of code in applications beyond the code of the core, critical algorithms.
7. Some algorithms run completely on a quantum computer.
8. Some algorithms run completely on a classical computer. They may or may not interact directly with the quantum algorithms.
9. Some classical algorithms might be used to prepare the data for a quantum algorithm.
10. Some classical algorithms might be used to generate the quantum circuit for a quantum algorithm. Not all quantum circuits will be coded by hand or even created using interactive tools. In fact, for more sophisticated quantum algorithms and applications, dynamic generation of quantum circuits will tend to be the norm.
11. Any input data must typically be encoded or dynamically generated in the gate structure (quantum code) of the quantum circuit.
12. Some classical algorithms might be used to interpret or post-process the measured results of a quantum circuit (quantum algorithm.)
13. Some algorithms are hybrid quantum/classical algorithms with parts which run on a quantum computer and other parts which run on a quantum computer.
14. Although applications will tend to have a fair amount of code beyond the core, critical algorithms of the application and that code will usually run on a classical computer, that does not necessarily mean that the application is a true hybrid quantum/classical application per se.
15. A true hybrid quantum/classical application is one in which one or more of the core, critical algorithms are hybrid quantum/classical algorithms, with some portions of the core, critical algorithms running on a quantum computer and other portions of those same core, critical algorithms running on a classical computer.
16. The use of code running on a classical computer to generate the quantum circuit for a quantum algorithm does not automatically mean that the application or algorithm is a true hybrid application or algorithm. The key distinction is whether all of the algorithm is embodied in the generated quantum circuit or if portions of the logic for the algorithm must be run on a classical computer before or after the quantum circuit is run.
17. The mere fact that classical code must be used to prepare the input data or parameters for the quantum circuit or is used to do post-processing of the measured results of the quantum circuit does not automatically mean that the application or algorithm is a true hybrid application or algorithm. The key distinction is whether the main logic of the algorithm itself is split, not whether preparation or post-processing are needed. For example, a variational quantum eigensolver (VQE) is a true hybrid quantum/classical algorithm since the classical code executed between the variations is a core part of the algorithm. Shor’s algorithm for factoring large semiprime integers is also a true hybrid quantum/classical algorithm with a significant portion of the algorithm logic run before and after each iteration of the order-finding algorithm, and part of the order-finding algorithm itself must be run on a classical computer.

The three types:

The proposed unified framework defines three primary types of quantum algorithms and quantum applications:

1. Type 1. Can be simulated fine on a quantum simulator, running on a classical computer (or specialized digital hardware.) A physical quantum computer is not needed. Requires only a modest number of qubits, but may require a combination of circuit depth, coherence time, or connectivity which is not supported by available physical quantum computers.
2. Type 2. Requires a physical quantum computer, cannot be simulated effectively. May require too many qubits to be simulated (beyond 40–56.)
3. Type 3. Cannot be run on existing quantum computers, but a future quantum computer should be sufficient.

The inspiration for these three types was Stellar population of astronomy which divides stars into three populations or groups:

1. Population I. Recent stars, the youngest stars.
2. Population II. Older stars, the oldest stars we can detect.
3. Population III. The earliest stars, which no longer exist.

The analogy is not perfect, but that is where I got the idea.

Five types:

Actually, five types of algorithms and applications for quantum computing are proposed here, the first being algorithms and applications which don’t require a quantum computer at all and can run just fine on a classical computer without a quantum simulator, and the fifth being theoretical quantum algorithms and applications which would not run on even an ideal quantum computer.

The other two types, beyond the three primary types:

1. Type 0. Can be run fine on a classical computer, no need for quantum operations (quantum logic gates or quantum circuits) or a quantum simulator. Includes quantum-inspired computing.
2. Type 4. Even in theory, cannot be run on even an ideal, ultimate quantum computer.

I am currently unaware of any real or proposed quantum algorithms or applications which cannot be run on an ideal, ultimate quantum computer, but hypothetically they may be possible.

Might full and accurate simulation of the human brain, human mind, and advanced, human-level intelligence be a Type 4 application? Possibly, but we know too little about the human mind and artificial general intelligence (AGI) to say for sure.

Other factors:

Four factors are outside of the scope of the three primary types of the proposed unified framework per se:

1. Hybrid quantum/classical algorithms and applications. Each of the quantum portions alone of the algorithm or application would be covered by the typology proposed here.
2. Quantum-inspired algorithms. They run on classical computers, so none of the typology of three primary types proposed here is relevant, but varying degrees of classical computing resources will be required, ranging from a single commodity classical computer, to high-end classical computers, to distributed commodity classical computers, to distributed high-end classical computers, and even to GPU, FPGA, and full-custom digital hardware possibly in the mix as well.
3. Logical qubits and quantum error correction. The presumption here remains NISQ devices. The presumption here is that the algorithm designer only cares about the number of qubits usable directly in algorithms, regardless of what technology is hidden under the hood of the machine.
4. NISQ (noisy intermediate scale quantum) devices. All of Type 2 as well as Type 3 initially would utilize NISQ devices. At some stage in the future, but not in the next few years, logical qubits and quantum error correction will become available and NISQ will gradually no longer be relevant to Type 3.

All five types:

Here, finally, is the full unified framework:

1. Type 0. Can be run fine on a classical computer, no need for quantum operations (quantum logic gates or quantum circuits) or a quantum simulator. Includes quantum-inspired computing.
2. Type 1. Can be simulated fine on a quantum simulator, running on a classical computer (or specialized digital hardware.) A physical quantum computer is not needed. Requires only a modest number of qubits, but may require a combination of circuit depth, coherence time, or connectivity which is not supported by available physical quantum computers.
3. Type 2. Requires a physical quantum computer, cannot be simulated effectively. May require too many qubits to be simulated (beyond 40–56.)
4. Type 3. Cannot be run on existing quantum computers, but a future quantum computer should be sufficient.
5. Type 4. Even in theory, cannot be run on even an ideal, ultimate quantum computer.

Subtypes

The three/five types should cover most or at least many of the cases of interest, but sometimes a finer granularity is needed. Subtypes can fill this gap.

It is not the primary purpose of this paper to lay out definitive definitions for all possible subtypes, but there are a number of obvious candidates, which are listed here more as examples than necessarily being definitive, although the subtypes listed here are all solid candidates for consideration.

Type 0 subtypes

1. Type 0.1. Truly classical, deterministic algorithm.
2. Type 0.2. Monte Carlo method or similar statistical approach which relies more on probability than determinism. May be competitive with quantum algorithms for some applications.
3. Type 0.3. Quantum-inspired algorithms. Using abstractions closely based on quantum parallelism which can be mapped to either a quantum computer or a classical computer. Limited parallelism using multiple processors. Unlike a quantum simulator, code would run native classical — a compiler from the quantum-inspired abstraction to native code, particularly to utilize multiple processors in parallel.

Type 1 subtypes

1. Type 1.1. Minimal classical hardware required to host a quantum simulator. Even commodity or personal computers. Even JavaScript in a web browser.
2. Type 1.2. Higher-end classical hardware required. More memory, more processors.
3. Type 1.3. Distributed classical hardware required. Ranging from a small number of commodity processors to a large cluster of high-end processors.
4. Type 1.4. Specialized hybrid hardware required, such as GPU, FPGA, or full-custom digital hardware.
5. Type 1.5. Distributed specialized hybrid hardware. Ranging from a small number of specialized processors to a large cluster of specialized processors.

Type 2 subtypes

1. Type 2.1. Physical quantum computer with a minimal number of qubits, gates, and coherence time. 5–8 qubits. Connectivity requirements will vary.
2. Type 2.2. Moderate number of qubits, gates, and coherence time. 16–32 qubits. Connectivity requirements will vary.
3. Type 2.3. Moderately large number of qubits, gates, and coherence time. 40–75 qubits. Connectivity requirements will vary.
4. Type 2.4. Large number of qubits, gates, and coherence time. 128–512 qubits. Connectivity requirements will vary.
5. Type 2.5. Very large number of qubits, gates, and coherence time. 1K to 4 K qubits. Connectivity requirements will vary.
6. Type 2.6. Extremely large number of qubits, gates, and coherence time. 8K or more qubits. Connectivity requirements will vary.

Type 3 subtypes

1. Type 3.1. Physical quantum computer with required capabilities expected shortly — less than a year.
2. Type 3.2. Expected relatively soon — 1–2 years.
3. Type 3.3. Expected relatively not so soon — 3–5 years.
4. Type 3.4. Expected relatively further out — 6–10 years.
5. Type 3.5. Expected relatively much further out — 11–15 years.
6. Type 3.6. Expected relatively even further out — 15–25 years.
7. Type 3.7. Expected relatively way out — 25–50 years.

Type 4 subtypes

There are no obvious candidates — at this time — for a more granular subdivision of possible algorithms or applications which could not in theory be run on even the most ideal quantum computer.

That said, I can’t help but wonder and speculate that there will indeed be subdivisions as we expand human knowledge of advanced algorithms and eventually hit a wall with what can be accomplished with even the most advanced quantum computers.

One possibility I can think of is the prospect of a universal quantum computer, which seamlessly merges quantum and classical computing. That would enable solutions beyond the abilities of quantum and classical computers alone and beyond even our best conceptions of hybrid quantum/classical solutions. This would raise the prospect of at least two subtypes:

1. Type 4.1. Solvable using a universal quantum computer which seamlessly merges quantum and classical computing. Either a single universal quantum computer or some number of networked universal quantum computers.
2. Type 4.2. Not solvable using even a universal quantum computer or even a large network of universal quantum computers.

Could there be alternative computing approaches beyond even a universal quantum computer? Yes, maybe, likely, and I personally expect so, but that’s beyond even my speculation at this stage.

Categorizing algorithms and applications

1. Generally, an algorithm or application should be categorized to run on the least capable hardware possible.
2. Some algorithms or applications may run only on a classical computer. Such as those using rich data types, complex data structures, and complex control flow which cannot be easily transformed into quantum parallelism.
3. Some algorithms and applications may require a quantum computer. Such as optimizing or evaluating such a large number of alternatives that running on a classical computer simply isn’t feasible.
4. Sometimes less capable hardware may deliver unacceptable performance, so the next level of hardware may be more appropriate.
5. Algorithms and applications which are cost-sensitive may be categorized as a lesser type even though a higher type might deliver better performance.

Future evolution

1. As time goes by and quantum computing technology progresses, algorithms and applications may shift from one type to another.
2. Shifts can occur in either direction — higher performance simulators can permit some Type 2 algorithms and applications to down-shift into Type 1. Advances in quantum-inspired algorithms can enable classical computers to compete with quantum computers for some use cases and some users. Algorithms and applications can become more sophisticated and require more capable hardware.
3. A more expansive view of an existing algorithm or application may suggest expansion to utilize hardware coming in the near future.
4. The precise boundaries and number of subtypes will likely evolve as well.
5. Someday people will chuckle at the thought of anyone trying to use a quantum computer with fewer than 1K qubits, much as people can no longer relate to a personal computer with only 256 bytes, 1K bytes, or even 4K bytes.
6. When will logical qubits and quantum error correction appear and then become common? Nobody has a clue.
7. When will NISQ be obsolete and be retired? Ditto, although the advent of logical qubits and quantum error correction will mark the beginning of the end for NISQ.
8. More exotic forms of computing will incrementally and abruptly appear on the horizon, so that Type 4 algorithms and applications may incrementally or abruptly drop into Type 3 and even Type 2.

What’s next?

I’ll continue to refine and update this framework, but I don’t expect many dramatic changes any time soon.

I don’t intend to formally publish this framework, but people are free to cite it as is.

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