Feynman Meets Turing: The Infeasibility of Digital Compilers for Gate-Based Quantum Computing

• Main Authors: Bock, Yannik N., Boche, Holger, del Toro, Zoe Garcia, Fitzek, Frank H. P.
• Format: Conference Proceeding
• Language: English
• Subjects: Accuracy; Computational modeling; Digital computers; Quantum algorithm; quantum compiler; Quantum computing; Quantum mechanics; Solovay-Kitaev theorem; Turing machine; Turing machines
• ISSN: 1938-1883
• DOI: 10.1109/ICC51166.2024.10622486

We consider the problem of computing gate-circuit approximations of quantum algorithms, i.e., unitary operators, from the perspective of computable (effective) analysis. The scientific community thinks the Solovay-Kitaev theorem a mile-stone in quantum compiling - the task of computing gate-circuit approximations - because it proves the existence of efficient quantum compilers in an analytic sense. However, since we cannot represent unitary operators in a mere analytical way on digital computers, contemporary digital implementations of quantum compiling resort to heuristic numerics and remain below the computational performance engineers hope to realize using the result of Solovay and Kitaev. This paper discusses quantum compiling within a framework of computable analysis, establishing a concept of computable unitary operators for digital computing based on the theory of Turing machines. Particularly, we prove that digital quantum compiling is uncomputable due to the underlying algebraic structure. Finally, we discuss several implications of our findings for heuristic digital implementations of quantum compiling, hinting toward possible research directions to thoroughly understand the relevant bottlenecks.