1. ROM-based computation: quantum versus classical
B.C. Travaglione, M.A. Nielsen, H.M. Wiseman, A. Ambainis
Quantum Information and Computation, Vol. 2, No. 4 (2002)
http://arxiv.org/abs/quant-ph/0109016
We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.
2. Universal simulation of Hamiltonian dynamics for qudits
Michael A. Nielsen, Michael J. Bremner, Jennifer L. Dodd, Andrew M. Childs, Christopher M. Dawson
Phys. Rev. A 66, 022317 (2002)
http://arxiv.org/abs/quant-ph/0109064
What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? Dodd et al. (quant-ph/0106064) provided a partial solution to this problem in the form of an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling N-qubit Hamiltonian, and local unitaries. We extend this result to the case where the component systems have D dimensions. As a consequence we explain how universal quantum computation can be performed with any fixed two-body entangling N-qudit Hamiltonian, and local unitaries.
3. Implementing the quantum random walk
B. C. Travaglione, G. J. Milburn
Physical Review A, Vol 65, 032310 (2002)
http://arxiv.org/abs/quant-ph/0109076
Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains `quantum', this algorithm could serve as an important benchmarking protocol for ion trap quantum computers.
4. Exact results for accepting probabilities of quantum automata
Andris Ambainis, Arnolds Kikusts
Theoretical Computer Science, 295(2003):3-25
http://arxiv.org/abs/quant-ph/0109136
One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...