"""Board pauli-cover: fewest local X/Y/Z measurement settings that cover every Pauli pattern on every set of t qubits (SPEC_v6 s.4, with Fable's review amendments V1-V4, discussion/verifiers/batch6/). Artifact {"settings": ["XYZX...", ...]}: a nonempty list of at most settings_max strings, each exactly n characters from X, Y, Z (setting r measures qubit q in basis settings[r][q]). Duplicate settings are allowed and counted. The file is at most artifact_bytes_max = 262,144 bytes (run_one.MAX_BYTES["pcover"], checked by load_artifact before parsing). Accepted iff for every increasing column tuple q_0 < ... < q_{t-1} < n and every pattern b in {X, Y, Z}^t some setting restricts to b on those columns (an array of strength t, in covering-array terms). Score {"settings": N}, minimized; equal counts tie. Exact method (review V2, the prefix-intersection recursion): B[q][b] is the set of rows whose letter at column q is b, as a Python int bitset over the N rows. For a column prefix q_0 < ... < q_i the 3^(i+1) partial intersections B[q_0][b_0] & ... & B[q_i][b_i] are built from the 3^i of the shorter prefix, one & each. An empty partial is a hole for every extension of its prefix, so the branch stops and the artifact is rejected with one concrete uncovered tuple and pattern. At the last column every one of the 3^(t-1) partials must meet all three bitsets of every later column. Every pattern of every t-subset is examined (no sampling, no submitted claims), and acceptance is returned only after the last prefix. Cost: about 3^t C(n, t) ANDs of N-bit integers (317,619,225 on pc4-n100); memory O(3 n N) bits. The CPU deadline (cpu_seconds - 20, from QARENA_CPU when set, counted from the start of the process in verify(), so parsing is included) is checked once per (t-1)-column prefix (161,700 times on pc4-n100, review V2); running out gives status error without a score, never an accept. """ import os import time from math import comb from common import Reject, exact_keys, is_int, load_instance, short, want_list MAX_ARTIFACT_BYTES = 262144 # SPEC_v6 s.2 byte cap; the enforced copy is run_one.MAX_BYTES["pcover"] LETTERS = "XYZ" _ONE = [str.maketrans({"X": "1", "Y": "0", "Z": "0"}), str.maketrans({"X": "0", "Y": "1", "Z": "0"}), str.maketrans({"X": "0", "Y": "0", "Z": "1"})] class Budget(Exception): pass def check_instance(I): """The instance file must be self-consistent; anything else is an internal inconsistency (status error).""" ok = (isinstance(I, dict) and all(is_int(I.get(k)) for k in ("n", "strength", "settings_max", "cpu_seconds", "artifact_bytes_max")) and 1 <= I["strength"] <= 8 and I["strength"] <= I["n"] <= 4096 and 1 <= I["settings_max"] <= 4096 and I["artifact_bytes_max"] == MAX_ARTIFACT_BYTES) if not ok: raise RuntimeError("instance file is inconsistent") def parse(art, I): """Validate the artifact; returns the list of settings (strings over X, Y, Z of length n).""" if not isinstance(art, dict): raise Reject("artifact must be a JSON object") exact_keys(art, ["settings"]) n, cap = I["n"], I["settings_max"] S = want_list(art["settings"], f"settings (instance {I.get('instance', '?')} allows 1 to {cap} settings)", max_len=cap, min_len=1) for i, s in enumerate(S): if not isinstance(s, str): raise Reject(f"settings[{i}] must be a string of {n} letters X/Y/Z, got {short(s)}") if len(s) != n: raise Reject(f"settings[{i}] has {len(s)} characters, the instance has n = {n} qubits: {short(s)}") if s.strip(LETTERS): p = next(j for j, ch in enumerate(s) if ch not in LETTERS) raise Reject(f"settings[{i}] has character {s[p]!r} at qubit {p}; only the uppercase letters X, Y, Z " "are allowed") return S def bitsets(S, n): """B[q] = (rows with X at q, rows with Y at q, rows with Z at q) as int bitsets (bit r = row r).""" B = [] for col in zip(*S): c = "".join(col)[::-1] # row 0 becomes the last character, i.e. bit 0 B.append(tuple(int(c.translate(tr), 2) for tr in _ONE)) if len(B) != n: raise RuntimeError("column count mismatch") return B def first_hole(B, n, t, deadline): """None if every pattern on every t-subset is covered; otherwise (columns, pattern) of one uncovered pair. Raises Budget when the CPU deadline passes (checked once per (t-1)-column prefix, before its work).""" def hole(cols, j, level, extra): # j indexes the 3^level partials of the prefix cols in base 3, first column most significant pat = [] for _ in range(level): pat.append(LETTERS[j % 3]) j //= 3 pat.reverse() return tuple(cols) + tuple(extra), "".join(pat) + "X" * len(extra) def rec(level, parts, cols): start = cols[-1] + 1 if cols else 0 if level == t - 1: if time.process_time() > deadline: raise Budget for q in range(start, n): for b, m in enumerate(B[q]): if not all(map(m.__and__, parts)): j = next(j for j, p in enumerate(parts) if not p & m) return hole(cols + [q], 3 * j + b, level + 1, ()) return None for q in range(start, n - (t - 1 - level)): x, y, z = B[q] new = [r for p in parts for r in (p & x, p & y, p & z)] if not all(new): # empty prefix: every extension by later columns is a hole j = new.index(0) return hole(cols + [q], j, level + 1, range(q + 1, q + t - level)) h = rec(level + 1, new, cols + [q]) if h is not None: return h return None return rec(0, [-1], []) # -1 has every bit set: the empty prefix contains every row def verify(inst, art, time_budget=None): """run_one's entry point. The CPU budget counts from the start of the process (time.process_time()), so the time spent reading and parsing the artifact before this call is charged to it (SPEC_v6 s.2).""" I = load_instance("pcover", inst) if time_budget is None: time_budget = max(1.0, float(os.environ.get("QARENA_CPU", I["cpu_seconds"])) - 20) - time.process_time() return check(I, art, time_budget) def check(I, art, time_budget=None): """verify() on an instance given as a loaded dict (tests pass small ad hoc instances this way).""" t0 = time.process_time() check_instance(I) budget = time_budget if time_budget is not None else max(1.0, float(os.environ.get("QARENA_CPU", I["cpu_seconds"])) - 20) deadline = t0 + budget n, t = I["n"], I["strength"] S = parse(art, I) N = len(S) B = bitsets(S, n) try: h = first_hole(B, n, t, deadline) except Budget: return {"status": "error", "detail": {"reason": "coverage check did not finish within the CPU budget (not ranked)", "n": n, "strength": t, "settings": N}} if h is not None: cols, pat = h if any(all(s[q] == b for q, b in zip(cols, pat)) for s in S): raise RuntimeError(f"reported hole {cols} {pat} is covered") # self-check of the diagnosis raise Reject(f"not every pattern is covered: no setting measures qubits {list(cols)} in the bases {pat} " f"(qubit {cols[0]} in {pat[0]}" + "".join(f", qubit {q} in {b}" for q, b in zip(cols[1:], pat[1:])) + f"); {N} settings must cover all 3^{t} = {3 ** t} patterns on every {t} of the {n} qubits") subsets = comb(n, t) return {"status": "accepted", "score": {"settings": N}, "detail": {"n": n, "strength": t, "settings": N, "distinct_settings": len(set(S)), "column_subsets": subsets, "pattern_checks": subsets * 3 ** t, "lower_bound": 3 ** t, "check": f"all {3 ** t} patterns on all {subsets} sets of {t} qubits are covered, checked " "exhaustively by bitset intersections", "verify_cpu_seconds": round(time.process_time() - t0, 3)}}