Automatic measurement based uncomputation reduces costly gates in quantum circuits
MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
Programming Languages
Summary
Quantum computers often use extra temporary memory called ancilla qubits that must be reset (uncomputed) for correct results. Traditional methods use complex operations to reset this memory, which can be expensive. The authors developed an automatic way to rewrite quantum programs to use measurement-based uncomputation, a cheaper technique that replaces some costly operations with simpler measurements. Their tool, MBUndo, applies this approach broadly and reduces the expensive parts of quantum programs by over 36%.
What this means in practice
- •For quantum software developers: Automatically optimize quantum algorithms by converting standard ancilla cleanup to measurement based uncomputation, reducing costly gate usage without manual redesign.
- •For hardware design teams: Improve quantum hardware resource utilization by enabling circuits with fewer expensive T gates through automated rewriting of ancilla uncomputation.
Authors
Shengyuan Yang, Charles Yuan
Abstract
Quantum programs that use temporary values, known as \emph{ancilla} qubits, must explicitly \emph{uncompute} each ancilla back to zero to ensure that the program produces correct outputs. Conventional uncomputation uses unitary quantum gates, whereas leading quantum algorithms now leverage \emph{measurement-based uncomputation} (MBU), which replaces costly unitary $T$ gates with cheaper measurements and phase corrections. Current quantum programming frameworks can use measurement to uncompute specific gates such as Toffoli. No automatic transformation, however, accepts an arbitrary circuit whose ancillas are computed and uncomputed via the standard approach and converts the circuit to use MBU\@. Researchers instead apply MBU to individual circuit designs by hand, which limits algorithm development and compiler optimization. Such a transformation has not existed due to two fundamental unknowns: where MBU applies and which gates realize MBU for an arbitrary computation. To solve these, we first present a static analysis that identifies, for each ancilla qubit, each circuit position where measurement is sound --- subsuming basic assumptions that MBU only applies at the end of a circuit. Next, we present circuit transformations that soundly turn unitary uncomputation gates into efficient phase corrections after measurement --- generalizing rewrite rules from prior literature that are either limited to a single gate or not applicable to a general circuit. We present \textsf{MBUndo}, an integrated compiler pass that automatically converts circuits to measurement-based uncomputation. 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. We evaluate \textsf{MBUndo} on 22 benchmarks to reveal \emph{T} gate reductions of ${>}36.5\%$ over uncomputation synthesizers.