By Amara Graps
45+ years ago, the availability of Apple I, II, Commodore, Kim and other personal computers, inspired a generation of hobbyists, who relished accessing the computer’s 6502 chip. I worked in a group at NASA-Ames, where we kept a half-dozen extra Apple IIs for parts to maintain the operations of our ‘portable’ infrared astronomy, data-acquisition system. One (left in this team photo) of the astronomy team members wrote the code closest to the Apple II’s hardware, which was in 6502 assembly-language; code that looked similar to this. 6502-Hobbyists should not throw out their old Apple II 6502 Assembly Language manuals, either, as they are apparently a collector’s item.
Today, quantum computer programmers, upon accessing a QPU, require a similar, raw programming style, that reminds me of those old days. Along with the ‘assembly-language code’, i.e., circuit programming, are their collection of algorithms, and a variety of languages and programming environments. From GQI’s Outlook Report: Quantum Algorithms Outlook
It is not possible to divorce algorithms from the specs of the hardware on which they are intended to run. Academics have been developing quantum algorithms for 30 years. Early quantum hardware varied from non-existent to very poor. […]
Inside Presentation GQI Quantum Software State of Play you’ll see GQI’s Framework for how GQI views Algorithm classes. GQI has incorporated the best conceptual ideas from the literature and will be expanding the GQI tool in the future. I’d like to step through the classification thinking in the Algorithm community first and provide some useful references for you.
Algorithms Organization Challenge
The software tools for writing today’s quantum algorithms have emerged as ubiquitously as the devices. When Kumar et al., 2022, in Futuristic view of the Internet of Quantum Drones, summarized the current programming tools for the quantum subset of Internet-of-Things, the authors required two pages of illustrations (see their Figures 14 and 15).
Dalzell et al.,2023 in Quantum Algorithms: A Survey of Applications and End-to-End Complexities addressed the algorithm organization challenge by providing an application focus woven in a Wiki format. Additional hyperlinks in the header of every page provide a means to quickly jump to sections and sub-sections. Nevertheless, for a document, which is 337 pages and ~1000 references, the hyperlinks provide a smart navigational solution, not a simplifying organizational structure.
Algorithms Re-Organization
This year, we see researchers approaching the algorithm maze with a purposeful classification mindset.
Arnault et al., 2024 in A typology of quantum algorithms looked at algorithmic trends in the NISQ era that might reveal the useful building blocks that can aid the discovery of quantum advantage. The authors categorized 133 quantum algorithms, based on their ability to solve basic mathematical problems, their practical applications, the primary subroutines they use, and other factors. Their aim was the discovery of relationships, dependencies or patterns among the algorithms and the criteria used.
Their dependence network offers a comprehensive picture of every layer of subroutines. It reveals also, to some degree, the history of ideas guiding the building of various algorithms, therefore providing an insight into the logical links among them. You can also download this figure and more from their paper from their Github site. A zoom into the center of the figure is below.
Arnault et al., 2024 saw changes in the development of the algorithms, with some mathematical classes and application domains becoming more and more prominent. Notably, there was an increase in the themes of “Operational Research,” “First-Principle Quantum Simulation,” and “Machine Learning & Data Science.” In Arnault’s Appendix A: Algorithms Classification table, there were 50 classified as potential candidates for using a NISQ processor, while the remaining candidates require a fully error-corrected (FTQC) machine. See also their Figure 6: Percentage of NISQ/ FTQC algorithms per Mathematical Class and Figure 7: Percentage of NISQ/ FTQC algorithms per Application Domain.
GQI’s Doug Finke says in a recent Laser Focus article that of Arnault et al.’s 133 algorithms, “a total of 50 were classified as potential candidates for using a NISQ processor, while the remaining candidates require a LSQ machine. It’s possible one of these NISQ algorithms can indeed provide a usable commercial quantum production before the FTQC quantum computers are available.”
You’ll recognize some of these same classifications in GQI’s own Algorithm Framework, where GQI has incorporated similar classifications and more to fit into NISQ and FTQC (fault-tolerant quantum computing) eras. GQI’s method of assessing quantum era and their uncertainties is here.
Slide from Presentation GQI Quantum Software State of Play showing GQI’s own Algorithm Framework that incorporates algorithmic themes for different hardware eras. If you are interested to learn more, please don’t hesitate to contact [email protected].
Now that you’ve seen useful classification of these algorithms, let’s see more tidying-up.
Programming Order: Abstracting the principles
Di Matteo et al., 2024, in An Abstraction Hierarchy Toward Productive Quantum Programming presented quantum computer programming in a similar level of abstraction as that for High Performance Computers; a three-layer abstraction hierarchy that incorporates:
1) a programming model is used to map algorithms onto software,
2) an execution model to understand how software executes, and
3) a hardware model to define an abstract machine that represents physical hardware.
Some Examples
- Programming model
- High-level quantum subroutines
- Ansatz with hybrid optimization loop
- Unitary operations
- Repeat-until-success
- Execution Model
- Logical (non-hardware-native) circuits
- Error mitigation
- Error correction
- QRASP
- Hardware model
- Hardware-native circuits
- Pulses
Figure. A proposed abstraction hierarchy derived from the three-level (Programming, Execution, Hardware) model. The state of today’s quantum computing hardware and software can lead to overlapping, blurry boundaries from, Di Matteo et al., 2024, in An Abstraction Hierarchy Toward Productive Quantum Programming
The authors provide two case studies of eigenvalue estimation using their methodology,
VQE with error mitigation and
QPE (Quantum Phase Estimation) with error correction.
With a hope (and a call for discussion) that they’ve provided a layered complexity of abstractions, which correspond to the levels of software development today. These abstractions would support the evolution of software, without the need to rethink hardware.
September 5, 2024
