DOI: 10.14704/nq.2014.12.3.759

Measurement Complexity and Oracle Quantum Computing

Subhash Kak


This paper explores the problem of quantum measurement complexity. In computability theory, the complexity of a problem is determined by how long it takes an effective algorithm to solve it. This complexity may be compared to the difficulty for a hypothetical oracle machine, the output of which may be verified by a computable function but cannot be simulated on a physical machine. We define a quantum oracle machine for measurements as one that can determine the state by examining a single copy. The complexity of measurement for a realizable machine will then be respect to the number of copies of the state that needs to be examined. A quantum oracle cannot perform simultaneous exact measurement of conjugate variables, although approximate measurement may be performed as circumscribed by the Heisenberg uncertainty relations. When considering the measurement of a variable, there might be residual uncertainty if the number of copies of the variable is limited. Specifically, we examine the quantum measurement complexity of linear polarization of photons that is used in several quantum cryptography schemes and we present a relation using information theoretic arguments. The idea of quantum measurement complexity is likely to find uses in measurements in biological systems.


quantum measurement; complexity; measurement; quantum oracle

Full Text:

Full Text PDF


Agarwal GS. Quantum Optics. Cambridge University Press, 2013.

Altepeter JB, Jeffrey ER and Kwiat PG. Photonic state tomography. In Advances in Atomic, Molecular, and Optical Physics. Elsevier, 2005.

Bagan E. et al. Optimal full estimation of qubit mixed states. Phys Rev A 2006; 73:032301.

Baker TP, Gill J, Solovay R. Relativizations of the P = NP question. SIAM Journal on Computing 1975; 4(4):431–442.

Barreiro JT, Langford NK, Peters NA, Kwiat PG. Generation of hyperentangled photon pairs. Phys. Rev. Lett. 2005; 95: 260501.

Bell J. On the Einstein Podolsky Rosen paradox. Physics 1964; 1(3):195–200.

Bennett CH and Brassard G. Quantum cryptography: Public key distribution and coin tossing. Proceeding of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, pp. 175–179, IEEE, New York, 1984.

Best D and Fisher N. Efficient simulation of the von Mises distribution. Applied Statistics 1979; 28: 152-157.

Bruno A, Capolupo A, Kak S, Raimondo G and Vitielli G. Gauge theory and two level systems. Mod Phys Lett B 2011; 25: 1661-1670.

Bužek V and Hillery, M. Quantum copying: beyond the no-cloning theorem. Phys Rev A 1996; 54: 1844.

Chen Y et al. Multi-photon tolerant secure quantum communication - from theory to practice. Proceedings International Communications Conference (ICC), Budapest, 2013.

Chiribella G and Yang Y. Optimal asymptotic cloning machines. arXiv:1404:0990, 2014.

Collini E et al. Coherently wired light-harvesting in photosynthetic marine algae at ambient temperature. Nature 2010; 463: 644-648.

Cunha D et al. Demonstrating highly symmetric single-mode, single-photon heralding efficiency in spontaneous parametric downconversion. Optics Letters 2013; 38: 1609.

Deutsch D and Jozsa R. Rapid solution of problems by quantum computation. Proc R Soc Lond. A 1992; 439:553.

Dyakonov M. Revisiting the hopes for scalable quantum computation. arXiv:1210.1782, 2012.

Freeman W and Vitiello G. Nonlinear brain dynamics as macroscopic manifestation of underlying many-body dynamics. Physics of Life Reviews 2006; 3:93-118.

Gerhardt I, Liu Q, Lamas-Linares A, Skaar J, Kurtsiefer C and Makarov V. Full-field implementation of a perfect eavesdropper on a quantum cryptography system. Nat Commun 2011; 2: 349.

Gray HB, Winkler JR. Long-range electron transfer. Proc Natl Acad Sci USA 2005; 102: 3534-3539.

Heisenberg W. Physics and Philosophy. London: George Allen & Unwin, 1958.

Hilgevoord J. The uncertainty principle for energy and time I. American Journal of Physics 1996; 64:1451-1456.

