Exact

Exact Union RegExp

Repository files (latest commit first)

Filename	Latest commit message	Latest commit date
Transaction Science b3c62ae7f4 WAI Quantum: a fast deterministic dense SVD, and the all-to-all peaked 56x1917 read on a chain ... The tracker's all-to-all peaked circuit P9_Hqap_56x1917 is read: its peak is the string the published solution (arXiv:2604.21908) checks its samples against, found in 139 s with 16 threads on a shared 32-core CPU host. The published run took an hour on a GPU and 734 s on a laptop CPU. It needed a dense SVD fast at bonds in the hundreds; the tensor networks' was scalar. quantum_svd (new module, with quantum_bptn): complex SVD, thin QR and product for matrices a few thousand on a side, our own code. Householder reduction to a real bidiagonal (a step's two updates sharing two passes over the trailing matrix; a matrix twice as tall as wide to its triangle first), the implicit-shift QR iteration of Demmel and Kahan with its rotations recorded and applied in panels of eight columns, the reflections back onto the kept vectors 32 at a time as I - V T V^H. Keep::Truncate forms only the kept vectors, Keep::Values the values alone. Every number is formed by one worker in an order the shape fixes, row sums go in blocks of 64 rows added in block order, no FMA, no library call: the same bits at any thread count and on arm64 and x86_64. examples/svd_bench.rs: one thread of a shared x86_64 host, 1.5 ms at 64^2, 59 ms at 256^2, 0.40 s at 512^2 (the Jacobi rotations 22 ms, 0.79 s, 5.8 s), 3.2 s at 1024^2, 28 s at 2048^2; the twelve matrices' hashes equal at 1, 4 and 16 threads and on macOS arm64 (tests/data/svd, tests/svd_bench.rs). quantum_peaked::chain (new): the published method in our own code. The blocks cut at half, those before on the operator's columns, those after on its rows, the side with fewer gates going next; each side routed onto a chain online by a lookahead heuristic; every two-site operation a TEBD update of the operator as a state of local dimension 4, truncated at a relative cutoff and a cap, the norm in an exact scale; past 10^6 numbers a SWAP of both indices, the columns or the rows tried on every bond and kept as a relabelling where it shrinks the bond. A layer's operations and a pass's trials run side by side on disjoint pairs, committed in order. route_both routes by whole sites, a qubit's row and column together: the published routing moves one side's index, and a row moved from its column costs a bond. Peak by exact conditional decoding, exact sampling, any string's amplitude. 56x1917 (tracker_peaked chain route=both): at most bond 512 and 975,352 numbers, 17,341 routed SWAPs, 813 kept by unswapping of 9,033 tried, 2.3e-4 discarded, 388 MB. Peak 01101110111001100000100000001010011100101101010111110111 (qubit 0 first), the published string, |<s|C|0>|^2 = 0.0999, 103 of 1000 exact samples (the published run: about 10.6%). chainverify at cutoffs 1e-3 and 5e-4: 0.09999. Routed as published: the same peak and 0.09996 in 762 s. Linux arm64 and macOS arm64 give every number of the x86_64 receipt, bit for bit. Tests: SVD reconstruction and orthonormality on full-rank, rank-deficient, graded, zero and extreme-scale matrices, the same bits across thread counts; chain amplitudes exact untruncated from any cut, a planted peak, a hidden permutation stripped by unswapping; tests/tracker_peaked.rs re-runs the 56x1917 operator's first 62 layers to the bits its receipt logs and checks the receipts; the P9 circuit kept as a fixture (unmodified, Apache-2.0). Co-Authored-By: Claude Opus 5.5 <[email protected]>		2026-11-12 10:29:47 -05:00
..
inputs.rs	WAI Quantum: a fast deterministic dense SVD, and the all-to-all peaked 56x1917 read on a chain	2026-11-12 10:29:47 -05:00