Skip to main content
Back to timeline
arXivSource publication:

Matrix formulas compile straight into quantum block encodings: MARBLE matches or beats 37 of 39 published baselines

Synopsis

Quantum algorithms need exponentially large matrices encoded efficiently into circuits, yet such circuits have mostly been built by hand or assumed sparse. MARBLE takes a formula for each matrix entry, uses static multiplicity to guarantee a fixed number of distinct entry expressions, and applies algebraic rewriting plus cost analysis to emit OpenQASM. Across 74 matrices from fluid dynamics, PDEs and physics Hamiltonians, it matches or surpasses 37 of 39 published baselines in subnormalization and compiles very large dimensions in under five seconds on a laptop.

Source-provided article image: Compiling Matrix Formulas to Quantum Block Encodings
Fig. 14 · arXiv · Page 5

Interpretation

Instead of enumerating entries and hand-building a circuit, a researcher writes the entry formula and the compiler synthesizes the corresponding quantum block encoding. The general-purpose tool FABLE builds circuits entry by entry with cost polynomial in matrix dimension, while Qualtran and Qrisp supply ready-made circuits only for specific sparse matrices, and Cobble composes block encodings but cannot encode arbitrary matrices. On 74 matrices drawn from fluid dynamics, partial differential equations and physics Hamiltonians, MARBLE matches or surpasses 37 of 39 published circuit baselines in subnormalization, including a 10,487-fold improvement over the D3Q27 Carleman matrix of Penuel et al.

The compilation separates a matrix's structure from its data and measures structure by multiplicity rather than sparsity. Sparsity is only a rough proxy for the existence of an efficient block encoding: a random diagonal matrix has one nonzero per row yet still needs one load per entry, while the dense quantum Fourier transform has an efficient circuit. MARBLE requires each entry to be computed by a fixed number of distinct expressions, called static multiplicity, which the type checker guarantees at compile time; the compiler then rewrites the program into mask formulas combined symbolically with known circuits and computes subnormalization, gate and qubit counts symbolically.

The compiler also certifies whether the emitted circuit actually meets the asymptotic efficiency quantum algorithms require. Earlier tools could not tell whether a given block encoding was near-optimal for a matrix, or whether any block encoding could realize the algorithm's speedup at all. MARBLE symbolically checks whether per-iteration gates and qubits grow poly-logarithmically with dimension, whether the ratio of subnormalization to the spectral-norm lower bound converges to a constant, and whether the spectral norm itself is bounded; for six matrices it correctly concludes that no efficient encoding exists.

Perspective

The demonstrated scope is 74 matrices from lattice Boltzmann methods, finite elements, finite differences, physics Hamiltonians and structured Markov processes; output circuits are numerically compared with NumPy-computed matrices at small dimensions. For structured Markov processes, MARBLE produces what it describes as the first explicit block-encoding circuits.

MARBLE can only represent matrices with static multiplicity, so it cannot represent the Heisenberg random-field model or the SYK model, which require loading explicit coefficients that grow with dimension. Gate counts are in the Clifford+T gate set, and arbitrary-angle rotations are either left in the output or estimated at a fixed number of T gates each. Rewrite rules are currently hand-written and incomplete, and the exploration stage has a fixed node cap that may affect whether the best block encoding is found.