wai-quantum 0.3.27: Gaussian boson sampling, exactly #145
Loading…
Reference in a new issue
No description provided.
Delete branch "wai-quantum-gbs"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Stacked on #144, which is stacked on #143. Merge them in order; until then this diff also shows their commits.
What
wai-quantum0.3.27 adds exact Gaussian boson sampling. A photonic sampler's outcome probabilities are matrix functions of its Gaussian state:Both are #P-hard. That hardness underlies every photonic advantage claim, and computing them exactly is how such a claim is checked wherever it can be.
hafnianuses power traces, a sum over 2^{n/2} pair subsets. The traces come from a Hessenberg reduction, La Budde's characteristic polynomial and Newton's identities, for O(n³·2^{n/2}) in total.torontoniansums by inclusion and exclusion over subsets of the clicked modes.GaussianStatedescribes squeezed vacua through an interferometer with uniform loss. It holds the complex covariance in the (a, a†) basis.click_probabilityandphoton_probabilitygive exact pattern probabilities, andsample_clicksdraws exact samples mode by mode from marginal torontonians.click_marginalsandcheck_samplescompute the one- and two-mode click statistics that every sampler of the state must reproduce. These are polynomial in the number of modes, so they are computable at experiment scale. Observed patterns are then held to them by z-score.wai-quantum gbs --squeezing … [--eta --seed | --unitary U.json] [--sample K | --check FILE] [--json]Evidence
Against an independent implementation
The growing difference with size comes from the alternating 2^{n/2}-term sum, which loses precision on either side.
Timing, this module against the independent implementation on the same machine:
Tests
check_samples, while the same samples tested against a different interferometer fail it.Mutations. Each of these fails a named test:
Removing the conjugate in A = X(I − Q⁻¹)* changes nothing, and correctly so: the hafnian of a conjugate is the conjugate of the hafnian, and probabilities are its real part.
Determinism and suite
bit_identitypins a 24×24 hafnian and a 14-click torontonian. Both run threaded natively and in sequence under WASI. It also pins probabilities, samples and marginals; all 12 pins pass on both targets.gbsoutput is byte-identical natively and as a WASI component, including a 16-mode all-click probability that runs the threaded torontonian.cargo test --locked --features full --lib --tests(debug): 371 + 12 + 2 + 3 passed. Every feature builds alone with zero warnings, and clippy is clean on the new code.Honest boundaries
🤖 Generated with Claude Code
quantum_tn turns a circuit (any unitary on any qubits, as a matrix) into the tensor network of one amplitude or an open-output batch, and contracts it. - Network::amplitude builds the network; simplify absorbs vectors and one-qubit gates into neighbours. - find_path is a seeded hyper-optimiser over two tree families: - randomised greedy, scoring size(out)/c - c(size(a)+size(b)) with Gumbel noise; - recursive bipartition, multilevel (heavy-edge coarsening, several initial cuts, refinement at every level), with greedy leaves. Families alternate until one leads; later trials sample near the best parameters. The best few trees are reconfigured: subtrees of up to eight tensors are re-contracted optimally by subset dynamic programming, until nothing improves. - slice fixes the index that leaves the least total work until the largest intermediate fits the cap, pricing each candidate incrementally. A second search round then finds a tree for the network with the first round's slices fixed (all, or the more valuable half). - contract_plan contracts every slice in a fixed accumulation order and sums them in order. Threads are bounded by an 8 GiB budget; WASI runs sequentially. The bits are the same everywhere. Measured on single amplitudes of random circuits on the 54-qubit advantage-experiment grid (fSim(pi/2, pi/6), staggered couplers), 256 trials, under ten seconds each, in log10 operations: m = 10: 10.48 m = 12: 13.91 m = 14: 14.63 m = 16: 17.60 m = 20: 18.77 An independently developed hyper-optimiser, given the identical networks, lands within 0.4 of these at every depth, in either direction. The 54-qubit, 10-cycle amplitude, contracted here in 16 slices, agrees with an independent contraction to 12 significant figures. Tests: - Amplitudes match a dense state vector for every tree family, with reconfiguration and with slicing. - Reconfiguration reaches the exact optimum on 40 random small networks. - Incremental slice pricing matches a full recount. - The same seed gives the same plan. - Mutating the permutation, the complex product, the contraction's summed indices, slice pricing, the slice offset or the reconfiguration DP fails a named test. - bit_identity pins a plan and its sliced, threaded amplitude natively and under wasm32-wasip2. CLI: wai-quantum tn --file CIRCUIT.jsonl [--bits --open --trials --seed --cap-log2 --plan-only --json], byte-identical natively and under wasm32-wasip2. Co-Authored-By: Claude Opus 5.5 <[email protected]>A photonic sampler's outcome probabilities are hafnians (photon-number detection) or torontonians (threshold detection) of its Gaussian state. quantum_gbs computes both exactly and reproducibly. - hafnian: power traces, a sum over 2^{n/2} pair subsets, each the lambda^{n/2} coefficient of exp(sum tr(B^k) lambda^k / 2k). The traces come from a Householder Hessenberg reduction, La Budde's characteristic polynomial and Newton's identities: O(n^3 2^{n/2}). - torontonian: inclusion-exclusion over the 2^m clicked-mode subsets. - Both sums run in 64 fixed chunks, threaded natively and sequential on WASI, added in chunk order, so the bits do not depend on threading. - GaussianState: squeezed vacua through an interferometer with uniform loss, as the complex covariance in the (a, a-dagger) basis. - click_probability, photon_probability: exact pattern probabilities. - sample_clicks: exact samples, drawn mode by mode from marginal torontonians. - click_marginals, check_samples: the one- and two-mode click statistics every sampler of the state must reproduce, polynomial in the modes, and a z-score check of observed patterns against them. Against an independent implementation: - click probabilities of three lossy states, every pattern: 1.1e-10; - photon probabilities up to four photons: 2.3e-13; - hafnians: 1.5e-12 up to 20x20 and 4.5e-8 at 36x36, where the alternating sum loses precision on either side. A 36x36 hafnian takes under 2 s. Tests: - hafnians match exhaustion over matchings, and (2k-1)!!; - squeezed vacuum reproduces its textbook click and photon statistics; - click probabilities sum to one with loss; - exact samples reproduce marginals and full-pattern frequencies, and pass the check, while a different interferometer fails it. Mutating the hafnian sign, La Budde's recurrence, Newton's identities, the torontonian sign or the loss channel fails a named test. bit_identity pins a 24x24 hafnian and a 14-click torontonian (threaded natively, sequential under WASI), probabilities, samples and marginals, on both targets. CLI: wai-quantum gbs --squeezing ... [--eta --seed | --unitary] [--sample K | --check FILE] [--json], byte-identical natively and under wasm32-wasip2. Co-Authored-By: Claude Opus 5.5 <[email protected]>