Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Quantum Engineering

Feynman Meets Turing: Computability Aspects of Exact Circuit Synthesis, Gate Efficiency, and the Spectral Gap Conjecture

Yannik N. Bock, Holger Boche, Frank H. P. Fitzek

Published Nov 24, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1109/tqe.2025.3636049

Related papers

Feynman Meets Turing: Computability Aspects of Quantum Compiling Revisited

Yannik N. Bock, Holger Boche, Zoe Garcia del Toro +1 more

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.

IEEE Transactions on Computers•Oct 28, 2025•3 citations

Computability of Matrix Functions and Compiling of Matrix Problems on Quantum Computers

Holger Boche, Adalbert Fono, Gitta Kutyniok B

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]

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

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

Yannik N. Bock, Holger Boche, Zoe Garcia del Toro +1 more

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.

International Conference on Communications•Jun 9, 2024•4 citations

Feynman Meets Turing: The Uncomputability of Quantum Gate-Circuit Emulation and Concatenation

Yannik N. Bock, Holger Boche, Zoe Garcia del Toro +1 more

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•4 citations

Approximate Quantum Circuit Synthesis for Diagonal Unitary

Wenqi Zhang, Jinyang Liu, Zixiang Zhou +1 more

The quantum circuit synthesis problem bridges quantum algorithm design and quantum hardware implementation in the Noisy Intermediate-Scale Quantum (NISQ) era. In quantum circuit synthesis problems, diagonal unitary synthesis plays a crucial role due to its fundamental and versatile nature. Meanwhile, experimental results have shown that moderately approximating the original algorithm to conserve quantum resources can improve the fidelity of algorithms during quantum execution. Building on this insight, we propose a quantum circuit synthesis algorithm to design diagonal unitary implementations based on specified quantum resource limits. Our algorithm can synthesize diagonal unitary for quantum circuits with up to 15 qubits on an ordinary laptop. In algorithm efficiency, synthesizing an n-qubit unitary matrix with an exact algorithm requires $2^n$ CNOT gates as a baseline. Within the algorithm error $\varepsilon $ range of interest (0\%-12\%), our algorithm achieves a $3.2\varepsilon $ reduction in CNOT gates on average. In runtime, the algorithm efficiently performs, synthesizing 12-qubit diagonal unitary in an average of 6.57 seconds and 15-qubit in approximately 561.71 seconds.

arXiv:2412.01869•Dec 2, 2024•0 citations

Convergence efficiency of quantum gates and circuits

Linghang Kong, Zimu Li, Zi-Wen Liu

We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing $t$-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients $\left(\fracπ{4}-\frac{1}{8}\arccos(\frac{1}{5}),\fracπ{8},\frac{1}{8}\arccos(\frac{1}{5})\right)$ (which we call $χ$ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.

arXiv:2411.04898•Nov 7, 2024•10 citations
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 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 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]
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 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.
The quantum circuit synthesis problem bridges quantum algorithm design and quantum hardware implementation in the Noisy Intermediate-Scale Quantum (NISQ) era. In quantum circuit synthesis problems, diagonal unitary synthesis plays a crucial role due to its fundamental and versatile nature. Meanwhile, experimental results have shown that moderately approximating the original algorithm to conserve quantum resources can improve the fidelity of algorithms during quantum execution. Building on this insight, we propose a quantum circuit synthesis algorithm to design diagonal unitary implementations based on specified quantum resource limits. Our algorithm can synthesize diagonal unitary for quantum circuits with up to 15 qubits on an ordinary laptop. In algorithm efficiency, synthesizing an n-qubit unitary matrix with an exact algorithm requires 2n2^n2n CNOT gates as a baseline. Within the algorithm error $\varepsilon $ range of interest (0\%-12\%), our algorithm achieves a $3.2\varepsilon $ reduction in CNOT gates on average. In runtime, the algorithm efficiently performs, synthesizing 12-qubit diagonal unitary in an average of 6.57 seconds and 15-qubit in approximately 561.71 seconds.
We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing ttt-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients (π4−18arccos⁡(15),π8,18arccos⁡(15))\left(\fracπ{4}-\frac{1}{8}\arccos(\frac{1}{5}),\fracπ{8},\frac{1}{8}\arccos(\frac{1}{5})\right)(4π​−81​arccos(51​),8π​,81​arccos(51​)) (which we call χχχ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.