Quantum Algorithm Implementations for Beginners

Abhijith Jayakumar, Adetokunbo Adedoyin, John Ambrosiano, Petr M. Anisimov, William Casper, Gopinath Chennupati, Carleton Coffrin, Hristo N. Djidjev, David Gunter, Satish Karra, Nathan Lemons, Shizeng Lin, Alexander Malyzhenkov, David Mascarenas, Susan M. Mniszewski, Balu Nadiga, Daniel O'Malley, Diane Oyen, Scott Pakin, Lakshman Prasad, Randy Roberts, Phillip Romero, Nandakishore Santhi, Nikolai Sinitsyn, Pieter J. Swart, James G. Wendelberger, Boram Yoon, Richard J. Zamora, Wei Zhu, Stephan J. Eidenbenz, Andreas Bärtschi, Patrick J. Coles, Marc Vuffray, Andrey Y. Lokhov

TL;DR

This paper provides a comprehensive, hands-on introduction to quantum algorithms and their implementation on real quantum hardware, specifically IBM's quantum computers. It aims to bridge the gap between theoretical quantum computing and practical application for computer scientists, physicists, and engineers by detailing 20 algorithms and their experimental results.

What Problem Does This Paper Address?

As quantum computing moves from theoretical curiosity to a tangible technology, there's a growing need to train a new generation of programmers. However, the fundamental differences between classical and quantum programming, coupled with the abstract nature of quantum mechanics, create significant barriers to entry. This paper addresses this by demystifying quantum algorithms and their implementation, making them accessible to a broader audience. It tackles the challenge of translating theoretical algorithms into executable code on current quantum hardware, highlighting the practical considerations and limitations involved.

Methods

The paper offers a self-contained explanation of quantum computing's core concepts, including qubits, superposition, entanglement, and quantum circuits. It then dives into the implementation of 20 distinct quantum algorithms, ranging from foundational ones like Grover's and Shor's to more advanced applications in linear systems, machine learning, and quantum simulation. A key methodological contribution is the detailed account of implementing these algorithms on IBM's quantum computers using the Qiskit SDK. This includes discussions on:

  • Quantum Circuit Design: Explaining how to construct quantum circuits for each algorithm.
  • Hardware Implementation: Detailing the available gate sets, physical gate implementations, and qubit connectivity on IBM's quantum processors.
  • Noise and Error Analysis: Discussing the impact of gate infidelity and decoherence on experimental results and comparing them with simulator outputs.
  • Qiskit Programming: Providing practical examples of how to code and run these algorithms using the Qiskit library.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully demonstrates that many quantum algorithms, previously confined to theoretical discussions, can be implemented and tested on current, albeit noisy, quantum hardware.
  • The Reality of Noise: Experimental results consistently show deviations from ideal simulator outputs, underscoring the significant impact of noise and decoherence on quantum computations. This highlights the critical need for error mitigation and correction strategies.
  • Qiskit as a Practical Tool: The extensive use of Qiskit showcases its utility as a powerful and accessible platform for developing and executing quantum algorithms, making quantum computing more tangible for developers.
  • Algorithm-Specific Challenges: Different algorithms present unique implementation challenges, from constructing complex oracles (e.g., for Bernstein-Vazirani) to managing qubit connectivity and gate depth (e.g., for Shor's algorithm).
  • The Importance of Understanding Hardware: The paper emphasizes that successful implementation requires a deep understanding of the underlying quantum hardware's limitations, such as qubit connectivity and available gates, which often necessitate clever circuit decompositions and optimizations.

Key Results

The paper presents experimental results for 20 quantum algorithms implemented on IBM's quantum computers (primarily the 5-qubit ibmqx4). Key findings include:

  • Grover's Algorithm: Successful implementation and testing on IBM's 5-qubit computer, demonstrating a ~65% success rate for finding the correct answer, with deviations attributed to hardware errors.
  • Bernstein-Vazirani Algorithm: Implementation on 2-bit and 3-bit hidden strings, showing noisy results on hardware compared to simulators, especially for longer circuits.
  • HHL Algorithm: Implementation for a 2x2 system on IBM's 5-qubit computer, with simulator results matching theoretical expectations, but hardware results showing significant deviations.
  • QAOA for MaxCut: Proof-of-concept experiments on ibmqx2, demonstrating that hardware performance can be comparable to simulation, but also highlighting the impact of noise on longer circuits.
  • Quantum State Preparation and Tomography: Experiments revealing significant noise and decoherence in IBM's quantum processors, impacting the fidelity of state preparation and measurement.

Limitations and Future Work

  • Noise and Decoherence: The paper repeatedly highlights that current quantum hardware is noisy, limiting the depth and accuracy of implemented algorithms. This is a major bottleneck for achieving significant quantum advantage.
  • Limited Qubit Count and Connectivity: The small number of qubits and restricted connectivity on current devices (e.g., ibmqx4) necessitate complex circuit decompositions, increasing gate counts and error probabilities.
  • Scalability: Many algorithms, while demonstrated on small instances, face significant challenges in scaling to larger problems due to hardware limitations and increasing error rates.
  • Future Work: The authors suggest that future work should focus on developing more robust error correction and mitigation techniques, exploring more efficient gate decompositions, and leveraging advancements in quantum hardware to tackle larger and more complex problems. The paper also points to the ongoing development of quantum software libraries like Qiskit and the continuous improvement of quantum processors.

Summary updated

Abstract

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims to explain the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM's quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.
BibTeX
@article{jayakumar2022quantum,
  author = {Abhijith Jayakumar and Adetokunbo Adedoyin and John Ambrosiano and Petr M. Anisimov and William Casper and Gopinath Chennupati and Carleton Coffrin and Hristo N. Djidjev and David Gunter and Satish Karra and Nathan Lemons and Shizeng Lin and Alexander Malyzhenkov and David Mascarenas and Susan M. Mniszewski and Balu Nadiga and Daniel O'Malley and Diane Oyen and Scott Pakin and Lakshman Prasad and Randy Roberts and Phillip Romero and Nandakishore Santhi and Nikolai Sinitsyn and Pieter J. Swart and James G. Wendelberger and Boram Yoon and Richard J. Zamora and Wei Zhu and Stephan J. Eidenbenz and Andreas Bärtschi and Patrick J. Coles and Marc Vuffray and Andrey Y. Lokhov},
  title = {{Quantum Algorithm Implementations for Beginners}},
  journal = {ACM Trans. Quantum Comput.},
  year = {2022},
  doi = {10.1145/3517340},
}
Figure