Tensor-network contraction

Why the full vector is optional

An amplitude is a multilinear function of the gates. Each gate is already a small tensor: two indices for a one-qubit unitary, four for a two-qubit unitary, plus indices that identify which wires it sits on. The circuit is therefore a network before anyone allocates a state vector. Contracting the network along a chosen order computes one amplitude, a batch of amplitudes, or an expectation value.

The saving appears only when intermediate tensors stay smaller than 2^n. That happens when the circuit’s entanglement, or the graph of qubit interactions, has a narrow cut. A deep, all-to-all random circuit does not have a narrow cut. A shallow circuit, or a circuit laid out along a line, often does.

Bond dimension

When a bipartition of the qubits is crossed, the number of independent correlations that must be kept is the bond dimension, usually written χ. A matrix-product state stores a chain of tensors whose shared index has size χ. If χ = 1 the state is unentangled across every cut. If χ grows to 2^(n/2) you have spent the same memory the state vector would have spent, and you have extra index overhead.

Algorithms that cap χ are approximate. They discard the smallest correlation weights at each cut. The truncation error is a research quantity, not a hidden constant: reports should state χ, the discarded weight, and the observable that was compared against an exact state vector on a size where both fit.

exact cost scales with intermediate tensor volume; χ_cap trades accuracy for memory

Contraction order is the algorithm

The order of pairwise multiplications changes the size of temporary tensors by exponential factors. Finding the optimal order is itself a hard combinatorial problem, closely related to treewidth of the line graph of the network. Heuristics — greedy scores, partitioning, and subtree reuse — are part of the method, not a preprocessing detail.

Slicing is the complementary lever. An index that would make an intermediate too large is fixed to a concrete value, the smaller contraction is repeated, and the slices are summed. Slices trade time for memory and are naturally parallel. A plan that ignores slice width will run out of memory on a graph that a sliced plan would finish.

• Contract the observable you need. Full-state reconstruction is rarely the goal.
• Record the contraction width, the peak intermediate size, and the slice count.
• Validate against a state vector whenever n is small enough that both methods fit.

Place in Kryptur research

Combinatorial encodings in the Kryptur programme often begin as graphs: paths, fleets, couplings. A tensor network is a different graph — indices instead of cities — but the planning habit is the same. Choose a cut, price the cut, and only then spend compute. When a QAOA layer is shallow, a tensor method can estimate a cost without holding every bitstring. When the layer entangles the whole register, the state vector or a hardware sample is the honest tool.