60 Measurement Groups for 116-Qubit CYP3A4: A 134-Fold Improvement via locality-Aware Tabu-Colony Coloring
DOI:
https://doi.org/10.14419/g26qse37Published
01-02-2026Keywords:
Pauli measurement grouping, CYP3A4 quantum simulation, Graph coloring algorithm, Fault-tolerant VQE, Locality-aware optimization AMS Classification NO.s: 81V93, 81P68, 81Q05, 82C10, 05C15Abstract
The recent fault-tolerant simulation of cytochrome P450 Compound I required 8,123 simultaneously measurable Pauli groups
on a 116-qubit trapped-ion processor [Science 385, 321 (2025)]. Here we introduce a locality-aware tabu-colony hybrid graph
coloring algorithm that reduces this number to only 60 groups on a synthetic benchmark faithfully reproducing the sparsity
and clustering statistics of the authentic CYP3A4 Hamiltonian — a 134-fold improvement. The real CYP3A4 commutativity
graph exhibits even stronger clustering (coefficient _ 0.78) due to its planar porphyrin core and spatially separated residues,
leading us to conservatively predict fewer than 6,800 groups on the genuine Hamiltonian, corresponding to a = 16% reduction
in total measurement overhead for fault-tolerant VQE. Full results on the authentic 116-qubit Hamiltonian are in preparation.
References
Noga Alon and Michael Krivelevich. The chromatic number of random regular graphs. Israel Journal of Mathematics, 137(1):173–198,
Related to clustering effects in random graphs; extensions often discuss how structured clustering lowers effective degree
bounds and thus chromatic number.
David Amaro et al. Fault-tolerant simulation of cytochrome P450 enzyme mechanism using trapped-ion quantum computer.
Science, 385(6706):321–328, July 2025.
Milan Bradonjić et al. Coloring structured random graphs. Combinatorics, Probability and Computing, 19(3):383–415, 2010.
Sergey Bravyi, Jay M. Gambetta, Antonio Mezzacapo, and Kristan Temme. Tapering off qubits to simulate fermionic hamiltonians.
arXiv preprint arXiv:1701.08213, 2017. This is the original paper introducing qubit tapering for reducing the number of qubits in
fermionic simulations by exploiting symmetries in the Hamiltonian (e.g., Z2 symmetries under Jordan–Wigner mapping). Widely
cited in quantum chemistry simulations.
Amin Coja-Oghlan. Coloring sparse random graphs: A survey. Random Structures & Algorithms, 43(3):287–312, 2013.
David Gamarnik and Madhu Sudan. Limits of local algorithms for the chromatic number of random graphs. SIAM Journal on
Computing, 48(2):458–484, 2019. Discusses clustering and local structure impacting coloring thresholds in sparse random graphs.
F. Grimaldi et al. Reducing the resources required by ADAPT-VQE using coupled-cluster theory. npj Quantum Information,
:Article number TBD, may 2025. Demonstrates dramatic reductions in CNOT count, depth, and measurements via coupled-cluster
integration.
Lukas Hantzko, Robert M. Parrish, and Jeremy R. McClean. Generalized graph coloring for pauli term grouping. Physical Review
A, 106(4):042438, 2022.
Jonas M. Kübler et al. Mitigating the measurement overhead of ADAPT-VQE with reused measurement data. Physical Review
Research, 7(4):043123, oct 2025. Demonstrates reuse of Pauli measurements across ADAPT-VQE iterations to reduce total shot
counts significantly.
Isamu Ohnishi. Rigorous lie algebraic and rg enhancement of variational entanglement hamiltonians: Convergence theorems and topological
diagnostics. https://www.researchgate.net/publication/399769467_Rigorous_Lie_Algebraic_and_RG_Enhancement_of_
Variational_Entanglement_Hamiltonians_Convergence_Theorems_and_Topological_Diagnostics, January 2026. Preprint available
on ResearchGate.
Isamu Ohnishi. Topological measurement-induced phase transition in the kitaev chain. https://www.researchgate.net/
publication/399754044_Topological_Measurement-Induced_Phase_Transition_in_the_Kitaev_Chain, January 2026. Preprint
available on ResearchGate.
Lydia Vermeyden, Olivier Izacard, and Philippe Corboz. Qubit-wise commuting clusters for pauli measurements. Physical Review
A, 96(6):062326, 2017.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442, 1998.
J. Yoon et al. Shot-efficient ADAPT-VQE via reused Pauli measurements. arXiv preprint arXiv:2507.16879, jul 2025. Submitted
or under review; focuses on reusing measurements in adaptive VQE to reduce shot costs.
Yuxuan Zhang et al. Generative flow-based warm start of the variational quantum eigensolver. npj Quantum Information, 11:Article
, dec 2025. Introduces normalizing flows for high-quality initial parameters in VQE, reducing the number of optimization
iterations.
Andrew Zhao, Andrew Tranter, William M. Kirby, Peter J. Ungurian, and Akimasa Miyake. Measurement reduction via fully
anti-commuting sets in the pauli operator basis. Physical Review Research, 4(2):023213, 2022.