Query Complexity Guide

Deterministic, randomized, and quantum query complexity measures for Boolean functions.

Overview

Query complexity measures how many input bits must be queried to compute a Boolean function. BooFun provides comprehensive tools including:

Decision tree complexity (D, D_avg)
Randomized complexity (R₀, R₁, R₂)
Quantum complexity (Q₂, QE) and lower bounds
Sensitivity measures (s, bs, es)
Certificate complexity (C, C₀, C₁)
Degree measures (exact, approximate, threshold)
Decision tree algorithms (DP, enumeration)

Decision Tree Complexity

The fundamental deterministic query measure.

Measure	Function	Description
D(f)	`complexity.decision_tree_depth(f)`	Deterministic depth
D_avg(f)	`complexity.average_decision_tree_depth(f)`	Average depth
Optimal tree (DP)	`decision_trees.decision_tree_depth_dp(f)`	DP algorithm
Randomized depth	`decision_trees.compute_randomized_complexity(f)`	R(f)
Count optimal trees	`decision_trees.count_decision_trees(f)`	Enumeration

Example: Decision Tree Analysis

import boofun as bf
from boofun.analysis import complexity
from boofun.analysis.decision_trees import (
    decision_tree_depth_dp,
    count_decision_trees
)

f = bf.majority(5)

# Deterministic decision tree depth
D_f = complexity.decision_tree_depth(f)
print(f"D(MAJ_5) = {D_f}")

# Using DP algorithm
D_dp = decision_tree_depth_dp(f)
print(f"D(f) via DP = {D_dp}")

# Count number of optimal decision trees
count = count_decision_trees(f)
print(f"Number of optimal trees: {count}")

Sensitivity Measures

How sensitive is f to single-bit changes?

Measure	Function	Description
s(f)	`complexity.max_sensitivity(f)`	Sensitivity
bs(f)	`complexity.block_sensitivity(f)`	Block sensitivity
es(f)	`complexity.everywhere_sensitivity(f)`	Everywhere sensitivity

Sensitivity vs Block Sensitivity

Sensitivity s(f): Maximum over all x of the number of single-bit flips that change f(x)
Block sensitivity bs(f): Maximum over all x of the number of disjoint blocks whose flip changes f(x)

from boofun.analysis import complexity

f = bf.AND(5)

s = complexity.max_sensitivity(f)
bs = complexity.block_sensitivity(f)

print(f"s(AND_5) = {s}")    # = 1
print(f"bs(AND_5) = {bs}")  # = 5

# Note: bs(f) ≥ s(f) always, with possible polynomial gap

Certificate Complexity

Minimum number of bits that “prove” a function value.

Measure	Function	Description
C(f)	`complexity.certificate_complexity(f)`	Certificate complexity
C₀(f)	`complexity.max_certificate_complexity(f, target=0)`	0-certificate
C₁(f)	`complexity.max_certificate_complexity(f, target=1)`	1-certificate

Example: Certificates

from boofun.analysis.complexity import (
    certificate_complexity,
    max_certificate_complexity
)

f = bf.OR(5)

C_f = certificate_complexity(f)
C_0 = max_certificate_complexity(f, target=0)
C_1 = max_certificate_complexity(f, target=1)

print(f"C(OR_5) = {C_f}")
print(f"C_0(OR_5) = {C_0}")  # Need to see all 0s
print(f"C_1(OR_5) = {C_1}")  # Just need one 1

Quantum Complexity

Quantum query complexity and lower bounds. Every function in boofun.analysis.query_complexity is classified as exact, certified lower bound (the exact value of an explicit feasible witness), or clamped estimate — see the module docstring for the full table.

Measure	Function	Status
Ambainis bound	`query_complexity.ambainis_complexity(f)`	Certified lower bound on ADV± (sensitive-edge relation)
Spectral adversary	`query_complexity.spectral_adversary_bound(f)`	Certified lower bound on ADV± (sensitivity-graph witness)
General adversary	`query_complexity.general_adversary_bound(f)`	Certified lower bound on ADV± (max of the above)
Polynomial method	`query_complexity.polynomial_method_bound(f)`	Certified lower bound on Q₂: deg̃(f)/2

Adversary values lower-bound ADV±(f), which characterizes Q₂(f) up to constant factors (Q₂ = Θ(ADV±)); because those constants are below 1, an adversary value can numerically exceed Q₂ (e.g. ADV±(PARITY_n) = n while Q₂ = ⌈n/2⌉). BooFun deliberately does not ship the ADV± semidefinite program; its witness values are cross-validated against pinned QuantumQueryOptimizer SDP optima in tests/cross_validation/test_qqo.py.

