×

Geometric algebra and information geometry for quantum computational software. (English) Zbl 1400.81044

Summary: The art of quantum algorithm design is highly nontrivial. Grover’s search algorithm constitutes a masterpiece of quantum computational software. In this article, we use methods of geometric algebra (GA) and information geometry (IG) to enhance the algebraic efficiency and the geometrical significance of the digital and analog representations of Grover’s algorithm, respectively. Specifically, GA is used to describe the Grover iterate and the discretized iterative procedure that exploits quantum interference to amplify the probability amplitude of the target-state before measuring the query register. The transition from digital to analog descriptions occurs via Stone’s theorem which relates the (unitary) Grover iterate to a suitable (Hermitian) Hamiltonian that controls Schrodinger’s quantum mechanical evolution of a quantum state towards the target state. Once the discrete-to-continuos transition is completed, IG is used to interpret Grover’s iterative procedure as a geodesic path on the manifold of the parametric density operators of pure quantum states constructed from the continuous approximation of the parametric quantum output state in Grover’s algorithm. Finally, we discuss the dissipationless nature of quantum computing, recover the quadratic speedup relation, and identify the superfluity of the Walsh-Hadamard operation from an IG perspective with emphasis on statistical mechanical considerations.

MSC:

81P45 Quantum information, communication, networks (quantum-theoretic aspects)
68Q12 Quantum algorithms and complexity in the theory of computing
68W30 Symbolic computation and algebraic computation

References:

