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
![C = diag[\cos(\theta_1), \cos(\theta_2), ..., \cos(\theta_{N_S})]](http://l.wordpress.com/latex.php?latex=C+%3D+diag%5B%5Ccos%28%5Ctheta_1%29%2C+%5Ccos%28%5Ctheta_2%29%2C+...%2C+%5Ccos%28%5Ctheta_%7BN_S%7D%29%5D&bg=ffffff&fg=000000&s=0 "C = diag[\cos(\theta_1), \cos(\theta_2), ..., \cos(\theta_{N_S})]")
,
![S = diag[\sin(\theta_1), \sin(\theta_2), ..., \sin(\theta_{N_S})]](http://l.wordpress.com/latex.php?latex=S+%3D+diag%5B%5Csin%28%5Ctheta_1%29%2C+%5Csin%28%5Ctheta_2%29%2C+...%2C+%5Csin%28%5Ctheta_%7BN_S%7D%29%5D&bg=ffffff&fg=000000&s=0 "S = diag[\sin(\theta_1), \sin(\theta_2), ..., \sin(\theta_{N_S})]")
,
and
![M = \left[\begin{array}{l} \;\;C\;\;S\\-S\;\:C\end{array}\right]](http://l.wordpress.com/latex.php?latex=M+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bl%7D+%5C%3B%5C%3BC%5C%3B%5C%3BS%5C%5C-S%5C%3B%5C%3AC%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "M = \left[\begin{array}{l} \;\;C\;\;S\\-S\;\:C\end{array}\right]")
.
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
![\Omega =\left[\begin{array}{l} \overline{\Delta}\;\;\Delta\\ \Delta\;\:\overline{\Delta}\end{array}\right]](http://l.wordpress.com/latex.php?latex=%5COmega+%3D%5Cleft%5B%5Cbegin%7Barray%7D%7Bl%7D+%5Coverline%7B%5CDelta%7D%5C%3B%5C%3B%5CDelta%5C%5C+%5CDelta%5C%3B%5C%3A%5Coverline%7B%5CDelta%7D%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\Omega =\left[\begin{array}{l} \overline{\Delta}\;\;\Delta\\ \Delta\;\:\overline{\Delta}\end{array}\right]")
.
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.
