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.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: