Fewest emitter-emitter gates for photonic graph states

Task

Each instance file gives a graph G on the vertices 0 to n−1 as a sorted edge list. The target is the graph state |G⟩ on n photons, with photon v playing vertex v: the unique state with K_v|G⟩ = |G⟩ for every v, where K_v = X_v ∏_{u adjacent to v} Z_u. Equivalently, |G⟩ is |+⟩^⊗n followed by one CZ gate per edge.

Photons cannot interact with each other. They come from quantum emitters: an emission creates a photon that is entangled with its emitter, and gates between emitters supply the rest of the entanglement. Write a sequence of emitter operations that leaves the photons in |G⟩ for every measurement outcome. Use no more emitters than the instance allows, and as few emitter-emitter gates as possible.

• grid-a×b: a rows and b columns; vertex (i, j) is i·b + j, with edges to the right and lower neighbours. At most min(a, b) + 1 emitters.
• tree-b×h: the complete b-ary tree of depth h in breadth-first numbering, so the children of v are b·v + 1 to b·v + b. At most h + 1 emitters.
• rep-m: the repeater graph on 2m photons, a complete graph on 0 to m−1 with a leaf m + i attached to each vertex i. At most 2 emitters. These are calibration instances.
• Every graph also has a -wide copy that allows one emitter per photon. These copies are debug instances and are not compared with the capped versions.

Submission file

JSON structure:

{"emitters": 1,
 "ops": [["RX", 0], ["EMIT", 0, 0], ["MX", 0]],
 "local_cliffords": [{"x": "+X", "z": "+Z"}],
 "photon_corrections": [{"x": [], "z": [0], "x_const": 0, "z_const": 0}]}

This example makes the one-photon graph state |+⟩. It shows the format and is not an instance; the verifier bundle contains an accepted file for grid-8x8.

• emitters: the number of emitters E, from 1 to the instance limit. Emitter labels are 0 to E−1, and every label must appear in ops.
• ops: at most 32,768 operations, applied in order. Each one has one of these exact forms:
  • ["RZ",e], ["RX",e] prepare emitter e in |0⟩ or |+⟩. This is allowed only before the emitter's first use or after it was measured; an emitter that is in use cannot be reset.
  • ["H",e], ["S",e], ["S_DAG",e], ["X",e], ["Z",e] are single-emitter gates.
  • ["CX",c,t] (control c, target t) and ["CZ",a,b] act on two different emitters. They are the only emitter-emitter gates. Any other two-qubit gate, such as SWAP or controlled-Y, has to be written with them.
  • ["EMIT",e,v] creates photon v in |0⟩ and applies CX with emitter e as control and photon v as target. Every photon 0 to n−1 is emitted exactly once, and no other operation acts on a photon.
  • ["MZ",e], ["MX",e] measure emitter e in the Z or X basis. Each measurement appends one record bit (0 for the outcome +1, 1 for −1), numbered 0, 1, 2, … in order. The emitter cannot be used again until it is prepared. At most 4,096 measurements.
  • ["PX",e,bits,value], ["PZ",e,bits,value] apply X or Z to emitter e when the XOR of the listed earlier record bits equals value (0 or 1). bits is strictly increasing; an empty list has XOR 0.
  Emitters may still be in use at the end, provided the photons are no longer entangled with them.
• local_cliffords: one entry per photon, {"x": P, "z": Q}, where P and Q are taken from +X, −X, +Y, −Y, +Z, −Z and lie on different axes. The entry is the single-photon gate U with U X U^† = P and U Z U^† = Q, hence U Y U^† = i P Q. All 24 single-qubit Clifford gates can be written this way.
• photon_corrections: one entry per photon, {"x": [...], "z": [...], "x_const": a, "z_const": b}. Photon v receives X when a XOR the records listed in x is 1, and Z when b XOR the records listed in z is 1. The lists hold strictly increasing record indices. The constants work differently from PX and PZ: here the constant is XORed in, while PX and PZ fire when the XOR equals value.
• At the end, every photon first gets its local Clifford gate and then its correction. This order is part of the definition.
• Parsing is strict: exact keys at every level, no duplicate keys, and integers must be JSON integers (not true or 1.0).

Validation

The verifier simulates the operations on a stabilizer tableau with exact arithmetic over GF(2):

1. It checks the format, the emitter life cycle, the photon labels and the limits.
2. It follows the joint state of all photons and emitters. A measurement with a random outcome gets a new symbol, and every sign in the state and every record bit is kept as an exact XOR formula in these symbols, so no outcome is sampled or skipped.
3. After the local Cliffords and corrections, it checks for every vertex v that K_v, with identity on the emitters, is a stabilizer of the final state with sign +1 for every combination of outcomes.

