IEEE International Symposium on Information Theory (ISIT)
Computability of Matrix Functions and Compiling of Matrix Problems on Quantum Computers
Holger Boche, Adalbert Fono, Gitta Kutyniok B
Abstract
We study quantum circuit synthesis through the lens of quantum compiler functions, i.e., mappings from unitary matrices to gate-circuit approximations. While the existence of compiler functions yielding low-complexity gate-circuit approximations for arbitrary unitary matrices is well established, their implementation is inherently classical and must therefore be assessed within the framework of digital computation. Digitally computing these functions has recently been shown to be infeasible in terms of Turing computability, i.e., uniform, universally correct, and error-controlled implementations. We strengthen this limitation by proving the non-existence of computable implementations even for restricted and practically relevant sub-tasks. In particular, we establish an infeasibility result for compiler functions based on currently known quantum algorithms for estimating features of solutions to linear systems. Our approach relies on a detailed computability analysis of associated matrix functions—most notably the pseudoinverse and the condition number—within the Turing model. This yields a complete characterization of the computability breakdown and, consequently, of the infeasibility of corresponding universal and computable compiler functions.For a version of this work including all proofs, we refer to [1]