Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation
Abstract
Classical simulability of quantum circuits plays a central role in characterizing and quantifying quantum computational advantage. Typically, the presence of non-Clifford gates introduces an exponential runtime overhead for classically estimating expectation values of observables. In this work, we introduce an efficient simulation framework that integrates the sum-over-Clifford method with quasi-probability-based stabilizer simulation to directly estimate expectation values. To optimize efficiency, we incorporate a circuit-adaptive reduction via variance estimation protocol, which terminates simulations once an empirical confidence bound is sufficient to guarantee the prescribed error tolerance. Our method circumvents overly conservative Hoeffding's inequality, thereby reducing the dependence on the gate-wise stabilizer extent from quadratic to linear in the low-variance regime, while maintaining the same space complexity as previous approaches. We explicitly prove the sample-complexity reduction for random quantum circuits and T-doped Clifford circuits and also empirically validate these advantages in the quantum approximate optimization algorithm and quantum kernel method.
Related
- New directions in dynamical expectation estimation
- Hardware-Friendly Estimation of LCU-Based Expectation Values via Quantum-to-Classical Workload Shifting
- Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation
- Efficient quantum phase estimation with adaptive entanglement-assisted Hadamard test
- Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
BibTeX
@misc{hwang2026efficient,
title = {{Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation}},
author = {Yunseo Hwang and Giwon Song and Kyoung Keun Park and Hyukjoon Kwon and Taehyun Kim},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14252},
eprint = {2609.14252},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14252},
}
RIS
TY - UNPB
TI - Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation
AU - Yunseo Hwang
AU - Giwon Song
AU - Kyoung Keun Park
AU - Hyukjoon Kwon
AU - Taehyun Kim
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14252
UR - https://arxiv.org/abs/2609.14252
AB - Classical simulability of quantum circuits plays a central role in characterizing and quantifying quantum computational advantage. Typically, the presence of non-Clifford gates introduces an exponential runtime overhead for classically estimating expectation values of observables. In this work, we introduce an efficient simulation framework that integrates the sum-over-Clifford method with quasi-probability-based stabilizer simulation to directly estimate expectation values. To optimize efficiency, we incorporate a circuit-adaptive reduction via variance estimation protocol, which terminates simulations once an empirical confidence bound is sufficient to guarantee the prescribed error tolerance. Our method circumvents overly conservative Hoeffding's inequality, thereby reducing the dependence on the gate-wise stabilizer extent from quadratic to linear in the low-variance regime, while maintaining the same space complexity as previous approaches. We explicitly prove the sample-complexity reduction for random quantum circuits and T-doped Clifford circuits and also empirically validate these advantages in the quantum approximate optimization algorithm and quantum kernel method.
ER -