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 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 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.
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 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.
Black box representations of functions, by definition, do not provide information on how a function, so represented, is computed. By a ‘circuit’ for the computation of a function we mean a sequence of ‘basic’ gates that implement the function. It can be shown that, given a classical circuit for the Boolean function https://www.w3.org/1998/Math/MathML" display="inline"> f ^ https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003264569/7139ce19-0d58-4a0c-820f-b76fb033e438/content/math18_1.tif "/> , there is a quantum circuit of equal ‘efficiency’ for the implementation of the unitary operator https://www.w3.org/1998/Math/MathML" display="inline"> U f ^ https://www.w3.org/1999/xlink" xlink:href=" https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003264569/7139ce19-0d58-4a0c-820f-b76fb033e438/content/math18_2.tif "/> and hence the quantum computation of f . In this chapter we consider examples of invertible digital functions and their evaluation using basic invertible Boolean gates; specifically the Toffoli and Feynman gates T D and F D . We recall that the Toffoli gate is complete for invertible digital computation, however, the inclusion of the Feynman gate, F D , simplifies the circuits. We proceed by example to demonstrate the process and consequential side-effects of such implementations and their quantum emulations. It is seen that the cost of using only Toffoli gates is that additional input bits/qubits may be required, and the computation of intermediate results (usually referred to as garbage or junk) may be necessary. We also consider a general circuit for re-setting registers containing ‘junk’, this is helpful to avoid problems with downstream computation.
Quantum computation was proposed as an alternate computing process in the late-20th century, when classical computing models faced limitation in solving quantum mechanical problems. Major breakthroughs came in the 1990s, when quantum algorithms for integer factoring and black-box searching were invented that are faster than the best classical algorithms known even today. In this thesis, we look at quantum circuits with limited depth and size and analyse their power and limitations.
Computer Science is about the study of computational problems, many of which are motivated by real-world applications. We are interested as much in an actual method to solve a problem as in its unsolvability. In computational complexity theory we separate out the actual problem from the computing apparatus (e.g. a Turing machine, an AND-OR circuit) and analyse the hardness of the computation, due both to the intrinsic complexity of the problem and to the underlying model.
In this thesis, we consider quantum circuits built with a universal set of gates and show that non-constant depth is required to compute a particular function (parity) and other similar functions. The parity function, extensively studied previously, was shown to take non-constant depth for classical circuits too, thus providing an evidence of an inherent hardness in the function itself. On the other hand we show that the quantum circuit model is rich enough to build a universal circuit (one circuit that can simulate all circuits) that has roughly the same depth or size as the simulated circuit. We also consider a fault model in which some of the inputs to a gate might not be connected to the gate's output. We ask if we can detect the faulty inputs by testing the gate on different inputs. Our goal is to minimise the number of tests. We show that this is very hard for general gates but for certain gates it can be provably easier to detect faulty inputs. We even show that quantum algorithms can provably outperform classical algorithms for these gates. These results give us a sense of wherein lies the power of quantum computation and quantum circuits in particular.