Exploring the Evolution of Quantum Algorithms: A Comparative Analysis
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 of the astronomy team members wrote the code closest to the Apple II’s hardware in 6502 assembly-language; code that looked similar to this.
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,’ 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, 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.
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 subsections.
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.
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:
- A programming model is used to map algorithms onto software.
- An execution model to understand how software executes.
- 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
- Execution Model: Logical (non-hardware-native) circuits
- Hardware model
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 that 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