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

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

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•0 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

Algorithms and Spectral Gaps for Quantum Problems

Zachary Stier

This dissertation is concerned with a variety of problems in quantum computing and the spectral theory of quantum-mechanical channels and Hamiltonians. We begin with the problem of quantum gate synthesis. The challenge is to find a fixed, finite set S of quantum gates such that, given a quantum circuit component U acting on n qubits and target precision ε, there is a short, efficiently computable composition of gates from S that approximates U to precision ε. This problem has already led to a rich literature in the case n=1 with deep connections to modern number theory. In this dissertation we present the state-of-the-art algorithm for a single qubit, achieving length 7 log (1/ε). The techniques used include the lattice structure of certain dense subgroups of PU(2) and Lenstra's algorithm for integer programming in convex domains. The next topic considered is scientific computing algorithms intended to run on a quantum computer. Specifically, we study a framework for computing functions of normal matrices using a quantum computer, with the objective of controlling the ancilla overhead, probability of success, and end precision. This arises as a special case of the multivariate quantum eigenvalue transform, for computing function of multiple commuting Hermitian matrices. The techniques applied include approximation of regular functions by low-degree polynomials and modern quantum primitives like quantum signal processing and linear combinations of unitaries. The third component is a spectral gap comparison result for Davies generators, a class of Lindbladians used for Gibbs state preparation and which are a well-studied example of quantum Markov dynamics, and which contain a canonical classical Markov chain. The main result shows that if the spectrum of the Hamiltonian driving the dynamics is free of long arithmetic progressions, then the spectral gaps of the quantum and classical Markov chains are comparable. Thus, classical techniques may be leveraged to control the behavior of the quantum dynamics. The proof is based on transferring any "off-diagonal" eigenvector of the Davies generator to an observable which commutes with the Hamiltonian and has a comparable Lindbladian Rayleigh quotient. Finally, we study the infimum of the spectrum, or ground state energy, of a discrete Schrödinger operator on the scaled integer grid in n dimensions, parameterized by a nonnegative potential V and a small frequency parameter θ. We relate this ground state energy to that of a corresponding continuous semiclassical Schrödinger operator on the full n-dimensional space with parameter θ, arising from the same choice of potential, and show that these quantities are equal up to vanishing factors depending on the regularity of V. The proofs are elementary and rely on sampling and interpolation to map low-energy functions for the discrete operator on the scaled grid to low-energy functions for the continuous operator on the full space, and vice versa. Coauthors on these works were J. Basso, T. R. Blackman, Y. Borns-Weil, I. Detherage, S. Ganguly, N. Srivastava, T. Saffat, A. Sinclair, and T.-D. Vuong.

•May 1, 2026•0 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 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 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.
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.
This dissertation is concerned with a variety of problems in quantum computing and the spectral theory of quantum-mechanical channels and Hamiltonians. We begin with the problem of quantum gate synthesis. The challenge is to find a fixed, finite set S of quantum gates such that, given a quantum circuit component U acting on n qubits and target precision ε, there is a short, efficiently computable composition of gates from S that approximates U to precision ε. This problem has already led to a rich literature in the case n=1 with deep connections to modern number theory. In this dissertation we present the state-of-the-art algorithm for a single qubit, achieving length 7 log (1/ε). The techniques used include the lattice structure of certain dense subgroups of PU(2) and Lenstra's algorithm for integer programming in convex domains. The next topic considered is scientific computing algorithms intended to run on a quantum computer. Specifically, we study a framework for computing functions of normal matrices using a quantum computer, with the objective of controlling the ancilla overhead, probability of success, and end precision. This arises as a special case of the multivariate quantum eigenvalue transform, for computing function of multiple commuting Hermitian matrices. The techniques applied include approximation of regular functions by low-degree polynomials and modern quantum primitives like quantum signal processing and linear combinations of unitaries. The third component is a spectral gap comparison result for Davies generators, a class of Lindbladians used for Gibbs state preparation and which are a well-studied example of quantum Markov dynamics, and which contain a canonical classical Markov chain. The main result shows that if the spectrum of the Hamiltonian driving the dynamics is free of long arithmetic progressions, then the spectral gaps of the quantum and classical Markov chains are comparable. Thus, classical techniques may be leveraged to control the behavior of the quantum dynamics. The proof is based on transferring any "off-diagonal" eigenvector of the Davies generator to an observable which commutes with the Hamiltonian and has a comparable Lindbladian Rayleigh quotient. Finally, we study the infimum of the spectrum, or ground state energy, of a discrete Schrödinger operator on the scaled integer grid in n dimensions, parameterized by a nonnegative potential V and a small frequency parameter θ. We relate this ground state energy to that of a corresponding continuous semiclassical Schrödinger operator on the full n-dimensional space with parameter θ, arising from the same choice of potential, and show that these quantities are equal up to vanishing factors depending on the regularity of V. The proofs are elementary and rely on sampling and interpolation to map low-energy functions for the discrete operator on the scaled grid to low-energy functions for the continuous operator on the full space, and vice versa. Coauthors on these works were J. Basso, T. R. Blackman, Y. Borns-Weil, I. Detherage, S. Ganguly, N. Srivastava, T. Saffat, A. Sinclair, and T.-D. Vuong.