×

zbMATH — the first resource for mathematics

Quantum computation and quantum information. (English) Zbl 1331.81080
Summary: Quantum computation and quantum information are of great current interest in computer science, mathematics, physical sciences and engineering. They will likely lead to a new wave of technological innovations in communication, computation and cryptography. As the theory of quantum physics is fundamentally stochastic, randomness and uncertainty are deeply rooted in quantum computation, quantum simulation and quantum information. Consequently quantum algorithms are random in nature, and quantum simulation utilizes Monte Carlo techniques extensively. Thus statistics can play an important role in quantum computation and quantum simulation, which in turn offer great potential to revolutionize computational statistics. While only pseudo-random numbers can be generated by classical computers, quantum computers are able to produce genuine random numbers; quantum computers can exponentially or quadratically speed up median evaluation, Monte Carlo integration and Markov chain simulation. This paper gives a brief review on quantum computation, quantum simulation and quantum information. We introduce the basic concepts of quantum computation and quantum simulation and present quantum algorithms that are known to be much faster than the available classic algorithms. We provide a statistical framework for the analysis of quantum algorithms and quantum simulation.

MSC:
81P45 Quantum information, communication, networks (quantum-theoretic aspects)
81P68 Quantum computation
62B10 Statistical aspects of information-theoretic topics
94A15 Information theory (general)
81-02 Research exposition (monographs, survey articles) pertaining to quantum theory
68Q12 Quantum algorithms and complexity in the theory of computing
62-02 Research exposition (monographs, survey articles) pertaining to statistics
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Abrams, D. S. and Lloyd, S. (1997). Simulation of many-body Fermi systems on a quantum computer. Phys. Rev. Lett. 79 2586-2589.
[2] Aharonov, D. and Ta-Shma, A. (2003). Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 20-29. ACM, New York (electronic). · Zbl 1192.81048
[3] Artiles, L. M., Gill, R. D. and Guţă, M. I. (2005). An invitation to quantum tomography. J. R. Stat. Soc. Ser. B Stat. Methodol. 67 109-134. · Zbl 1060.62137
[4] Aspect, A., Grangier, P. and Roger, G. (1981). Experimental tests of realistic local theories via Bell’s theorem. Phys. Rev. Lett. 47 460-463.
[5] Aspect, A., Grangier, P. and Roger, G. (1982a). Experimental realization of Einstein-Podolsky-Rosen-Bohm Gedankenexperiment: A new violation of Bell’s inequalities. Phys. Rev. Lett. 49 91-94.
[6] Aspect, A., Grangier, P. and Roger, G. (1982b). Experimental test of Bell’s inequalities using time-varying analyzers. Phys. Rev. Lett. 49 1804-1807.
[7] Aspuru-Guzik, A. D., Dutoi, P. J. L. and Head-Gordon, M. (2005). Simulated quantum computation of molecular energies. Science 309 1704.
[8] Barndorff-Nielsen, O. E., Gill, R. D. and Jupp, P. E. (2003). On quantum statistical inference. J. R. Stat. Soc. Ser. B Stat. Methodol. 65 775-816. · Zbl 1059.62128
[9] Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J.F., Zeilinger, A. and Walther, P. (2012). Demonstration of blind quantum computing. Science 335 303-308. · Zbl 1355.81057
[10] Bell, J. (1964). On the Einstein Podolsky Rosen paradox. Physics 1 195-200.
[11] Bennett, C. H., Cirac, J. I., Leifer, M. S., Leung, D. W., Linden, N., Popescu, S. and Vidal, G. (2002). Optimal simulation of two-qubit Hamiltonians using general local operations. Phys. Rev. A (3) 66 012305.
[12] Berry, D. W., Ahokas, G., Cleve, R. and Sanders, B. C. (2007). Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys. 270 359-371. · Zbl 1115.81011
[13] Boghosian, B. M. and Taylor, W. IV (1998). Simulating quantum mechanics on a quantum computer. Phys. D 120 30-42. · Zbl 1040.81505
[14] Bohm, D. (1951). Quantum Theory . Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0048.21802
[15] Butucea, C., Guţă, M. and Artiles, L. (2007). Minimax and adaptive estimation of the Wigner function in quantum homodyne tomography with noisy data. Ann. Statist. 35 465-494. · Zbl 1117.62027
[16] Calderbank, A. R. and Shor, P. W. (1996). Good quantum error-correcting codes exist. Phys. Rev. A 54 1098-1105.
[17] Childs, A. M. (2010). On the relationship between continuous- and discrete-time quantum walk. Comm. Math. Phys. 294 581-603. · Zbl 1207.81029
[18] Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S. and Spielman, D. A. (2003). Exponential algorithmic speedup by quantum walk. In Proc. 35 th ACM Symposium on Theory of Computing 59-68. ACM Press, New York. · Zbl 1192.81059
[19] Clarke, J. and Wilhelm, F. K. (2008). Superconducting quantum bits. Nature 453 1031-1042. · Zbl 0428.53033
[20] Clauser, J. F., Horne, M. A., Shimony, A. and Holt, R. A. (1969). Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23 880-884. · Zbl 1371.81014
[21] Cory, D. G., Mass, W., Price, M., Knill, E., Laflamme, R., Zurek, W. H., Havel, T. F. and Somaroo, S. S. (1998). Experimental quantum error correction. Phys. Rev. Lett. 81 2152-2155.
[22] Crandall, R. and Pomerance, C. (2001). Prime Numbers : A Computational Perspective . Springer, New York. · Zbl 1088.11001
[23] Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. Ser. A 400 97-117. · Zbl 0900.81019
[24] DiCarlo, L., Chow, J. M., Gambetta, J. M., Bishop, L. S., Johnson, B. R., Schuster, D. I., Majer, J., Blais, A., Frunzio, L., Girvin, S. M. and Schoelkopf, R. J. (2009). Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature 460 240-244.
[25] DiVincenzo, D. P. (1995). Quantum computation. Science 270 255-261. · Zbl 1226.68037
[26] Einstein, A., Podolsky, B. and Rosen, N. (1935). Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47 777-780. · Zbl 0012.04201
[27] Feynman, R. P. (1981/82). Simulating physics with computers. Internat. J. Theoret. Phys. 21 467-488.
[28] Freedman, M. H., Kitaev, A. and Wang, Z. (2002). Simulation of topological field theories by quantum computers. Comm. Math. Phys. 227 587-603. · Zbl 1014.81006
[29] Griffiths, D. J. (2004). Introduction to Quantum Mechanics , 2nd ed. Benjamin Cummings, San Francisco, CA. · Zbl 0818.00001
[30] Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing ( Philadelphia , PA , 1996) 212-219. ACM, New York. · Zbl 0922.68044
[31] Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79 325-328.
[32] Hayashi, M. (2006). Quantum Information : An Introduction . Springer, Berlin. Translated from the 2003 Japanese original. · Zbl 1195.81031
[33] Heinrich, S. (2003). From Monte Carlo to quantum computation. Math. Comput. Simulation 62 219-230. · Zbl 1025.65005
[34] Holevo, A. S. (1982). Probabilistic and Statistical Aspects of Quantum Theory. North-Holland Series in Statistics and Probability 1 . North-Holland, Amsterdam. Translated from the Russian by the author. · Zbl 0497.46053
[35] Holevo, A. S. (1998). The capacity of the quantum channel with general signal states. IEEE Trans. Inform. Theory 44 269-273. · Zbl 0897.94008
[36] Huber, P. J. and Ronchetti, E. M. (2009). Robust Statistics , 2nd ed. Wiley, Hoboken, NJ. · Zbl 1276.62022
[37] Jané, E., Vidal, G., Dür, W., Zoller, P. and Cirac, J. I. (2003). Simulation of quantum dynamics with quantum optical systems. Quantum Inf. Comput. 3 15-37. · Zbl 1152.81744
[38] Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., Chapple, E. M., Enderud, C., Hilton, J. P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M. C., Tolkacheva, E., Truncik, C. J. S., Uchaikin, S., Wang, J., Wilson, B., Rose, G. et al. (2011). Quantum annealing with manufactured spins. Nature 473 194-198.
[39] Kato, T. (1978). Trotter’s product formula for an arbitrary pair of self-adjoint contraction semigroups. In Topics in Functional Analysis ( Essays Dedicated to M. G. KreĭN on the Occasion of His 70 th Birthday ). Adv. in Math. Suppl. Stud. 3 185-195. Academic Press, New York. · Zbl 0461.47018
[40] Kiefer, C. (2004). On the interpretation of quantum theory-from Copenhagen to the present day. In Time , Quantum and Information 291-299. Springer, Berlin.
[41] Lee, N., Benichi, H., Takeno, Y., Takeda, S., Webb, J., Huntington, E. and Furusawa, A. (2011). Teleportation of nonclassical wave packets of light. Science 332 330-333.
[42] Lloyd, S. (1996). Universal quantum simulators. Science 273 1073-1078. · Zbl 1226.81059
[43] Magniez, F., Nayak, A., Roland, J. and Santha, M. (2011). Search via quantum walk. SIAM J. Comput. 40 142-164. · Zbl 1223.05289
[44] Mariantoni, M., Wang, H., Yamamoto, T., Neeley, M., Bialczak1, R. C., Chen, Y., Lenander, M., Lucero, E., O’Connell, A. D., Sank, D., Weides, M., Wenner, J., Yin, Y., Zhao, J., Korotkov, A. N., Cleland, A. N. and Martinis, J. M. (2011). Implementing the quantum von Neumann architecture with superconducting circuits. Science 7 1208517.
[45] Menezes, A., van Oorschot, P. C. and Vanstone, S. A. (1996). Handbook of Applied Cryptography . CRC Press, New York. · Zbl 0868.94001
[46] Nayak, A. and Wu, F. (1999). The quantum query complexity of approximating the median and related statistics. In Annual ACM Symposium on Theory of Computing ( Atlanta , GA , 1999) 384-393. ACM, New York (electronic). · Zbl 1345.68141
[47] Neumann, P., Mizuochi, N., Rempp, F., Hemmer, P., Watanabe, H., Yamasaki, S., Jacques, V., Gaebel, T., Jelezko, F. and Wrachtrup, J. (2008). Multipartite entanglement among single spins in diamond. Science 320 1326-1329.
[48] Nielsen, M. A. and Chuang, I. L. (2000). Quantum Computation and Quantum Information . Cambridge Univ. Press, Cambridge. · Zbl 1049.81015
[49] Nightingale, M. P. and Umrigar, C. J., eds. (1999). Quantum Monte Carlo Methods in Physics and Chemistry. NATO Science Series C : Mathematical and Physical Sciences 525 . Kluwer Academic, Dordrecht. · Zbl 0942.00068
[50] Nussbaum, M. and Szkoła, A. (2009). The Chernoff lower bound for symmetric quantum hypothesis testing. Ann. Statist. 37 1040-1057. · Zbl 1162.62100
[51] Parthasarathy, K. R. (1992). An Introduction to Quantum Stochastic Calculus. Monographs in Mathematics 85 . Birkhäuser, Basel. · Zbl 0751.60046
[52] Richter, P. C. (2007). Quantum speedup of classical mixing processes. Phys. Rev. A 76 042306.
[53] Rivest, R. L., Shamir, A. and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21 120-126. · Zbl 0368.94005
[54] Rousseau, V. G. (2008). Stochastic Green function algorithm. Phys. Rev. E (3) 77 056705.
[55] Sakurai, J. J. and Napolitano, J. (2010). Modern Quantum Mechanics , 2nd ed. Addison-Wesley, Reading, MA. · Zbl 1392.81003
[56] Sayrin, C., Dotsenko, I., Zhou, X., Peaudecerf, B., Rybarczyk, T., Gleyzes, S., Rouchon, P., Mirrahimi, M., Amini, H., Brune, M., Raimond, J. M. and Haroche, S. (2011). Real-time quantum feedback prepares and stabilizes photon number states. Nature 477 10376.
[57] Schumacher, B. (1995). Quantum coding. Phys. Rev. A (3) 51 2738-2747.
[58] Schumacher, B. and Westmoreland, M. D. (1997). Sending classical information via noisy quantum channels. Phys. Rev. A 56 131138.
[59] Shankar, R. (1994). Principles of Quantum Mechanics , 2nd ed. Plenum Press, New York. · Zbl 0893.00007
[60] Shenvi, N., Kempe, J. and Whaley, K. B. (2003). Quantum random-walk search algorithm. Phys. Rev. A 67 052307.
[61] Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In 35 th Annual Symposium on Foundations of Computer Science ( Santa Fe , NM , 1994) 124-134. IEEE Comput. Soc. Press, Los Alamitos, CA.
[62] Shor, P. W. (1995). Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 52 2493-2496.
[63] Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 1484-1509. · Zbl 1005.11065
[64] Steane, A. M. (1996a). Error correcting codes in quantum theory. Phys. Rev. Lett. 77 793-797. · Zbl 0944.81505
[65] Steane, A. (1996b). Multiple-particle interference and quantum error correction. Proc. R. Soc. Lond. Ser. A 452 2551-2577. · Zbl 0876.94002
[66] Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. In Proc. 45 th IEEE Symposium on Foundations of Computer Science 32-41. IEEE Computer Society Press, Los Alamitos, CA.
[67] Trotter, H. F. (1959). On the product of semi-groups of operators. Proc. Amer. Math. Soc. 10 545-551. · Zbl 0099.10401
[68] Tsirelson, B. S. (1980). Quantum generalizations of Bell’s inequality. Lett. Math. Phys. 4 93-100.
[69] Tulsi, A. (2008). Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78 012310. · Zbl 1255.81118
[70] Vidakovic, B. (1999). Statistical Modeling by Wavelets . Wiley, New York. · Zbl 0924.62032
[71] von Neumann, J. (1955). Mathematical Foundations of Quantum Mechanics . Princeton Univ. Press, Princeton, NJ. Translated by Robert T. Beyer. · Zbl 0064.21503
[72] Wang, Y. Z. (1994). Quantum Gaussian processes. Acta Math. Appl. Sin. ( Engl. Ser. ) 10 315-327. · Zbl 0810.60052
[73] Wang, Y. (2011). Quantum Monte Carlo simulation. Ann. Appl. Stat. 5 669-683. · Zbl 1223.62174
[74] Wocjan, P. and Abeyesinghe, A. (2008). Speed-up via quantum sampling. [quant-ph]. arXiv:0804.4259v3
[75] Wootters, W. K. and Zurek, W. H. (1982). A single quantum cannot be cloned. Nature 299 802-803. · Zbl 1369.81022
[76] Yu, A. B. (2001). Campbell-Hausdorff formula. In Encyclopaedia of Mathematics (M. Hazewinkel, ed.). Kluwer Academic, Dordrecht.
[77] Zalka, C. (1998). Simulating a quantum systems on a quantum computer. R. Soc. Lond. Philos. Trans. Ser. A Math. Phys. Eng. Sci. 454 313-322. · Zbl 0915.68048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.