C.29.2:5.3 - Count a dense state before allocating it

Question. Can a proposed dense numerical pure-state array for 50 qubits fit in a 64 GiB memory budget? The representation stores one complex amplitude for each binary string of length 50. There are two choices at each position, hence 2^50 entries. Stipulate 16 bytes per stored complex value: two 8-byte components.

The payload alone is:

16 × 2^50 = 2^54 = 18,014,398,509,481,984 bytes,

or 16 PiB = 16,777,216 GiB, where 1 GiB = 2^30 bytes and 1 PiB = 2^50 bytes. Since 64 GiB = 2^36 bytes, the payload exceeds the budget by a factor of 2^18 = 262,144. Workspace, copies and indexing cannot reduce this payload requirement. This rejects the proposed dense allocation without building the simulator.

The count is tied to a representation. It says nothing by itself about the cost of every way of answering a quantum-modeling question. Using 8 bytes per amplitude halves the payload to 8 PiB and still fails this budget; it also changes numerical precision. Discarding small amplitudes requires an error argument for the requested output. Calling the representation sparse supplies no bound on the number of retained entries or on growth during its operations.

Construct a restricted alternative. Suppose the admitted states are products of 50 normalized single-qubit pure states, every operation is a single-qubit unitary gate, and the requested output is the probability that a named qubit is read as 1. Store the 50 pairs (alpha_i, beta_i) instead of the full array. The corresponding joint amplitude for bit string s is the product, over positions i, of alpha_i when s_i=0 and beta_i when s_i=1.

Initialize each pair from its supplied single-qubit state. For a gate with unitary 2-by-2 matrix U on qubit i, replace just that pair by U*(alpha_i,beta_i), retaining the old two values while computing both new ones. The tensor-product rule preserves the product form, and unitarity preserves the pair’s normalization. For normalized pairs, return |beta_i|^2. The payload is now 50 × 2 × 16 = 1,600 bytes, with additional algorithm and representation overhead to be counted separately.

Starting with all pairs (1,0), apply the Hadamard operation (a,b) -> ((a+b)/sqrt(2),(a-b)/sqrt(2)) to the first pair. It becomes (1/sqrt(2),1/sqrt(2)), and the requested probability for the first qubit is 1/2. The construction uses a fixed number of complex operations per gate and stores only the pairs. Its structural factorization is exact under the admitted model; stored numerical coefficients still require their precision account.

An entangling gate can invalidate that representation. The two-qubit state with nonzero amplitudes 1/sqrt(2) at 00 and 11 and zeros at 01 and 10 cannot be one product: nonzero alpha_0*alpha_1 and beta_0*beta_1 would make all four factors nonzero, contradicting a zero cross term. The product procedure must therefore reject that extension or receive a richer representation and update algorithm. Even in the product class, requesting all 2^50 amplitudes explicitly restores an exponential output count.

First result and next contribution. The original dense proposal is ruled out. The factorized procedure answers the separately stated restricted question; it is not a replacement for an unspecified general circuit. To continue, recover the actual input-state and gate family, requested observable or samples, and tolerated error, then obtain and cost an applicable domain algorithm. The general method supplied the count and the construction question; quantum simulation supplies the representations and update/readout algorithms.