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

Abstract

In this work, we are interested in the detailed analysis of complexity aspects of both time and space that arises from the implementation of a quantum algorithm on a quantum based hardware. In particular, some steps of the implementation, as state preparation and readout processes, in most of the cases can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations, from state preparation to the number of measurements needed to obtain good statistics from the final states of the quantum system, in order to assess the overall complexity of the processes.

Some reviews in the main text have been made since the first version. 11 pages, 2 figures, 1 table. Comments are welcome

References in corpus (10)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Efficient quantum state tomography
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Architectures for a quantum random access memory
• Universal resources for measurement-based quantum computation
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Circuit-Based Quantum Random Access Memory for Classical Data
• A quantum algorithm to solve nonlinear differential equations