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.
Introduction
Classical simulation of quantum circuits is a fundamental challenge in computational complexity. While Clifford gates (e.g., CNOT, Hadamard) are efficiently simulatable, non-Clifford gates like the $T$-gate introduce exponential complexity. Current state-of-the-art strong simulators, which calculate exact amplitudes, exhibit runtimes scaling exponentially with the $T$-gate count $N$, such as $O(2^{0.47N})$. This research establishes a formal "speed limit" for such simulations by linking their complexity to the 3-SAT problem and the Exponential Time Hypothesis (ETH).
Reductions from 3-SAT to Quantum Circuits
The core methodology involves a reduction from 3-SAT to quantum circuit simulation. The process follows three primary stages:
- 3-SAT to Reversible Circuits: A 3-SAT instance with $n$ variables and length $L$ is mapped to a classical reversible circuit. This circuit utilizes Toffoli gates to implement the necessary boolean logic.
- Reversible to Quantum: These reversible circuits are converted into Clifford+$T$ quantum circuits. A critical component of this mapping is the decomposition of Toffoli gates. As shown in Figure 2, a single Toffoli gate can be decomposed into a sequence of Clifford gates and exactly 7 $T$-gates.
- Boolean Logic Implementation: The reduction requires constructing circuits for conjunction, disjunction, and negation to represent the 3-SAT formula. Figure 1 illustrates the quantum circuit constructions for these fundamental logical operations.
- Sparsification Lemma: To ensure the number of $T$-gates remains manageable, the authors employ the Sparsification Lemma. This allows a complex 3-SAT instance to be broken into multiple "sparse" instances where the number of clauses is linear relative to the number of variables. This ensures the resulting quantum circuit has a $T$-gate count $N$ that is directly proportional to the 3-SAT formula length $L$.
Establishing the "Speed Limit"
By tying the $T$-gate count $N$ to the complexity of 3-SAT, the authors derive explicit lower bounds for strong simulation.
- Theorem 1: Under the ETH, there exists a constant $\epsilon > 0$ such that strong simulation of a Clifford+$T$ circuit with $N$ $T$-gates requires at least $2^{\epsilon N}$ time.
- Theorem 2: The authors calculate an explicit "speed limit." If a simulator could determine if $\langle 0|C|0 \rangle \neq 0$ in time $O(2^{2.2451 \times 10^{-8}N})$, it would outperform the best known classical 3-SAT solvers (currently $\approx O(1.3^n)$), representing a significant breakthrough in classical algorithms.
The reduction efficiency demonstrated shows that a 3-SAT instance of length $L$ can be reduced to a quantum circuit with at most $14L$ $T$-gates.
Discussion and Limitations
While this work provides a rigorous lower bound, a significant gap remains between the proven bound ($10^{-8}$) and the performance of current algorithms ($0.47$). This suggests that either current simulation techniques are highly inefficient or the theoretical lower bound can be tightened through more efficient reductions.
Furthermore, this study focuses on strong simulation (exact amplitudes). The complexity of weak simulation (sampling), which is more common in practical quantum algorithms, remains an open area for similar ETH-based lower bounds. Finally, while the Clifford+$T$ set is universal, the specific constants derived here are tied to this gate set; other universal sets like Toffoli+Hadamard may yield different explicit bounds.
Summary updated