1. The limitations of nice mutually unbiased bases
Michael Aschbacher, Andrew M. Childs, Pawel Wocjan
Journal of Algebraic Combinatorics, Vol. 25, No. 2 (2007) 111-123
http://arxiv.org/abs/quant-ph/0412066
Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets.
2. Limits on Efficient Computation in the Physical World
Scott Aaronson
http://arxiv.org/abs/quant-ph/0412143
More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.
3. Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Scott Aaronson
http://arxiv.org/abs/quant-ph/0412187
I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold, and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.