Example: Quantum Bounds

from boofun.analysis import query_complexity as qc

f = bf.OR(4)

# Ambainis adversary method lower bound: ADV(OR_4) = sqrt(4) = 2,
# achieved exactly by the sensitive-edge relation
amb = qc.ambainis_complexity(f)
print(f"Ambainis bound: ADV±(OR_4) ≥ {amb:.2f}")

# Certified lower bound on Q2 via the polynomial method
poly = qc.polynomial_method_bound(f)
print(f"Q2(OR_4) ≥ {poly:.2f}")

# For comparison, classical deterministic
D_f = complexity.decision_tree_depth(f)
print(f"D(OR_4) = {D_f}")

# Quantum achieves a sqrt speedup for OR (Grover)

Degree Measures

Polynomial degree measures related to query complexity.

Measure	Function	Description
deg(f)	`fourier.fourier_degree(f)`	Exact real degree
deg̃(f)	`query_complexity.approximate_degree(f)`	Approximate degree (LP-exact, n ≤ 12)
deg_th(f)	`query_complexity.threshold_degree(f)`	Threshold degree (LP-exact, n ≤ 12)
ndeg(f)	`query_complexity.nondeterministic_degree(f)`	Nondeterministic degree (exact, n ≤ 12)

Example: Degree Analysis

from boofun.analysis.fourier import fourier_degree
from boofun.analysis.query_complexity import approximate_degree, threshold_degree

f = bf.parity(4)
print(f"deg(PAR_4) = {fourier_degree(f)}")        # = 4 (full degree)
print(f"deg~(PAR_4) = {approximate_degree(f)}")   # = 4 (parity needs full degree)

f = bf.OR(4)
print(f"deg(OR_4) = {fourier_degree(f)}")         # = 4
print(f"deg_th(OR_4) = {threshold_degree(f)}")    # = 1 (OR is a threshold function)

Huang’s Theorem

The celebrated result connecting sensitivity to degree.

Function	Description
`huang.sensitivity_lower_bound(f)`	s(f) ≥ √deg(f)
`huang.verify_huang_theorem(f)`	Verify the relationship

Example: Verifying Huang’s Theorem

from boofun.analysis import huang

f = bf.AND(6)

# Verify Huang's theorem: s(f) >= sqrt(deg(f))
result = huang.verify_huang_theorem(f)
print(f"s(f) = {result['sensitivity']}")
print(f"deg(f) = {result['degree']}")
print(f"sqrt(deg(f)) = {result['sqrt_degree']:.2f}")
print(f"Huang satisfied: {result['satisfied']}")

Complexity Relationships

Known relationships between measures (all polynomial):

       s(f) ≤ bs(f) ≤ C(f) ≤ D(f)
         ↓
    deg(f) ≤ D(f)
         ↓
      Q(f) ≤ D(f)

Key results:
- D(f) ≤ bs(f)² (classical)
- s(f) ≥ √deg(f) (Huang 2019)
- Q(f) = Θ(√D(f)) for some functions (Grover)

Full Complexity Profile

Get all measures at once:

from boofun.analysis.query_complexity import QueryComplexityProfile

f = bf.majority(5)

profile = QueryComplexityProfile(f)
print(profile.summary())

# Access individual measures
print(f"D(f) = {profile.deterministic_depth}")
print(f"s(f) = {profile.sensitivity}")
print(f"bs(f) = {profile.block_sensitivity}")
print(f"C(f) = {profile.certificate_complexity}")

Decision Tree Algorithms

Advanced algorithms for decision tree analysis.

DP Algorithm

Compute optimal decision tree depth via dynamic programming:

from boofun.analysis.decision_trees import decision_tree_depth_dp

f = bf.tribes(2, 4)  # 2 tribes of 4

depth = decision_tree_depth_dp(f)
print(f"D(TRIBES) = {depth}")

Tree Enumeration

Count the number of optimal decision trees:

from boofun.analysis.decision_trees import count_decision_trees

f = bf.majority(3)

count = count_decision_trees(f)
print(f"Number of optimal trees for MAJ_3: {count}")

Randomized Complexity

Compute randomized decision tree complexity:

from boofun.analysis.decision_trees import compute_randomized_complexity

f = bf.OR(4)

R_f = compute_randomized_complexity(f)
print(f"R(OR_4) = {R_f:.2f}")