Quantum Computational Complexity of Matrix Functions

PRX Quantum, vol. 7

Abstract

We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function f and a Hermitian matrix A , we compute a matrix element of f ( A ) or a local measurement on f ( A ) | 0 ⟩ ⊗ n , with | 0 ⟩ ⊗ n being an n -qubit reference state vector, in both cases up to additive approximation error. We consider four functions—monomials, Chebyshev polynomials, the time evolution function, and the inverse function—and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm and sparsity), the approximation error, and function-specific parameters. We identify BQP- forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results, we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree poly ( n ) , both problems can be efficiently classically simulated when A has O ( log  n ) nonzero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP- in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity O ( log  n ) . Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.

Authors 5

1. Santiago Cifuentes

   Consejo Nacional de Investigaciones Científicas y Técnicas · Universidad de Buenos Aires · Institute of Astronomy and Space Physics

   Affiliation as printed

   UBA-CONICET

2. Samson Wang

   California Institute of Technology

   Affiliation as printed

   Caltech

3. Thais de Lima Silva

   Technology Innovation Institute

   Affiliation as printed

   Technology Innovation Institute

4. Mario Berta Aachen

   Imperial College London · RWTH Aachen University

   Affiliation as printed

   Imperial College London

   RWTH Aachen University

5. Leandro Aolita

   Technology Innovation Institute

   Affiliation as printed

   Technology Innovation Institute