"How to measure a quantum algorithm: complexities and models"

Abstract

Currently, quantum algorithm developments are growing, and it is becoming essential to determine how efficient and feasible a quantum algorithm is. Although there is continuous development of quantum hardware, it is important to remember that we are still in the NISQ (Noisy Intermediate-Scale Quantum) era, which limits accessibility to this technology and imposes restrictions on time and the number of qubits. Furthermore, the coexistence of multiple computing paradigms and quantum architectures can lead to ambiguities when proposing quantum algorithms, making it essential to analyze their complexity. The adiabatic quantum computing (AQC) model and the quantum gate (QG) model, being the most widely used models, were considered in this study. The first approach to analyzing quantum algorithmic complexity involves counting the number of quantum gates employed by the algorithm in the QG model. However, the measurement of quantum algorithmic complexity extends beyond the QG framework. This gate-counting metric does not apply to the AQC paradigm, since adiabatic algorithms rely on continuous Hamiltonian evolution rather than discrete quantum gates. The purpose of this study is to explore the theoretical developments concerning quantum complexity, based on the approach presented in 1997 by Bernstein and Vazirani and the demonstration of the equivalence between the QG and AQC models presented in 2004 by Aharonov et al. As a result of this research, our proposal is illustrated using Grover’s search algorithm and Deutsch’s algorithm. Finally, a method is presented to measure the complexity of a quantum algorithm in an approximate manner, which enables us to visualize its scope while disregarding the influence that the chosen quantum model may have. Likewise, it is emphasized that the algorithm’s objective will be crucial when analyzing its complexity.