Quantum computing · Theory (AI-assisted)

A sensitivity-constrained polynomial method for DQC1 query complexity

Changpeng Shao

arXiv:2611.26231v1 ↗PDF ↗Submitted 19 November 2026

Question
The one-clean-qubit model, DQC1, starts from one pure qubit and \(m\) maximally mixed qubits. It still estimates normalised traces that are believed hard classically. Its query complexity, however, has lacked a general lower-bound method. For standard quantum algorithms, the polynomial method turns a \(T\)-query algorithm into a polynomial of degree at most \(2T\) and reads lower bounds from approximation theory. What extra constraint does a maximally mixed query register impose on that polynomial, and which query speedups survive it?
Result
The output bias \(p(x)\) of any \(T\)-query DQC1 algorithm on \(N\) input bits is a multilinear polynomial with degree at most \(2T\), values in \([-1,1]\), and a new constraint: flipping any single input bit changes it by at most \(2T/N\), that is \(|\partial_ip|\le T/N\). Building this constraint into approximate degree gives a measure whose lower bound is \(2(1-\varepsilon)N/\Delta_H\), where \(\Delta_H\) is the least Hamming distance between inputs with different answers. Several consequences follow. Every non-constant total Boolean function needs at least \((1-2\varepsilon)N\) DQC1 queries, even the dictator \(x_1\). For symmetric partial functions the measure is \(\Theta(N/\Delta)\), and DQC1 query complexity is at most the square of the standard quantum one, which is tight for OR. Under product or exchangeable input distributions, a classical algorithm with \(O(T^2\varepsilon^{-2}\log\delta^{-1})\) queries approximates the acceptance probability. Finally, 2-Forrelation needs \(\Omega(N^{1/4})\) DQC1 queries.

The paper in detail

DQC1 starts from \(\ket0\bra0\otimes I/2^m\), applies a unitary, and measures the clean qubit. Its output bias is a normalised trace, \(p=\tau(ZUZU^\dagger)\) with \(\tau(A)=\operatorname{tr}A/\dim\). In the query version, \(U_x\) interleaves fixed unitaries with \(T\) calls to the controlled-phase oracle \(O_x=P_0+\sum_ix_iP_i\), where \(P_i\) projects onto "control on, index \(i\)" and \(\tau(P_i)=1/2N\). The polynomial method for ordinary quantum algorithms rests on the fact that acceptance probabilities after \(T\) queries are polynomials of degree at most \(2T\) in the input bits. That remains true here, but it ignores that every register except one starts maximally mixed.

The new ingredient is a bound on how strongly the output can depend on a single input bit. Flipping \(x_i\) changes the oracle by \(2P_i\), and in a normalised trace this projector has weight only \(1/2N\), whatever unitaries surround it. Summing over the \(2T\) oracle occurrences gives \(|\partial_ip|\le T/N\) for every \(i\) and every setting of the other bits. The paper builds this into a sensitivity approximate degree. This is the least \(d\) such that a polynomial of degree at most \(d\), bounded by 1, approximates the function, and has every coordinate derivative at most \(d/2N\). Because of the derivative term the measure can exceed \(N\). The dictator \(x_1\) has degree 1 but sensitivity approximate degree about \(2N\).

Walking along a shortest path in the Boolean cube between two oppositely labelled inputs gives the general lower bound \(2(1-\varepsilon)N/\Delta_H\). For a total function some two adjacent inputs differ in label, so \(\Delta_H=1\) and at least \((1-2\varepsilon)N\) queries are needed. For symmetric partial functions, symmetrisation reduces the measure to univariate approximation with a slope limit on the Hamming-weight grid, and a Lipschitz-preserving Jackson theorem gives a matching upper bound \(O(N/\Delta)\). An example shows the contrast with standard approximate degree. Promises on the weight layers \(\{0,1\}\) and \(\{N/2,N/2+1\}\) both have sensitivity approximate degree \(\Theta(N)\), but standard approximate degrees \(\Theta(\sqrt N)\) and \(\Theta(N)\). A DQC1 circuit that runs a classical sampling algorithm with \(2t\) queries supplies the algorithmic side of \(Q^{\rm DQC1}=O(Q^{\rm BQP\,2})\).

