Quantum Bayesian Networks

January 27, 2009

Quantum Computer Programming with Oracles

Filed under: Uncategorized — rrtucci @ 1:25 am

fantasiaQuantum 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})],


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.

%d bloggers like this: