Measurement-Based Uncomputation from an Error Correction Perspective
Abstract
Coherent uncomputation can be as costly as the computation itself, creating substantial spacetime overheads that can be prohibitive on early fault-tolerant quantum computers. We develop an algebraic framework for measurement-based uncomputation (MBU) through a quantum error-correction picture: measurements of the garbage register induce relative phases analogous to errors causing non-trivial syndromes. Accepting only zero-syndrome outcomes achieves post-selected MBU, removing the need for an uncomputation oracle at the cost of a probabilistic success rate determined by the affine rank of the populated garbage support. This rank can be much smaller than the number of garbage qubits, as illustrated through an example of the HHL algorithm. We then derive a structural condition under which the original uncomputation oracle can be reused to correct the phase for all measurement outcomes. No correction is required for the zero syndrome, while corrections for non-zero syndromes can be further adapted to individual measurement outcomes for simpler circuits, as illustrated by existing modular-arithmetic, QROM, and QRAM MBU constructions. Phase-correction circuits can be further simplified by co-optimising their implementation with the representation of the measurement-induced phases. Selecting which syndrome classes to correct interpolates between post-selected, partially corrected, and deterministic MBU, enabling trade-offs among correction cost, workspace, and repetitions.
Related
- Particle-loss error correction using 2l-step states generated via particle-number-resolving measurement schemes
- MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
- Error-Correction Transitions in Finite-Depth Quantum Channels
- Bosonic quantum error correction with microwave cavities for quantum repeaters
- Quantitative Fabrication-Error Reduction in Optomechanical Crystal using Proximity Error Correction
BibTeX
@misc{jeon2026measurementbased,
title = {{Measurement-Based Uncomputation from an Error Correction Perspective}},
author = {Minjun Jeon and Po-Wei Huang and Zhenyu Cai},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31605},
eprint = {2609.31605},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31605},
}
RIS
TY - UNPB
TI - Measurement-Based Uncomputation from an Error Correction Perspective
AU - Minjun Jeon
AU - Po-Wei Huang
AU - Zhenyu Cai
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31605
UR - https://arxiv.org/abs/2609.31605
AB - Coherent uncomputation can be as costly as the computation itself, creating substantial spacetime overheads that can be prohibitive on early fault-tolerant quantum computers. We develop an algebraic framework for measurement-based uncomputation (MBU) through a quantum error-correction picture: measurements of the garbage register induce relative phases analogous to errors causing non-trivial syndromes. Accepting only zero-syndrome outcomes achieves post-selected MBU, removing the need for an uncomputation oracle at the cost of a probabilistic success rate determined by the affine rank of the populated garbage support. This rank can be much smaller than the number of garbage qubits, as illustrated through an example of the HHL algorithm. We then derive a structural condition under which the original uncomputation oracle can be reused to correct the phase for all measurement outcomes. No correction is required for the zero syndrome, while corrections for non-zero syndromes can be further adapted to individual measurement outcomes for simpler circuits, as illustrated by existing modular-arithmetic, QROM, and QRAM MBU constructions. Phase-correction circuits can be further simplified by co-optimising their implementation with the representation of the measurement-induced phases. Selecting which syndrome classes to correct interpolates between post-selected, partially corrected, and deterministic MBU, enabling trade-offs among correction cost, workspace, and repetitions.
ER -