← All papers
First page of Compiling Matrix Formulas to Quantum Block Encodings

Compiling Matrix Formulas to Quantum Block Encodings

Daksh Shami, Charles Yuan

cs.PL Nov 13, 2026 · v1 quant-ph
The authors use Lean 4 to mechanize proofs that each of MARBLE's algebraic rewrite rules preserves matrix semantics and well-formedness of the symbolic form.
Realizing the promise of quantum applications such as chemistry or fluid dynamics requires building quantum circuits that efficiently encode and manipulate exponentially large matrices. This process forces researchers to grapple with the reality that a matrix expressible as one equation on paper can map to thousands of bit-level quantum logic gates, historically written by hand. Even worse, it often ends with a discovery that the needed resources grow so quickly with matrix size that the quantum algorithm loses its asymptotic speedup. In this work, we present MARBLE, a language that automatically synthesizes an efficient circuit from the publication-style formula for the entries of a matrix. MARBLE algebraically rewrites programs into symbolic combinations of simpler matrices that have known circuit realizations. It analyzes costs of possible representations, notably the subnormalization term that dominates time complexity. It then emits an OpenQASM circuit and certifies whether its cost is poly-logarithmic in problem size, as required by quantum algorithms. When evaluated on quantum applications ranging from fluid dynamics to physical Hamiltonians, MARBLE matches or surpasses 37 of 39 published baselines. On the low end, it automatically matches many theoretically optimal circuits, and on the high end, it improves on a published construction in fluid dynamics by 10,487x in subnormalization. MARBLE produces exponentially smaller circuits than the leading tool FABLE, and it successfully compiles matrices whose dimensions exceed 2^100 within five seconds on a laptop.

Quantum linear-algebra algorithms need efficient block-encoding circuits for exponentially large matrices. These circuits are usually written by hand from publication-style formulas, a process that is error-prone and can lose the asymptotic speedup.

MARBLE is a language in which users write entry comprehensions for matrix entries. Its compiler synthesizes mask formulas and applies algebraic rewrite rules to decompose the matrix into simpler matrices with known circuits. It then symbolically analyzes gate, qubit, and subnormalization costs, emits OpenQASM, and certifies poly-logarithmic cost. The rewrite rules are proven semantics-preserving in Lean 4.

MARBLE matches or surpasses 37 of 39 published block-encoding baselines and improves one fluid-dynamics construction by 10,487x in subnormalization. It produces exponentially smaller circuits than FABLE and compiles matrices of dimension above 2^100 in under five seconds.

Candidateαα(T+R)Q
Eq. (7)7.254720
Eq. (7), fewer qubits7.21,36812
Kuklinski et al.146~31,80027
FABLE64262,14413
Candidate block encodings for the lattice Boltzmann collision matrix F1