Project Description

Quantum computation is a relatively new model of computation that incorporates the quantum mechanical properties of the physical universe. In this model, the states of the bits, instead of ranging over the binary 1 and 0, are allowed to range over unit vectors in a complex vector space, and the gates (or operations) are unitary operators on this space. It is becoming apparent that quantum computing is more powerful than the classical Turing model, in that for certain computational problems there exist quantum algorithms whose asymptotic running time is faster than the theoretical classical limit. One such instance of this is the Grover search algorithm. Suppose we had a list of n ordered objects in a database, one of which is marked as special, and we wished to determine which object is marked. We are allowed to make queries to the database asking if a given object is marked. Classically, the worst case running time of any algorithm can do no better than O(n), because you must check every object. However, with the Grover search algorithm, we are able to find the object in only O(\sqrt{n}) queries.

The Grover search algorithm can be interpreted as the repeated application of two generalized reflection operations. A reflection is simply a linear transformation that fixes some subspace, and reflects its complement space (that is, a vector v of the complement space is sent by the operation to -v). Our project is concerned with the role of reflections in quantum computing. One question we are investigating is, given an unknown reflection operator, by what means can we discover the subspace which it fixes?