Thomas Huffstutler and colleagues at the Stony Brook University have identified the conditions under which quantum computers cannot outperform classical algorithms. Their work presents a key framework for definitively excluding the possibility of quantum speedups. The team utilise promise-aware complexity measures and function completions to determine when superpolynomial quantum speedups are unattainable for partial Boolean functions. This connection between the collapse of specific complexity measures and polynomially related deterministic and quantum query complexities offers sharp characterisations for structured function families. By formalising completion complexity, the study further identifies criteria for ruling out speedups in functions with predictable properties, advancing understanding of the limits of quantum computation. Defining computational limits using minimal function extension Completion complexity, a central technique in this analysis, operates much like filling in gaps in an incomplete puzzle to reveal the full picture. It is formally defined as the minimum complexity needed when extending a partial function, one defined for only some inputs, into a total function applicable to all inputs. This process of ‘completion’ isn’t arbitrary; it seeks the simplest total function consistent with the known values of the partial one, effectively minimising computational effort. Establishing criteria for when a quantum speedup is impossible is now possible through analysing how complexity measures change during this completion process, revealing fundamental limits to quantum computation. The approach was employed to determine when quantum computers can outperform classical algorithms, focusing on partial Boolean functions. Using a ‘gap parameter’ to characterise potential speedups, the analysis focused on symmetric functions and those defined on ‘slices’ of the input space. The minimum complexity of all possible total functions extending the partial one proved important in identifying limits to quantum computation and establishing criteria for when a quantum advantage is impossible. Polynomial relationships between deterministic and quantum query complexity for partial Boolean A