Kak S. Quantum neural computing. In Advances in Imaging and Electron Physics, vol. 94, P. Hawkes (editor). Academic Press, pp.259-313, 1995.

Kak S. The initialization problem in quantum computing. Foundations of Physics 1999; 29: 267-279.

Kak S. Active agents, intelligence, and quantum computing. Information Sciences 2000; 128: 1-17.

Kak S. General qubit errors cannot be corrected. Information Sciences 2003; 152: 195-202.

Kak S. Artificial and biological intelligence. ACM Ubiquity 2005; 6(42):1-22.

Kak S. A three-stage quantum cryptography protocol. Foundations of Physics Letters 2006; 19: 293-296.

Kak S. Quantum information and entropy. International Journal of Theoretical Physics 2007; 46: 860-876.

Kak S. The Nature of Physical Reality. New York: Peter Lang, 1986/2011.

Kak S. The problem of testing a quantum gate. Infocommunications Journal 2012; 4:18-22.

Kak S. Threshold quantum cryptography. arXiv:1310.6333, 2013a.

Kak S. Biological memories and agents as quantum collectives. NeuroQuantology 2013b; 11: 391-398.

Kak S. Probability constraints and the classical/quantum divide. NeuroQuantology 2013c; 11: 600-606.

Kak S. From the no-signaling theorem to veiled non-locality. NeuroQuantology 2014a; 12: 12-20.

Kak S. Observability and computability in physics. Quantum Matter 2014b; 3: 172-176.

Kak S. The piggy bank cryptographic trope. Infocommunications Journal 2014c; 6: 22-25.

Klauder, JR and Sudarshan ECG. Fundamentals of Quantum Optics. Dover, 2006.

Kwiat PG, Mattle K, Weinfurter H, Zeilinger A, Sergienko AV and Shih Y. New high-intensity source of polarization-entangled photon pairs. Phys Rev Lett 1995; 75:4337–4341.

Lamas-Linares A, Simon C, Howell JC, Bouwmeester D. Experimental quantum cloning of single photons. Science 2002; 296: 712.

Lambert N et al., Quantum biology. Nature Physics 2013; 9: 10-18.

Leonhardt U. Measuring the Quantum State of Light. Cambridge University Press, 2005.

Mandel L and Wolf E. Optical Coherence and Quantum Optics. Cambridge University Press, 1995.

Misra B and Sudarshan ECG. The Zeno’s paradox in quantum theory. Journal of Mathematical Physics 1977; 18: 758–763.

Molina-Terriza G, Torres JP, Toerner L. Twisted photons. Nature Physics 2007; 3: 305-310.

Nielsen MI and Chuang IL. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Pittman T, Jacobs B and Franson, J. Heralding single photons from pulsed parametric down-conversion. Opt Commun 2005; 246:545-550.

Polli D et al. Conical intersection dynamics of the primary photoisomerization event in vision. Nature 2010; 467:440-443.

Ritz T, Thalau P, Phillips JB, Wiltschko R & Wiltschko W. Resonance effects indicate a radical pair mechanism for avian magnetic compass. Nature 2004; 429:177-180.

Scarani V, Iblisdir S, Gisin N. Quantum cloning. Rev Mod Phys 2005; 77: 1225-1256.

Stapp HP. Mind, Matter, and Quantum Mechanics. New York: Springer-Verlag, 2003.

Tegmark M. The interpretation of quantum mechanics: many worlds or many words? Fortsch Phys 1998; 46:855-862.

Turin L. A spectroscopic mechanism for primary olfactory reception. Chem Senses 1996; 21: 773-791.

Von Neumann J. Mathematical Foundations of Quantum Mechanics. Princeton, NJ: Princeton University Press. 1932/1955.

Watrous J. Quantum computational complexity. Encyclopedia of Complexity and Systems Science. Springer, 2009.

Zurek WH. Decoherence, einselection, and the quantum origins of the classical. Rev Mod Phys 2003; 75: 715-775.

Supporting Agencies

This research was supported in part by the National Science Foundation grant CNS-1117068.

| NeuroScience + QuantumPhysics> NeuroQuantology :: Copyright 2001-2019