Decoherence in Search Algorithms
Resumo
Recentemente, vários algoritmos quânticos de busca baseados em passeios aleatórios quânticos foram apresentados. Estes algoritmos são diferentes do algoritmo de Grover em vários aspectos. O objetivo é encontrar um vértice marcado em um grafo mais rápido do que algoritmos clássicos. Uma vez que a implementação destes novos algoritmos em computadores quânticos ou qualquer outro dispositivo quântico está sujeito a erros, é importante analisar a robustez em relação à descoerência. Neste trabalho, analisamos a descoerência dos algoritmos quânticos de busca em malhas bi-dimensionais e hipercubos.Referências
G. Alagic and A. Russell, Decoherence in quantum walks on the hypercube, Phys. Rev. A 72 (2005), 062304.
A. Ambainis, Quantum walk algorithm for element distinctness, Proceedings 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS), 2004.
Andris Ambainis, Julia Kempe, and Alexander Rivosh, Coins make quantum walks faster, SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2005, pp. 1099–1108.
L. Grover, A fast quantum mechanical algorithm for database search, Proc. 28th Annual ACM Symposium on the Theory of Computation (New York, NY), ACM Press, New York, 1996, pp. 212–219.
J. Kempe, Quantum random walks – an introductory overview, Contemp. Phys. 44 (2003), no. 4, 307–327.
V. Kendon and B. Tregenna, Decoherence can be useful in quantum walks, Phys. Rev. A 67 (2003), 042315.
Yun Li, Lei Ma, and Jie Zhou, Gate imperfection in the quantum random-walk search algorithm, Journal of Physics A 39 (2006), 9309–9319.
Gui Lu Long, Yan Song Li, Wei Lin Zhang, and Chang Cun Tu, Dominant gate imperfection in grover’s quantum search algorithm, Phys. Rev. A 61 (2000), no. 4, 042305.
F. Magniez, M. Santha, and M. Szegedy, Quantum algorithms for the triangle problem, SIAM Journal on Computing 37 (2007), no. 2, 413–424.
F. L. Marquezino, R. Portugal, G. Abal, and R. Donangelo, Mixing times in quantum walks on the hypercube, Physical Review A 77 (2008), 042312.
C. Moore and A. Russell, Quantum walks on the hypercube, Proceedings of 6th International Workshop on Randomization and Approximation Techniques (RANDOM 2002), Vol. 2483 of Lecture Notes in Computer Science (LNCS) (Cambridge, MA) (J. D. P. Rolim and S. Vadhan, eds.), Springer-Verlag, Berlin, 2002, 2002, pp. 164– 178.
Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, October 2000.
A.C. Oliveira, R. Portugal, and R. Donangelo, Decoherence in two-dimensional quantum walks, Phys. Rev. A 74 (2006), 012312.
A. Romanelli, R. Siri, G. Abal, A. Auyuanet, and R. Donangelo, Decoherence in the quantum walk on the line, Physica A 347 (2004), 137–152.
N. Shenvi, K. R. Brown, and K. B. Whaley, Effects of a random noisy oracle on search algorithm complexity, Physical Review A 68 (2003), 052313.
N. Shenvi, J. Kempe, and K. B. Whaley, A quantum random walk search algorithm, Physical Review A 67 (2003), 052307.
Mario Szegedy, Quantum speed-up of markov chain based algorithms, Foundations of Computer Science, Annual IEEE Symposium on 0 (2004), 32–41.
A. Tulsi, Faster quantum walk algorithm for the two dimensional spatial search, Phys. Rev. A 78 (2008), no. 1, 012310.
A. Ambainis, Quantum walk algorithm for element distinctness, Proceedings 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS), 2004.
Andris Ambainis, Julia Kempe, and Alexander Rivosh, Coins make quantum walks faster, SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2005, pp. 1099–1108.
L. Grover, A fast quantum mechanical algorithm for database search, Proc. 28th Annual ACM Symposium on the Theory of Computation (New York, NY), ACM Press, New York, 1996, pp. 212–219.
J. Kempe, Quantum random walks – an introductory overview, Contemp. Phys. 44 (2003), no. 4, 307–327.
V. Kendon and B. Tregenna, Decoherence can be useful in quantum walks, Phys. Rev. A 67 (2003), 042315.
Yun Li, Lei Ma, and Jie Zhou, Gate imperfection in the quantum random-walk search algorithm, Journal of Physics A 39 (2006), 9309–9319.
Gui Lu Long, Yan Song Li, Wei Lin Zhang, and Chang Cun Tu, Dominant gate imperfection in grover’s quantum search algorithm, Phys. Rev. A 61 (2000), no. 4, 042305.
F. Magniez, M. Santha, and M. Szegedy, Quantum algorithms for the triangle problem, SIAM Journal on Computing 37 (2007), no. 2, 413–424.
F. L. Marquezino, R. Portugal, G. Abal, and R. Donangelo, Mixing times in quantum walks on the hypercube, Physical Review A 77 (2008), 042312.
C. Moore and A. Russell, Quantum walks on the hypercube, Proceedings of 6th International Workshop on Randomization and Approximation Techniques (RANDOM 2002), Vol. 2483 of Lecture Notes in Computer Science (LNCS) (Cambridge, MA) (J. D. P. Rolim and S. Vadhan, eds.), Springer-Verlag, Berlin, 2002, 2002, pp. 164– 178.
Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, October 2000.
A.C. Oliveira, R. Portugal, and R. Donangelo, Decoherence in two-dimensional quantum walks, Phys. Rev. A 74 (2006), 012312.
A. Romanelli, R. Siri, G. Abal, A. Auyuanet, and R. Donangelo, Decoherence in the quantum walk on the line, Physica A 347 (2004), 137–152.
N. Shenvi, K. R. Brown, and K. B. Whaley, Effects of a random noisy oracle on search algorithm complexity, Physical Review A 68 (2003), 052313.
N. Shenvi, J. Kempe, and K. B. Whaley, A quantum random walk search algorithm, Physical Review A 67 (2003), 052307.
Mario Szegedy, Quantum speed-up of markov chain based algorithms, Foundations of Computer Science, Annual IEEE Symposium on 0 (2004), 32–41.
A. Tulsi, Faster quantum walk algorithm for the two dimensional spatial search, Phys. Rev. A 78 (2008), no. 1, 012310.
Publicado
20/07/2009
Como Citar
ABAL, G.; DONANGELO, R.; MARQUEZINO, F. L.; OLIVEIRA, A. C.; PORTUGAL, R..
Decoherence in Search Algorithms. In: SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE (SEMISH), 36. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 293-306.
ISSN 2595-6205.
