Q The Query Complexity Zoo
ANDNotExactOne

AND of complemented EXACT-ONE functions

New quantum-certification lower bounds separate $\mathrm{Q}_0$ from both $\mathrm{Q}$ and rational degree.

total separating-total arity: $m^2$ bits

Description

Partition $m^2$ bits into $m$ blocks of length $m$. Accept iff no block has Hamming weight exactly one.

Formal definition

$f_m=\mathrm{AND}_m\circ(\neg\mathrm{EXACT}_{1,m})$

Measure values

MeasureValueNotes
\(\mathrm{rdeg}(f)\) Rational degree \(m\) Theorem 10. KLLPV26
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity \(\Omega(m^{3/2}/\log^2 m)\) Theorem 10 proof: Ω(√(m³/log⁴m)). KLLPV26
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) Theorem 10 and Lemma 55. KLLPV26
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(m)\) Lemma 55 gives O(m). At the all-zero input, all m² single-bit flips reject, so bs=m² and Q=Ω(√bs). KLLPV26
\(\mathrm{bs}(f)\) Block sensitivity \(m^2\) All m² bits are sensitive at zero; the arity is the matching ceiling. KLLPV26
\(\mathrm{s}(f)\) Sensitivity \(m^2\) Every single-bit flip at zero creates an EXACT-ONE block. KLLPV26
\(\mathrm{C}(f)\) Certificate complexity \(m^2\) At zero every bit is sensitive; C≥s and C≤m². KLLPV26
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(m^2\) Squeezed between bs and C. KLLPV26
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(m)\) QC=Θ(√fbs). Aaronson08 KLLPV26
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) 2QEcert≥degcert and QEcert=O(Q₀). KLLPV26
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) Theorem 5 and the QEcert bounds. KLLPV26
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree \(\Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) degcert=O(osdeg) and osdeg=O(Q₀). KLLPV26

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 16 in total, strongest first.

… and 2 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Cited as a witness by