The same derivative bound makes the acceptance probability concentrate. Under any product distribution it is \(T/N\)-Lipschitz in each coordinate, so it stays close to its mean, and a classical simulator can often answer without querying anything. A martingale over uniformly random strings of fixed Hamming weight extends this to exchangeable distributions. In Section 5, degree and sensitivity together bound the level-two Fourier growth by \(O(T^2)\), which with the Girish–Raz–Zhan reduction gives the Forrelation bound. Open directions include stronger lower-bound methods, such as adversary or dual-polynomial versions that use the trace structure, and a DQC1 analogue of the completely bounded forms that characterise standard quantum query algorithms.

Transferable methods

  1. A maximally mixed register dilutes every coordinate to weight 1/N

    The polynomial method for standard algorithms cannot separate DQC1 from BQP, because both produce low-degree bounded polynomials. What DQC1 lacks is the ability to point its query register at one input coordinate. A pure query register can put all its weight on index \(i\) and read \(x_i\) in one query. A maximally mixed register spreads its weight evenly, and no unitary can concentrate a maximally mixed spectrum. A one-line trace inequality turns this into a uniform derivative bound, and a path argument turns the derivative bound into a lower bound.

    Fix every bit except \(x_i\), and write \(O_\pm\) for the oracle with \(x_i=\pm1\), so \(O_+-O_-=2P_i\). Replace the oracle occurrences one at a time in \(\tau(ZU_{x^+}ZU_{x^+}^\dagger)-\tau(ZU_{x^-}ZU_{x^-}^\dagger)\). This telescopes into \(2T\) terms of the form \(2\tau(AP_iB)\), where \(A\) and \(B\) are products of unitaries. Cyclicity and Hölder's inequality bound each term: \[|\tau(AP_iB)|=|\tau(P_iBA)|\le\tau(P_i)\,\|BA\|\le\frac1{2N},\qquad\text{so}\qquad|\partial_ip(x)|=\tfrac12|p(x^+)-p(x^-)|\le\frac TN.\] For a pure-state algorithm the weight \(\tau(P_i)\) becomes \(\bra\psi P_i\ket\psi\), which can be \(\tfrac12\), and no such bound holds.

    Let \(p\) \(\varepsilon\)-approximate \(f\) with every derivative at most \(d/2N\). Take oppositely labelled \(x,y\) at Hamming distance \(\Delta_H\), and walk between them one bit at a time. Each step changes \(p\) by at most \(d/N\), while the endpoints differ by at least \(2(1-\varepsilon)\), so \[2(1-\varepsilon)\le\frac{d\,\Delta_H}N\quad\Longrightarrow\quad d\ge\frac{2(1-\varepsilon)N}{\Delta_H},\qquad Q^{\rm DQC1}_\varepsilon(f)\ge\tfrac12d.\] The editorial simulation showed the derivative bound is sharp. Optimised one-query algorithms on four input bits reach \(|\partial_ip|=1/4\) exactly.

    How to reuse it

    Any model whose state is close to maximally mixed inherits a per-coordinate Lipschitz bound from the same trace inequality. Examples are high-temperature NMR, DQC\(k\) with an extra factor \(2^k\), and noisy circuits that have mixed towards the identity. Checking the minimum Hamming distance between differently labelled inputs is then a quick test of whether such a model can offer any query advantage for a given problem.

  2. Bounded differences give concentration and classical simulation

    Once each input bit can move the acceptance probability by at most \(T/N\), standard concentration inequalities apply without using the degree bound at all. The acceptance probability of a short DQC1 algorithm is nearly constant on typical inputs, so a classical simulator can output its mean. Symmetrisation uses the same derivative bound to reduce symmetric problems to one variable with a slope limit.

    For independent input bits, McDiarmid's inequality with bounded differences \(c_i=T/N\) gives \[\Pr\bigl[|p_{\mathcal A}(X)-\mathbb E\,p_{\mathcal A}|\ge s\bigr]\le2\exp\Bigl(-\frac{2s^2}{\sum_ic_i^2}\Bigr)=2\exp\Bigl(-\frac{2Ns^2}{T^2}\Bigr).\] So once \(N\ge T^2(2\varepsilon^2)^{-1}\ln(2/\delta)\), outputting the mean, with no queries, is within \(\varepsilon\) except with probability \(\delta\). For a uniform string of fixed Hamming weight, revealing the positions of the minority bits one at a time defines a Doob martingale. Swapping two candidate positions changes at most two bits, so each increment is at most \(2T/N\), and Azuma's inequality gives \(2\exp(-N^2s^2/8rT^2)\), where \(r\) is the number of minority bits.

    For a symmetric partial function, averaging \(p\) over coordinate permutations keeps the degree, the bound and the derivative bound, and yields \(q(\mathrm{wt}(x))\). The derivative condition becomes a slope condition on consecutive weights: \[|q(k+1)-q(k)|\le\frac dN,\qquad k=0,\dots,N-1.\] Conversely, a piecewise-linear target that changes sign over a gap of \(\Delta\) weights has slope about \(N/\Delta\) on \([-1,1]\). Jackson's theorem in its Lipschitz-preserving form approximates it with a polynomial of degree \(O(N/\Delta)\) and comparable slope, which gives the matching upper bound \(\Theta(N/\Delta)\).

    How to reuse it

    Any class of algorithms with uniformly small influence per input coordinate can be simulated on average by its mean. This applies to noisy quantum algorithms whose noise contracts influences, to property-testing lower bounds, and to deciding whether a claimed speedup survives once the input distribution is product or exchangeable rather than adversarial.

Source: Section 2 (Theorem 2.4, Definition 2.5, Theorems 2.8–2.9, Corollary 2.10); Section 3 (Theorems 3.1–3.2, Corollary 3.3, Lemma 3.7); Section 4 (Theorem 4.1, Lemmas 4.3–4.4). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The paper gives DQC1 a polynomial method of its own and pins down what limits the model in the oracle setting. A maximally mixed register cannot concentrate on one input coordinate, so each query reveals only a \(1/N\) share of any single bit. For total functions DQC1 therefore has no asymptotic query advantage, even over classical algorithms; any speedup must come from a promise on the input. The average-case simulation results sharpen this: an algorithm making \(o(\sqrt N)\) queries behaves like a constant on typical inputs from such distributions.

Limitations. The method proves lower bounds only, and the author does not expect sensitivity approximate degree to characterise DQC1 query complexity in general. The bounds are for a specific controlled-phase oracle. With \(k\) clean qubits the sensitivity bound weakens by a factor \(2^k\). The \(N^{1/4}\) Forrelation bound is not shown to be tight, and it relies on the Fourier-growth reduction of Girish, Raz and Zhan. The classical simulations are average-case and count queries only, with unbounded computation. The AI disclosure states that ChatGPT played a substantial role in developing proofs, carrying out calculations and exploring extensions; the author reviewed and verified the arguments.

Description based on the full arXiv HTML of v1, read 2026-11-22: Sections 1–3 with the proofs of Theorems 2.4, 2.8, 2.9, 3.1 and 3.2, Corollary 3.3, Proposition 3.5 and Lemma 3.7; Section 4 with Theorem 4.1 and Lemmas 4.3–4.4; the statements and the Forrelation argument of Section 5; and the conclusion. The circuit of Lemma 3.8 and the Fourier-growth proofs of Section 5 were skimmed. Editorial check: exact simulation of DQC1 query algorithms with \(N=4\), one clean qubit and three maximally mixed qubits. Over 300 random algorithms for each \(T\), the largest \(|\partial_ip|\) was between 0.11 and 0.16. Optimising the unitaries directly pushed it to 0.2500, 0.4989 and 0.717 for \(T=1,2,3\), against the bound \(T/N=0.25\), 0.5 and 0.75, so the bound is attained at \(T=1\) and nearly at \(T=2\). The \(T=1\) output bias had Fourier degree 2, as the degree bound allows.