Given an arbitrary ${2}^{w}\ifmmode\times\else\texttimes\fi{}{2}^{w}$ unitary matrix
U, a powerful matrix decomposition can be applied, leading to four different syntheses of a
w-qubit quantum circuit performing the unitary transformation. The demonstration is based on a recent theorem by H. F\"uhr and Z. Rzeszotnik [Linear Algebra Its Appl. 484, 86 (2015)] generalizing the scaling of single-bit unitary gates (
w=1) to gates with arbitrary value of
w. The synthesized circuit consists of controlled one-qubit gates, such as negator gates and phasor gates. Interestingly, the approach reduces to a known synthesis method for classical logic circuits consisting of controlled not gates in the case that
U is a permutation matrix.
This chapter introduces Boolean quantum gates that allow us to map any Boolean circuit in such a way that the circuit becomes reversible. It describes quantum gates for one qubit, like for example Clifford gates that are the elements of the Clifford group and can be efficiently simulated with a classical computer. The chapter introduces the controlled-U gates and the unitary decomposition and formulate the process of transpilation. A Boolean quantum circuit represents a permutation in Hilbert space and can be represented by a unitary permutation matrix composed of the unitary matrices representing the quantum gates. Such a mapping does not alter the distribution of the amplitudes; the distribution remains unchanged during the execution of the quantum Boolean gates.
The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates -- unitaries which permute the
2n basis states -- in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as \emph{staircase form}, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates
{Uk}k≥3 in staircase form such that each
Uk is in the third level but its inverse is not in the
k-th level.