Quantum multiplexors are a type of unitary operator that shows up frequently when compiling a unitary matrix into a sequence of elementary operations like CNOTs and single-qubit rotations. Unfortunately, the time complexity of quantum multiplexors of dimension is exponential in . Thus, it is of interest to find multiplexor approximations with lower time complexity.
Suppose is a nonzero integer, the number of bits, and is the number of states. For some angles , let
is a special case of a quantum multiplexor.
Let be a diagonal matrix of dimension , such that all its diagonal entries are either 0 or 1. Let . Let
is a special case of a quantum oracle, a unitary operator which shows up frequently in quantum complexity theory.
Note that the entries of are real numbers between -1 and 1 whereas those of are either 0 or 1. Both matrices are zero outside the main diagonal and the two “off-diagonals”.
In my youngest paper, I show how to approximate a multiplexor like using oracles like . As an added bonus, I also show how to approximate an arbitrary diagonal unitary matrix using oracles.