Document Open Access Logo

Controlled Quantum Amplification

Authors Catalin Dohotaru, Peter Høyer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.18.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Catalin Dohotaru
Peter Høyer

Cite As Get BibTex

Catalin Dohotaru and Peter Høyer. Controlled Quantum Amplification. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.18

Abstract

We propose a new framework for turning quantum search algorithms that decide into quantum algorithms for finding a solution.  Consider we are given an abstract quantum search algorithm A that can determine whether a target g exists or not.  We give a general construction of another operator U that both determines and finds the target, whenever one exists.  Our amplification method at most doubles the cost over using A, has little overhead, and works by controlling the evolution of A.  This is the first known general framework to the open question of turning abstract quantum search algorithms into quantum algorithms for finding a solution.

We next apply the framework to random walks.  We develop a new classical algorithm and a new quantum algorithm for finding a unique marked element.  Our new random walk finds a unique marked element using H update operations and 1/eps checking operations.  Here H is the hitting time, and eps is the probability that the stationary distribution of the walk is in the marked state.  Our classical walk is derived via quantum arguments.  Our new quantum algorithm finds a unique marked element using H^(1/2) update operations and 1/eps^(1/2) checking operations, up to logarithmic factors.  This is the first known quantum algorithm being simultaneously quadratically faster in both parameters.  We also show that the framework can simulate Grover's quantum search algorithm, amplitude amplification, Szegedy's quantum walks, and quantum interpolated walks.

Subject Classification

Keywords
  • Quantum algorithms
  • quantum walks
  • random walks
  • quantum search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/~aldous/RWG/book.
  2. A. Ambainis. Quantum walks and their algorithmic applications. International Journal of Quantum Information, 1:507-518, 2003. URL: http://arxiv.org/abs/quant-ph/0403120.
  3. A. Ambainis. Quantum walk algorithm for element distinctness. In 45th IEEE Symposium on Foundations of Computer Science, FOCS'04, pages 22-31, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.54.
  4. A. Ambainis, A. M. Childs, B. Reichardt, R. Špalek, and S. Zhang. Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. SIAM Journal on Computing, 39:2513-2530, 2010. URL: http://dx.doi.org/10.1109/FOCS.2007.57.
  5. A. Ambainis, J. Kempe, and A. Rivosh. Coins make quantum walks faster. In 16th ACM Symposium on Discrete Algorithms, SODA'05, pages 1099-1108, 2005. URL: http://arxiv.org/abs/quant-ph/0402107.
  6. A. Ambainis and M. Kokainis. Analysis of the extended hitting time and its properties. Poster presented at QIP 2015, 2015. Google Scholar
  7. A. Belovs, A. M. Childs, S. Jeffery, R. Kothari, and F. Magniez. Time-efficient quantum walks for 3-distinctness. In 40th International Colloquium on Automata, Languages, and Programming, ICALP'13, pages 105-122, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_10.
  8. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. URL: http://arxiv.org/abs/quant-ph/0005055.
  9. H. Buhrman and R. Špalek. Quantum verification of matrix products. In 17th ACM-SIAM Symposium on Discrete Algorithms, SODA'06, pages 880-889, 2006. URL: http://arxiv.org/abs/quant-ph/0409035.
  10. A. M. Childs and R. Kothari. Quantum query complexity of minor-closed graph properties. In 28th Symposium on Theoretical Aspects of Computer Science, STACS'11, pages 661-672, 2011. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2011.661.
  11. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London, Series A, 454:339-354, 1998. URL: http://arxiv.org/abs/quant-ph/9708016.
  12. A. Drucker and R. de Wolf. Quantum Proofs for Classical Theorems. Number 2 in Graduate Surveys. Theory of Computing Library, 2011. URL: http://dx.doi.org/10.4086/toc.gs.2011.002.
  13. F. Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In 55th IEEE Symposium on Foundations of Computer Science, FOCS'14, pages 216-225, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.31.
  14. F. Le Gall and S. Nakajima. Quantum algorithm for triangle finding in sparse graphs. In 15th Asian Quantum Information Science Conference, AQIS'15, 2015. URL: http://arxiv.org/abs/1507.06878.
  15. L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79:325-328, 1997. URL: http://dx.doi.org/10.1103/PhysRevLett.79.325.
  16. P. Høyer and R. de Wolf. Improved quantum communication complexity bounds for disjointness and equality. In 19th Symp. on Theoretical Aspects of Computer Science, STACS'02, pages 299-310, 2002. URL: http://dx.doi.org/10.1007/3-540-45841-7_24.
  17. P. Høyer, M. Mosca, and R. de Wolf. Quantum search on bounded-error inputs. In 30th International Colloquium on Automata, Languages and Programming, ICALP'03, pages 291-299, 2003. URL: http://dx.doi.org/10.1007/3-540-45061-0_25.
  18. J. Kempe. Quantum random walks: An introductory overview. Contemporary Physics, 44(4):307-327, 2003. URL: http://dx.doi.org/10.1080/00107151031000110776.
  19. A. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995. URL: http://arxiv.org/abs/quant-ph/9511026.
  20. H. Krovi, F. Magniez, M. Ozols, and J. Roland. Finding is as easy as detecting for quantum walks. In 37st International Colloquium on Automata, Languages and Programming, ICALP'10, pages 540–-551, 2010. URL: http://arxiv.org/abs/1002.2419v1.
  21. H. Krovi, F. Magniez, M. Ozols, and J. Roland. Quantum walks can find a marked element on any graph. Algorithmica, 74:851-907, February 2016. URL: http://dx.doi.org/10.1007/s00453-015-9979-8.
  22. H. Krovi, M. Ozols, and J. Roland. Adiabatic condition and the quantum hitting time of Markov chains. Physical Review A, 82:022333, 2010. URL: http://dx.doi.org/10.1103/PhysRevA.82.022333.
  23. F. Magniez, A. Nayak, P. Richter, and M. Santha. On the hitting times of quantum versus random walks. Algorithmica, 63(1):91-116, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9521-6.
  24. F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. 39th ACM Symposium on Theory of Computing, pages 575-584, 2007. URL: http://dx.doi.org/10.1137/090745854.
  25. F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, Jan 2011. URL: http://dx.doi.org/10.1137/090745854.
  26. F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 27:413-424, 2007. URL: http://dx.doi.org/10.1137/050643684.
  27. A. Nayak and F. Magniez. Quantum complexity of testing group commutativity. Algorithmica, 48:221-232, 2007. URL: http://dx.doi.org/10.1007/s00453-007-0057-8.
  28. A. Nayak, P. C. Richter, and M. Szegedy. Quantum analogs of markov chains. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 1-10. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-642-27848-8_302-2.
  29. M. Santha. Quantum walk based search algorithms. In International Conference on Theory and Applications of Models of Computation, pages 31-46, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79228-4_3.
  30. M. Szegedy. Quantum speed-up of Markov chain based algorithms. In 45th IEEE Symposium on Foundations of Computer Science, FOCS'04, pages 32-41, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.53.
  31. A. Tulsi. Faster quantum walk algorithm for the two dimensional spatial search. Physical Review A, 78:012310, 2008. URL: http://dx.doi.org/10.1103/PhysRevA.78.012310.
  32. S. E. Venegas-Andraca. Quantum walks: A comprehensive review. Quantum Information Processing, 11(5):1015-1106, 2012. URL: http://arxiv.org/abs/1201.4780.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact