1. Realization of quantum process tomography in NMR
Andrew M. Childs, Isaac L. Chuang, Debbie W. Leung
Phys. Rev. A 64, 012314 (2001)
http://arxiv.org/abs/quant-ph/0012032
Quantum process tomography is a procedure by which the unknown dynamical evolution of an open quantum system can be fully experimentally characterized. We demonstrate explicitly how this procedure can be implemented with a nuclear magnetic resonance quantum computer. This allows us to measure the fidelity of a controlled-not logic gate and to experimentally investigate the error model for our computer. Based on the latter analysis, we test an important assumption underlying nearly all models of quantum error correction, the independence of errors on different qubits.
2. Quantum Walks On Graphs
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani
Proceedings of ACM Symposium on Theory of Computation (STOC’01), July 2001, p. 50-59
http://arxiv.org/abs/quant-ph/0012090
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
3. Finding cliques by quantum adiabatic evolution
Andrew M. Childs, Edward Farhi, Jeffrey Goldstone, Sam Gutmann
Quantum Information and Computation 2, 181 (2002)
http://arxiv.org/abs/quant-ph/0012104
Quantum adiabatic evolution provides a general technique for the solution of combinatorial search problems on quantum computers. We present the results of a numerical study of a particular application of quantum adiabatic evolution, the problem of finding the largest clique in a random graph. An n-vertex random graph has each edge included with probability 1/2, and a clique is a completely connected subgraph. There is no known classical algorithm that finds the largest clique in a random graph with high probability and runs in a time polynomial in n. For the small graphs we are able to investigate (n <= 18), the quantum algorithm appears to require only a quadratic run time.