Mapping Pauli pools to F2 binary matrices lets the authors certify minimal complete pools in O(N³) by matrix rank and push NI-DUCC-VQE to a 26-qubit H2O

It proves the MCP Congruence Theorem: a bracket-independent set A of Pauli strings is an MCP for a given Pauli Lie algebra g if and only if there exists an invertible matrix P such that P^T ΓA P equals the canonical matrix of an MCP for g, i.e. ΓA is congruent to Γcanonical-MCP. Previously, completeness was decided by greedy construction over an exponentially growing candidate set, or by explicitly computing nested commutators and checking the algebra dimension; this work recasts the contraction of anti-commutation graphs as elementary row and column operations over F2, turning the problem into a matrix congruence relation. The theorem and corollaries are stated in the main text with full proofs in Supplementary Note 3; a worked example (Fig. 1) shows the modulo-2 row and column additions of ΓA under contraction.

It reduces verification of minimality and completeness to a rank evaluation of the ΓA matrices, giving O(N³) complexity in the number of qubits N, with corollaries that the rank of ΓA for an MCP is necessarily even and that two bracket-independent sets of equal cardinality with equal rank are both MCPs. Table 1 contrasts this with a full Lie-algebra check that is provable but exponential at O(4^N), and with product-group size plus inseparability and greedy pool construction that are polynomial at O(N³) but only numerically robust without a provable guarantee; the proposed method is both provable and O(N³). The complexity and guarantee comparison is given in Table 1, and the rank criterion draws on the classification of symmetric binary matrices with zero diagonal over F2 (citing a 2008 reference).

For quantum chemistry it introduces MB-ADAPT-VQE, which uses complete pools built from MCPs and appends a batch of k operators per iteration (k∈{1,5,10,20,30}); on H2O and H8, k=20 and k=30 converge faster to chemical accuracy with significantly fewer function evaluations than k=1 or k=5, and on strongly correlated stretched H6, k=10 reaches chemical accuracy with fewer than 50 parameters and about 200 CNOTs, whereas standard ADAPT-VQE needs nearly 150 parameters and more than 1600 CNOTs. Standard ADAPT-VQE uses an O(N⁴) QEB pool and must measure an energy gradient for every pool operator, giving a naive O(N⁸) measurement scaling per iteration; MCPs shrink the pool to O(N), immediately lowering the measurement cost to O(N⁵). Benchmarks cover LiH (12 qubits), H6 (12 qubits), H8 (16 qubits) and H2O (26 qubits), run on the Hyperion statevector emulator with Jordan–Wigner mapping, and are scored by energy accuracy, CNOT count, function evaluations and number of variational parameters, with chemical accuracy set at 1.6×10⁻³ Ha.

The framework removes the MCP construction bottleneck that previously limited NI-DUCC-VQE to N≤14 qubits, letting it reach chemical accuracy on stretched H6, H8 and a 26-qubit H2O, where k=25 reaches chemical accuracy in about 1500 function evaluations (16725 parameters, 99850 CNOTs). Prior applications of NI-DUCC-VQE were constrained by the computational cost of constructing the minimal complete pool; the rank criterion here enables pool construction at the 26-qubit scale. Results are presented as convergence curves in Fig. 3 together with parameter and CNOT counts; the authors note that the price of this classical speed is a very high CNOT count, which is challenging for current NISQ devices.

The framework targets Lie algebras with a natural Pauli-string basis, in particular su(2^N) and its subalgebras, and in quantum chemistry it addresses molecular systems with time-reversal symmetry and without external magnetic fields or relativistic corrections, so the ansatz is restricted to real values and the operators to odd Pauli strings. It is meant for quantum chemistry simulations using adaptive or fixed-ansatz variational quantum algorithms, and for settings that benefit from compact Pauli bases such as quantum error correction, quantum control, quantum machine learning and Hamiltonian simulation. Methodologically it provides a procedure to decide and construct pool completeness and minimality: start from physically motivated starters, extract a bracket-independent subset, check whether the rank of ΓA reaches the empirically validated target rank 2N−4, expand within the UCCSD pool if not, and in the worst case generate candidates on the fly from products of the current pool and symmetry-preserving operators, a fallback search with exponential worst-case cost.

The rank 2N−4 as the MCP rank of the restricted subalgebra currently rests on numerical evidence for the studied systems (pools reaching rank 2N−4 span the target subalgebra, and a leave-one-out test shows removing any single operator collapses the dimension of the generated Lie algebra), and the authors state that a general proof for this restricted subalgebra remains open. Characterizing the sub-Lie algebras and relating the ranks of these ΓA matrices to dynamical Lie algebras (DLAs) are still under investigation. Basis selection, the number of starters and the optimal selection algorithm are listed as open questions. MB-ADAPT-VQE lacks a very compact representation, which the authors suggest could be improved with overlap-driven compactification techniques. On the 26-qubit H2O system both approaches show signs of stagnation, which the authors attribute to vanishing gradients as system size grows and which may require techniques tailored to large, flat optimization landscapes. In addition, the k=25 NI-DUCC-VQE ansatz for H2O requires nearly 100000 CNOTs, which the authors note poses significant challenges for current NISQ devices, citing noise-resilience benchmarks showing that the allowable gate-error probability for chemical accuracy scales inversely with the number of entangling gates. This is an Article in Press version, Table 2's caption appears as a placeholder in the text, and details such as the H2O geometry, exact complete pool configurations and symmetry proofs reside in the supplementary material, so those details cannot be verified from the main text alone.