Three Types of Quantum Algorithms and Quantum Applications

  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.
  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 computationwhat 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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store