Computing with highly mixed states

ABSTRACT

Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k, the number of clean qubits in the initial state of the register. In this article, we show that unless m∈O(k + log n), oblivious (gate-by-gate) simulation of an ideal m-qubit quantum circuit by an n-qubit circuit with k clean qubits is impossible. Effectively, this indicates that there is no avoiding physical initialization of a quantity of qubits proportional to that required by the best ideal quantum circuit.

REFERENCES

• 1: Farid M. Ablayev , Cristopher Moore , Chris Pollett, Quantum and Stochastic Branching Programs of Bounded Width, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.343-354, July 08-13, 2002
• 2: Adams, J. F. 1982. Lectures on Lie Groups. University of Chicago Press.
• 3: Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467.
• 4: David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989 [doi>10.1016/0022-0000(89)90037-8]
• 5: Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung D. W., and Lloyd, S. 1998. Experimental realization of a quantum algorithm. Nature 393, 143--146.
• 6: Cory, D. G., Fahmy, A. F., and Havel, T. F. 1997. Ensemble quantum computing by nuclear magnetic resonance spectroscopy. Proc. Natl. Acad. Sci. 94, 1634--1639.
• 7: Fulton, W., and Harris, J. 1991. Representation Theory. A First Course. Springer-Verlag, New York.
• 8: Gershenfeld, N., and Chuang, I. 1997. Bulk spin-resonance quantum computation. Science 275, 350.
• 9: Hoffman, P. N., and Humphreys, J. F. 1992. Projective Representations of the Symmetric Groups. Oxford University Press.
• 10: Knill, E., and Laflamme, R. 1998. On the power of one bit of quantum information. Phys. Rev. Lett. 81, 5672.
• 11: Mishchenko, S. P. 1996. Lower bounds on the dimensions of irreducible representations of symmetric groups and of the exponents of the exponential of varieties of Lie algebras. Matemat. Sbornik 187, 83--94.
• 12: Cristopher Moore , Martin Nilsson, Parallel Quantum Computation and Quantum Codes, SIAM Journal on Computing, v.31 n.3, p.799-815, 2001 [doi>10.1137/S0097539799355053]
• 13: Nielsen, M. Probability distributions consistent with a mixed state. LANL archive, http://xxx.lanl.gov/abs/quant-ph/9909020.
• 14: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 15: Rasala, R. 1977. On the minimal degrees of characters of Sn. J. Algebra 45, 132--181.
• 16: Sagan, B. 2001. The Symmetric Group (2nd edition). Springer-Verlag, New York.
• 17: Leonard J. Schulman , Umesh V. Vazirani, Molecular scale heat engines and scalable quantum computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.322-329, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301332]
• 18: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 19: Vandersypen, L., Steffen, M., Breyta, G., Yannoni, C., Cleve, R., and Chuang, I. 2000. Experimental realization of an order-finding algorithm with an NMR quantum computer. Phys. Rev. Lett. 85, 5452--5455.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory

Keywords:
Quantum Computation