Abstract
The reversible implementation of classical functions accounts for the bulk of most known quantum algorithms. As a result, a number of reversible circuit constructions over the Clifford+ gate set have been developed in recent years which use both the state and phase spaces, or and bases, to reduce circuit costs beyond what is possible at the strictly classical level. We study and generalize two particular classes of these constructions: relative phase circuits, including Giles and Selinger's multiply-controlled gates and Maslov's qubit Toffoli gate, and measurement-assisted circuits, including Jones' Toffoli gate and Gidney's temporary logical-AND. In doing so, we introduce general methods for implementing classical functions up to phase and for measurement-assisted termination of temporary values. We then apply these techniques to find novel -count efficient constructions of some classical functions in space-constrained regimes, notably multiply-controlled Toffoli gates and temporary products.