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

arXiv:1902.04764

Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count

Cupjin Huang, Michael Newman, Márió Szegedy

Published Feb 13, 2019• 2 citations
arXivHTMLPDF

Abstract

We investigate Clifford+$T$ quantum circuits with a small number of $T$-gates. Using the sparsification lemma, we identify time complexity lower bounds in terms of $T$-gate count below which a strong simulator would improve on the state-of-the-art $3$-SAT solving.

DOI
10.48550/arxiv.1902.04764

Related papers

Explicit Lower Bounds on Strong Quantum Simulation

Cupjin Huang, Michael Newman, Márió Szegedy

We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.

arXiv:1804.10368•IEEE Transactions on Information Theory•Jun 23, 2020•30 citations

Lower T-count with faster algorithms

Vivien Vandaele

Among the cost metrics characterizing a quantum circuit, the T -count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the T -count reduction problem by proposing efficient T -count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best T -count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of T gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal T -count than the state of the art on most quantum circuits evaluated. We also prove that the number of T gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of n qubits is upper bounded by n ( n + 1 ) / 2 + 1 , which improves on the worst-case T -count of existing optimization algorithms. From this we derive an upper bound of ( n + 1 ) ( n + 2 h ) / 2 + 1 for the number of T gates in a Clifford + T circuit where h is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last T gate of the circuit.

arXiv:2407.08695•Quantum•Sep 16, 2025•4 citations

The Parameterized Complexity of Quantum Verification

Srinivasan Arunachalam, Sergey B. Bravyi, Chinmay Nirkhe +1 more

We initiate the study of parameterized complexity of $\textsf{QMA}$ problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + $t$ $T$-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most $t$ qubits (independent of the system size). Furthermore, we derive new lower bounds on the $T$-count of circuit satisfiability instances and the $T$-count of the $W$-state assuming the classical exponential time hypothesis ($\textsf{ETH}$). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.

arXiv:2202.08119•Leibniz international proceedings in informatics•Jan 1, 2022•3 citations

Clifford recompilation for faster classical simulation of quantum circuits

Hammam Qassim, Joel J. Wallman, Joseph Emerson

Simulating quantum circuits classically is an important area of research in quantum information, with applications in computational complexity and validation of quantum devices. One of the state-of-the-art simulators, that of Bravyi et al, utilizes a randomized sparsification technique to approximate the output state of a quantum circuit by a stabilizer sum with a reduced number of terms. In this paper, we describe an improved Monte Carlo algorithm for performing randomized sparsification. This algorithm reduces the runtime of computing the approximate state by the factor ℓ/m , where ℓ and m are respectively the total and non-Clifford gate counts. The main technique is a circuit recompilation routine based on manipulating exponentiated Pauli operators. The recompilation routine also facilitates numerical search for Clifford decompositions of products of non-Clifford gates, which can further reduce the runtime in certain cases by reducing the 1-norm of the vector of expansion, ‖a‖1 . It may additionally lead to a framework for optimizing circuit implementations over a gate-set, reducing the overhead for state-injection in fault-tolerant implementations. We provide a concise exposition of randomized sparsification, and describe how to use it to estimate circuit amplitudes in a way which can be generalized to a broader class of gates and states. This latter method can be used to obtain additive error estimates of circuit probabilities with a faster runtime than the full techniques of Bravyi et al. Such estimates are useful for validating near-term quantum devices provided that the target probability is not exponentially small.

arXiv:1902.02359•Quantum•Aug 5, 2019•15 citations

An algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.

arXiv:1308.4134•Aug 19, 2013•32 citations

An algorithm for the T-countAn algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and $T$ gates. In this context the $T$ gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an $n$-qubit unitary $U$ we are interested in computing a circuit that implements it using the minimum possible number of $T$ gates (called the $T$-count of $U$). A related task is to decide if the $T$-count of $U$ is less than or equal to $m$; we consider this problem as a function of $N=2^n$ and $m$. We provide a classical algorithm which solves it using time and space both upper bounded as $\mathcal{O}(N^m \text{poly}(m,N))$. We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 $T$ gates. This implies that the known 7 $T$ gate circuits for these gates are $T$-optimal. We also provide a simple expression for the $T$-count of single-qubit unitaries.

Quantum Information and Computation•Nov 1, 2014•65 citations
Explicit lower bounds on strong simulation of quantum circuits in terms of TTT-gate count
We investigate Clifford+TTT quantum circuits with a small number of TTT-gates. Using the sparsification lemma, we identify time complexity lower bounds in terms of TTT-gate count below which a strong simulator would improve on the state-of-the-art 333-SAT solving.
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.
Among the cost metrics characterizing a quantum circuit, the T -count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the T -count reduction problem by proposing efficient T -count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best T -count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of T gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal T -count than the state of the art on most quantum circuits evaluated. We also prove that the number of T gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of n qubits is upper bounded by n ( n + 1 ) / 2 + 1 , which improves on the worst-case T -count of existing optimization algorithms. From this we derive an upper bound of ( n + 1 ) ( n + 2 h ) / 2 + 1 for the number of T gates in a Clifford + T circuit where h is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last T gate of the circuit.
We initiate the study of parameterized complexity of QMA\textsf{QMA}QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + ttt TTT-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most ttt qubits (independent of the system size). Furthermore, we derive new lower bounds on the TTT-count of circuit satisfiability instances and the TTT-count of the WWW-state assuming the classical exponential time hypothesis (ETH\textsf{ETH}ETH). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.
Simulating quantum circuits classically is an important area of research in quantum information, with applications in computational complexity and validation of quantum devices. One of the state-of-the-art simulators, that of Bravyi et al, utilizes a randomized sparsification technique to approximate the output state of a quantum circuit by a stabilizer sum with a reduced number of terms. In this paper, we describe an improved Monte Carlo algorithm for performing randomized sparsification. This algorithm reduces the runtime of computing the approximate state by the factor ℓ/m , where ℓ and m are respectively the total and non-Clifford gate counts. The main technique is a circuit recompilation routine based on manipulating exponentiated Pauli operators. The recompilation routine also facilitates numerical search for Clifford decompositions of products of non-Clifford gates, which can further reduce the runtime in certain cases by reducing the 1-norm of the vector of expansion, ‖a‖1 . It may additionally lead to a framework for optimizing circuit implementations over a gate-set, reducing the overhead for state-injection in fault-tolerant implementations. We provide a concise exposition of randomized sparsification, and describe how to use it to estimate circuit amplitudes in a way which can be generalized to a broader class of gates and states. This latter method can be used to obtain additive error estimates of circuit probabilities with a faster runtime than the full techniques of Bravyi et al. Such estimates are useful for validating near-term quantum devices provided that the target probability is not exponentially small.
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
We consider quantum circuits composed of Clifford and TTT gates. In this context the TTT gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an nnn-qubit unitary UUU we are interested in computing a circuit that implements it using the minimum possible number of TTT gates (called the TTT-count of UUU). A related task is to decide if the TTT-count of UUU is less than or equal to mmm; we consider this problem as a function of N=2nN=2^nN=2n and mmm. We provide a classical algorithm which solves it using time and space both upper bounded as O(Nmpoly(m,N))\mathcal{O}(N^m \text{poly}(m,N))O(Nmpoly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 TTT gates. This implies that the known 7 TTT gate circuits for these gates are TTT-optimal. We also provide a simple expression for the TTT-count of single-qubit unitaries.