query-complexity 0.1.2

Adversary-bound SDP and space-efficient transducer tools for Boolean query complexity

query-complexity

query-complexity is a small Python package for computing adversary-bound SDPs and building the associated space-efficient phase-oracle transducers for Boolean query complexity.

The package intentionally keeps the compact one-vector transducer construction and removes the older direct-sum bit-flip implementation.

Install

From the repository root:

pip install -e .

For development tools:

pip install -e .[dev]

For MOSEK or Qiskit support:

pip install -e .[mosek,qiskit]

General Boolean functions

Use solve_adversary_sdp for arbitrary, non-symmetric Boolean functions.

import query_complexity as qc

inputs = qc.all_binary_inputs(3)
outputs = [int(x[0] and x[1] and x[2]) for x in inputs]

sol = qc.solve_adversary_sdp(
    inputs,
    outputs,
    solver="MOSEK",
    epsilon=1e-5,
)

td = qc.build_adversary_transducer(sol)

print("adversary objective:", sol.objective_value)
print("private dimension:", td.private_dim)
print("map error:", td.map_error)

Symmetric Boolean functions

For functions that depend only on Hamming weight, use the Terwilliger/orbit-reduced solver and expand it to the full Boolean basis:

import query_complexity as qc

n = 4
k = 2

sol = qc.solve_symmetric_adversary_sdp(
    n,
    qc.THRESHOLD_layers(n, k),
    solver="MOSEK",
    epsilon=1e-5,
)

td = qc.build_adversary_transducer(sol)

print("adversary objective:", sol.objective_value)
print("witness dimensions:", sol.witness_dims)
print("private dimension:", td.private_dim)

If you only want the compact orbit-level SDP solution, use:

orbit = qc.solve_symmetric_orbit_sdp(n, qc.THRESHOLD_layers(n, k))

Analytic helpers

import query_complexity as qc

sol = qc.analytic_or_solution(2)
td = qc.build_adversary_transducer(sol)
qc.show_catalysts(sol)

blocks = qc.threshold_eta_blocks(4, 2)
for r, data in blocks.items():
    print(r, data["labels"], data["eta"])

Main API

• solve_adversary_sdp(...): full one-vector adversary SDP for arbitrary Boolean domains.
• solve_symmetric_value(...): value-only rescaled primal Schrijver/Terwilliger SDP for symmetric functions.
• solve_symmetric_orbit_sdp(...): compact dual/orbit SDP for symmetric functions, used when you want witnesses/transducers.
• solve_symmetric_adversary_sdp(...): symmetric solver plus expansion to the Boolean input basis.
• build_adversary_transducer(...): construct the input-independent transducer unitary.
• adversary_query(...): build the input-dependent phase oracle on the witness space.
• adversary_step(...): return the single-query transducer step.
• run_adversary_algorithm(...): simulate the repeated transducer algorithm.
• qiskit_adversary_circuit(...): optional dense-unitary Qiskit circuit export.
• analytic_or_solution(...): closed-form adversary solution for OR.
• threshold_eta_blocks(...): closed-form rank-one Schrijver blocks for thresholds.

Value-only SDP solvers

If you only need the adversary bound and do not want the second trace-minimization pass, use the value-only APIs.

For a general Boolean function:

import query_complexity as qc

inputs = qc.all_binary_inputs(3)
outputs = [int(any(x)) for x in inputs]

res = qc.solve_adversary_value_sdp(inputs, outputs, solver="MOSEK")
print(res.objective_value)        # phase-normalized value T
print(res.usual_adversary_value)  # usual adversary value 2T

For a symmetric function using the rescaled primal Schrijver/Terwilliger SDP:

res = qc.solve_symmetric_value(
    10,
    qc.THRESHOLD_layers(10, 4),
    solver="MOSEK",
)
print(res["value"])                 # usual adversary value Adv^pm(f)
print(res["objective_convention"])  # full symmetric primal objective

solve_symmetric_value uses the primal variables from the original rescaled solver:

alpha_k     = binom(n, k) beta_k
eta_{a,b,t} = N_{a,b,t} gamma_{a,b,t}

and imposes PSD through Schrijver/Terwilliger blocks. It skips witness extraction and trace minimization.