An in-depth review of algorithms for noisy quantum computers

In Reviews of Modern Physics, CQT researchers and their collaborators identify novel qubit design, material discovery for hardware and error mitigation algorithms among important research directions to harness the most computational power from noisy, intermediate-scale quantum (NISQ) computing devices. Image: Omelchenko/Shutterstock.com

Researchers from Singapore, Canada, the United Kingdom and the United States teamed up to survey over 800 papers about algorithms for noisy, intermediate-scale quantum (NISQ) computing devices. The 14 co-authors have distilled their work into a 91-page, comprehensive review published on 15 February in Reviews of Modern Physics.

NISQ algorithms are designed to work in the presence of noise and without a large number of qubits. This makes them suitable for current quantum computers which are small, made up of only tens or hundreds of qubits, and error prone. NISQ algorithms are being developed for applications in areas such as machine learning, quantum chemistry, and combinatorial optimisation.

The idea to prepare a review article came from the team of CQT Principal Investigator Kwek Leong Chuan. Kwek says, “The group has been fairly active in NISQ algorithms. The project arose from a group discussion and we decided to join forces with an alumnus, Thi Ha Kyaw, currently employed in the University of Toronto under Alán Aspuru-Guzik’s group.”

That group is known for developing quantum computing algorithms for applications in the physical sciences such as the simulation of molecules and materials. Thi Ha and Alán joined the project, along with other collaborators in Toronto and around the world.

At CQT, Kishor Bharti, who was then a joint PhD student with Kwek and Principal Investigator Vlatko Vedral, drove the work. He is now a Postdoctoral Fellow at the University of Maryland. Mok Wai-Keong, an undergraduate student from the NUS Department of Physics, contributed to the work as part of his Final Year Project with Kwek. CQT PhD graduates Tobias Haug, now at Imperial College London, UK, and Hermanni Heimonen, now employed at the quantum computing startup IQM in Finland, are also co-authors on the paper.

The co-authors held many meetings and brainstorming sessions to go through the details of the review. “It was a massive collaboration,” says CQT alumnus Kishor, who shares first authorship of the work with Alba Cervera-Lierta and Thi Ha in Toronto. “Many algorithms are being developed and it is difficult to keep pace with the field, which is exploding. This review is like an encyclopaedia for the NISQ era, a one-stop place for the work of many people.”

The review aims to provide a compilation of the available algorithms suited for the NISQ era and which could deliver results in the near-term. One section is devoted to variational quantum algorithms, which make up most of the current NISQ algorithms. Variational quantum algorithms use a hybrid quantum-classical approach. The classically difficult part of a computation is delegated to the quantum computer while the rest is performed on a classical computer. Other sections cover approaches such as quantum annealing and boson sampling.

The review also gives perspectives on potential future developments given the progress in quantum hardware.

Recent milestones in experimental hardware include separate claims of quantum advantage by Google in 2019 and by scientists in China in 2020. Both built quantum computers using different technologies that performed in minutes a specifically designed calculation that would take the world’s best supercomputers thousands of years to complete.

A major goal now is to demonstrate quantum advantage for useful problems. In the review, the researchers write that advances on three fronts are necessary. Those are hardware developments, such as novel qubit design and material discovery; designing algorithms to suit the device hardware and algorithms for error mitigation; and lastly, identifying applications suited for NISQ devices, which can be done with closer collaboration with experts in industrial fields.