[1] Feynman, R. P., Simulating physics with computers, Internat. J. Theoret. Phys., 21, 467 (1982)
[2] Bennett, C. H.; Di Vincenzo, D. P., Quantum information and computation, Nature, 404, 247 (2000) · Zbl 1369.81023
[3] Gottesman, D., An introduction to quantum error correction and fault-tolerant quantum computation, (Quantum Information Science and Its Contributions to Mathematics, AMS Proceedings of Symposia in Applied Mathematics, vol. 68 (2010), American Mathematical Society: American Mathematical Society Providence, RI, USA) · Zbl 1211.81043
[4] Cafaro, C.; Mancini, S., Quantum stabilizer codes for correlated and asymmetric depolarizing errors, Phys. Rev. A, 82, 012306 (2010)
[5] Cafaro, C.; Maiolini, F.; Mancini, S., Quantum stabilizer codes embedding qubits into qudits, Phys. Rev. A, 86, 022308 (2012)
[6] Cafaro, C.; van Loock, P., Approximate quantum error correction for generalized amplitude-damping errors, Phys. Rev. A, 89, 022316 (2014)
[7] Feynman, R., The development of the space-time view of quantum electrodynamics, (Nobel Lectures, Physics 1963-1970 (1972), Elsevier Publishing Company: Elsevier Publishing Company Amsterdam)
[8] Nielsen, M. A.; Dowling, M. R.; Gu, M.; Doherty, A. C., Quantum computation as geometry, Science, 311, 1133 (2006) · Zbl 1226.81049
[9] Brandt, H. E., Riemannian curvature in the differential geometry of quantum computation, Physica E, 42, 449 (2010)
[10] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 1484 (1997) · Zbl 1005.11065
[11] Grover, L. K., Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett., 79, 325 (1997)
[12] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Information (2000), Cambridge University Press · Zbl 1049.81015
[13] Gisin, N.; Ribordy, G.; Tittel, W.; Zbinden, H., Quantum cryptography, Rev. Modern Phys., 74, 145 (2002) · Zbl 1371.81006
[14] Vandersypen, L. M.K.; Steffen, M.; Breyta, G.; Yannoni, C. S.; Sherwood, M. H.; Chuang, I. L., Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature, 414, 883 (2001)
[15] Knuth, D. E., (The Art of Computer Programming. The Art of Computer Programming, Sorting and Searching, vol. 3 (1975), Addison-Wesley: Addison-Wesley Reading, MA)
[16] Galindo, A.; Martin-Delgado, M. A., Information and computation: classical and quantum aspects, Rev. Modern Phys., 74, 347 (2002) · Zbl 1205.94004
[17] Chuang, I. L.; Gershenfeld, N.; Kubinec, M., Experimental implementation of fast quantum searching, Phys. Rev. Lett., 80, 3408 (1998)
[18] Hestenes, D., spacetime Algebra (1966), Gordon Breach: Gordon Breach New York · Zbl 0183.28901
[19] Doran, C.; Lasenby, A., Geometric Algebra for Physicists (2005), Cambridge University Press
[20] Amari, S.; Nagaoka, H., Methods of Information Geometry (2000), Oxford University Press · Zbl 0960.62005
[21] Lasenby, J.; Lasenby, A. N.; Doran, C. J.L., A unified mathematical language for physics and engineering in the 21st century, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. A, 358, 21 (2000) · Zbl 0965.01007
[22] Hestenes, D., Oersted Medal Lecture 2002: Reforming the mathematical language for physics, Amer. J. Phys., 71, 104 (2003)
[23] Lasenby, A.; Doran, C.; Gull, S., Gravity gauge theories and geometric algebra, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. A, 356, 487 (1998) · Zbl 0945.83023
[24] Francis, M. R.; Kosowsky, A., Geometric algebra techniques for general relativity, Ann. Physics, 311, 459 (2004) · Zbl 1062.83060
[25] Baylis, W. E., Electrodynamics: A Modern Geometric Approach (1988), World Scientific
[26] Cafaro, C.; Ali, S. A., The spacetime algebra approach to massive classical electrodynamics with magnetic monopoles, Adv. Appl. Clifford Algebr., 17, 23 (2007) · Zbl 1113.78003
[27] Cafaro, C., Finite-range electromagnetic interaction and magnetic charges: spacetime algebra or algebra of physical space?, Adv. Appl. Clifford Algebr., 17, 617 (2007) · Zbl 1156.78002
[28] Janke, W.; Johnston, D. A.; Kenna, R., Information geometry and phase transitions, Physica A, 336, 181 (2004) · Zbl 1036.82508
[29] Cafaro, C., Information geometry, inference methods and chaotic energy levels statistics, Modern Phys. Lett. B, 22, 1879 (2008) · Zbl 1153.82306
[30] Kim, D.-H.; Ali, S. A.; Cafaro, C.; Mancini, S., Information geometric modeling of scattering induced quantum entanglement, Phys. Lett. A, 375, 2868 (2011)
[31] Cafaro, C.; Giffin, A.; Lupo, C.; Mancini, S., Softening the complexity of entropic motion on curved statistical manifolds, Open Syst. Inf. Dyn., 19, 1250001 (2012) · Zbl 1238.81069
[32] Felice, D.; Mancini, S.; Pettini, M., Quantifying network complexity from information geometry viewpoint, J. Math. Phys., 55, 043505 (2014) · Zbl 1305.90093
[33] Franzosi, R.; Felice, D.; Mancini, S.; Pettini, M., A geometric entropy detecting the Erdos-Renyi phase transition, Europhys. Lett., 111, 20001 (2015)
[34] Franzosi, R.; Felice, D.; Mancini, S.; Pettini, M., Riemannian-geometric entropy for measuring network complexity, Phys. Rev. E, 93, 062317 (2016)
[35] Gregoric, M.; Borstnik, N. S., Quantum gates and quantum algorithms with Clifford algebra techniques, Internat. J. Theoret. Phys., 48, 507 (2008) · Zbl 1162.81342
[36] Alves, R.; Lavor, C., Clifford algebra applied to Grover’s algorithm, Adv. Appl. Clifford Algebr., 20, 477 (2010) · Zbl 1210.81017
[37] Chappell, J. M., Quantum Computing, Quantum Games and Geometric Algebra (Ph.D. thesis) (2011), University of Adelaide
[38] Chappell, J. M.; Iqbal, A.; Lohe, M. A.; von Smekal, L.; Abbott, D., An improved formalism for quantum computation based on geometric algebra-case study: Grover’s search algorithm, Quantum Inf. Process., 12, 1719 (2012) · Zbl 1267.81112
[41] Miyake, A.; Wadati, M., Geometric strategy for the optimal quantum search, Phys. Rev. A, 64, 042317 (2001)
[42] Cafaro, C.; Mancini, S., A geometric algebra perspective on quantum computational gates and universality in quantum computing, Adv. Appl. Clifford Algebr., 21, 493 (2011) · Zbl 1226.81044
[43] Cafaro, C.; Mancini, S., An information geometric viewpoint of algorithms in quantum computing, AIP Conf. Proc., 1443, 374 (2012)
[44] Cafaro, C.; Mancini, S., On Grover’s search algorithm from a quantum information geometry viewpoint, Physica A, 391, 1610 (2012)
[45] Grover, L. K., From Schrodinger’s equation to the quantum search problem, Amer. J. Phys., 69, 769 (2001)
[47] Grover, L. K., Fixed-point quantum search, Phys. Rev. Lett., 95, 150501 (2005) · Zbl 1255.81106
[48] Ekert, A.; Jozsa, R., Quantum algorithms: entanglement enhanced information processing, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., A356, 1769 (1998) · Zbl 1152.81837
[49] Jozsa, R., Quantum effects in algorithms, Lect. Notes Comput. Sci., 1509, 103 (1999) · Zbl 0960.81008
[50] Lloyd, S., Quantum search without entanglement, Phys. Rev. A, 61, 010301(R) (1999)
[51] Braunstein, S. L.; Pati, A. K., Speed-up and entanglement in quantum searching, Quantum Inf. Comput., 2, 399 (2002) · Zbl 1152.81682
[52] Jozsa, R.; Linden, N., On the role of entanglement in quantum-computational speed-up, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., A459, 2011 (2003) · Zbl 1092.81518
[53] Vedral, V., The elusive source of quantum speedup, Found. Phys., 40, 1141 (2010) · Zbl 1210.81020
[54] Kaye, P.; Laflamme, R.; Mosca, M., An Introduction to Quantum Computing (2007), Oxford University Press · Zbl 1297.68001
[55] Ekert, A.; Jozsa, R., Quantum computation and Shor’s factoring algorithm, Rev. Modern Phys., 68, 733 (1996)
[56] Preble, S.; Fanto, M. L.; Steidle, J. A.; Tison, C. C.; Howland, G. A.; Wang, Z.; Alsing, P. M., On-chip quantum interference from a single silicon ring-resonator source, Phys. Rev. Appl., 4, 021001 (2015)
[58] Cafaro, C.; Ali, S. A.; Giffin, A., On the violation of Bell’s inequality for all non-product quantum states, Int. J. Quantum Inf., 14, 1630003 (2016) · Zbl 1344.81051
[59] Alsing, P. M.; Fuentes, I., Observer-dependent entanglement, Classical Quantum Gravity, 29, 224001 (2012) · Zbl 1266.83091
[60] Cafaro, C.; Capozziello, S.; Mancini, S., On relativistic quantum information properties of entangled wave vectors of massive fermions, Internat. J. Theoret. Phys., 51, 2313 (2012) · Zbl 1248.83002
[62] Mair, A.; Vaziri, A.; Weihs, G.; Zeilinger, A., Entanglement of the orbital angular momentum states of photons, Nature, 412, 313 (2001)
[63] Horodecki, R.; Horodecki, P.; Horodecki, M.; Horodecki, K., Quantum entanglement, Rev. Modern Phys., 81, 865 (2009) · Zbl 1205.81012
[64] Heinosaari, T.; Ziman, M., The Mathematical Language of Quantum Theory: From Uncertainty to Entanglement (2011), Cambridge University Press
[65] Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A., Quantum amplitude amplification and estimation., (Quantum Computation and Information. Quantum Computation and Information, Contemp. Math., vol. 305 (2002)), 53 · Zbl 1063.81024
[66] Lasenby, A.; Doran, C.; Gull, S., 2-Spinors twistors and supersymmetry in the spacetime algebra, (Oziewicz, Z.; Borowiec, A.; Jancewicz, B., Spinors, Twistors, Clifford Algebras and Quantum Deformations (1993), Kluwer Academic: Kluwer Academic Dordrecht) · Zbl 0879.15031
[67] Doran, C.; Lasenby, A.; Gull, S., States and operators in the spacetime algebra, Found. Phys., 23, 1239 (1993)
[68] Doran, C.; Lasenby, A.; Gull, S.; Somaroo, S.; Challinor, A., Spacetime algebra and electron physics, Adv. Imaging Electron Phys., 95, 271 (1996)
[69] Somaroo, S.; Lasenby, A.; Doran, C., Geometric algebra and the causal approach to multiparticle quantum mechanics, J. Math. Phys., 40, 3327 (1999) · Zbl 1059.81544
[70] Havel, T. F.; Doran, C. J.L., Geometric algebra in quantum information processing, Contemp. Math., 305, 81 (2002) · Zbl 1063.81029
[71] Hestenes, D., New Foundations for Classical Mechanics (1986), D. Reidel Publishing Company · Zbl 0612.70001
[72] Peres, A.; Terno, D., Quantum information and relativity theory, Rev. Modern Phys., 76, 93 (2004) · Zbl 1205.81050
[73] Jones, J. A.; Mosca, M.; Hansen, R. H., Implementation of a quantum search algorithm on a quantum computer, Nature, 393, 344 (1998)
[74] Ernst, R. R.; Bodenhausen, G.; Wokaun, A., Principles of Nuclear Magnetic Resonance in One and Two Dimensions (1987), Oxford University Press
[75] Kwiat, P. G.; Mitchell, J. R.; Schwindt, P. D.D.; White, A. G., Grover’s search algorithm: An optical approach, J. Modern Opt., 47, 257 (1999)
[76] Scully, M. O.; Zubairy, M. S., Quantum optical implementation of Grover’s algorithm, Proc. Natl. Acad. Sci., 98, 9490 (2001) · Zbl 0995.81014
[77] Kok, P.; Munro, W. J.; Nemoto, K.; Ralph, T. C.; Dowling, J. P.; Milburn, G. J., Linear optical quantum computing with photonic qubits, Rev. Modern Phys., 79, 135 (2007)
[78] Leuenberger, M. N.; Loss, D., Quantum computing in molecular magnets, Nature, 410, 789 (2001)
[79] Leuenberger, M. N.; Loss, D., Grover algorithm for large nuclear spins in semiconductors, Phys. Rev. B, 68, 165317 (2003)
[80] Leuenberger, M. N.; Loss, D.; Poggio, M.; Awschalom, D. D., Quantum information processing with large nuclear spins in GaAs semiconductors, Phys. Rev. Lett., 89, 207601 (2002)
[81] Sharf, Y.; Cory, D. G.; Somaroo, S. S.; Havel, T. F.; Knill, E.; Laflamme, R.; Zurek, W. H., A study of quantum error correction by geometric algebra and liquid-state NMR spectroscopy, Mol. Phys., 98, 1347 (2000)
[84] Farhi, E.; Gutmann, S., Analog of a digital quantum computation, Phys. Rev. A, 57, 2403 (1998)
[86] Bae, J.; Kwon, Y., Generalized quantum search Hamiltonians, Phys. Rev. A, 66, 012314 (2002)
[87] Cencov, N. N., Statistical decision rules and optimal inference, (Transl. Math. Monographs, vol. 53 (1981), Amer. Math. Soc.: Amer. Math. Soc. Providence-RI)
[88] Campbell, L. L., An extended Cencov characterization of the information metric, Proc. Amer. Math. Soc., 98, 135 (1986) · Zbl 0608.62013
[89] Morozova, E. A.; Cencov, N. N., Markov invariant geometry on state manifold, J. Sov. Math., 56, 2648 (1991) · Zbl 0734.60004
[90] Petz, D., Monotone metrics on matrix spaces, Linear Algebra Appl., 244, 81 (1996) · Zbl 0856.15023
[91] Grasselli, M. R.; Streater, R. F., On the uniqueness of the Chentsov metric in quantum information geometry, Infin. Dimens. Anal. Quantum Probab. Relat. Top., 04, 173 (2001) · Zbl 1039.81011
[92] Luo, S., Fisher information for wavefunctions: classical and quantum, Chin. Phys. Lett., 23, 3127 (2006)
[93] Wigner, E. P.; Yanase, M., Information content of distribution, Proc. Natl. Acad. Sci. USA, 49, 910 (1963) · Zbl 0128.14104
[94] Gibilisco, P.; Isola, S., Wigner-Yanase information on quantum state space: the geometric approach, J. Math. Phys., 44, 3752 (2003) · Zbl 1062.81019
[95] Anandan, J.; Aharonov, Y., Geometry of quantum evolution, Phys. Rev. Lett., 65, 1697 (1990) · Zbl 0960.81524
[96] Provost, J. P.; Vallee, G., Riemannian structure on manifolds of quantum states, Comm. Math. Phys., 76, 289 (1980) · Zbl 0451.53053
[97] Kane, B. E., A silicon-based nuclear spin quantum computer, Nature, 393, 133 (1998)
[98] Cirac, J. I.; Zoller, P., Quantum computations with cold trapped ions, Phys. Rev. Lett., 74, 4091 (1995)
[99] Monroe, C.; Meekhof, D. M.; King, B. E.; Itano, W. M.; Wineland, D. J., Demonstration of a fundamental quantum logic gate, Phys. Rev. Lett., 75, 4714 (1995) · Zbl 1020.81550
[100] Di Vincenzo, D. P., The physical implementation of quantum computation, Fortschr. Phys., 48, 771 (2000) · Zbl 1071.81510
[101] Diedrich, F.; Bergquist, J. C.; Itano, W. M.; Wineland, D. J., Laser cooling to the zero-point energy of motion, Phys. Rev. Lett., 62, 403 (1989)
[102] Monroe, C.; Meekhof, D. M.; King, B. E.; Jefferts, S. R.; Itano, W. M.; Wineland, D. J.; Gould, P., Resolved-sideband Raman cooling of a bound atom to the 3D zero-point energy, Phys. Rev. Lett., 75, 4011 (1995)
[103] Grover, L. K., Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett., 80, 4329 (1998)
[104] Cover, T. M.; Thomas, J. A., Elements of Information Theory (2006), John Wiley & Son, Inc.: John Wiley & Son, Inc. Hoboken, New Jersey, USA · Zbl 1140.94001
[105] Luo, S., Fisher Information kinetic energy and uncertainty relation inequalities, J. Phys. A: Math. Gen., 35, 5181 (2002) · Zbl 1066.81515
[106] Roland, J.; Cerf, N. J., Quantum search by local adiabatic evolution, Phys. Rev. A, 65, 042308 (2002)
[107] Vaidman, L., Minimum time for the evolution to an orthogonal quantum state, Amer. J. Phys., 60, 182 (1992) · Zbl 1219.81145
[108] Margolus, N.; Levitin, L. B., The maximum speed of dynamical evolution, Physica D, 120, 188 (1998)
[109] Luo, S., How fast can a quantum state evolve into a target state?, Physica D, 189, 1 (2004) · Zbl 1069.81512
[111] Ruppeiner, G., Thermodynamics: A Riemannian geometric model, Phys. Rev. A, 20, 1608 (1979)
[112] Ruppeiner, G., Riemannian geometry in thermodynamic fluctuation theory, Rev. Modern Phys., 67, 605 (1995)
[113] Crooks, G. E., Measuring thermodynamic length, Phys. Rev. Lett., 99, 100602 (2007)
[114] Divak, D. A.; Crooks, G. E., Thermodynamic metrics and optimal paths, Phys. Rev. Lett., 108, 190602 (2012)
[115] Rotskoff, G. M.; Crooks, G. E., Optimal control in nonequilibrium systems: dynamic Riemannian geometry of the Ising model, Phys. Rev. E, 92, 060102(R) (2015)
[116] Wootters, W. K., Statistical distance and Hilbert space, Phys. Rev. D, 23, 357 (1981)
[117] Braunstein, S. L.; Caves, C. M., Statistical distance and the geometry of quantum states, Phys. Rev. Lett., 72, 3439 (1994) · Zbl 0973.81509
[118] Boyer, M.; Brassard, G.; Hoyer, P.; Tapp, A., Tight bounds on quantum searching, Fortschr. Phys., 46, 493 (1998)
[119] Brassard, G., Searching a quantum phone book, Science, 275, 627 (1997)
[120] Xiao, L.; Jones, J. A., Error tolerance in an NMR implementation of Grover’s fixed-point quantum search algorithm, Phys. Rev. A, 72, 032326 (2005)
[121] Bhole, G.; Anjusha, V. S.; Mahesh, T. S., Steering quantum dynamics via bang-bang control: Implementing optimal fixed-point quantum search algorithm, Phys. Rev. A, 93, 042339 (2016)
[122] Yoder, T. J.; Low, G. H.; Chuang, I. L., Fixed-point quantum search with an optimal number of queries, Phys. Rev. Lett., 113, 210501 (2014)
[123] Iwai, T.; Hayashi, N.; Mizobe, K., The geometry of entanglement and Grover’s algorithm, J. Phys. A., 41, 105202 (2008) · Zbl 1138.81359
[124] Dorst, L.; Fontijne, D.; Mann, S., Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry (2007), Morgan Kaufmann Publishers
[125] Tulsi, T.; Grover, L. K.; Patel, A., A new algorithm for fixed point quantum search, Quantum Inf. Comput., 6, 483 (2006) · Zbl 1152.81821
[126] Mizel, A., Critically damped quantum search, Phys. Rev. Lett., 102, 150501 (2009)
[127] Kim, D.-H.; Ali, S. A.; Cafaro, C.; Mancini, S., Information geometry of quantum entangled wave-packets, Physica A, 391, 4517 (2012)
[129] Toscani, G., New a priori estimates for the spatially homogeneous Boltzmann equation, Contin. Mech. Thermodyn., 4, 81 (1992) · Zbl 0760.76081
[130] Villani, C., Decrease of the Fisher information for the Landau equation with Maxwellian molecules, Math. Models Methods Appl. Sci., 10, 153 (2000) · Zbl 1010.82023
[131] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions (1970), Dover Publications, Inc.: Dover Publications, Inc. New York
[132] Spreeuw, R. J.C.; Hijmans, T. W., Robust quantum searching with spontaneously decaying qubits, Phys. Rev. A, 76, 022306 (2007)
[134] Ivanov, S. S.; Tonchev, H. S.; Vitanov, N. V., Time-efficient implementation of quantum search with qudits, Phys. Rev. A, 85, 06232 (2012)
[135] Cafaro, C.; Ali, S. A.; Giffin, A., Thermodynamic aspects of information transfer in complex dynamical systems, Phys. Rev. E, 93, 022114 (2016)
[136] Cafaro, C.; van Loock, P., Towards an entropic analysis of quantum error correction with imperfections, AIP Conf. Proc., 1553, 275 (2013)
[137] Cafaro, C.; van Loock, P., An entropic analysis of approximate quantum error correction, Physica A, 404, 34 (2014) · Zbl 1395.81094
[138] Ekert, A.; Jozsa, R., Quantum algorithms: entanglement enhanced information processing, Philos. Trans. R. Soc. Lond., 356, 1769 (1998) · Zbl 1152.81837
[139] Vedral, V.; Plenio, M. B.; Rippin, M. A.; Knight, P. L., Quantifying entanglement, Phys. Rev. Lett., 78, 2275 (1997) · Zbl 0944.81011
[140] Vedral, V.; Plenio, M. B.; Jacobs, K.; Knight, P. L., Statistical inference, distinguishability of quantum states, and quantum entanglement, Phys. Rev. A, 56, 4452 (1997)
[141] Weinberg, S., Gravitation and Cosmology (1972), John Wiley & Sons, Inc.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.