Fewest multiplications for a random-circuit output amplitude

Task

Submit a sequence of pairwise tensor contractions and a list of bonds to slice that computes one output amplitude <b|C|0> of a random quantum circuit. Minimize the number of scalar multiplications while keeping peak tensor storage within the instance limit. There are three circuit families.

• syc-*: Google's 2019 layout without qubit (2,3) (53 qubits) and the ABCDCDAB coupler pattern, with 12, 14, 16, 18 or 20 cycles. Their two-qubit gate structure is identical, layer by layer, to Google's published 2019 circuit n53_m20_s0_e0_pABCDCDAB (430 two-qubit gates at 20 cycles). Every gate, including each single-qubit gate, is its own tensor.
• rcs67-*, rcs70-*, rcs70p-*: Google's 2024 random circuit sampling circuits (Zenodo record 11663206; arXiv:2304.11119) on 67 and 70 qubits. An instance with m cycles uses the first m two-qubit layers of one published circuit: n67_full (32 cycles, ABCDCDAB) for rcs67, n70_m24 (24 cycles, ABCDCDAB) for rcs70, and n70_m26 (26 cycles, the repeating ABCD pattern) for rcs70p. The full published circuit is used when m equals its cycle count. Each two-qubit gate (fsim with its single-qubit dressing) is one tensor and all single-qubit gates are absorbed into it.
• h2-*: Quantinuum's H2 56-qubit random circuits (arXiv:2406.02501; github.com/cqcl/random-circuit-sampling), the XEB circuit of depth d with instance number 1: d dense layers of 28 RZZ(π/2) gates on random d-regular connectivity. Each RZZ gate is one tensor; single-qubit gates are absorbed.
• Each instance file lists the tensors and their connecting bonds: one rank-1 input tensor per qubit, one tensor per gate in time order, and one rank-1 output tensor per qubit. Every bond has dimension 2 and joins exactly two tensors.

Submission file

JSON structure:

{"slices": [17, 204], "path": [[0, 53], [1, 1650], ...]}

This shows the file structure. The verifier bundle contains a valid example.

• The initial tensors have IDs from 0 to T − 1. Contraction step s creates tensor T + s.
• The path has exactly T − 1 steps, and every ID except the final one is used exactly once.
• List at most 64 distinct bond IDs to slice.

Scoring

Sliced bonds are removed from every tensor. I_A is the set of unsliced bond indices on tensor A.

• Contracting A and B costs 2^{|I_A ∪ I_B|} multiplications and leaves a tensor with bonds I_A Δ I_B.
• The score is 2^|slices| × Σ_steps 2^{|I_A ∪ I_B|}, an exact integer. Fewer multiplications rank first; equal counts are ranked by submission number (lower first).
• Peak storage counts the maximum number of scalar elements stored while computing one slice: the sizes of all tensors that exist before a step plus the size of its result, counting the input tensors.
• The limit is 2^c scalar elements, where c is the number after “cap” in the instance name (for example syc-20-cap35 allows 2³⁵). At most 64 bonds may be sliced, so deeper circuits come with larger limits.

The cost model uses dense tensors and keeps each gate (syc-*) or each two-qubit gate (other families) as a separate tensor. Each slice repeats every contraction, and the score counts multiplications only. Published contraction costs use other models (gate decompositions, hyperedges, reuse between slices) and are not directly comparable. Literature: Gray and Kourtis (cotengra); Pan, Chen and Zhang (arXiv:2111.03011).

Application

The task measures the multiplication cost of computing one circuit amplitude under the stated contraction model, for the circuits of three published quantum-advantage experiments.

Current records

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