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 investigate the feasibility of computing quantum gate-circuit emulation (QGCE) and quantum gate-circuit concatenation (QGCC) on digital hardware. QGCE serves the purpose of rewriting gate circuits comprised of gates from a varying input gate set to gate circuits formed of gates from a fixed target gate set. Analogously, QGCC serves 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 assumed an easy task for the digital computers controlling the quantum hardware. Arguably, this belief is due to analogical reasoning: The classical Boolean equivalents of QGCE and QGCC are natively computable on digital hardware. In the present paper, we present two insights in this regard: Upon applying a rigorous theory of computability, QGCE and QGCC turn out to be uncomputable on digital hardware. The results remain valid when we restrict the set of feasible inputs for the relevant functions to one parameter families of fixed gate sets. Our results underline the possibility that several ideas from quantum-computing theory may require a rethinking to become feasible for practical implementation.

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.

In-Network Computing has brought computing and communication together at every communication node in the digital world, this work lays the foundations for doing the same in the quantum world, improving communication properties in the process - a combination of quantum computing and quantum communication. Full network softwarization, in-network intelligence, and massive connectivity will create an unprecedented demand for computing resources in the digital world. Accordingly, the scientific and industrial communities have begun to explore technologies such as quantum computing and have made significant efforts to demonstrate an algorithmic advantage for various problems. However, practical quantum computers are resource-inefficient and difficult to build. This article introduces a new communication paradigm leading to the concept of quantum in-network computing in the context of entanglement-assisted communication and computing for inherent distributed resilience and sensing. We review the fundamentals of digital hardware as characterized by Turing’s computability theory and demonstrate their relevance to mathematically rigorous characterizations of gate-based quantum computing. We then provide such a characterization using methods from effective analysis, leading to significant results that reveal the inherent theoretical limitations of universal gate-based quantum computers. These results support our assessment that gate-based quantum in-network computing is only possible through specialized, non-universal solutions that are seamlessly integrated with high-performance digital computing.

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.

We consider the task of converting different digital descriptions of analog bandlimited signals and systems into each other. Albeit fundamental, the problem of finding the proper digital description of analog information is crucial to digital twinning. The latter is an emerging concept in the field of digital data processing that is regularly mentioned as key approach in the optimization of future communication technologies like 6G. We prove that quantities such as the peak-to-average power ratio and the bounded-input/bounded-output norm, which determine the behavior of the real-world analog system, cannot generally be determined from the system's digital twin, depending on which of the above-mentioned descriptions is chosen. As a main result, we introduce a new digital description of analog signals and systems and prove it to be algorithmically more powerful than the traditional description based on Shannon's sampling approach.

The duality between time- and frequency-domain representations of information-carrying signals is an established cornerstone of information theory. In terms of computability and signal processing, asymptotically-vanishing sequences are well-behaved in the time-domain, since they can be equipped with Banach-Space norms. It is then possible to define computable asymptotically-vanishing sequences, each of which is characterized by an effective global approximation procedure. In this paper, we investigate whether the time-frequency duality preserves these characteristics, i.e., whether the image of asymptotically-vanishing sequences under the Z-Transform yields a set of computationally well-behaved functions. In particular, we classify the associated radius of convergence into the arithmetical hierarchy of definable numbers by Zheng and Weihrauch, and, as a corollary, present that it may attain non-computable values. We then proceed to investigate the computability of upper and lower bounds on the radius of convergence, as well as several related decidability problems. Lastly, we subsume our insights into a collection of contemporary results on the fundamental limits of numerical techniques in signal processing and information theory.

The bandwidth of a signal is an important physical property that is of relevance in many signal- and information-theoretic applications. In this paper we study questions related to the computability of the bandwidth of computable bandlimited signals. To this end we employ the concept of Turing computability, which exactly describes what is theoretically feasible and can be computed on a digital computer. Recently, it has been shown that there exist computable bandlimited signals with finite energy, the actual bandwidth of which is not a computable number, and hence cannot be computed on a digital computer. In this work, we consider the most general class of band-limited signals, together with different computable descriptions thereof. Among other things, our analysis includes a characterization of the arithmetic complexity of the bandwidth of such signals and yields a negative answer to the question of whether it is at least possible to compute non-trivial upper or lower bounds for the bandwidth of a bandlimited signal. Furthermore, we relate the problem of bandwidth computation to the theory of oracle machines. In particular, we consider halting and totality oracles, which belong to the most frequently investigated oracle machines in the theory of computation.

We consider a decision problem associated to the task of estimating the state of a dynamic plant remotely via a noisy communication channel: given the characteristics of some unstable linear time-invariant (LTI) plant and some discrete memoryless channel (DMC), does there exist an encoder/decoder pair that allows for the remote tracking of the plant’s state with bounded error? Questions of this kind are becoming increasingly important in communication technologies, since future communication networks are expected to incorporate distributed control and decision-making. Analytically, this problem has been shown to involve the zero-error capacity of the DMC. Starting from this result, we approach the problem from the view of theoretical computer science, with an explicit treatment of the underlying machine Model. In particular, we prove that for every pair of a finite channel input alphabet and a finite channel output alphabet, there exists a Blum-Shub-Smale (BSS) algorithm that computes the zero-error capacity in dependence of the channel matrix. Based on this, we devise a BSS algorithm that solves the above decision problem given the plant’s and DMC’s characteristics. BSS machines are a promising candidate for a universal model of real number processing hardware, comparable to the Turing machine in the digital domain. Recently, we observe an increased interest in research and development towards real number and/or analog computing hardware, usually referred to by the term "neuromorphic computing".

The bandwidth of a signal is an important physical property that is of relevance in many signal processing applications. In this paper we study questions related to the computability of the bandwidth of bandlimited signals. To this end we employ the concept of Turing computability, which exactly describes what is theoretically feasible and can be computed on a digital machine. Recently, it has been shown that there exist bandlimited signals, the actual bandwidth of which cannot be algorithmically determined, i.e., computed on a digital machine. In this work, we consider the most general class of bandlimited signals and analyze whether it is at least possible to compute nontrivial upper or lower bounds for the actual bandwidth of its members. We show that this is not possible in general.

Fekete's lemma is a well known assertion that states the existence of limit values of superadditive sequences. In information theory, superadditivity of rate functions occurs in a variety of channel models, making Fekete's lemma essential to the corresponding capacity problems. We analyze Fekete's lemma with respect to effective convergence and computability and show that Fekete's lemma exhibits no constructive derivation. In particular, we devise a superadditive, computable sequence of rational numbers so that the associated limit value in the sense of Fekete's lemma is not a computable number. We further characterize the requirements for effective convergence and investigate the speed of convergence, as proposed by Rudolf Ahlswede in his 2006 Shannon lecture.