We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two complementary lenses: promise-aware complexity measures and function completions. First, we introduce promise versions of standard combinatorial measures (including block sensitivity and related variants) and prove that if the relevant promise and completion measures "collapse", then deterministic and quantum query complexities are necessarily polynomially related, i.e., D(f) = poly(Q(f)). We then analyze structured families of promises, including symmetric partial functions and promises supported on Hamming slices, obtaining sharp (up to polynomial factors) characterizations in terms of a single gap parameter for the symmetric case and refined slice-dependent bounds for k-slice domains. Next, we formalize completion complexity as the minimum of a measure over total completions of a partial function, and show that completability of a measure captures the possibility of superpolynomial quantum speedups. Finally, we apply this viewpoint to derive broad non-speedup criteria for some classes of functions admitting well-behaved completions, such as functions with low maximum influence on both the standard and p-biased hypercubes and functions with efficiently identifiable domains, and then show some hardness results for general completion techniques.

We introduce a new operational technique for deriving chain rules for general information theoretic quantities. This technique is very different from the popular (and in some cases, fairly involved) methods like SDP formulation and operator algebra or norm interpolation. Instead, our framework considers a simple information transmission task and obtains lower and upper bounds for it. The lower bounds are obtained by leveraging a successive cancellation encoding and decoding technique. Pitting the upper and lower bounds against each other gives us the desired chain rule. As a demonstration of this technique, we derive a chain rule for the smooth-Hypothesis testing mutual information.

We introduce a new operational technique for deriving a chain rule for general information theoretic quantities. This technique is very different from the popular (and in some cases fairly involved) methods like SDP formulation and operator algebra or norm interpolation. Instead, our framework considers a simple information transmission task and obtains lower and upper bounds for it. The lower bounds are obtained leveraging a successive cancellation encoding and decoding technique. Pitting the upper and lower bounds against each other gives us the desired chain rule. As a demonstration of this technique we derive the chain rule for the smooth-Hypothesis testing mutual information.The full version of this paper can be found online, see [CK].

We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graph$G$, its graph state distance is either$\delta $or$\delta +1$, where$\delta $is the minimum vertex degree of$G$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.