Reducing depth and measurement weights in Pauli-based computation

Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several new techniques for reducing the weight of the Pauli measurements and their associated $\text{textsc}cnot$ complexity; we also demonstrate how to decrease this model’s computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a pre-compilation step. We also propose a heuristic algorithm that can contribute reductions of over 30% to the average weight of Pauli measurements (and associated $\text{textsc}cnot$ count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 $T$ gates and over 20% for instances with larger $T$ counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the $\text{textsc}cnot$ count by 18% to 96% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger $T$ counts, it leads to a number of $\text{textsc}cnot$s roughly 30% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.