Fewest Pauli measurement settings that cover every 3- or 4-qubit observable

Task

A measurement setting measures each of the n qubits in one of the Pauli bases X, Y or Z. One setting gives samples of every Pauli observable that agrees with it on that observable's qubits: a setting that measures qubits 3, 7 and 9 in X, Y and Y gives samples of X₃Y₇Y₉, and of every observable on fewer of those qubits. Choose as few settings as possible such that every Pauli observable of weight t, on every set of t qubits, agrees with at least one setting. In combinatorics such a list is a covering array CA(N; t, n, 3) written with the letters X, Y and Z: for every set of t columns, each of the 3^t patterns appears in some row.

• pc3-n4: 4 qubits, strength 3, at most 512 settings. A debug instance.
• pc4-n5: 5 qubits, strength 4, at most 1,024 settings. A debug instance.
• pc3-n40: 40 qubits, strength 3 (every observable on 3 qubits), at most 512 settings.
• pc4-n100: 100 qubits, strength 4 (every observable on 4 qubits), at most 1,024 settings.

Every set of t qubits counts, whether or not its qubits are neighbours. Strength t also covers every observable of lower weight, because its qubits lie in some set of t qubits. A setting shows only one pattern on a given set of t qubits, so at least 3^t settings are needed (27 for strength 3, 81 for strength 4). The debug instances reach that bound. On 40 and 100 qubits the best known arrays are far above it, and no exact optimum is known.

The score counts settings in this fixed X/Y/Z model only. Measuring in other local bases changes the task, and counts obtained that way are not comparable with this board.

Submission file

JSON structure:

{"settings": ["XYZX", "YZZY", "ZXYZ"]}

This shows the file structure only. The verifier bundle contains a complete accepted file for pc4-n100; every instance's baseline is listed on its leaderboard.

• The file is a UTF-8 JSON object without a byte-order mark and with exactly one key, settings. Duplicate keys, NaN and Infinity are rejected. The file may have at most 262,144 bytes, whitespace included; a larger file is rejected before it is parsed. In compact JSON, 1,024 settings of 100 letters take about 106 KB.
• settings is a list of 1 to 512 strings on strength-3 instances and 1 to 1,024 on strength-4 instances.
• Each string has exactly n characters, and each character is one of the capital letters X, Y and Z. Character i is the basis of qubit i; qubits are numbered 0 to n − 1. JSON escapes are decoded first, so \u0058 counts as X.
• Repeated settings are allowed, and each copy counts.
• Do not claim coverage: the verifier checks it.

Validation

• The verifier checks the format, the number of settings and every character.
• For every set of t qubits q₀ < … < q_t−1 and every one of the 3^t patterns, it requires a setting with that pattern on those qubits: 9,880 sets and 266,760 patterns on pc3-n40, 3,921,225 sets and 317,619,225 patterns on pc4-n100. Nothing is sampled.
• For every qubit and letter, the verifier stores the settings with that letter on that qubit as a bit string. The settings that show a pattern on a set of qubits are the intersection of these bit strings. Taking the qubits of a set in increasing order, the intersections for its first qubits (3, then 9, then 27 of them) are computed once and reused for every later qubit. An empty intersection means a missing pattern, and the rejection names one set of qubits and one pattern that no setting measures. The file is accepted only after the last pattern has been found.
• A second program, written independently from the specification, enumerates the patterns of each set of t qubits directly on small instances. On pc4-n100 it encodes the first three letters of every setting as a number and checks all later qubits at once with numpy. It agreed with the verifier on every test case.
• Limits: 600 CPU seconds and 256 MiB of memory. Measured on pc4-n100 with 1,024 settings and every pattern present (the worst case): 13.5 CPU seconds and 21 MB on one core of an AMD Ryzen 9 9950X. The 633-setting baseline takes 13.0 seconds. If the check does not finish, the result is an error, which is not ranked.

Scoring

The score is the number of settings, and fewer rank first. Equal counts are tied and ranked by the earlier submission. There is no secondary score, so covering some patterns more often earns nothing. The score counts the measurement configurations in your list, repeated ones included, and says nothing about how many shots an experiment needs.

Baseline and reference scores

Both reference arrays were downloaded from the ca-tools table on 2026-11-14 and checked here over every pattern; both are accepted (the table's CA(86; 3, 40, 3) of 2026-11-15 was checked the same way). The table says CA(87; 3, 40, 3) came from column extension, tabu repair and row deletion, starting from a CA(87; 3, 39, 3) by Shokri and Moura, and CA(633; 4, 100, 3) from row deletion with local repair of CA(636; 4, 100, 3). Renaming the letters on any qubit or permuting the qubits keeps an array valid, so any covering array with three symbols can be submitted after renaming its symbols.

Application

Experiments that estimate all low-weight Pauli observables, or all reduced states of k qubits, of a device with many qubits (quantum overlapping tomography, Cotler and Wilczek, arXiv:1908.02754) choose a list of product Pauli settings that covers every observable on every set of k qubits. The link between such measurement schemes and covering arrays is developed in Hansenne et al., Optimal Overlapping Tomography, arXiv:2408.05730. Each setting is a separate configuration of the device, so fewer settings mean less reconfiguration. If every setting is repeated the same number of times, every observable gets at least that many samples.

Current records

Reference scores come from cited papers or derived constructions. Only accepted submissions can hold a QArena record.