We consider a formalism ofquantum compiler functions– functions that map unitary matrices to corresponding gate-circuit approximations – and prove the infeasibility of digitally computing such functions. Since the gate-circuit model of quantum computing emerged, much research has been conducted to find algorithmic solutions to thequantum compiler problem. The renownedSolovay-Kitaev theoremproves the existence of quantum compiler functions that provide low-complexity gatecircuit approximations to arbitrary unitary matrices, which is indispensable for the practical feasibility of gate-based quantum computing. However, the mere existence of such functions does not imply theirrealizabilityby means of analgorithm– a constructive procedure executed by aTuring machine. In fact, no algorithm for computing any quantum compiler function is known today. The present article demonstrates that no such algorithm can exist. We prove that no quantum compiler function can satisfyBanach-Mazur computability, which is a formalization of algorithmic feasibility with (mathematically) weak requirements. In consequence, there definitely does not exist a Turing machine that computes any quantum compiler function in the above sense, nor can there exist aconstructive proofof the existence of any such function. Furthermore, we discuss proposed methods of quantum compiling and analyze them in the context of our results.
We consider a formalism ofquantum compiler functions– functions that map unitary matrices to corresponding gate-circuit approximations – and prove the infeasibility of digitally computing such functions. Since the gate-circuit model of quantum computing emerged, much research has been conducted to find algorithmic solutions to thequantum compiler problem. The renownedSolovay-Kitaev theoremproves the existence of quantum compiler functions that provide low-complexity gatecircuit approximations to arbitrary unitary matrices, which is indispensable for the practical feasibility of gate-based quantum computing. However, the mere existence of such functions does not imply theirrealizabilityby means of analgorithm– a constructive procedure executed by aTuring machine. In fact, no algorithm for computing any quantum compiler function is known today. The present article demonstrates that no such algorithm can exist. We prove that no quantum compiler function can satisfyBanach-Mazur computability, which is a formalization of algorithmic feasibility with (mathematically) weak requirements. In consequence, there definitely does not exist a Turing machine that computes any quantum compiler function in the above sense, nor can there exist aconstructive proofof the existence of any such function. Furthermore, we discuss proposed methods of quantum compiling and analyze them in the context of our results.
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.
We consider a formal model of quantum circuit description languages (QCDLs) in which semantically meaningful programs correspond to computable unitary matrices. We show that any semantically universal QCDL -- that is, any QCDL able to describe all computable unitary matrices, which in turn form the set of matrices we can meaningfully represent on digital hardware -- cannot have a semi-decidable set of semantically meaningful descriptions. In particular, no such language admits a compiler that reliably recognizes all valid program descriptions. This result stands in contrast to classical programming languages. While compilation in languages such as C or C++ may itself involve non-terminating computations, the set of semantically meaningful programs remains recursively enumerable, since successful compilation provides a witness of validity. The essential difference lies in the nature of the semantic domains: classical languages describe partial recursive functions, whereas QCDLs describe total unitary operators. Our analysis establishes a fundamental limitation of quantum circuit description languages and highlights a structural distinction between classical and quantum models of computation at the level of formal language theory.
We consider exact quantum circuit synthesis, quantum gate efficiency, and the spectral gap conjecture from the perspective of computable analysis. Circuit synthesis, in both its exact and its approximate variant, is fundamental to the circuit model of quantum computing. As an engineering problem, however, the practical and theoretical aspects of quantum circuit synthesis are far from being fully understood. Particularly, this concerns explicit methods for gate-agnostic circuit synthesis and questions of gate efficiency. More than 20 years ago, Harrow et al. published their famous spectral gap theorem – given a suitable family of quantum gates, it is possible to approximate any unitary transformation by means of a quantum circuit whose length is proportional to the required accuracy's logarithm. Moreover, Harrow et al. suspected that all universal gate families allow for this type of approximation, a hypothesis that became known as the spectral gap conjecture and remains unproven until today. Being an entirely classical task, quantum circuit synthesis must be considered in the context of digital computing – that is, in the context of Turing computability and computable analysis. Using the relevant mathematical framework, we establish no-go results concerning exact quantum circuit synthesis and quantum big-O analysis. Our findings relate to the theory of approximate t-designs, which has recently received notable attention through the literature. Moreover, as follows from our findings, the existence of an algorithm that computes leading big-O coefficients would prove the spectral gap conjecture true within the computable special unitary group.
We investigate the feasibility of computing quantum gate-circuit emulation (QGCE)functions and quantum gate-circuit concatenation (QGCC) functions on digital hardware. QGCE functions serve the purpose of rewriting gate-circuits comprised of gates from a varying (possibly universal) input gate-set to gate-circuits comprised of gates from a fixed target gate set. Analogously, QGCC functions serve the purpose of finding an approximation to the concatenation of two arbitrary elements of a varying list of input gate circuits in terms of another element from the same list. Problems of this kind occur regularly in quantum computing and are often considered an easy task for the digital computers controlling the quantum hardware. However, recent results employing a rigorous mathematical theory of computability indicate that this may not be the case. This paper extends the aforementioned theory, providing two relevant insights: Upon applying a rigorous theory of computability, QGCE functions and QGCC functions turn out to be uncomputable on digital hardware. The results remain valid when we restrict the set of feasible inputs for these functions to one-parameter families of fixed gate sets, which is applicable even to standard one-qubit systems. Our insights underline the possibility that several ideas from the theory of quantum computing may require a rethinking in order to become feasible for practical implementation.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.