Metadata-Version: 2.4
Name: query-complexity
Version: 0.1.1
Summary: Adversary-bound SDP and space-efficient transducer tools for Boolean query complexity
Author: Ke Li
License: MIT
Project-URL: Homepage, https://github.com/your-org/query-complexity
Project-URL: Repository, https://github.com/your-org/query-complexity
Project-URL: Issues, https://github.com/your-org/query-complexity/issues
Keywords: quantum,query complexity,adversary bound,sdp,semidefinite programming
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.23
Requires-Dist: scipy>=1.9
Requires-Dist: cvxpy>=1.3
Provides-Extra: mosek
Requires-Dist: mosek; extra == "mosek"
Provides-Extra: qiskit
Requires-Dist: qiskit; extra == "qiskit"
Provides-Extra: dev
Requires-Dist: build; extra == "dev"
Requires-Dist: pytest; extra == "dev"
Requires-Dist: twine; extra == "dev"
Dynamic: license-file

# 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:

```bash
pip install -e .
```

For development tools:

```bash
pip install -e .[dev]
```

For MOSEK or Qiskit support:

```bash
pip install -e .[mosek,qiskit]
```

## General Boolean functions

Use `solve_adversary_sdp` for arbitrary, non-symmetric Boolean functions.

```python
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:

```python
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:

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

## Analytic helpers

```python
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_orbit_sdp(...)`: compact Terwilliger/orbit-reduced SDP for symmetric functions.
- `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:

```python
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 Schrijver/Terwilliger blocks:

```python
res = qc.solve_symmetric_orbit_value_sdp(
    10,
    qc.THRESHOLD_layers(10, 4),
    solver="MOSEK",
)
print(res.objective_value)
print(res.usual_adversary_value)
```

These functions skip witness extraction and trace minimization.
