Shengyuan Yang and Charles Yuan of University of Wisconsin-Madison have developed MBUndo, an integrated compiler pass that automatically converts quantum circuits to use measurement-based uncomputation. The new system addresses a longstanding bottleneck in quantum algorithm development, as researchers previously had to manually transform circuits to replace costly quantum gates with cheaper measurements and phase corrections.

This automatic transformation was previously impossible due to unknowns regarding where measurement-based uncomputation applies and which gates realize it for any given computation. Evaluations on 22 benchmarks reveal MBUndo achieves greater than 36.5% reductions in T gate counts over existing uncomputation synthesizers.

MBUndo: Automatic Transformation to Measurement-Based Uncomputation

Prior to this work, researchers manually applied MBU to individual circuit designs, a process that limited both the development of new algorithms and the optimization of existing ones. This manual approach stemmed from a lack of understanding regarding both where MBU could be applied within a circuit and which gates could realize it effectively. MBUndo, the integrated compiler pass developed by Yang and Yuan, addresses these limitations by performing a static analysis that identifies valid measurement points for each ancilla qubit throughout the entire circuit, not just at the circuit’s end.

This analysis tracks the basis value on each qubit, effectively determining the “lifetime” of each ancilla and pinpointing where measurement is sound. The system then employs circuit transformations to convert unitary uncomputation gates into efficient phase corrections following measurement, generalizing previously limited rewrite rules.

Static Analysis for Sound MBU Application Points

The new system identifies specific points within a quantum circuit where measurement-based uncomputation (MBU) can be reliably applied, moving beyond the limitation of prior approaches that assumed MBU only functioned at a circuit’s conclusion. This static analysis, central to the MBUndo compiler pass, determines “lifetimes” for each ancilla qubit, the periods where its state is guaranteed to be zero, by tracing backwards through the circuit’s operations.

The process establishes a foundation for converting standard ancilla uncomputation into more efficient MBU techniques. The core of the analysis involves a symbolic execution that assesses each “ancilla qubit” and its state throughout the circuit’s progression; this process scales with the size of the circuit but remains computationally feasible. This capability allows for generalization of rewrite rules from previous work, which were either limited to single gates or not applicable to general circuits.

It requires no user annotations other than which qubits are ancillas, the same as needed by existing uncomputation synthesizers, and can enhance their output circuits. The work’s complexity remains consistent with the initial analysis, ensuring scalability for larger and more complex quantum programs.

Entanglement and the Need for Quantum Uncomputation

Entanglement between temporary and data qubits necessitates a process called uncomputation to maintain program correctness, a challenge addressed by a new system that precisely pinpoints when measurement-based uncomputation can be applied. Conventional uncomputation relies on executing as many gates as the original computation, potentially accounting for half the runtime of a quantum circuit, whereas measurement-based uncomputation offers a potentially cheaper alternative.

This reduction is particularly impactful in circuits like quantum adders, where ancillas are computed by Toffoli gates, effectively halving the total T gate count. The system’s ability to identify these opportunities automatically represents a step forward in optimizing quantum computations.

Unitary Uncomputation vs. Measurement-Based Uncomputation (MBU)

Measurement-based uncomputation (MBU) offers a potential efficiency gain over traditional unitary uncomputation by replacing sequences of quantum gates with a single measurement and subsequent phase correction. While unitary uncomputation requires an equivalent number of gates to reverse a computation, MBU uses the destructive nature of quantum measurement to discard temporary values, known as ancilla qubits, more economically. This shift, however, has historically demanded manual intervention from programmers, limiting its widespread adoption and hindering automated compiler optimization.

The core challenge in automating MBU lies in determining where measurements can be safely inserted into a circuit without altering the final result. Prior approaches to rewriting quantum circuits for MBU were constrained by their inability to address entire circuits, functioning only on isolated gates or failing to account for complex dependencies.

MBU Implementation with Hadamard and X-Basis Measurement

The transformation of ancilla qubit uncomputation from unitary gates to measurement-based uncomputation (MBU) relies on a specific sequence of operations: a Hadamard gate followed by measurement in the computational basis. This process yields either a 0 or 1 with equal probability, effectively cleaning up the temporary qubit without the need for costly quantum gates.

The efficiency gain is particularly noticeable when applied to gates like the Toffoli, where MBU replaces a complex series of gates with a single X-basis measurement and a controlled-Z gate, a Clifford gate requiring no T gates. The system completes analysis of each benchmark within 43 milliseconds on a standard laptop.

MBUndo as a Compiler Pass Enhancing Existing Synthesizers

MBUndo distinguishes itself from prior approaches by functioning as an integrated compiler pass, a capability previously absent in automated measurement-based uncomputation techniques. This allows the system to enhance the output of existing uncomputation synthesizers like Unqomp and Reqomp, rather than requiring a complete circuit redesign. The tool achieves this by automatically converting circuits to use measurement-based uncomputation without requiring additional user input beyond identifying ancilla qubits, mirroring the annotation requirements of current synthesizers.

The system’s design allows for flexible application; it performs a static analysis to map logical lifetimes of ancilla qubits, then applies either endpoint or interval measurement-based uncomputation transformations. Benchmarks containing these more complex uncomputation requirements saw an additional reduction of 2.3 to 18.4 percentage points in T gate usage. This demonstrates MBUndo’s ability to optimize circuits beyond what is achievable with simpler, endpoint-focused approaches.

The researchers write, highlighting the system’s modularity and adaptability. This rapid processing time, combined with its ability to automatically match three of four previously published specialized measurement-based uncomputation circuits, positions MBUndo as a practical tool for quantum algorithm development.

👉 More information
🗞 MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
✍️ Shengyuan Yang and Charles Yuan (University of Wisconsin–Madison, USA)
🧠 ArXiv: https://arxiv.org/abs/2611.02345

More like this