Listing: Listing

import itertools
import math
from fractions import Fraction

def bits_of(word, n):
    return tuple((word >> (n - 1 - j)) & 1 for j in range(n))

def hamming(a, b):
    return (a ^ b).bit_count()

def exact_classical_covering(n, states, max_codebooks=1000000):
    if not isinstance(n, int) or n < 1:
        raise ValueError("positive integer input length required")
    if not isinstance(states, int) or states < 1:
        raise ValueError("positive integer state count required")
    if not isinstance(max_codebooks, int) or max_codebooks < 1:
        raise ValueError("positive search guard required")

    words = 1 << n
    k = min(states, words)
    number = math.comb(words, k)
    if number > max_codebooks:
        raise ValueError(
            "exhaustive search rejected; no upper certificate returned"
        )

    # Adding codewords never worsens the distance objective.
    # Thus exactly k words suffice for the <=states optimum.
    best_cost, best_book, visited = None, None, 0
    for book in itertools.combinations(range(words), k):
        cost = sum(
            min(hamming(x, c) for c in book)
            for x in range(words)
        )
        visited += 1
        if best_cost is None or cost < best_cost:
            best_cost, best_book = cost, book

    assert visited == number
    score = Fraction(1, 1) - Fraction(best_cost, n * words)
    return {
        "score": score,
        "minimum_total_distance": best_cost,
        "codebook": tuple(bits_of(c, n) for c in best_book),
        "visited": visited,
        "required": number,
        "certificate": "completed_exact_codebook_enumeration",
        "architecture": "batch encoder; not arbitrary streaming equality",
    }

def enumerate_two_state_tables():
    inputs = tuple(itertools.product((0, 1), repeat=2))
    best = Fraction(0, 1)
    visited = 0
    for encoder in itertools.product((0, 1), repeat=4):
        # Flat decoder entries: (m=0,j=0), (m=0,j=1),
        #                       (m=1,j=0), (m=1,j=1).
        for decoder in itertools.product((0, 1), repeat=4):
            correct = 0
            for x_index, x in enumerate(inputs):
                memory = encoder[x_index]
                for j in range(2):
                    correct += decoder[2 * memory + j] == x[j]
            score = Fraction(correct, 8)
            best = max(best, score)
            visited += 1
    assert visited == 256
    return best, visited

def square_state_from_sequential_gates(x1, x2):
    if x1 not in (0, 1) or x2 not in (0, 1):
        raise ValueError("binary inputs required")
    angle = ((-1) ** x1) * math.pi / 4
    state = (math.cos(angle / 2), math.sin(angle / 2))
    if x2:
        state = (state[1], state[0])
    return state

def bloch_xz_from_real_state(state):
    a, b = state
    return 2 * a * b, a * a - b * b

def quantum_success(eta=1.0, steps=0):
    eta = float(eta)
    if not math.isfinite(eta) or not 0 <= eta <= 1:
        raise ValueError("depolarizing factor outside [0,1]")
    if not isinstance(steps, int) or steps < 0:
        raise ValueError("nonnegative integer delay required")
    retained = eta ** steps if steps else 1.0
    values = []
    for x1, x2 in itertools.product((0, 1), repeat=2):
        rx, rz = bloch_xz_from_real_state(
            square_state_from_sequential_gates(x1, x2)
        )
        values.extend((
            0.5 * (1 + ((-1) ** x1) * retained * rx),
            0.5 * (1 + ((-1) ** x2) * retained * rz),
        ))
    return sum(values) / 8, tuple(values)

def complete_score(p, v, assignment_error, eta, steps):
    p, v, assignment_error = map(float, (p, v, assignment_error))
    if not all(math.isfinite(x) for x in (p, v, assignment_error)):
        raise ValueError("finite detector factors required")
    if not 0 <= p <= 1 or not 0 <= v <= 1 \
            or not 0 <= assignment_error <= 0.5:
        raise ValueError("invalid independent-detector specification")
    q, _ = quantum_success(eta, steps)
    return 0.5 + p * v * (1 - 2 * assignment_error) * (q - 0.5)

def exclusion_certificate(scores, delta, e_classical=0.0,
                          anytime=False):
    scores = tuple(float(s) for s in scores)
    if not scores or not all(
        math.isfinite(s) and 0 <= s <= 1 for s in scores
    ):
        raise ValueError("complete attempted-run scores required")
    delta, e_classical = float(delta), float(e_classical)
    if not math.isfinite(delta) or not 0 < delta < 1:
        raise ValueError("confidence error outside (0,1)")
    if not math.isfinite(e_classical) or e_classical < 0:
        raise ValueError("invalid classical discrepancy allowance")
    n = len(scores)
    null_bound = min(1.0, 0.75 + e_classical)
    logarithm = math.log(
        n * (n + 1) / delta if anytime else 1.0 / delta
    )
    radius = math.sqrt(logarithm / (2 * n))
    mean = sum(scores) / n
    return {
        "n_attempts": n,
        "mean": mean,
        "radius": radius,
        "lower_mean_allowance": max(0.0, mean - radius),
        "null_bound": null_bound,
        "reject": mean - radius > null_bound,
        "inspection_policy": "anytime" if anytime else "fixed_sample",
        "capacity_and_freshness_checked_by_code": False,
    }

def proposed_tests():
    # Specifications only: no executed pass is asserted.
    best, count = enumerate_two_state_tables()
    assert best == Fraction(3, 4)
    assert count == 256

    for states, expected in (
        (1, Fraction(1, 2)),
        (2, Fraction(3, 4)),
        (3, Fraction(7, 8)),
        (4, Fraction(1, 1)),
    ):
        record = exact_classical_covering(2, states)
        assert record["score"] == expected
        assert record["visited"] == record["required"]

    ideal = 0.5 + 1 / (2 * math.sqrt(2))
    q, individual = quantum_success()
    assert math.isclose(q, ideal, abs_tol=1e-12)
    assert all(math.isclose(v, ideal, abs_tol=1e-12)
               for v in individual)

    # At the exact theoretical isotropic boundary the score is 3/4.
    q, _ = quantum_success(1 / math.sqrt(2), 1)
    assert math.isclose(q, 0.75, abs_tol=1e-12)

    assert complete_score(0.0, 1.0, 0.0, 1.0, 0) == 0.5
    assert complete_score(1.0, 0.0, 0.0, 1.0, 0) == 0.5
    assert complete_score(1.0, 1.0, 0.5, 1.0, 0) == 0.5

    # Query-2 erasure must not be discarded.
    full_attempt_scores = (1.0, 0.5)
    assert sum(full_attempt_scores) / len(full_attempt_scores) == 0.75

    try:
        exact_classical_covering(8, 8, max_codebooks=1)
    except ValueError:
        pass
    else:
        raise AssertionError("oversized search was not rejected")