The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.
The techniques of effective descriptive set theory are applied to the mathematical formalism of quantum mechanics in order to see whether it actually provides effective algorithms for the computation of various physically significant quantities, e.g. matrix elements. Various Hamiltonians are proven to be recursive (effectively computable) and shown to generate unitary groups which act recursively on the Hilbert space of physical states. In particular, it is shown that the
n-particle Coulombic Hamiltonian is recursive, and that the time evolution of
n-particle quantum Coulombic systems is recursive.
We investigate the groups generated by the sets of
CP,
CNOT and
SWAPα (power-of-SWAP) quantum gate operations acting on
n qubits. Isomorphisms to standard groups are found, and using techniques from representation theory, we are able to determine the invariant subspaces of the
n−qubit Hilbert space under the action of each group. For the
CP operation, we find isomorphism to the direct product of
n(n−1)/2 cyclic groups of order
2, and determine
2n 1-dimensional invariant subspaces corresponding to the computational state-vectors. For the
CNOT operation, we find isomorphism to the general linear group of an
n-dimensional space over a field of
2 elements,
GL(n,2), and determine two
1-dimensional invariant subspaces and one
(2n−2)-dimensional invariant subspace. For the
SWAPα operation we determine a complex structure of invariant subspaces with varying dimensions and occurrences and present a recursive procedure to construct them. As an example of an application for our work, we suggest that these invariant subspaces can be used to construct simple formal verification procedures to assess the operation of quantum computers of arbitrary size.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.
Universal quantum computation on decoherence-free subspaces and subsystems (DFSs) is examined with particular emphasis on using only physically relevant interactions. A necessary and sufficient condition for the existence of decoherence-free (noiseless) subsystems in the Markovian regime is derived here for the first time. A stabilizer formalism for DFSs is then developed which allows for the explicit understanding of these in their dual role as quantum error correcting codes. Conditions for the existence of Hamiltonians whose induced evolution always preserves a DFS are derived within this stabilizer formalism. Two possible collective decoherence mechanisms arising from permutation symmetries of the system-bath coupling are examined within this framework. It is shown that in both cases universal quantum computation which always preserves the DFS (natural fault-tolerant computation) can be performed using only two-body interactions. This is in marked contrast to standard error correcting codes, where all known constructions using one- or two-body interactions must leave the code space during the on-time of the fault-tolerant gates. A further consequence of our universality construction is that a single exchange Hamiltonian can be used to perform universal quantum computation on an encoded space whose asymptotic coding efficiency is unity. The exchange Hamiltonian, which is naturally present in many quantum systems, is thus asymptotically universal.