Quantum algorithms for basic numerical linear algebraic tasks have proven essential for translating diverse problems to a unified quantum computational context. Many of these tasks—for example, applying a polynomial function to the spectrum of a matrix embedded in a unitary process (a so-called block encoding), or taking linear combinations of block encodings—are well addressed by techniques such as quantum singular value transformation (QSVT) or linear combination of unitaries (LCU). However, there exist useful matrix transforms whose realization by existing quantum algorithms is unclear or inefficient.

In this work, we construct improved quantum algorithms for some of these transforms, the simplest of which is a polynomial function applied element-wise. We show that the space required to compute quantum element-wise transforms (QEWTs) can be reduced exponentially in the degree of the applied function compared with prior work, and we identify and rectify errors in previous constructions. Consequently, in addition to building a new family of space-and query-efficient quantum algorithms for common matrix transforms, we establish a firm foundation for the theory of QEWTs, bringing their resource requirements in line with widely applied block-encoding-based quantum algorithms. We present our algorithms alongside applications to machine learning, simulation, and signal processing.