Chain-of-thought (CoT) reasoning has emerged as a powerful paradigm for extending the computational capabilities of transformer-based models. A growing body of recent work has begun to uncover the fine-grained computational power of transformers augmented with CoT, as well as their connections to classical complexity theory. In this work, we advance this line of research by establishing the first hierarchy theorem for CoT-based computation. Our main result shows that for any reasonable resource bound
r(n)≥n and any
ε>0,
CoT(r(n))⊊CoT(r(n)1+ε), where
CoT(r(n)) denotes the class of decision problems solvable by transformers using
O(r(n)) CoT reasoning steps on inputs of length
n. Our result shows that increasing the number of CoT reasoning steps provably yields strictly greater computational power, establishing CoT steps as a fundamental resource in transformer-based computation. Unlike classical hierarchy theorems, which are typically proved via diagonalization, our approach leverages known coarse-grained simulations between CoT-augmented transformers and Turing machines in both directions. Building on these connections, we adapt the classical padding technique from complexity theory to this setting to obtain a tight hierarchy. A key technical contribution of our work is the implementation of padding within the transformer-based CoT model.
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form
F(x,y)=f(x1∧y1,…,xn∧yn), when the outer function
f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors.
In this work, we settle this problem in a strong way. We show that for every Boolean function
f, the bounded-error quantum and classical deterministic communication complexities of the function
f∘AND2 are polynomially related, up to polylogarithmic factors in
n. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of
f.
Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.