ANDNotExactOne
AND of complemented EXACT-ONE functions
New quantum-certification lower bounds separate $\mathrm{Q}_0$ from both $\mathrm{Q}$ and rational degree.
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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.5}\big)\)from \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) against \(\mathrm{rdeg}(f) = m\)
-
\(\mathrm{s}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.3333}\big)\)from \(\mathrm{s}(f) = m^2\) against \(\mathrm{Q}_{0}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{bs}(f_n) = \Omega\big(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{bs}(f) = m^2\) against \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.5}\big)\)from \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) against \(\mathrm{rdeg}(f) = m\)
-
\(\mathrm{s}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{s}(f) = m^2\) against \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{bs}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.3333}\big)\)from \(\mathrm{bs}(f) = m^2\) against \(\mathrm{Q}_{0}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\overline{\deg}^{\mathrm{cert}}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.5}\big)\)from \(\overline{\deg}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m)\) against \(\mathrm{rdeg}(f) = m\)
-
\(\mathrm{s}(f_n) = \Omega\big(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{s}(f) = m^2\) against \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{bs}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{bs}(f) = m^2\) against \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{fbs}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{1.3333}\big)\)from \(\mathrm{fbs}(f) = m^2\) against \(\mathrm{Q}_{0}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^{1.5}\big)\)from \(\overline{\mathrm{osdeg}}_{\varepsilon}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\) against \(\mathrm{rdeg}(f) = m\)
-
\(\mathrm{fbs}(f_n) = \Omega\big(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{fbs}(f) = m^2\) against \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{QC}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{0.6667}\big)\)from \(\mathrm{QC}(f) = \Theta(m)\) against \(\mathrm{Q}_{0}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
-
\(\mathrm{fbs}(f_n) = \Omega\big(\mathrm{Q}_{0}^{\mathrm{cert}}(f_n)^{1.3333}\big)\)from \(\mathrm{fbs}(f) = m^2\) against \(\mathrm{Q}_{0}^{\mathrm{cert}}(f) = \Omega(m^{3/2}/\log^2 m),\ O(m^{3/2})\)
… 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
-
\(\overline{\deg}^{\mathrm{cert}}(f_m)=\widetilde\Omega(\mathrm{rdeg}(f_m)^{3/2})\)
-
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_m)=\widetilde\Omega(\mathrm{QC}(f_m)^{3/2})\)
-
\(\mathrm{Q}_0^{\mathrm{cert}}(f_m)=\widetilde\Omega(\mathrm{QC}(f_m)^{3/2})\)
-
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\) total Gap open →\(\overline{\mathrm{osdeg}}(f_m)=\widetilde\Omega(\widetilde{\deg}(f_m)^{3/2})\)
-
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f_m)=\widetilde\Omega(\mathrm{Q}(f_m)^{3/2})\)
-
\(\mathrm{Q}_0^{\mathrm{cert}}(f_m)=\widetilde\Omega(\mathrm{Q}(f_m)^{3/2})\)