Abstract
Quantum computation, in particular Grover’s algorithm, has aroused a great deal of interest since it allows for a quadratic speed-up to be obtained in search procedures. Classical search procedures for an N element database require at most O(N) time complexity. Grover’s algorithm is able to find a solution with high probability in \({O(\sqrt{N})}\) time through an amplitude amplification scheme. In this work we draw elements from both classical and quantum computation to develop an alternative search proposal based on quantum entanglement detection schemes. In 2002, Horodecki and Ekert proposed an efficient method for direct detection of quantum entanglement. Our proposition to quantum search combines quantum entanglement detection alongside entanglement inducing operators. The quantum search algorithm relies on measuring a quantum superposition after having applied a unitary evolution. We deviate from the standard method by focusing on fine-tuning a unitary operator in order to infer the solution with certainty. Our proposal sacrifices space for speed and depends on the mathematical properties of linear positive maps Λ which have not been operationally characterized. Whether such a Λ can be easily determined remains an open question.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Barenco, A., Berthiaume, A., Deutsch, D., Ekert, A., Jozsa, R., Macchiavello, C.: Stabilization of quantum computations by symmetrization. SIAM J. Comput. 26(5),1541–1557 (1997) doi:10.1137/S0097539796302452. http://link.aip.org/link/?SMJ/26/1541/1
Bennett C.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973)
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing (1997) http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/9701001
Cook, S.A.: The complexity of theorem-proving procedures. In: STOC ’71: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM, New York, NY, USA (1971) http://doi.acm.org/10.1145/800157.805047
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 2/e. MIT Press, Cambridge (2001)
Deutsch D., Jozsa R.: Rapid solution of problems by quantum computation. R. Soc. Lond. Proc. Ser. A 439, 553–558 (1992)
Einstein A., Podolsky B., Rosen N.: Can quantum-mechanical description of physical reality be considered complete?. Phys. Rev. 47(10), 777–780 (1935). doi:10.1103/Phys.Rev.47.777
Gharibian, S.: Strong NP-Hardness of the Quantum Separability Problem. ArXiv e-prints (2008)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC ’96: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York, NY, USA (1996) http://doi.acm.org/10.1145/237814.237866
Grover, L.K., Radhakrishnan, J.: Is partial quantum search of a database any easier? (2004) http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0407122
Gühne O., Tóth G.: Entanglement detection. Phys. Rep. 474, 1–75 (2009). doi:10.1016/j.physrep.2009.02.004
Gurvits, L.: Classical deterministic complexity of edmonds’ problem and quantum entanglement. In: STOC ’03: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 10–19. ACM, New York, NY, USA (2003) http://doi.acm.org/10.1145/780542.780545
Horodecki, M., Horodecki, P., Horodecki, R.: Separability of mixed states:necessary and sufficient conditions. Phys. Lett. A 223(1–2),1–8 (1996) doi:10.1016/S0375-9601(96)00706-2. http://www.sciencedirect.com/science/article/B6TVM-3VSFHG4-1J/2/30233fc8e862b1e50e0d0a7e340f7859
Horodecki, M., Horodecki, P., Horodecki, R.: Separability of n-particle mixed states: necessary and sufficient conditions in terms of linear maps. Phys. Lett. A 283(1–2),1–7 (2001) doi:10.1016/S0375-9601(01)00142-6. http://www.sciencedirect.com/science/article/B6TVM-42YFC9G-1/2/9c9d0b6d096a6b59a89d0b03fe825977
Horodecki P., Ekert A.: Method for direct detection of quantum entanglement. Phys. Rev. Lett. 89(12), 127,902 (2002). doi:10.1103/PhysRevLett.89.127902
Horodecki, R., Horodecki, P., Horodecki, M., Horodecki, K.: Quantum entanglement. ArXiv Quantum Physics e-prints (2007)
Ioannou, L.M.: Computational complexity of the quantum separability problem. ArXiv Quantum Physics e-prints (2006)
Ioannou L.M., Travaglione B.C.: Quantum separability and entanglement detection via entanglement-witness search and global optimization. Phys. Rev. A 73(5), 052,314 (2006). doi:10.1103/PhysRevA.73.052314
Kaye P.R., Laflamme R., Mosca M.: An Introduction to Quantum Computing. Oxford University Press, USA (2007)
Keyl M., Werner R.F.: Estimating the spectrum of a density operator. Phys. Rev. A 64(5), 052,311 (2001). doi:10.1103/PhysRevA.64.052311
Krammer, P.: Quantum entanglement—detection, classification, and quantification. Master’s thesis, University of Vienna, (2005)
Lewenstein M., Kraus B., Cirac J.I., Horodecki P.: Optimization of entanglement witnesses. Phys. Rev. A 62(5), 052,310 (2000). doi:10.1103/PhysRevA.62.052310
Lewenstein M., Kraus B., Horodecki P., Cirac J.I.: Characterization of separable states and entanglement witnesses. Phys. Rev. A 63(4), 044,304 (2001). doi:10.1103/PhysRevA.63.044304
von Neumann J.: Mathematische Grund lagen der Quantenmechanic. Springer, Berlin (1932)
Peres A.: Separability criterion for density matrices. Phys. Rev. Lett. 77(8), 1413–1415 (1996). doi:10.1103/PhysRevLett.77.1413
Schrödinger, E.: Die gegenwärtige situation in der quantenmechanik. Naturwissenschaften 23(807) (1935)
Shor, P.:Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994) doi:10.1109/SFCS.1994.365700
Fiurášek J.: Structural physical approximations of unphysical maps and generalized quantum measurements. Phys. Rev. A 66(5), 052,315 (2002). doi:10.1103/PhysRevA.66.052315
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by FCT (INESC-ID multiannual funding) through the PIDDAC Program funds and FCT grant DFRH–SFRH/BD/61846/2009.
Rights and permissions
About this article
Cite this article
Tarrataca, L., Wichert, A. Can quantum entanglement detection schemes improve search?. Quantum Inf Process 11, 55–66 (2012). https://doi.org/10.1007/s11128-011-0231-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-011-0231-4