# Quantum Bayesian Networks

## January 27, 2009

### Quantum Computer Programming with Oracles

Filed under: Uncategorized — rrtucci @ 1:25 am

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 $2^{N_B}$ is exponential in $N_B$. Thus, it is of interest to find multiplexor approximations with lower time complexity.

Suppose $N_B$ is a nonzero integer, the number of bits, and $N_S=2^{N_B}$ is the number of states. For some angles $\theta_1, \theta_2, ..., \theta_{N_S}$, let

$C = diag[\cos(\theta_1), \cos(\theta_2), ..., \cos(\theta_{N_S})]$,

$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]$.

$M$ is a special case of a quantum multiplexor.

Let $\Delta$ be a diagonal matrix of dimension $N_S$, such that all its diagonal entries are either 0 or 1. Let $\overline{\Delta}=1-\Delta$. Let

$\Omega =\left[\begin{array}{l} \overline{\Delta}\;\;\Delta\\ \Delta\;\:\overline{\Delta}\end{array}\right]$.

$\Omega$ is a special case of a quantum oracle, a unitary operator which shows up frequently in quantum complexity theory.

Note that the entries of $M$ are real numbers between -1 and 1 whereas those of $\Omega$ 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 $M$ using oracles like $\Omega$. As an added bonus, I also show how to approximate an arbitrary diagonal unitary matrix using oracles.

## January 16, 2009

### Frank Wilczek fond of Quantum Computers

Filed under: Uncategorized — rrtucci @ 2:43 am

Frank Wilczek is a Nobel prize winner in High Energy Physics with wide ranging and impeccable taste in physics. A very friendly person too. In a recent interview, he said some nice things about quantum computing.

Blog at WordPress.com.