Some challenges in quantum computing for linear algebra algorithms and data structures

Sep 12 14:00 ₂₀₂₃

Quantum computing aims at addressing computations that are currently intractable by conventional supercomputers but it is also a promising technology for speeding up some existing simulations. However it is commonly accepted that quantum algorithms will be essentially ``hybrid'' with some tasks being executed on the quantum processor while others will remain treated on classical processors (CPU, GPU,...). Among the crucial tasks achieved on classical computers, several require efficient linear algebra algorithms.

The first example concerns the quantum circuit synthesis which is equivalent to the compilation phase in classical computing and consists in transforming a quantum operator, namely a unitary matrix, into an optimized quantum circuit. Our method based on linear algebra factorization minimizes the cost in classical resources required for the synthesis and scales well with the number of qubits.

The second example is related to the implementation of sparse and dense matrices in quantum algorithms. This task is essential if we want to address practical applications with quantum computing. We investigate methods which consist in embedding a given matrix into a larger unitary matrix and then obtaining the resulting quantum circuit. We evaluate the classical and quantum cost of such methods and how it can exploit the sparsity of the initial matrix. Finally we introduce some issues in upcoming quantum-classical programming models and efficient quantum simulations.