# The bitter truth about gate-based quantum algorithms in the NISQ era

@article{Leymann2020TheBT, title={The bitter truth about gate-based quantum algorithms in the NISQ era}, author={Frank Leymann and Johanna Barzen}, journal={arXiv: Quantum Physics}, year={2020} }

Implementing a quantum algorithm on a NISQ device has several challenges that arise from the fact that such devices are noisy and have limited quantum resources. Thus, various factors contributing to the depth and width as well as to the noise of an implementation of an algorithm must be understood in order to assess whether an implementation will execute successfully on a given NISQ device. In this contribution, we discuss these factors and their impact on algorithm implementations. Especially… Expand

#### Figures from this paper

figure 1 figure 2 figure 3 figure 4 figure 5 figure 6 figure 7 figure 8 figure 9 figure 10 figure 11 figure 12 figure 13 figure 14 figure 15 figure 16 figure 17 figure 18 figure 20 figure 21 figure 22 figure 23 figure 24 figure 25 figure 26 figure 27 figure 28 figure 29 figure 30 figure 31 figure 32 figure 33 figure 34 figure 35 figure 36 figure 37 figure 38

#### 36 Citations

Service-Oriented Computing: 14th Symposium and Summer School on Service-Oriented Computing, SummerSOC 2020, Crete, Greece, September 13-19, 2020

- Computer Science
- SummerSOC
- 2020

A system for personalized recommendations as part of a smart IoT-driven tour guide platform that leverages data-streaming technologies for online training and interactive response in coordination with a commercial IoT platform and mobile application. Expand

A Heuristic Method to solve large-scale Integer Linear Programs by combining Branch-and-Price with a Quantum Algorithm

- 2021

Marika Svensson, 2, 3, ∗ Martin Andersson, Mattias Grönkvist, Pontus Vikst̊al, Devdatt Dubhashi, Giulia Ferrini, and Göran Johansson Jeppesen, 411 03 Gothenburg, Sweden Department of Computer… Expand

Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers—How They Work, How They Fail, How to Test Them?

- Computer Science
- 2021 IEEE 39th VLSI Test Symposium (VTS)
- 2021

The promise and challenge of NISQ computing are critically assessed; for instance, variational optimisers are based on intertwining relatively short quantum and classical computations, thus maximizing the chances of success. Expand

Detailed Account of Complexity for Implementation of Quantum Algorithms

- 2021

Fernando R. Cardoso,1 Daniel Yoshio Akamatsu,1 Eduardo I. Duzzioni,2 Alfredo Jaramillo Palma,3 and Celso J. Villas-Boas1 Departamento de Fı́sica, Universidade Federal de São Carlos, 13565-905 São… Expand

Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms

- Physics
- 2021

Fernando R. Cardoso,1 Daniel Yoshio Akamatsu,1 Vivaldo Leiria Campo Junior,1 Eduardo I. Duzzioni,2 Alfredo Jaramillo Palma,3 and Celso J. Villas-Boas1 Departamento de Fı́sica, Universidade Federal de… Expand

An Exploratory Study on the Challenges of Engineering Quantum Applications in the Cloud

- Computer Science
- Q-SET@QCE
- 2021

This work implemented four quantum applications highlighting different scenarios of using quantum software components in cloud applications and analyzed the challenges and limitations encountered during the implementation process and documented the key observations. Expand

Expanding Data Encoding Patterns For Quantum Algorithms

- Computer Science
- 2021 IEEE 18th International Conference on Software Architecture Companion (ICSA-C)
- 2021

To capture knowledge about different encodings, this work presents two data encoding patterns that extend the previous collection of encoding patterns and describes the consequences of a particular data encoding. Expand

TOSCA4QC: Two Modeling Styles for TOSCA to Automate the Deployment and Orchestration of Quantum Applications

- Computer Science
- 2020 IEEE 24th International Enterprise Distributed Object Computing Conference (EDOC)
- 2020

This work proposes TOSCA4QC that introduces two deployment modeling styles based on the Topology and Orchestration Specification for Cloud Applications (TOSCA) standard for automating the deployment and orchestration of quantum applications: SDK-specific modeling style to cover all technical deployment details and SDK-agnostic modeling style supporting common modeling principles. Expand

From Digital Humanities to Quantum Humanities: Potentials and Applications

- Computer Science, Physics
- ArXiv
- 2021

Both the theoretical basis and the tooling support for analyzing the data from the digital humanities project MUSE is described, which includes a data analysis pipeline, containing e.g. various approaches for data preparation, feature engineering, clustering, and classification, supported by quantum computers. Expand

Quantum Software Development Lifecycle

- Computer Science, Physics
- ArXiv
- 2021

The integrated lifecycle serves as a basis for the development and execution of hybrid quantum applications, and identifies the points of connection between the various lifecycles and integrate them into the overall quantum software development lifecycle. Expand

#### References

SHOWING 1-10 OF 114 REFERENCES

Quantum Computing in the NISQ era and beyond

- Computer Science, Physics
- Quantum
- 2018

Noisy Intermediate-Scale Quantum (NISQ) technology will be available in the near future, and the 100-qubit quantum computer will not change the world right away - but it should be regarded as a significant step toward the more powerful quantum technologies of the future. Expand

Quantum circuits for incompletely specified two-qubit operators

- Computer Science, Mathematics
- Quantum Inf. Comput.
- 2005

This work identifies cases in which unitary operators can be implemented using fewer quantum gates than are required for generic completely specified operators, and takes up the practical challenge of satisfying a given specification with the smallest possible circuit. Expand

Optimizing Quantum Programs Against Decoherence: Delaying Qubits into Quantum Superposition

- Computer Science, Physics
- 2019 International Symposium on Theoretical Aspects of Software Engineering (TASE)
- 2019

The experimental results show that QLifeReducer reduces the error rate of a quantum program when executed on IBMQ 5 Tenerife by 11%; and can reduce the longest qubit lifetime as well as average qubit Lifetime by more than 20% on most quantum workloads. Expand

Efficient networks for quantum factoring.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1996

The number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor are estimated. Expand

Validating quantum computers using randomized model circuits

- Physics
- Physical Review A
- 2019

We introduce a single-number metric, quantum volume, that can be measured using a concrete protocol on near-term quantum computers of modest size ($n\ensuremath{\lesssim}50$), and measure it on… Expand

Quantum Algorithm Implementations for Beginners

- Computer Science, Physics
- ArXiv
- 2018

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

QuRE: The Quantum Resource Estimator toolbox

- Mathematics, Computer Science
- 2013 IEEE 31st International Conference on Computer Design (ICCD)
- 2013

The tradeoff between concatenated and surface error correction coding techniques is investigated, demonstrating the existence of a crossover point for the Ground State Estimation Algorithm. Expand

Practical Quantum Error Mitigation for Near-Future Applications

- Computer Science, Physics
- Physical Review X
- 2018

This work describes a protocol for systematically measuring the effect of errors so as to design efficient QEM circuits and introduces an exponential variant of the extrapolation method to enable practical implementation of these ideas. Expand

Circuit-Based Quantum Random Access Memory for Classical Data

- Computer Science, Physics
- Scientific Reports
- 2019

This work presents a circuit-based flip-flop quantum random access memory to construct a quantum database of classical information in a systematic and flexible way and presents a procedure to convert classical training data for a quantum supervised learning algorithm to a quantum state. Expand

Error Mitigation for Short-Depth Quantum Circuits.

- Computer Science, Physics
- Physical review letters
- 2017

Two schemes are presented that mitigate the effect of errors and decoherence in short-depth quantum circuits by resampling randomized circuits according to a quasiprobability distribution. Expand