Matrix inversion polynomials for the quantum singular value transformation

Quantum singular value transformation (QSVT) is a meta quantum algorithm, which allows to apply a polynomial transformation to a matrix. The matrix A is embedded in the quantum circuit as a so-called block-encoding unitary, i.e. a unitary with top-left block equal to A/α, with some subnormalisation α>0. Then QSVT can implement p(A), and the required circuit length (query complexity to the block encoding of A) is the degree of the polynomial d. The output of QSVT is again a block-encoding, of the matrix p(A). How the result will be extracted from the quantum computer depends on the next requirements: Individual matrix elements can be probabalistically sampled. If follow-up calculations are required, they can be performed on the quantum computer within the block-encoding framework. Matrix-Vector multiplications can be performed by preparing the vector as an initial quantum state.

In order to use QSVT for quantum matrix inversion, a polynomial p(x) that approximates 1/x is required. The specifics of allowable error and approximation region depend on user requirements and the condition number of the block encoding. In this work, we find the polynomial with provably lowest degree d.

The QSVT (quantum singular value transformation) algorithm together with the block-encoding framework is well-known and has been described elsewhere. However, these topics are essential for many quantum algorithms in the broad linear-algebra area, such that this talk will give an introduction to these topics for the benefit of audience members unfamiliar with these tools.

Specifically for matrix inversion, we seek the odd polynomial p(x) with lowest degree d that approximates 1/x in the region [1/kappa, 1], where kappa is the condition number (smallest singular value) of the block-encoding, and has desired error ||p(x) - 1/x|| <= epsilon in that region. While this optimal polynomial had previously been computed by the Remez approximation method, this involves very heavy computation.

We solve this problem by giving a proof for an explicit form of the optimal polynomial. We also provide a fast python code based on a recurrence relation to compute the coefficients of p(x) in the Chebyshev basis, as required for phase factor finding algorithms for QSVT. We numerically compare our polynomial with prior polynomials from the literature and thereby confirm the optimality.

The query complexity of the QSVT circuit is d, where d is the degree of our polynomial. We derive an explicit and exact formula for the degree d based on condition number κ and error ε. Asymptotically, d ~ κ log(κ/ε), with prefactor 1.

This can give an exponential improvement to classical matrix inversion, which scales as ca. N^3 for a NxN dimensional matrix. (N=2^n, where n is the number of system qubits required for the matrix.)

However, the the polynomial degree merely gives the query complexity to the block encoding. In order to have a practical quantum advantage, it is paramount that the matrix have sufficient structure for an efficient block encoding circuit to exist.

Another important factor is any required downscaling of the optimal polynomial due to the normalisation requirement of unitary optimisations. This is studied numerically in the paper, and it is seen that the optimal polynomial outperform the other polynomials considered.