The n checks hold exactly when the photons are in |G⟩ and unentangled with the emitters in every run. A state that is right for only some outcomes, or a photon that is still entangled with an emitter, is rejected, and the report names the vertex that fails. On one PC core, the largest files the limits allow verify in about a second.

Scoring

Each instance is ranked by its number of emitter-emitter gates, CX plus CZ. Fewer gates rank first; equal counts are ranked by fewer emitters, then by submission number (lower first). Emissions, single-emitter gates, measurements, conditional Pauli gates and the final photon operations cost nothing. There is no time or duration score.

Baseline and reference scores

The QArena baselines for grids and trees use chain growth. When an emitter emits photon v and then applies H to itself, photon v takes over the emitter's vertex together with its edges, and the emitter becomes a new vertex joined to photon v. Edges made this way need no emitter-emitter gate; this is how a single emitter produces a linear cluster state (Lindner and Rudolph, arXiv:0810.2587).

• Grids: one emitter per rail along the longer side grows its rail by chain growth. Each edge between neighbouring rails is one CZ, so the count is b(a−1) for a ≤ b, with min(a, b) emitters. Linking the chains of neighbouring emitters with CZ gates goes back to Economou, Lindner and Rudolph, who proposed it for 2×N cluster states (arXiv:1003.2410). Grid 2×3 is the exception; its baseline is described below.
• Trees: an emitter attaches leaves for free (the leaf photon gets H as its local Clifford). Its path through the tree can climb and then descend: it builds a vertex's first non-leaf child, turns into the vertex by chain growth, and later continues by chain growth into the vertex's last non-leaf child. Every other non-leaf child is built the same way on another emitter and joined with one CZ.

The streaming construction of the board specification keeps every graph vertex on an emitter prepared in |+⟩, applies one CZ per edge, and moves each finished vertex to its photon with an emission, an X measurement and a Z correction, reusing the emitter. It uses exactly the emitter limit, and the verifier's tests keep it as a known answer with the counts in the last row.

For the repeater graphs, the baseline is a two-emitter construction with m−2 gates: 2, 4, 6, 10 and 14 for m = 4, 6, 8, 12 and 16. This is the count of Takou, Barnes and Economou (arXiv:2407.15777), who state that it is optimal in their protocol model; this verifier checks the construction but does not prove that it is optimal. In the construction, emitter B holds a hub vertex and emitter A builds each spoke (a core photon with its leaf), attaching it to the hub with one CZ. The first spoke comes from B alone. A local complementation at the hub (local Clifford gates on the hub and its neighbours, which toggle every edge between two neighbours) then turns the spokes into a complete graph, and B emits the last leaf and core. Each -wide baseline puts every vertex on its own emitter, giving one CZ per edge with n emitters.

No published count is known for the grids and trees under these emitter limits. Li, Economou and Barnes give an algorithm that finds the minimum number of emitters for a fixed emission order, together with a protocol (arXiv:2108.12466); it is a natural starting point for improving the baselines.

Two lower bounds hold for every protocol. In them, the cut rank of a set of photons is the number of ebits the set shares with the other photons in |G⟩, which is the GF(2) rank of the adjacency matrix between the set and the rest.

• Emitters. For a given emission order, a protocol needs at least as many emitters as the largest cut rank of the photons emitted so far (Li, Economou and Barnes). For every capped instance with at most 16 photons, the smallest value of this bound over all emission orders is the number of emitters the QArena baseline uses.
• One gate. With a single emitter-emitter gate, only the two emitters it joins can emit photons, because G is connected. The photons an emitter sends out before the gate reach the other qubits only through that emitter, so for every k the first k of them share at most one ebit with the rest. The photons it sends out after the gate come from that emitter alone, so the last k of them share at most one ebit with the rest. The two emitters' photon sets share at most the one ebit the gate made. Measuring and re-preparing an emitter does not help: photons sent out before a reset are in a product state with everything after it, and G is connected. An exhaustive computer check over every way to split the photons into these four groups finds no split that meets all these limits for grid 2×3 or tree 2×3.

So 2 gates with 2 emitters is the best possible score for both instances. The tree 2×3 baseline already reaches it. For grid 2×3, chain growth needs 3 gates; an exhaustive computer search over protocols with at most two gates, comparing photon states up to local Clifford gates, found one with 2 gates and 2 emitters, and that protocol is the QArena baseline.

Application

Deterministic photonic graph states are resource states for measurement-based quantum computing and for all-photonic quantum repeaters. Entangling gates between emitters are a costly step in hardware, so a protocol that needs fewer of them under a fixed emitter budget lowers the cost of producing these states. The score does not model photon loss, emitter decoherence or emission timing.

Current records

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