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.

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

References in corpus (32)

• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Quantum state tomography via compressed sensing
• Quantum random access memory
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Efficient quantum state tomography
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Quantum computers can search arbitrarily large databases by a single query
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Architectures for a quantum random access memory
• Preconditioned quantum linear system algorithm
• Amplitude estimation without phase estimation
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Universal resources for measurement-based quantum computation
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Quantum Algorithm for Simulating the Wave Equation
• Quantum State Tomography via Linear Regression Estimation
• Circuit-Based Quantum Random Access Memory for Classical Data
• Generation of cluster states
• Quantum advantage with noisy shallow circuits in 3D
• Quantum singular value decomposition of non-sparse low-rank matrices
• Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
• Using concatenated quantum codes for universal fault-tolerant quantum gates
• Quantum algorithm for non-homogeneous linear partial differential equations
• A quantum algorithm to solve nonlinear differential equations
• Electronic structure with direct diagonalization on a D-Wave quantum annealer